contests - it's getting worse again...

Krzysztof Duleba · Post by **Krzysztof Duleba** » Tue Sep 20, 2005 4:15 pm

Competing in UVA contests is getting impossible. I got used to waiting very long for results, but this time OJ didn't even accept submissions

little joey · Post by **little joey** » Tue Sep 20, 2005 4:25 pm

Yeah... The last succesful submission was at 13:44:11; submissions were not possible the last 16 minutes of the contest.

misof · Post by **misof** » Tue Sep 20, 2005 4:26 pm

Krzysztof Duleba wrote:Competing in UVA contests is getting impossible. I got used to waiting very long for results, but this time OJ didn't even accept submissions

+1

I spent the last hour clicking "browse...", "submit", "browse...", "submit", and so on... Throwing away submissions (while printing that it was successful!) is indeed very bad practice. The behavior of the UVa judge during the last 90 minutes ruined what could be a nice contest.

(Needless to say, I've got at least one solution I assume is correct, but I was unable to submit it for quite a long time.)

When I see the "progress" the UVa judge made in the last months, I can't help thinking that it won't get any better soon

Is anyone actually taking care of the judge currently?

Griffon · Post by **Griffon** » Tue Sep 20, 2005 4:37 pm

But the submits during the last 16 minutes were not lost! they appeared in the judge status after the end of the contest and of course got "Out of contest time". Isn't it unfair?

misof · Post by **misof** » Tue Sep 20, 2005 4:43 pm

Griffon wrote:But the submits during the last 16 minutes were not lost! they appeared in the judge status after the end of the contest and of course got "Out of contest time". Isn't it unfair?

Yeah, now (40 minutes after the contest) I'm getting a lot of "out of contest time" e-mails for submits I made an hour ago. Sad and annoying

BTW not only the last 16 minutes were problematic, from my point of view during the last hour there were just (probably) 5-10 minutes when submitting actually worked.

Griffon · Post by **Griffon** » Tue Sep 20, 2005 4:58 pm

I think that these "Out of contest time" submits must be judged. Sorry for offtopic, but can anyone tell me the algo for problem H - Simple Minded Hashing.

Krzysztof Duleba · Post by **Krzysztof Duleba** » Tue Sep 20, 2005 5:35 pm

DP. Note that state space is much smaller than is seems.

Griffon · Post by **Griffon** » Tue Sep 20, 2005 5:41 pm

Of course DP, but what is the state space? It seems to be L * S * size(alphabet), how to make it smaller?

Krzysztof Duleba · Post by **Krzysztof Duleba** » Tue Sep 20, 2005 5:47 pm

L can be greater than 26? What about S? Think about the worst case - it's still small.

Sanny · Post by **Sanny** » Tue Sep 20, 2005 5:53 pm

There were lots of Runtime Error on Problem-G (Forming Quiz Teams). I used weighted bipartite matching and got lots of RTEs and I am pretty sure that my code is correct. Can anybody give any tricky cases that might cause RTE?

Regards
Sanny

mf · Post by mf » Tue Sep 20, 2005 6:14 pm

Problem G needs a general matching algorithm (not bipartite)
And did you read the clarification: there are test cases with N=8.

Griffon · Post by **Griffon** » Tue Sep 20, 2005 6:16 pm

To Krzysztof Duleba: Thank you very much, I just didn't read the statement carefully, so I missed "strict ascending" and tried to solve non strict one. Thanks a lot once more.
To Sanny: Read the contest clarification board. There it is written that N <= 8, but not N <= 7. Rather unfair I think, but so it is. By the way, I got AC just by bruteforce without any bipartite matching.

Sanny · Post by **Sanny** » Tue Sep 20, 2005 6:20 pm

I saw the clarification. That's not the problem.

Bipartite matching can be applied in this way:
On left are 2*n people and on the right are those same 2*n people. Then you find mincost matching and divide total cost by two.

Regards
Sanny

misof · Post by **misof** » Tue Sep 20, 2005 6:27 pm

Griffon wrote:To Krzysztof Duleba: Thank you very much, I just didn't read the statement carefully, so I missed "strict ascending" and tried to solve non strict one. Thanks a lot once more.

You're not alone

Oh, for how long did I try to solve the task without the word "ascending"? I kept wondering why so many people solved it... until finally I noticed this magic word

Griffon wrote:To Sanny: Read the contest clarification board. There it is written that N <= 8, but not N <= 7. Rather unfair I think, but so it is. By the way, I got AC just by bruteforce without any bipartite matching.

Yep, I had two wrong submits on that one, the first one assumed that N<=7 and crashed, the second one contained an assert(N<=7) and aborted. After that I e-mailed clarify@acm.uva.es with a suggestion that the input data should be fixed and the problem should be rejudged. Apparrently, the only result of my e-mail was the added clarification.

In the contest I got AC with a O(N*2^{2N}) algorithm (for each subset compute the best solution).

misof · Post by **misof** » Tue Sep 20, 2005 6:36 pm

Sanny wrote:I saw the clarification. That's not the problem.

Bipartite matching can be applied in this way:
On left are 2*n people and on the right are those same 2*n people. Then you find mincost matching and divide total cost by two.

Regards
Sanny

IMHO this approach doesn't work. Consider 6 people distributed as follows:

Code: Select all

 A                                              D

B  C                                         E   F

(let the short distances be approx. 10, the long ones approx. 200)

The min cost matching you find is A1-B2, B1-C2, C1-A2, D1-E2, E1-F2, F1-D2 with a total cost of 60. Still, the best solution for the original problem is A-B, D-F, C-E with a total cost of 220.

OJ Board

contests - it's getting worse again...

contests - it's getting worse again...

Re: contests - it's getting worse again...