Search found 83 matches

by david
Sat Apr 14, 2007 10:34 am
Forum: Algorithms
Topic: SWERC 2006 - The Right Tip
Replies: 3
Views: 2692

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.
by david
Tue Jan 09, 2007 2:06 am
Forum: Algorithms
Topic: k-connectivity of a graph
Replies: 1
Views: 1731

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...
by david
Wed Jan 03, 2007 2:04 pm
Forum: Bugs and suggestions
Topic: 10002 center of masses
Replies: 2
Views: 2473

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...
by david
Sat Nov 11, 2006 12:34 pm
Forum: Algorithms
Topic: 2-SAT problem
Replies: 3
Views: 3015

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...
by david
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: 2944

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).
by david
Sat Oct 21, 2006 11:39 pm
Forum: Algorithms
Topic: Problems using LCA form arhive.
Replies: 8
Views: 3946

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...
by david
Thu Oct 19, 2006 1:37 am
Forum: Volume 111 (11100-11199)
Topic: 11105 - Semi-prime H-numbers
Replies: 16
Views: 11537

There are 89070 h-primes and 105753 h semi-primes in the range allowed.
by david
Tue Oct 17, 2006 6:35 pm
Forum: Volume 111 (11100-11199)
Topic: 11119 - Chemical Attraction
Replies: 19
Views: 8512

Intention is what matters, as we all know...
Anyway this explains why nobody got WA during the contest, only AC, TLE and RE.
by david
Mon Oct 16, 2006 10:56 am
Forum: Volume 111 (11100-11199)
Topic: 11120 - Very Funny Mr. Feynman
Replies: 11
Views: 3996

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, I don't k...
by david
Sun Oct 15, 2006 2:53 pm
Forum: Volume 111 (11100-11199)
Topic: 11122 - Tri Tri
Replies: 29
Views: 8914

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 ...
by david
Sun Oct 15, 2006 1:58 pm
Forum: Volume 111 (11100-11199)
Topic: 11122 - Tri Tri
Replies: 29
Views: 8914

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...
by david
Sun Oct 15, 2006 11:19 am
Forum: Volume 111 (11100-11199)
Topic: 11122 - Tri Tri
Replies: 29
Views: 8914

My program passes all those cases, but I keep getting WA. Can anyone supply more tricky examples?
by david
Sat Oct 14, 2006 7:23 pm
Forum: Volume 111 (11100-11199)
Topic: 11122 - Tri Tri
Replies: 29
Views: 8914

Shouldn't the answer to case 9:

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

be no?
by david
Sun Oct 08, 2006 11:44 pm
Forum: Volume 111 (11100-11199)
Topic: 11112 - Babylonian Roulette
Replies: 6
Views: 6087

You are assuming that at at least one player must turn the roulette, but this isn't so. (Zero is a valid answer).
by david
Sun Oct 08, 2006 2:36 am
Forum: Volume 111 (11100-11199)
Topic: 11110 - Equidivisions
Replies: 33
Views: 18985

I also had a lot of trouble with this problem. The trick is that some cells appear twice in the input.

Go to advanced search