## Search found 429 matches

Wed Feb 08, 2006 10:35 am
Forum: Volume 109 (10900-10999)
Topic: 10983 - Buy one, get the rest free
Replies: 15
Views: 6152
However, in practice, Dinic's algorithm beats push-relabel. Look at this paper: Cherkassky and Goldberg, "On implementing push-relabel method for the maximum flow problem," Technical report. Stanford, CA, USA, 1994. Basically, they show that the only way for push-relabel to beat Dinic's algorithm i...
Mon Jan 23, 2006 7:48 pm
Forum: Volume 109 (10900-10999)
Topic: 10982 - Troublemakers
Replies: 17
Views: 6289
2 Per: I am a little bit confused by your last post. You want to say that we need to calculate probability of splitting n/2 pairs and after that just do appropriate number of random divisions. If feasible division was not found then it is impossible to split graph in such a way. No. I wanted to say...
Mon Jan 23, 2006 11:10 am
Forum: Volume 109 (10900-10999)
Topic: 10982 - Troublemakers
Replies: 17
Views: 6289
This is not a matching problem.

Hint: take a random division into two groups. What is the probability that a fixed pair is split by this division? What is the expected value on the total number of pairs split?
Mon Jan 23, 2006 10:55 am
Forum: Volume 109 (10900-10999)
Topic: 10982 - Troublemakers
Replies: 17
Views: 6289
What do you do if the graph is not bicolorable?
Thu Dec 15, 2005 3:52 pm
Forum: Other words
Topic: ICPC '05 regional in Manila and Coimbatore
Replies: 9
Views: 5119
Thx misof. But I was more in the line whether the chief contest director monitor the regional contests, rather than appealing the results. Does he believe whatever the regional director reports or does he crosscheck the result to find anything peculiar? Or does he need to be pointed to a problem be...
Wed Dec 14, 2005 10:02 pm
Forum: Volume 108 (10800-10899)
Topic: 10863 - Shovelling Snow
Replies: 10
Views: 2437
Overall, this algorithm reduces the original problem to 7 shortest path problems, and its running time is dominated by Dijkstra's algorithm. Ah, very nice! I take it you use every house map \in A with potential f(u, A \ map ) as the source(s) for step 3? Btw, may I ask for some hint on 10857? Certa...
Wed Dec 14, 2005 3:49 pm
Forum: Volume 108 (10800-10899)
Topic: 10863 - Shovelling Snow
Replies: 10
Views: 2437
mf wrote:Well, my solution is the fastest on the ranklist, but in the worst case it's O((mn)^2), too.
(I can improve it to O(mn log(mn)), but that's a bit tricky.)
Could you elaborate a bit on this point?
Mon Nov 14, 2005 11:12 am
Forum: Volume 120 (12000-12099)
Topic: 12081 - Reduced ID Numbers
Replies: 18
Views: 1147
AnGeLoSo wrote:I'm trying this on http://acmicpc-live-archive.uva.es/nuevoportal/ but it takes more than 10 seconds!!
You have an array size issue. The answer can be a lot bigger than 305.
Mon Nov 14, 2005 12:56 am
Forum: Volume 120 (12000-12099)
Topic: 12081 - Reduced ID Numbers
Replies: 18
Views: 1147

### Re: NWERC Problem F

This is NWERC's problem F. If you try to solve it by generating values for m starting with the number of students and checking you don't get repeated values for the reduced SINs you will get "Time Limit Exceded". No, you will not. :) This is indeed the indended solution, and I doubt there is anythi...
Sun Nov 13, 2005 9:58 pm
Forum: Volume 105 (10500-10599)
Topic: 10531 - Maze Statistics
Replies: 8
Views: 5020
The case I originally failed to handle was:

Code: Select all

1
0.5
Tue Oct 25, 2005 6:14 pm
Forum: Volume 109 (10900-10999)
Topic: 10939 - Ants, Aphids and a Ladybug
Replies: 13
Views: 5677
But in my opinion, for programming contest, if someone gets an algorithm which has the same time complexity as the judge's solution. He should pass the time limit no matter how slow (say, 10 times slower) his implementation is. I disagree. First, what you suggest cannot be implemented, since there ...
Tue Oct 25, 2005 4:39 pm
Forum: Volume 100 (10000-10099)
Topic: 10089 - Repackaging
Replies: 41
Views: 14605
I remember spending way too much time thinking about this problem, back when, so I guess I was just happy when I finally solved it.
Tue Oct 25, 2005 4:09 pm
Forum: Volume 100 (10000-10099)
Topic: 10089 - Repackaging
Replies: 41
Views: 14605
My proof that 4 vectors are enough was a bit messy. But when thinking about using just three vectors, I came up with a quite nice characterization of when the problem is solvable. (So warning, spoiler ahead.) Let v_1, ..., v_n be the vectors sorted by angle, and let t_i be the angle from v_i to v_{i...
Sun Oct 23, 2005 8:17 pm
Forum: Volume 103 (10300-10399)
Topic: 10383 - Queen vs Rook
Replies: 8
Views: 3651
In case anyone is still interested in this very old thread, pls clarify for me. Why the output of the first sample "WKa1 BKa3 WRc2 BQd2 B" is not: Black mates in 1 Qxc1# Do I need to know further rules of Chess to get the sample output? I'm guessing you mean "Qxc2#" rather than "Qxc1#". Check mate ...
Sun Oct 23, 2005 9:04 am
Forum: Volume 109 (10900-10999)
Topic: 10943 - How do you add?
Replies: 38
Views: 13284
The problem description is not as specific as it should've been, for which I apologize, as it is my first contest on UVa. I guess most problemsolvers have been jaded to the various trick cases people have thrown at because of the wording, but this was intended to be as a relatively simple DP proble...