Search found 724 matches

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

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...
by Adrian Kuegel
Sun Nov 25, 2007 12:36 pm
Forum: Volume 113 (11300-11399)
Topic: 11358 - Faster Processing Feasibility
Replies: 8
Views: 4031

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.
by Adrian Kuegel
Sun Nov 25, 2007 12:32 pm
Forum: Volume 113 (11300-11399)
Topic: 11354 - Bond
Replies: 13
Views: 6262

If you use union by rank, you can answer queries in O(log n) on the union find tree.
by Adrian Kuegel
Tue Jul 31, 2007 8:11 pm
Forum: Volume 112 (11200-11299)
Topic: 11248 - Frequency Hopping
Replies: 20
Views: 8841

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...
by Adrian Kuegel
Tue Jul 31, 2007 2:29 pm
Forum: Volume 112 (11200-11299)
Topic: 11248 - Frequency Hopping
Replies: 20
Views: 8841

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.
by Adrian Kuegel
Tue Jul 31, 2007 11:07 am
Forum: Volume 112 (11200-11299)
Topic: 11248 - Frequency Hopping
Replies: 20
Views: 8841

There is another way which needs only O(n) network flows. In fact it is similar to step 2 of mf's algorithm.
by Adrian Kuegel
Mon Jul 30, 2007 1:33 pm
Forum: Volume 112 (11200-11299)
Topic: 11248 - Frequency Hopping
Replies: 20
Views: 8841

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: ...
by Adrian Kuegel
Sun Jul 29, 2007 6:17 pm
Forum: Volume 112 (11200-11299)
Topic: 11248 - Frequency Hopping
Replies: 20
Views: 8841

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...
by Adrian Kuegel
Sun Jul 29, 2007 2:51 pm
Forum: Volume 112 (11200-11299)
Topic: 11249 - Game
Replies: 32
Views: 12606

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).
by Adrian Kuegel
Sun Jul 29, 2007 1:05 pm
Forum: Volume 112 (11200-11299)
Topic: 11249 - Game
Replies: 32
Views: 12606

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).
by Adrian Kuegel
Sun Jul 29, 2007 12:13 am
Forum: Bugs and suggestions
Topic: Problem 11245
Replies: 24
Views: 8777

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.
by Adrian Kuegel
Thu Jul 19, 2007 12:00 am
Forum: Volume 112 (11200-11299)
Topic: 11232 - Cylinder
Replies: 34
Views: 14819

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...
by Adrian Kuegel
Mon Jul 16, 2007 12:07 pm
Forum: Volume 112 (11200-11299)
Topic: 11240 - Antimonotonicity
Replies: 33
Views: 11832

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...
by Adrian Kuegel
Wed Jul 11, 2007 7:03 pm
Forum: Volume 112 (11200-11299)
Topic: 11232 - Cylinder
Replies: 34
Views: 14819

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.
Use w / 2.0 instead.
And please delete your code when you got Accepted.
by Adrian Kuegel
Wed Jul 11, 2007 9:19 am
Forum: Volume 112 (11200-11299)
Topic: 11230 - Annoying painting tool
Replies: 10
Views: 4067

Well, you just describe the greedy everyone uses. But if you implement this naively, it will be O(r*(n-r)*m*(m-c)), because each time when you apply the operation it takes r * c steps. The idea how to get O(n*m) is to store how many operations have been applied with the top left corner in one of the...

Go to advanced search