## Search found 83 matches

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.
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.
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...
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...
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.
Sat Mar 04, 2006 11:02 pm
Forum: Volume 110 (11000-11099)
Replies: 9
Views: 3154
Given an important point (x, y), k is negative for a pair of segments if and only if ai
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 ...
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...
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.
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...
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...
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.
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.
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.
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".