Search found 83 matches

by david
Sun Mar 19, 2006 1:24 pm
Forum: Volume 110 (11000-11099)
Topic: 11012 - Cosmic Cabbages
Replies: 29
Views: 8843

shalinmangar wrote: The hint that wook gave is the key to solving the problem in O(n). Thanks wook.
What hint? wook hasn't said anything useful.
by david
Wed Mar 15, 2006 1:05 pm
Forum: C++
Topic: Impossible to use C++
Replies: 13
Views: 3871

You're talking nonsense. ceil(), sin, exp().. all work perfectly, as does everything I have tried using from the STL, for instance. You are still to provide an example of a problem with the judge compiler.
by david
Tue Mar 14, 2006 2:35 pm
Forum: Volume 108 (10800-10899)
Topic: 10804 - Gopher Strategy
Replies: 39
Views: 23227

Abednego: Could you explain why your bpm algorithm works? The only one I know of is that based on the Ford-Fulkerson method, which requires finding alternating paths (which is what your bpm function does) until none remains. Instead, for each vertex, you check only once for the existence of an alter...
by david
Mon Mar 13, 2006 11:19 pm
Forum: Algorithms
Topic: Bignum arithmetic
Replies: 9
Views: 2340

Both multiplication and division can be done in O(n^2) without much trouble. The so-called "karatsuba algorithm" (O(n^(log 3 / log2)) is just the divide-and-conquer method for integer multiplication found in every textbook. It isn't difficult to code, but as far as I know the gain in speed is only n...
by david
Thu Mar 09, 2006 2:38 pm
Forum: Volume 110 (11000-11099)
Topic: 11000 - Bee
Replies: 25
Views: 12051

Yes, it is correct.
Suppose there are f[n] - 1 male bees and f[n+1] - 1 bees in total. Then there are f[n - 1] female bees, and next year there will be 1 + f[n] - 1 = f[n] female bees and f[n-1] + f[n] - 1 = f[n + 1] - 1 male ones.
by david
Sat Mar 04, 2006 11:02 pm
Forum: Volume 110 (11000-11099)
Topic: 11004 - Changing Roadmap
Replies: 9
Views: 3154

Given an important point (x, y), k is negative for a pair of segments if and only if ai
by david
Sun Feb 26, 2006 2:20 am
Forum: Volume 109 (10900-10999)
Topic: 10999 - Crabbles
Replies: 26
Views: 13822

You say we can consider just 2^p words and look for them in dictionary but,shouldn't we consider every permutation of this 2^p words? No, why should we? If we have the letters a, c, a, d, we can build the words acad, cada, aadc..., regardless of the letter order within a word. So if the dictionary ...
by david
Sun Feb 26, 2006 1:52 am
Forum: Volume 109 (10900-10999)
Topic: 10905 - Children's Game
Replies: 66
Views: 25405

As it turns out, my proof that R is transitive was wrong. I had taked it for granted that a+b > b+a implies a+c+b > b+c+a, which is false as you duly point out. Anyway, assuming R is transitive (which seems to be harder to prove than one might think, but I think is true), the correctness of the gree...
by david
Sun Feb 26, 2006 1:25 am
Forum: Volume 109 (10900-10999)
Topic: 10999 - Crabbles
Replies: 26
Views: 13822

There are many fewer words that can be formed with the given letters (2^10, ignoring letter order) than there are words in the dictionary, and for each word that can be formed you can check efficiently whether it is in the dictionary or not.
by david
Fri Feb 24, 2006 4:20 pm
Forum: Volume 109 (10900-10999)
Topic: 10905 - Children's Game
Replies: 66
Views: 25405

david 223++22 > 22++223 but 22 4 223 > 223 4 22 (if '4' is placed in between 'a' and 'b'), so this is not true for arbitrarily placed pairs. Porbably it still can be proven via adjacent swaps, but it is not obvious for me how to prove that bubble sort local maximums will yield global maximum (since...
by david
Sun Feb 19, 2006 4:16 pm
Forum: Volume 7 (700-799)
Topic: 748 - Exponentiation
Replies: 26
Views: 8366

The output shown in Eduard's post is incorrect (it contains nonsensical results such as 0.00000001^25 = 0.1). The correct output is .00000005148554641076956121994511276767154838481760200726351203835429763013462401 43992025569.928573701266488041146654993318703707511666295476720493953024 29448126.7641...
by david
Sun Feb 19, 2006 1:59 am
Forum: Volume 101 (10100-10199)
Topic: 10109 - Solving Systems of Linear Equations
Replies: 18
Views: 8741

I used simple Gaussian elimination, representing rationals as a pair
of long long's, and got AC in about 1.5 seconds, so there's no need to do anything complicated here.
by david
Fri Dec 02, 2005 2:13 am
Forum: Volume 109 (10900-10999)
Topic: 10958 - How Many Solutions?
Replies: 17
Views: 5640

This seems to be a real TLE.
Since what you have to do is find the number of divisors of a lot of numbers in a limited range, you can do this much faster by precomputing the list of primes in that interval and factoring.
by david
Tue Nov 15, 2005 12:47 am
Forum: Volume 3 (300-399)
Topic: 315 - Network
Replies: 68
Views: 21098

Finally, about one year later, I managed to find out what was wrong with my code... When reading the adjacency list, I never read more lines than the number of vertices of the graph.
by david
Sat Nov 05, 2005 1:37 am
Forum: Volume 1 (100-199)
Topic: 104 - Arbitrage
Replies: 223
Views: 13247

Your algorithm, as written, is wrong: it doesn't return the shortest arbitrage sequence but the one with minimum starting point (albeit breaking ties by sequence length).
The outermost loop should be the one indexed by the variable "j".

Go to advanced search