Tune in right now for the ACM ICPC 2015 NEERC broadcast: video in Russian, current standings, prediction contest favorites, online mirror starting in 7 minutes. I will be joining the video commentary team around 3 hours into the contest!
Codeforces Round 333 happened on Tuesday (problems, results, top 5 on the left). TooSimple got a clear first place thanks to solving all problems fast, and doing that in the reverse order. Had he chosen the more standard easiest-to-hardest sequence, his score would be 470+1115+1025+1464+1580=5654, just 1 point above izrak's second place! More generally, the Codeforces format has the score of each problem lose a constant fraction of its total points every minute. As a result, the optimal order of solving the problems is in decreasing order of points-per-minute (maximum points for the problem divided by the time required to solve it). For TooSimple the points-per-minute values were: A – 33, B – 104, C – 69, D – 91, E – 100. So the optimal order would actually be B, E, D, C, A – it would’ve yielded 1190+2130+1528+865+316=6029 points.
I’ve tried a new competition format at Croatian Open Competition in Informatics (COCI) Internet Contest #3 on Saturday (problems, results, top 5 on the left). More precisely, the format is not entirely new: it’s the almost forgotten old IOI format, but limited to 3 hours. You can submit your solutions at any time, and they’re judged only after the end of the contest, with independent scoring for each testcase your solution passes, so slow and partially correct solutions still score some points.
Competing without a scoreboard felt quite strange, it was probably the first time in the 13 years since IOI 2002 for me. The problems were somewhat “professional”, so the contest was a good training. Here’s the problem that was worth the most points: you’re given an NxN field with non-negative integers in each cell, and need to place exactly K non-overlapping dominoes so that the sum of the 2K covered cells is the maximum possible.
Normally covering with dominoes is reduced to dynamic programming on a ragged boundary, but in this problem N was up to 2000, so that was out of question. On the other hand, K was just up to 8, so different approaches came into play. Can you see how to solve this problem?
Another interesting question about this problem is: does it matter that we require exactly K dominoes, not “at most K dominoes” as one would normally expect? More precisely, do there exist such K and N, such that 2K<=NxN, and a NxN field of non-negative integers, such that we can get a higher sum by placing K-1 dominoes than by placing K dominoes?
ACM ICPC 2015 NWERC on Sunday was the penultimate European regional contest (problems, results, top 5 on the left, online mirror results, analysis videos). The first place went to the University of Helsinki team Game of Nolife, who have managed to escape the huge time penalty they’ve accumulated by solving one problem more than the second-placed team – congratulations!
Thanks for reading, and check back later for this week's summary!
And to repeat: tune in right now for the ACM ICPC 2015 NEERC broadcast: video in Russian, current standings, prediction contest favorites, online mirror starting in 7 minutes. I will be joining the video commentary team around 3 hours into the contest!
Competing without a scoreboard felt quite strange, it was probably the first time in the 13 years since IOI 2002 for me. The problems were somewhat “professional”, so the contest was a good training. Here’s the problem that was worth the most points: you’re given an NxN field with non-negative integers in each cell, and need to place exactly K non-overlapping dominoes so that the sum of the 2K covered cells is the maximum possible.
Normally covering with dominoes is reduced to dynamic programming on a ragged boundary, but in this problem N was up to 2000, so that was out of question. On the other hand, K was just up to 8, so different approaches came into play. Can you see how to solve this problem?
Another interesting question about this problem is: does it matter that we require exactly K dominoes, not “at most K dominoes” as one would normally expect? More precisely, do there exist such K and N, such that 2K<=NxN, and a NxN field of non-negative integers, such that we can get a higher sum by placing K-1 dominoes than by placing K dominoes?
Thanks for reading, and check back later for this week's summary!
And to repeat: tune in right now for the ACM ICPC 2015 NEERC broadcast: video in Russian, current standings, prediction contest favorites, online mirror starting in 7 minutes. I will be joining the video commentary team around 3 hours into the contest!
No comments:
Post a Comment