## Search found 83 matches

Sat Apr 14, 2007 10:34 am
Forum: Algorithms
Topic: SWERC 2006 - The Right Tip
Replies: 3
Views: 2864
Because the greedy algorithm is wrong in this case (not all coin values are divisible by the previous one).
Don't be mistaken, this problem is not so easy. What happens is that at SWERC, test data for this problem was very weak and almost everybody got accepted with the (incorrect) greedy algorithm.
Tue Jan 09, 2007 2:06 am
Forum: Algorithms
Topic: k-connectivity of a graph
Replies: 1
Views: 1840
Let S be the set of vertices reachable from the source via an augmenting path, and T the set of those from which there exists an augmenting path to the sink. If you use the Ford Fulkerson method to find the max flow, at the end no augmenting path from the source to the sink exists, so S and T are di...
Wed Jan 03, 2007 2:04 pm
Forum: Bugs and suggestions
Topic: 10002 center of masses
Replies: 2
Views: 2558

### 10002 center of masses

I think judge's input is flawed. I'm pretty sure my solution is correct, but I always get WA, and browsing through the forums shows that only people who compute the convex hull first get AC, but this shouldn't be necessary as the problem description says the polygon is convex (so one should only nee...
Sat Nov 11, 2006 12:34 pm
Forum: Algorithms
Topic: 2-SAT problem
Replies: 3
Views: 3153
Write the boolean formula as a conjunction of implications (e.g. (x1->x2)^(~x1->x3)), and create a graph whose vertices are xi and ~xi for all variables xi, and whose edges are the implications. The formula is satisfiable if and only if no contradiction of the form xi -> ~xi -> xi arises following a...
Sat Nov 11, 2006 12:27 pm
Forum: Algorithms
Topic: Diameter of Tree - can it be done better than in O(V*(V+E))
Replies: 6
Views: 3097
This can quite easily be done in O(V). Pick a root and start a DFS from it which returns both the diameter of the subtree and its maximum height. The diameter is the maximum of (left diameter, right diameter, left height + right height).
Sat Oct 21, 2006 11:39 pm
Forum: Algorithms
Topic: Problems using LCA form arhive.
Replies: 8
Views: 4159
There is also a very easy to code algorithm due to Tarjan, in which you find the lca of several pairs of vertices during a dfs of the tree (in O(V+Q+alfa(V+Q)), where V is the number of vertices, Q the number of queries and alfa is the very slow-growing inverse of the Ackermann function). You can fi...
Thu Oct 19, 2006 1:37 am
Forum: Volume 111 (11100-11199)
Topic: 11105 - Semi-prime H-numbers
Replies: 16
Views: 12483
There are 89070 h-primes and 105753 h semi-primes in the range allowed.
Tue Oct 17, 2006 6:35 pm
Forum: Volume 111 (11100-11199)
Topic: 11119 - Chemical Attraction
Replies: 19
Views: 9372
Intention is what matters, as we all know...
Anyway this explains why nobody got WA during the contest, only AC, TLE and RE.
Mon Oct 16, 2006 10:56 am
Forum: Volume 111 (11100-11199)
Topic: 11120 - Very Funny Mr. Feynman
Replies: 11
Views: 4366
I think that it can't be predicted is a property of irrational number. The fact that a number is irrational has nothing to do with whether we can "predict" its digits by a simple formula or not. (For example, there is an explicit expression for the nth hexadecimal digit of pi). That said,...
Sun Oct 15, 2006 2:53 pm
Forum: Volume 111 (11100-11199)
Topic: 11122 - Tri Tri
Replies: 29
Views: 9561
Make sure you don't overflow if you use integer arithmetics. And if you use floating point numbers make sure you make your comparisons are good (use epsilon). Thanks for replying, but I use long long and I checked with assert that all input data fit within an int, so multiplications won't overflow ...
Sun Oct 15, 2006 1:58 pm
Forum: Volume 111 (11100-11199)
Topic: 11122 - Tri Tri
Replies: 29
Views: 9561
Why let others do the work for you? Take your scetch-book and pencil and make some of your own. It's not so hard finding the tricky cases (co-linearity, nearly touching, shared corners, paralel to the axis, etc. etc.), and the nice thing is: you can instantly check them by inspecting your scetch. A...
Sun Oct 15, 2006 11:19 am
Forum: Volume 111 (11100-11199)
Topic: 11122 - Tri Tri
Replies: 29
Views: 9561
My program passes all those cases, but I keep getting WA. Can anyone supply more tricky examples?
Sat Oct 14, 2006 7:23 pm
Forum: Volume 111 (11100-11199)
Topic: 11122 - Tri Tri
Replies: 29
Views: 9561
Shouldn't the answer to case 9:

0 0 0 1 1 0
0 1 1 0 1 1

be no?
Sun Oct 08, 2006 11:44 pm
Forum: Volume 111 (11100-11199)
Topic: 11112 - Babylonian Roulette
Replies: 6
Views: 6276
You are assuming that at at least one player must turn the roulette, but this isn't so. (Zero is a valid answer).
Sun Oct 08, 2006 2:36 am
Forum: Volume 111 (11100-11199)
Topic: 11110 - Equidivisions
Replies: 33
Views: 19788
I also had a lot of trouble with this problem. The trick is that some cells appear twice in the input.