Search found 429 matches

by Per
Wed Feb 08, 2006 10:35 am
Forum: Volume 109 (10900-10999)
Topic: 10983 - Buy one, get the rest free
Replies: 15
Views: 6030

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...
by Per
Mon Jan 23, 2006 7:48 pm
Forum: Volume 109 (10900-10999)
Topic: 10982 - Troublemakers
Replies: 17
Views: 6195

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...
by Per
Mon Jan 23, 2006 11:10 am
Forum: Volume 109 (10900-10999)
Topic: 10982 - Troublemakers
Replies: 17
Views: 6195

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?
by Per
Mon Jan 23, 2006 10:55 am
Forum: Volume 109 (10900-10999)
Topic: 10982 - Troublemakers
Replies: 17
Views: 6195

What do you do if the graph is not bicolorable?
by Per
Thu Dec 15, 2005 3:52 pm
Forum: Other words
Topic: ICPC '05 regional in Manila and Coimbatore
Replies: 9
Views: 5058

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...
by Per
Wed Dec 14, 2005 10:02 pm
Forum: Volume 108 (10800-10899)
Topic: 10863 - Shovelling Snow
Replies: 10
Views: 2383

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...
by Per
Wed Dec 14, 2005 3:49 pm
Forum: Volume 108 (10800-10899)
Topic: 10863 - Shovelling Snow
Replies: 10
Views: 2383

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?
by Per
Mon Nov 14, 2005 11:12 am
Forum: Volume 120 (12000-12099)
Topic: 12081 - Reduced ID Numbers
Replies: 18
Views: 1055

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.
by Per
Mon Nov 14, 2005 12:56 am
Forum: Volume 120 (12000-12099)
Topic: 12081 - Reduced ID Numbers
Replies: 18
Views: 1055

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...
by Per
Sun Nov 13, 2005 9:58 pm
Forum: Volume 105 (10500-10599)
Topic: 10531 - Maze Statistics
Replies: 8
Views: 4981

The case I originally failed to handle was:

Code: Select all

1
0.5
by Per
Tue Oct 25, 2005 6:14 pm
Forum: Volume 109 (10900-10999)
Topic: 10939 - Ants, Aphids and a Ladybug
Replies: 13
Views: 5627

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 ...
by Per
Tue Oct 25, 2005 4:39 pm
Forum: Volume 100 (10000-10099)
Topic: 10089 - Repackaging
Replies: 41
Views: 14447

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. :)
by Per
Tue Oct 25, 2005 4:09 pm
Forum: Volume 100 (10000-10099)
Topic: 10089 - Repackaging
Replies: 41
Views: 14447

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...
by Per
Sun Oct 23, 2005 8:17 pm
Forum: Volume 103 (10300-10399)
Topic: 10383 - Queen vs Rook
Replies: 8
Views: 3604

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 ...
by Per
Sun Oct 23, 2005 9:04 am
Forum: Volume 109 (10900-10999)
Topic: 10943 - How do you add?
Replies: 38
Views: 13124

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...

Go to advanced search