|
Algorithm Finals: Jan_Kuipers wins! - 06.29.07 6:30 PM EDT By Petr TopCoder Member 4:07 - 23 minutes before the round starts. 4:08 - Vitaliy has already completed his setup and is walking around nervously. There's an interesting story about his participation in this TCO - it turns out that he is at the military training camp this month, and had to request an officer approval to get here. 4:10 - speaking of the odds... Well, bmerry is the person performing best lately. 4:11 - and no, I don't watch the webcast, so I can be a little out of discussion today. 4:12 - 1 african, 1 asian and 6 europeans today. 4:15 - speaking of the component competition, if anyone is interested, kyky has won the third component as well in the design. A last-minute change brought hefeng to the first place in development, so he's probably going to win given he was first in two components. 4:16 - as we have only 8 participants today, probably it's not so bad an idea to introduce them. 4:17 - Jan_Kuipers from the Netherlands. He's studying at Utrecht University, and is an experienced TopCoder with 129 matches. He's not at his maximum rating now, but he's at a big rise. 4:19 - Eryx from Poland. I believe he's a PhD student at Warsaw University. The champion of TCO 05. He has the longest hair of all the finalists. 4:21 - Vitaliy from Russia. See my 'Meet Team Russia' article. 4:22 - tomekkulczynski from Poland. He's a highschooler, and has attended the TCHS tournament, scoring highest in the final round (but not winning the tournament). 4:23 - bmerry from South Africa. The "Awards" section of his resume is awesome. 4:24 - darnley from Russia. See my 'meet team Russia' article. 4:25 - JongMan from Korea. He's by far at the best point of his career now. 4:26 - and tomek. 4:27 - the competitors have been introduced to the public and are invited onstage. 4:28 - will we be able to watch the contest in the Arena?.. It seems no. 4:31 - the contest has started, and has appeared in the Arena. All 8 competitors start with the easy problem. 4:32 - the problem seems to be very straightforward - one should always own the shares that rise the fastest. 4:34 - Yarin , the tester of the round, says the two other problems are "one hard and one super hard imho". 4:37 - probably the easy is not that easy. Calculating the point where the 'optimal' share changes is not that easy. Some binary search is needed. Or some equation. 4:40 - Jan_Kuipers and JongMan submit the easy. Jan_Kuipers only switches at the slope change points, and JongMan only at the integer time points. Is that OK? 4:43 - I think I can prove that switching only at slope changes is OK. The points where the change would be profitable are found by solving f'(x)/f(x)=g'(x)/g(x), where f(x) and g(x) are the share price functions. We get b/(a+bx)=d/(c+dx), or bc+bdx=ad+bdx, or bc=ad - that doesn't depend on x. 4:45 - tomek, bmerry and tomekkulczynski have submitted the easy. 4:48 - Jan_Kuipers went for the hard, all others opened the medium. 4:51 - darnley submits the easy. 4:52 - and so does Eryx. darnley went for the hard. 4:55 - Vitaliy submits the easy, too. There'll probably be a long gap before the next submit. 5:02 - about the medium problem solution: first, suppose we are only allowed to leave the raft once. Then, we should iterate over all possible orderings of visited sites, and then for each ordering to find the best point to leave the raft. To do that, we can apply binary search: in the optimal solution, the angles at which we leave and return to the river should be equal (this is proved similar to the laws of light traveling), so we binary search over the function 'leaving angle minus returning angle'). 5:05 - and it seems like we can then do a DP on the subset of the sites visited. This seems to be not obviously correct because the periods when we are off the raft might overlap, however, I have a feeling that in that cases we can obtain an even better solution by not returning to the raft in between. 5:02 - about the medium problem solution: first, suppose we are only allowed to leave the raft once. Then, we should iterate over all possible orderings of visited sites, and then for each ordering to find the best point to leave the raft. To do that, we can apply binary search: in the optimal solution, the angles at which we leave and return to the river should be equal (this is proved similar to the laws of light traveling), so we binary search over the function 'leaving angle minus returning angle'). 5:05 - and it seems like we can then do a DP on the subset of the sites visited. This seems to be not obviously correct because the periods when we are off the raft might overlap, however, I have a feeling that in that cases we can obtain an even better solution by not returning to the raft in between. 5:16 - sorry for not updating frequently, I'm trying to think about the problems. Meanwhile, we have 3 compiles on the medium and 2 on the hard. 5:18 - darnley seems to know some idea for the hard, at least his solution seems quite conscious. 5:20 - and he does submit! 5:22 - darnley has tested his solution thoroughly, and it works lightning fast. He seems to be sure in his solution. Can we understand it? Meanwhile, he moves to the medium. 5:29 - sorry, TV duties. 5:29 - tomek submits the medium! Let's read it. 5:33 - he seems to iterate over all possible scenarios of the form 'go there, then there, then return to the raft, then there, ..." That's logical. However, can he evaluate each scenario correctly? It seems that he does independent binary search for different trips off the raft, just as we have suggested. This solution may well pass. 5:37 - his lastPos variable probably indicates that the segments were treated as dependent earlier, but later he decided to drop that as the value assigned to lastPos is never used. 5:41 - in fact, I'm pretty sure about darnley's solution, as the maxtest is fairly obvious, and its runs in time, and as for the correctness, he has seemingly tested it to find all the strings of small length, so that should be ok, too. And also, there's no point in switching to the medium in such situation if you're not absolutely sure. 5:43 - as for how his solution works, the idea is: once we have fixed the first half (or more) of the string, it becomes easy to count the number of appropriate second halves: we just check that it doesn't end with each prefix of length <=n/2, i.e., subtract some powers of two from some power of two. Then, we iterate over the possible first halves, and when we found the required first half, we start increasing it by one character until we get the full string. 5:48 - actually, n=50 might not be the worst case as the first half will consist of almost all zeroes. Let's hope he tested it for several different n's and k=2 billion. 5:51 - bmerry submits the medium. 5:51 - I expect darnley's solution to be tested quite a lot during the challenge phase, however, it may not be challenged with the 'proper' worst cases. 5:54 - misof predicts tomek getting second place with only the easy and a challenge on bmerry's 500. 5:55 - the coding is over. There's not much to be seen in the challenge phase, but that's still very important. 5:59 - in fact, I expect very fast challenges on the 500. 6:04 - -25 for tomek on darnley's 1000. bmerry reads tomek's 500, Jan_Kuipers decided to walk away. 6:07 - and Vitaliy kills darnley's 1000. Too bad. 6:08 - Eryx kills bmerry's 500. Jan_Kuipers' chances are increasing. 6:11 - darnley's solution failed with WA, not TL. Some bug. 6:22 - darnley's solution doesn't work for n=7. Meanwhile, they have announced the results of the Studio competition - yiming won - so probably there's not much wait left. 6:25 - Marathon matches: Mojito1, doudouille, grotmol, jdmetz. 6:26 - Development: hefeng, PE, cnettel. 6:28 - Design: kyky, bendlund, oldbam, sql_lall. 6:30 - Algorithm: all the easys stand, tomek's medium fails. Jan_Kuipers!!! Go Netherlands :) again :) 6:45 - darnley's bug seems to be: "int wwend = ww & ((1 << (pref - p)) - 1);" should be "int wwend = ww & ((1 << p) - 1);". 6:57 - after fixing that bug, the solution passed systests in the practice room. 7:10 - and tomek's solution for the 500 passes after uncommenting the line "if(chosenPoints[p].x - exd1 < lastPos) return 1e100;" 7:11 - that was a lucky day for Jan_Kuipers. |
