contests - it's getting worse again...

Post here if you don't find any other place for your post. But please, stay on-topic: algorithms, programming or something related to this web site and its services.

Moderator: Board moderators

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

contests - it's getting worse again...

Post by Krzysztof Duleba »

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
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey »

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

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

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

Post by misof »

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
New poster
Posts: 4
Joined: Tue Sep 20, 2005 4:31 pm

Post by Griffon »

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
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof »

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
New poster
Posts: 4
Joined: Tue Sep 20, 2005 4:31 pm

Post by Griffon »

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
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba »

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

Griffon
New poster
Posts: 4
Joined: Tue Sep 20, 2005 4:31 pm

Post by Griffon »

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

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba »

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

Sanny
Learning poster
Posts: 78
Joined: Sat Feb 14, 2004 3:59 pm
Location: BUET
Contact:

Post by Sanny »

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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf »

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

Griffon
New poster
Posts: 4
Joined: Tue Sep 20, 2005 4:31 pm

Post by Griffon »

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
Learning poster
Posts: 78
Joined: Sat Feb 14, 2004 3:59 pm
Location: BUET
Contact:

Post by Sanny »

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
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof »

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
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof »

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.

Post Reply

Return to “Other words”