This post used to contain a link to auto-updating live commentary about our attempt to solve the World Finals problems in real time together with Gennady Korotkevich and Jakub Pachocki - here's the recap:
10:00 - It looks like there will be twelve problems today. Only a few moments before start.
10:06 - the problems are still not available for us, waiting for the online version of the contest to start. The real contestants are already solving them :)
10:08 - we got the problem statements!
10:13 - meret has got the idea how to solve K, that’s what we’re going to try now. The submission system is still not working, but we hope it will work by the time we have the code working.
10:33 - meret still coding K, we got the idea for C, will code it afterwards. Still no way to submit solutions. The World Finals standings shows Tsinghua submitted K, but the outcome is unknown.
11:00 - meret finished K, but the system only allowed submitting A-F at that point, so I coded C and got it accepted. Now Gennady is coding D, and we’re still waiting to be able to submit K.
11:04 - we’re finally able to submit K, and get Wrong Answer. Meret is now reading his code, while Gennady continues to code D.
11:09 - meret found a bug but still got WA after resubmitting.
11:11 - Gennady submitted D, got TLE, meret resubmitted again, got WA.
11:25 - we’ve got plenty more incorrect attempts on K, now Gennady is speeding up his D. I will code E afterwards. Not very lucky start :)
11:49 - now we have 4 problems solved: C, D, E and K. C is +, D is +2, E is +1, K is +8.
11:58 - Gennady started on B. We know how to solve G in O(N^4), but that might be too slow.
12:14 - we decided that B might time out, and decided to code the slow-ish G instead - it has more chances to fit under the time limit. Jakub is solving G now.
12:30 - meret got G coded but it doesn’t work on examples. Gennady started on B again. I’m trying to figure out the formulas in J - the problem shouldn’t be that hard after you have all the formulas :)
12:52 - meret’s G TLEs, Gennady almost ready with B. We came up with a way to speed up G from O(n^4) to O(n^3logn), will do that after we submit B.
13:07 - Gennady’s B is accepted after a WA and a bugfix. meret is now speeding up G.
13:16 - We got G accepted as well, 6 problems now! We kind of know how to solve H, will try to code it since we don’t have any better ideas.
13:59 - and H is accepted, somewhat surprising! Jakub will bruteforce A, and we’ll try to solve other problems with Gennady. 7 problems for us versus 6 for the current leader Moscow SU.
14:04 - here’s an overview of what’s left. Problem A is the constructive one, and Jakub will try to bruteforce small cases to see the pattern. Problems F, I, J, L are all geometry problems. Problems J and L are relatively straightforward algorithmically but awful to code. Problem F probably involves some kind of ternary search so it’s dangerous to solve it. Problem I should be easy to code once we have the solution, so we’re trying to solve it right now.
14:23 - we’ve discussed J with Jakub and decided that we don’t actually need any formulas and can use binary search everywhere, so it becomes tolerable. I will code it now.
14:51 - I’ve coded J for half an hour and realized I haven’t even approached the “lexicographically smallest” part, so won’t be able to finish it in time, should give up. Now Jakub is trying to code some bruteforce with pruning for A.
14:56 - That’s still too slow.
14:59 - I guess we’ll finish with 7 problems solved. Well, it was a nice contest!
15:03 - We have 7 problems and 1244 penalty minutes. Let’s see how the teams did. Thanks for reading, this story will probably not be updated anymore.
The award ceremony is going on right now, but it looks like we did slightly better than the winning teams. The top two teams are SPb SU and Moscow SU, with 1300+ penalty minutes. Of course, they were under much more pressure. Congratulations to the winners!
10:00 - It looks like there will be twelve problems today. Only a few moments before start.
10:06 - the problems are still not available for us, waiting for the online version of the contest to start. The real contestants are already solving them :)
10:08 - we got the problem statements!
10:13 - meret has got the idea how to solve K, that’s what we’re going to try now. The submission system is still not working, but we hope it will work by the time we have the code working.
10:33 - meret still coding K, we got the idea for C, will code it afterwards. Still no way to submit solutions. The World Finals standings shows Tsinghua submitted K, but the outcome is unknown.
11:00 - meret finished K, but the system only allowed submitting A-F at that point, so I coded C and got it accepted. Now Gennady is coding D, and we’re still waiting to be able to submit K.
11:04 - we’re finally able to submit K, and get Wrong Answer. Meret is now reading his code, while Gennady continues to code D.
11:09 - meret found a bug but still got WA after resubmitting.
11:11 - Gennady submitted D, got TLE, meret resubmitted again, got WA.
11:25 - we’ve got plenty more incorrect attempts on K, now Gennady is speeding up his D. I will code E afterwards. Not very lucky start :)
11:49 - now we have 4 problems solved: C, D, E and K. C is +, D is +2, E is +1, K is +8.
11:58 - Gennady started on B. We know how to solve G in O(N^4), but that might be too slow.
12:14 - we decided that B might time out, and decided to code the slow-ish G instead - it has more chances to fit under the time limit. Jakub is solving G now.
12:30 - meret got G coded but it doesn’t work on examples. Gennady started on B again. I’m trying to figure out the formulas in J - the problem shouldn’t be that hard after you have all the formulas :)
12:52 - meret’s G TLEs, Gennady almost ready with B. We came up with a way to speed up G from O(n^4) to O(n^3logn), will do that after we submit B.
13:07 - Gennady’s B is accepted after a WA and a bugfix. meret is now speeding up G.
13:16 - We got G accepted as well, 6 problems now! We kind of know how to solve H, will try to code it since we don’t have any better ideas.
13:59 - and H is accepted, somewhat surprising! Jakub will bruteforce A, and we’ll try to solve other problems with Gennady. 7 problems for us versus 6 for the current leader Moscow SU.
14:04 - here’s an overview of what’s left. Problem A is the constructive one, and Jakub will try to bruteforce small cases to see the pattern. Problems F, I, J, L are all geometry problems. Problems J and L are relatively straightforward algorithmically but awful to code. Problem F probably involves some kind of ternary search so it’s dangerous to solve it. Problem I should be easy to code once we have the solution, so we’re trying to solve it right now.
14:23 - we’ve discussed J with Jakub and decided that we don’t actually need any formulas and can use binary search everywhere, so it becomes tolerable. I will code it now.
14:51 - I’ve coded J for half an hour and realized I haven’t even approached the “lexicographically smallest” part, so won’t be able to finish it in time, should give up. Now Jakub is trying to code some bruteforce with pruning for A.
14:56 - That’s still too slow.
14:59 - I guess we’ll finish with 7 problems solved. Well, it was a nice contest!
15:03 - We have 7 problems and 1244 penalty minutes. Let’s see how the teams did. Thanks for reading, this story will probably not be updated anymore.
The award ceremony is going on right now, but it looks like we did slightly better than the winning teams. The top two teams are SPb SU and Moscow SU, with 1300+ penalty minutes. Of course, they were under much more pressure. Congratulations to the winners!
Hi god
ReplyDeletelol
Delete