## Search found 724 matches

Wed Jan 27, 2010 3:13 pm
Forum: Bugs and suggestions
Topic: 11630 special judge
Replies: 1
Views: 2024

### 11630 special judge

It seems that the special judge of problem 11630 is still wrong. This was already detected during the online contest ("ULM Local Contest"), and Miguel told me that the reason is that my special judge prints debug output to stderr, and the judge interprets this as a wrong answer, no matter what the r...
Sun Nov 25, 2007 12:36 pm
Forum: Volume 113 (11300-11399)
Topic: 11358 - Faster Processing Feasibility
Replies: 8
Views: 4264
The greedy is actually quite easy: Process those tasks first which have smallest difference "time to deadline" - "remaining processing time needed". I think it should be correct.
Sun Nov 25, 2007 12:32 pm
Forum: Volume 113 (11300-11399)
Topic: 11354 - Bond
Replies: 13
Views: 6703
If you use union by rank, you can answer queries in O(log n) on the union find tree.
Tue Jul 31, 2007 8:11 pm
Forum: Volume 112 (11200-11299)
Topic: 11248 - Frequency Hopping
Replies: 20
Views: 9223
Did you also implement the gap heuristic? It is posed as a problem at the end of the chapter. I implemented it in such a way that the complexity of the algorithm remains the same (for each relabel operation, I have amortized O(1) for the gap heuristic). For only calculating the minimum cut, my progr...
Tue Jul 31, 2007 2:29 pm
Forum: Volume 112 (11200-11299)
Topic: 11248 - Frequency Hopping
Replies: 20
Views: 9223
Yes, that is what I meant, only that I don't run it in the residual graph, but instead each time I add an additional edge, so if I run it for node u, I add an edge from source to u with capacity C, and the condition in the end becomes min(f(u),f(v)) >= C.
Tue Jul 31, 2007 11:07 am
Forum: Volume 112 (11200-11299)
Topic: 11248 - Frequency Hopping
Replies: 20
Views: 9223
There is another way which needs only O(n) network flows. In fact it is similar to step 2 of mf's algorithm.
Mon Jul 30, 2007 1:33 pm
Forum: Volume 112 (11200-11299)
Topic: 11248 - Frequency Hopping
Replies: 20
Views: 9223
Yes, I am sure the output for that test case must be "not possible" (of course with Case number is shown in problem statement). Because edge 4 1 1 can be ignored completely, a channel from 4 to 1 is not useful, because it can not be used in other direction. So there is exactly one path from 1 to 4: ...
Sun Jul 29, 2007 6:17 pm
Forum: Volume 112 (11200-11299)
Topic: 11248 - Frequency Hopping
Replies: 20
Views: 9223
I can't answer your question, but something I have found out about the input: it seems there are channels from one station to itself. Not sure if there are also duplicate channels between two stations, I would handle that as one channel with added frequency values (which should be the correct way to...
Sun Jul 29, 2007 2:51 pm
Forum: Volume 112 (11200-11299)
Topic: 11249 - Game
Replies: 32
Views: 13406
Try to check against a brute force program with small values (for example a, b <= 1000), that should be sufficient to find the mistake(s).
Sun Jul 29, 2007 1:05 pm
Forum: Volume 112 (11200-11299)
Topic: 11249 - Game
Replies: 32
Views: 13406
You missed something. Some part of your idea is right though.
But think why for a = k+2 and b = (k+2)*(k+2) it is a winning position (you would print it is a losing position).
Sun Jul 29, 2007 12:13 am
Forum: Bugs and suggestions
Topic: Problem 11245
Replies: 24
Views: 9201

### Problem 11245

It seems there are inputs with n > 2 * 10^9
I used assert to check this; I got Accepted after I also handled n upto 2^50.
Thu Jul 19, 2007 12:00 am
Forum: Volume 112 (11200-11299)
Topic: 11232 - Cylinder
Replies: 34
Views: 15494
Try your program on the test cases posted in this thread, then you see why you got WA. Many of your answers are too small. I believe your find method is incorrect, I am not completely sure I understand it, but it seems you combine the two ways to get the cylinder in one function and do a modified bi...
Mon Jul 16, 2007 12:07 pm
Forum: Volume 112 (11200-11299)
Topic: 11240 - Antimonotonicity
Replies: 33
Views: 12575
You can use low-level I/O functions like read / write. I guess this is how Rio gets his fast runtime. When the algorithm is O(n), most of the time is spent on I/O, so you can really optimize a lot there. Ignore Ghalib who is listed on first place, I am quite sure he just prints the output without re...
Wed Jul 11, 2007 7:03 pm
Forum: Volume 112 (11200-11299)
Topic: 11232 - Cylinder
Replies: 34
Views: 15494
Your mistake is in this line:
if ((r1 * 2) > w) r1 = w / 2;
since w is integer, you use integer division here, rounding down if w is odd.