tag:blogger.com,1999:blog-19533250797934499712018-12-04T09:36:58.076+03:00Algorithms Weekly by Petr MitrichevPetr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.comBlogger383125PetrMitrichevhttps://feedburner.google.comtag:blogger.com,1999:blog-1953325079793449971.post-6487188545221039652018-11-18T06:31:00.000+03:002018-11-18T06:31:05.767+03:00A fjzzq2002 week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/--rY_uL2Aq0o/W-ygQ8S_vkI/AAAAAAACLg0/8NjcT2Ksxc4tMShwhHCVlJceK3EBM8HPwCLcBGAs/s1600/srm737top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="150" data-original-width="783" height="122" src="https://3.bp.blogspot.com/--rY_uL2Aq0o/W-ygQ8S_vkI/AAAAAAACLg0/8NjcT2Ksxc4tMShwhHCVlJceK3EBM8HPwCLcBGAs/s640/srm737top5.png" width="640" /></a></div>TopCoder SRM 737 started the competitive Sep 17 - Sep 23 week (<a href="http://community.topcoder.com/stat?c=round_overview&er=5&rd=17265">problems</a>, <a href="http://community.topcoder.com/stat?c=round_stats_sorted&rd=17265&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://www.topcoder.com/blog/single-round-match-737-editorials/">analysis</a>). There was quite a bit of challenge phase action at the top, but the final results mostly reflect the coding phase order. Congratulations to fjzzq2002 on the win!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-ISVCOvgLWAg/W-yZ_X2xjHI/AAAAAAACLgU/xV6eyH3zRBQS0Rs-pcGufpKRJxqNEJDqQCLcBGAs/s1600/cf511top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="273" data-original-width="1104" height="158" src="https://2.bp.blogspot.com/-ISVCOvgLWAg/W-yZ_X2xjHI/AAAAAAACLgU/xV6eyH3zRBQS0Rs-pcGufpKRJxqNEJDqQCLcBGAs/s640/cf511top5.png" width="640" /></a></div>Codeforces Round 511 followed (<a href="http://codeforces.com/contest/1034">problems</a>, <a href="http://codeforces.com/contest/1034/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/61993">analysis</a>). eds467 was quite a bit slower than the rest of the top scorers on the first three problems, but managed to squeeze in problem E in 982 ms out of 1 second time limit and won. Well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-WCOR-nuB8wo/W-yb54OMQoI/AAAAAAACLgo/w-YKLoiV48EcvOyZ9t5Uh73Vb1oO-GDDACLcBGAs/s1600/oc1819spbtop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="193" data-original-width="997" height="122" src="https://3.bp.blogspot.com/-WCOR-nuB8wo/W-yb54OMQoI/AAAAAAACLgo/w-YKLoiV48EcvOyZ9t5Uh73Vb1oO-GDDACLcBGAs/s640/oc1819spbtop5.png" width="640" /></a></div>Open Cup 2018-19 Grand Prix of SPb opened a busy Sunday (<a href="http://opencup.ru/index.cgi?data=macros/stage&head=index&menu=index&stg=3&region=main&ncup=ocj&class=ocj">results</a>, top 5 on the left). Team Past Glory has managed to solve Artur Riazanov's trademark "formal logic" problem B with a few minutes to go, cementing the first place they earned by solving other problems fast. Well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-Fc2ReXH6T98/W-ybHCSVQqI/AAAAAAACLgg/ebRf-9zZzNIN6cMzZYe8030loguDiAgZQCLcBGAs/s1600/cf512top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="269" data-original-width="1099" height="156" src="https://2.bp.blogspot.com/-Fc2ReXH6T98/W-ybHCSVQqI/AAAAAAACLgg/ebRf-9zZzNIN6cMzZYe8030loguDiAgZQCLcBGAs/s640/cf512top5.png" width="640" /></a></div>Finally, Codeforces Round 512 started even before the Open Cup ended (<a href="http://codeforces.com/contest/1053">problems</a>, <a href="http://codeforces.com/contest/1053/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/62013">analysis</a>). This time fateice was actually able to solve the hardest problem E, but the five incorrect attempts they needed to pass pretests meant that they ended up below the competitors who solved problem D instead. Nevertheless, congratulations to fateice on solving E and to fjzzq2002 on the second victory of the week!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-pssa1RP8qSE/W_DazLSRJbI/AAAAAAACLhU/LnLkHDV4hZAMqOs7Wn3lJshx4gwxTJO3wCLcBGAs/s1600/IMG_20180805_120235.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1200" data-original-width="1600" height="480" src="https://2.bp.blogspot.com/-pssa1RP8qSE/W_DazLSRJbI/AAAAAAACLhU/LnLkHDV4hZAMqOs7Wn3lJshx4gwxTJO3wCLcBGAs/s640/IMG_20180805_120235.jpg" width="640" /></a></div>In <a href="https://petr-mitrichev.blogspot.com/2018/11/an-interactive-week.html">my previous summary</a>, I have mentioned an AtCoder problem: construct any 500 by 500 matrix of distinct positive integers up to 10<sup>15</sup>, such that if we take any two vertically or horizontally adjacent numbers <i>a</i>, <i>b</i> in the matrix and compute max(<i>a</i>,<i>b</i>) mod min(<i>a</i>,<i>b</i>) we always get the same non-zero result.<br /><br />After playing with the problem a bit, one can notice that it's helpful to separate the numbers into <i>big</i> and <i>small</i> numbers (in any given pair of adjacent numbers, we call the dividend max(a,b) the big number, and the divisor min(a,b) the small number). If we put the big numbers into the black cells of a chessboard pattern, and the small numbers into the white cells of the same pattern, then in any pair of adjacent numbers one will be big and one will be small, just as we need.<br /><br />Suppose we have chosen the small numbers. Then we can pick each big number as least common multiple of the adjacent small numbers plus one, and max(<i>a</i>,<i>b</i>) mod min(<i>a</i>,<i>b</i>) will always be equal to one. However, that's not yet a solution, as we need to balance two conflicting needs:<br /><ul style="text-align: left;"><li>The small numbers need to be big enough to be distinct and for the resulting least common multiples to also be distinct.</li><li>The least common multiples, however, need to be small enough to fit under 10<sup>15</sup>. </li></ul>Naively picking the small numbers randomly, as they need to be distinct, would result in numbers on the order of 10<sup>5</sup>, so the products of four numbers would end up being on the order of 10<sup>20</sup>, and the least common multiple of random numbers is not too unlikely to be equal to their product.<br /><br />That means we need to find a way for the least common multiple of four numbers to be significantly smaller than their product, which means that they must have large common divisors. One way to achieve that is to pick a number <i>a<sub>i</sub></i> for each row, a number <i>b<sub>j</sub></i> for each column, and put <i>a<sub>i</sub></i>*<i>b<sub>j</sub></i> as the small numbers. Then the four small numbers surrounding a big number at position (<i>i</i>,<i>j</i>) are <i>a</i><sub><i>i</i>-1</sub>*<i>b<sub>j</sub></i>, <i>a</i><sub><i>i</i>+1</sub>*<i>b<sub>j</sub></i>, <i>a<sub>i</sub></i>*<i>b</i><sub><i>j</i>-1</sub>, and <i>a<sub>i</sub></i>*<i>b</i><sub><i>j</i>+1</sub>. They have quite a few common divisors, and their least common multiple is at most <i>a</i><sub><i>i</i>-1</sub>*<i>a</i><sub><i>i</i></sub>*<i>a</i><sub><i>i</i>+1</sub>*<i>b</i><sub><i>j</i>-1</sub>*<i>b</i><sub><i>j</i></sub>*<i>b</i><sub><i>j</i>+1</sub>. If each <i>a<sub>i</sub></i> and <i>b<sub>j</sub></i> are on the order of 10<sup>3</sup> (we have 500 rows + 500 columns), the product of six such numbers is on the order of 10<sup>18</sup>, two orders of magnitude better than the naive approach but still not good enough.<br /><br />We can notice that among the above four numbers only <i>a<sub>i</sub></i> and <i>b<sub>j</sub></i> were repeated, thus contributing to the reduction of the least common multiple, while <i>a</i><sub><i>i</i>-1</sub>, <i>a</i><sub><i>i</i>+1</sub>, <i>b</i><sub><i>j</i>-1</sub>, and <i>b</i><sub><i>j</i>+1</sub> only appeared once; this suggests a way to improve the solution: instead of assigning numbers to rows and columns, we need to assign them to diagonals containing small numbers. Each small number is at intersection of two diagonals, and we still have just 1000 diagonals in total. Since each big number is surrounded by only four diagonals, its least common multiple will be equal to a product of only four diagonal numbers, and thus be only on the order of 10<sup>12</sup>.<br /><br />Since we need all products and least common multiples to be distinct, we can't actually assign numbers from 1 to 1000 to the diagonals, but we can take the first 1000 prime numbers, first 500 to diagonals of one kind, and next 500 for the other kind. The 1000-th prime number is 7919, the 500-th prime number is 3571, so our least common multiples will not exceed 7919*7919*3571*3571 which is less than 10<sup>15</sup>, and the diagonal numbers being distinct primes guarantees that all numbers in the matrix will be distinct, so we're done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-IR7wTZ1i_DA/W_Dc2ImSvjI/AAAAAAACLho/emuc9Ac1ajgIZAxYwGQ3LQQuSgiriwe_QCLcBGAs/s1600/IMG_20180818_150550.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1056" data-original-width="1600" height="422" src="https://2.bp.blogspot.com/-IR7wTZ1i_DA/W_Dc2ImSvjI/AAAAAAACLho/emuc9Ac1ajgIZAxYwGQ3LQQuSgiriwe_QCLcBGAs/s640/IMG_20180818_150550.jpg" width="640" /></a></div>I have also mentioned an Open Cup problem in the previous summary: the judging program has a hidden string of 1000 digits, each either 0 or 1. In one query, you ask about a segment [<i>l</i>,<i>r</i>], and the judging program returns one of the two things, each with probability 50%:<br /><ul style="text-align: left;"><li>the number <i>u</i> of 1s in the given segment</li><li>a uniformly chosen random integer between 0 and <i>r</i>-<i>l</i>+1 that is <i>not</i> equal to <i>u</i>.</li></ul>In other words, with probability 50% the judging program gives an incorrect answer to your query. Your goal is to reconstruct the hidden string using at most 18000 queries, with one more important restriction: you are also not allowed to ask the same query twice.<br /><br />This problem has been discussed quite extensively in <a href="https://codeforces.com/blog/entry/61880?#comment-458362">the post-match discussion</a> (this is problem E), including my own solution sketch, so I will refer interested readers there :)<br /><br />Thanks for reading, and check back for more!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/qv5BIstqny4" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com2http://petr-mitrichev.blogspot.com/2018/11/a-fjzzq2002-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-42895022236380359012018-11-15T00:05:00.001+03:002018-11-15T04:41:36.255+03:00An interactive week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-LpPFmH8PiBs/W-xn7bEwZTI/AAAAAAACLfw/4IOca-iqWYIn3YnYk1c5yZaJxh704gLIgCLcBGAs/s1600/agc027top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="448" data-original-width="1177" height="242" src="https://1.bp.blogspot.com/-LpPFmH8PiBs/W-xn7bEwZTI/AAAAAAACLfw/4IOca-iqWYIn3YnYk1c5yZaJxh704gLIgCLcBGAs/s640/agc027top5.png" width="640" /></a></div>AtCoder has returned with its Grand Contest 027 during the Sep 10 - Sep 16 week (<a href="https://agc027.contest.atcoder.jp/assignments">problems</a>, <a href="https://agc027.contest.atcoder.jp/standings#page_1">results</a>, top 5 on the left, <a href="https://youtu.be/Vkv4tVBhTb4">my screencast</a>, <a href="https://img.atcoder.jp/agc027/editorial.pdf">analysis</a>). There was a pretty tense fight for the second place with cospleermusora getting problem B accepted with less than a minute remaining; but tourist's victory was not really in doubt as he finished all problems with 25 minutes to spare. Congratulations to both!<br /><br />I've really enjoyed solving <a href="https://agc027.contest.atcoder.jp/tasks/agc027_d">problem D</a> (the choice of constructive problems for this blog is becoming quite a pattern, isn't it?): you need to construct any 500 by 500 matrix of distinct positive integers up to 10<sup>15</sup>, such that if we take any two vertically or horizontally adjacent numbers <i>a</i>, <i>b</i> in the matrix and compute max(<i>a</i>,<i>b</i>) mod min(<i>a</i>,<i>b</i>) we always get the same non-zero result.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-sx6npozqUow/W-xtP0ZE3AI/AAAAAAACLf8/_oZOJY2TeWgeUkuIb_kET5Zk2VKMk-njACLcBGAs/s1600/oc1819udmurtiatop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="198" data-original-width="834" height="150" src="https://4.bp.blogspot.com/-sx6npozqUow/W-xtP0ZE3AI/AAAAAAACLf8/_oZOJY2TeWgeUkuIb_kET5Zk2VKMk-njACLcBGAs/s640/oc1819udmurtiatop5.png" width="640" /></a></div>The second Open Cup stage, the Grand Prix of Udmurtia, followed on Sunday (<a href="http://opencup.ru/index.cgi?data=macros/stage&head=index&menu=index&stg=2&region=main&ncup=ocj&class=ocj">results</a>, top 5 on the left). Team Havka-papstvo had dug themselves into a hole thanks to having a lot of incorrect attempts, then marvelously escaped with just 8 minutes remaining by solving the most difficult problem. Congratulations on the victory!<br /><br />The Grand Prix of Udmurtia was a pioneer of interactive problems in the past, and this incarnation had four of those, too. Problem E went like this: the judging program has a hidden string of 1000 digits, each either 0 or 1. In one query, you ask about a segment [<i>l</i>,<i>r</i>], and the judging program returns one of the two things, each with probability 50%:<br /><ul style="text-align: left;"><li>the number <i>u</i> of 1s in the given segment</li><li>a uniformly chosen random integer between 0 and <i>r</i>-<i>l</i>+1 that is <i>not</i> equal to <i>u</i>.</li></ul>In other words, with probability 50% the judging program gives an incorrect answer to your query. Your goal is to reconstruct the hidden string using at most 18000 queries, with one more important restriction: you are also not allowed to ask the same query twice.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-QCfm8NZ1jIw/W-yNu9DFd-I/AAAAAAACLgI/_fAQcURCmrQL2mxff1yn8uZzH1KG7LkLQCLcBGAs/s1600/IMG_20180801_135603.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1200" data-original-width="1600" height="480" src="https://4.bp.blogspot.com/-QCfm8NZ1jIw/W-yNu9DFd-I/AAAAAAACLgI/_fAQcURCmrQL2mxff1yn8uZzH1KG7LkLQCLcBGAs/s640/IMG_20180801_135603.jpg" width="640" /></a></div>In my previous summary, I have mentioned another problem with segment queries: there's a hidden integer between 1 and 10<sup>18</sup>. You can make queries, and in one query you give a segment [<i>l</i>,<i>r</i>] and the judging program tells you whether the hidden number lies in that segment. In case it does, and your segment has length 1 (<i>l</i>=<i>r</i>), you win. After each query, the hidden number can change a bit — more precisely, by at most <i>k</i>=10. These changes do not depend on your queries — in each testcase the sequence of changes is always the same. You have at most 4500 queries to win.<br /><br />If the hidden number did not change, we would do a binary search: by querying the segment [1,<i>m</i>] we can compare the hidden number with <i>m</i>, so if we knew that our number was within some segment [<i>a</i>,<i>b</i>] before our query, we would narrow it down to either [<i>a</i>,<i>m</i>] or [<i>m</i>+1,<i>b</i>] after this query, and determine our number after at most ceil(log(10<sup>18</sup>))=60 queries.<br /><br />When the hidden number changes under the hood, we need to adapt this approach: now we go from [<i>a</i>,<i>b</i>] to either [<i>a-k</i>,<i>m+k</i>] or [<i>m</i>+1-<i>k</i>,<i>b+k</i>]. When the segment [<i>a</i>,<i>b</i>] is big, this still divides it roughly in half, so we can proceed as before. However, when it becomes small, it will actually stop decreasing, and will never converge to a segment of length 1.<br /><br />So we will do the following: when the length <i>b</i>-<i>a</i>+1 of the current segment is bigger than some boundary <i>b</i>, we will divide it in two using the above approach. And when it's <i>b</i> or less, we will just pick a random number <i>c</i> within the segment, and send [<i>c</i>,<i>c</i>] query. With probability of at least 1/<i>b</i>, we will win in this case. In case we don't, our candidate segment grows from [<i>a</i>,<i>b</i>] to [<i>a</i>-<i>k</i>,<i>b</i>+<i>k</i>], and we continue as before.<br /><br />It's important to pick the right value of <i>b</i>: if it's too big, the probability of winning in each attempt of the second kind would be too low, and we won't always finish under 4500 queries. And if it's too small, it will take too many queries of the first kind between two queries of the second kind to reduce the segment size, and we would have too few queries of the second kind and also won't finish under 4500 queries. It's probably possible to find mathematically optimal value of b, or we can take a guess (I've used <i>b</i>=99 during the contest) and verify that it leads to good enough probability to finish under 4500 queries.<br /><br />Thanks for reading, and check back for more!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/MalA2Kel7ks" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2018/11/an-interactive-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-44938998691071576982018-11-14T21:04:00.000+03:002018-11-14T21:04:12.858+03:00A too difficult week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-nJAO9bPFuAQ/W-xa2PZkShI/AAAAAAACLfU/jhEaXEQBfjUkn-2-MAbET98pO2LWVOI5ACLcBGAs/s1600/cf507top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="270" data-original-width="1102" height="156" src="https://4.bp.blogspot.com/-nJAO9bPFuAQ/W-xa2PZkShI/AAAAAAACLfU/jhEaXEQBfjUkn-2-MAbET98pO2LWVOI5ACLcBGAs/s640/cf507top5.png" width="640" /></a></div>The Sep 3 - Sep 9 week started with Codeforces Round 507 on Wednesday (<a href="http://codeforces.com/contest/1039">problems</a>, <a href="http://codeforces.com/contest/1039/standings">results</a>, top 5 on the left, <a href="https://youtu.be/XxfXYRhDHsU">my screencast</a>, <a href="https://codeforces.com/blog/entry/61668">analysis</a>). Once again the hardest problem was not solved during the round, and thus it all came down to the speed on the first four problems. Um_nik was considerably faster than the competition, finishing the four problems under an hour, and thus got a well-deserved first place. Congratulations!<br /><br /><a href="http://codeforces.com/contest/1039/problem/B">Problem B</a> in this round added a nice twist to a standard setting. This is an interactive problem in which you need to find a hidden integer between 1 and 10<sup>18</sup>. You can make queries, and in one query you give a segment [<i>l</i>, <i>r</i>] and the judging program tells you whether the hidden number lies in that segment. In case it does, and your segment has length 1 (<i>l</i>=<i>r</i>), you win. So far this is a classical binary search problem.<br /><br />Here comes the twist: after each query, the hidden number can change a bit — more precisely, by at most 10. These changes do not depend on your queries — in each testcase the sequence of changes is always the same.<br /><br />Can you see how to adapt the binary search for this setup? You have at most 4500 queries to win.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-gJhXrkaC7bY/W-xf9zkehAI/AAAAAAACLfk/0qgD6xjX6f0AcZnj5oI9TZVFm0XpVHvjQCLcBGAs/s1600/oc1819zhejiangtop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="285" data-original-width="844" height="216" src="https://1.bp.blogspot.com/-gJhXrkaC7bY/W-xf9zkehAI/AAAAAAACLfk/0qgD6xjX6f0AcZnj5oI9TZVFm0XpVHvjQCLcBGAs/s640/oc1819zhejiangtop5.png" width="640" /></a></div>On Sunday, the new season of the Open Cup kicked off with the Grand Prix of Zhejiang (<a href="http://opencup.ru/index.cgi?data=macros/stage&head=index&menu=index&stg=1&region=main&ncup=ocj&class=ocj">results</a>, top 5 on the left). This will most likely be the most brutal contest of the year :) As I understand, this was the first "big" contest set by Yuhao Du, and the scoreboard reminds me of my own <a href="http://acm.math.spbu.ru/cgi-bin/monitor.pl/m060829.dat">first Petrozavodsk contest</a>, or my <a href="http://community.topcoder.com/stat?c=round_stats_sorted&rd=10007&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">second TopCoder SRM</a>. Team japan02 chose the solvable problems well and earned the victory with quite some margin. Well done!<br /><br />Thanks for reading, and check back for more!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/dJbWuMqK8fo" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com1http://petr-mitrichev.blogspot.com/2018/11/a-too-difficult-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-20954426148376702722018-11-14T05:38:00.003+03:002018-11-14T05:38:42.593+03:00A plus four week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-g6MzfSnhnmA/W-s6rhgTnkI/AAAAAAACLd8/RZPQ5AIdK_IuAJQJl3EmC446CwzVo9bPQCLcBGAs/s1600/aimr5top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="271" data-original-width="1197" height="144" src="https://2.bp.blogspot.com/-g6MzfSnhnmA/W-s6rhgTnkI/AAAAAAACLd8/RZPQ5AIdK_IuAJQJl3EmC446CwzVo9bPQCLcBGAs/s640/aimr5top5.png" width="640" /></a></div>Codeforces hosted two rounds during the Aug 27 - Sep 2 week. AIM Tech Round 5 took place on Monday (<a href="http://codeforces.com/contest/1028">problems</a>, <a href="http://codeforces.com/contest/1028/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/61493">analysis</a>). All problems were solvable this time for LHiC and OO0OOO00O0OOO0O00OOO0OO, but Mikhail was considerably faster of the two. Congratulations on the win!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-NByS1GwKqYU/W-s7P8a38cI/AAAAAAACLeE/6X82xzxIxOcUayqVHncmtXT4eGRN_hNcACLcBGAs/s1600/manthan18top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="270" data-original-width="1121" height="154" src="https://1.bp.blogspot.com/-NByS1GwKqYU/W-s7P8a38cI/AAAAAAACLeE/6X82xzxIxOcUayqVHncmtXT4eGRN_hNcACLcBGAs/s640/manthan18top5.png" width="640" /></a></div>Manthan, Codefest 18 was the second Codeforces round of the week (<a href="http://codeforces.com/contest/1037">problems</a>, <a href="http://codeforces.com/contest/1037/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/61606">analysis</a>). The contest really came down to the wire, with the top three participants all completing the problem set with just a few minutes to go. Tourist was just a tiny bit faster with the easier problems, and thus earned the victory. Well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-4YcJ_kbTrdA/W-uJ7GQL80I/AAAAAAACLe8/ZcGmh_vltaEOgQUqgk1QYZVxzyzc8kTcACLcBGAs/s1600/pzsummer2018top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="146" data-original-width="1444" height="64" src="https://2.bp.blogspot.com/-4YcJ_kbTrdA/W-uJ7GQL80I/AAAAAAACLe8/ZcGmh_vltaEOgQUqgk1QYZVxzyzc8kTcACLcBGAs/s640/pzsummer2018top5.png" width="640" /></a></div>This week also marked the end of the summer Petrozavodsk training camp (<a href="http://karelia.snarknews.info/index.cgi?data=macros/results&menu=index&head=index&round=09&class=2018s&sbname=2018s">results</a>, top 5 on the left), the 9-contest event for top Russian and some other ICPC teams to practice before the new season. Given that the second-placed team in those standings <a href="http://codeforces.com/blog/entry/62039">is not actually going</a> to participate in official ICPC contests this year, the gap between the first team (current ICPC World Champions) and the rest of the field is daunting, even though it's only August yet :)<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-dJ1QWqQ-f1Y/W-t6POaXewI/AAAAAAACLeo/v8q1uUcMvO4RcKx4lVsIn9DoGlM-tURAgCLcBGAs/s1600/IMG_20180723_180839.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1200" data-original-width="1600" height="480" src="https://3.bp.blogspot.com/-dJ1QWqQ-f1Y/W-t6POaXewI/AAAAAAACLeo/v8q1uUcMvO4RcKx4lVsIn9DoGlM-tURAgCLcBGAs/s640/IMG_20180723_180839.jpg" width="640" /></a></div>In <a href="https://petr-mitrichev.blogspot.com/2018/11/a-250-week.html">my previous summary</a>, I have mentioned a TopCoder problem: you are given a 10x10 grid and can place at most 150 unit cubes onto it. A cube can be placed onto a cell of the grid, or on top of another cube. Given a number <i>s</i> between 1 and 500, you need to place the cubes in such a way that the surface area of the resulting figure (the total number of sides of the cubes that do not touch the grid or other cubes) is equal to <i>s</i>, or report that it's impossible.<br /><br />The approach I will describe is a very typical one for such "constructive" problems. Suppose we have found the solution for some value of <i>s</i>. Let's take one extra cube and put it on top of an existing one. This will increase the surface by four (five new sides appear, and one old one is covered), so we'd get a solution for <i>s</i>+4. We can now apply the same trick to get a solution for <i>s</i>+8, <i>s</i>+12 and so on.<br /><br />Since we spend one cube to increase the surface by 4, and 150*4 is significantly bigger than 500, we won't run out of cubes.<br /><br />Now the only task that remains is to find out the smallest possible figure for each remainder of <i>s</i> modulo 4. This can be done by analyzing a few cases by hand: it turns out the minimum solvable <i>s</i> for each remainder are 8, 5, 10 and 11.<br /><br />During the round I've initially discovered another induction idea: just placing a new cube on the grid in such a way that it's disconnected from the rest adds 5 to the surface, so I've tried to build a similar solution modulo 5. However, in that case we do run out of space as we can have at most 50 independent cubes on the 10x10 grid, and 50*5 is less than 500.<br /><br />Thanks for reading, and check back for more!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/9uj4oIrx8GQ" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com1http://petr-mitrichev.blogspot.com/2018/11/a-plus-four-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-26047060514651228802018-11-13T23:48:00.001+03:002018-11-13T23:48:52.309+03:00A 250+ week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-ohwB8XBEa5g/W-s2Qy0FDdI/AAAAAAACLdw/VauT9lNmnUknscozq52XSD80_lqQT5NKQCLcBGAs/s1600/tco18wildtop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="146" data-original-width="778" height="120" src="https://4.bp.blogspot.com/-ohwB8XBEa5g/W-s2Qy0FDdI/AAAAAAACLdw/VauT9lNmnUknscozq52XSD80_lqQT5NKQCLcBGAs/s640/tco18wildtop5.png" width="640" /></a></div>The Aug 20 - Aug 26 week was very calm compared to the previous ones, with just the TopCoder Open 2018 Online Wildcard Round on Saturday (<a href="http://community.topcoder.com/stat?c=round_overview&er=5&rd=17246">problems</a>, <a href="http://community.topcoder.com/stat?c=round_stats_sorted&rd=17246&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="http://community.topcoder.com/stat?c=round_stats_sorted&rd=17247&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">parallel round results</a>, <a href="https://www.topcoder.com/blog/2018-tco-algorithm-wildcard-round-editorials/">analysis</a>). ACRush, Egor and Stonefeang were the only participants to solve all three problems, but ACRush and Egor were almost twice as fast in solving the hardest one, thus qualifying to the TCO onsite with a 250+ point margin. Well done!<br /><br /><a href="http://community.topcoder.com/stat?c=problem_statement&pm=15011&rd=17246">The easy problem</a> in this round was cute. You are given a 10x10 grid and can place at most 150 unit cubes onto it. A cube can be placed onto a cell of the grid, or on top of another cube. Given a number <i>s</i> between 1 and 500, you need to place the cubes in such a way that the surface area of the resulting figure (the total number of sides of the cubes that do not touch the grid or other cubes) is equal to <i>s</i>, or report that it's impossible.<br /><br />Thanks for reading, and check back for more!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/QVlv9lpmMxM" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2018/11/a-250-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-79173603371708040402018-11-13T23:30:00.001+03:002018-11-13T23:30:17.117+03:00A birdie week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-cPH0ri9ryZg/W-szEXlCQKI/AAAAAAACLdk/eNyCojYoM_wTuE-nRzVVQQQZaP5GniiogCLcBGAs/s1600/srm736top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="149" data-original-width="781" height="122" src="https://2.bp.blogspot.com/-cPH0ri9ryZg/W-szEXlCQKI/AAAAAAACLdk/eNyCojYoM_wTuE-nRzVVQQQZaP5GniiogCLcBGAs/s640/srm736top5.png" width="640" /></a></div>TopCoder SRM 736 started the Aug 13 - Aug 19 week (<a href="http://community.topcoder.com/stat?c=round_overview&er=5&rd=17242">problems</a>, <a href="http://community.topcoder.com/stat?c=round_stats_sorted&rd=17242&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://youtu.be/WhpC_sdoqNc">my screencast</a>, <a href="https://www.topcoder.com/blog/single-round-match-736-editorials/">analysis</a>). This was the first round under <a href="https://tco19.topcoder.com/home/algorithm/algorithm-rules">the new system</a> in which one can qualify for the last online round and even to the onsite round of TopCoder Open 2019 by placing well in all SRMs in a quarter. rng_58 has claimed the early lead in that leaderboard by winning the SRM by less than one full point!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-V7TnZ0YM5Ps/W-st5sACm8I/AAAAAAACLdE/6Yv346VrjEMFLS2u3PRDPd5Fhvw3MrY2wCLcBGAs/s1600/cf504top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="269" data-original-width="1104" height="154" src="https://2.bp.blogspot.com/-V7TnZ0YM5Ps/W-st5sACm8I/AAAAAAACLdE/6Yv346VrjEMFLS2u3PRDPd5Fhvw3MrY2wCLcBGAs/s640/cf504top5.png" width="640" /></a></div>Codeforces then held two rounds based on VK Cup Finals problems, starting with Round 504 on Friday (<a href="http://codeforces.com/contest/1023">problems</a>, <a href="http://codeforces.com/contest/1023/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/61356">analysis</a>). Just as in the official round, the hardest problem remained unsolved, but this time the winner was determined on challenges. ko_osaga found 9 opportunities and got a clear first place as the result. Well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-Dl5l-Z8rqWo/W-svxgJLJTI/AAAAAAACLdY/tLYUYk6JnvsA-1KYNcDJtCYosg-qYSeegCLcBGAs/s1600/fbhc2018r3top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="413" data-original-width="930" height="284" src="https://3.bp.blogspot.com/-Dl5l-Z8rqWo/W-svxgJLJTI/AAAAAAACLdY/tLYUYk6JnvsA-1KYNcDJtCYosg-qYSeegCLcBGAs/s640/fbhc2018r3top5.png" width="640" /></a></div>Facebook Hacker Cup Round 3 on Saturday selected the 25 lucky finalists going to Menlo Park (<a href="https://www.facebook.com/hackercup/problem/1851349144951409/">problems</a>, <a href="https://www.facebook.com/hackercup/scoreboard/2175104102721970/?filter=everyone">results</a>, top 5 on the left, <a href="https://www.facebook.com/notes/facebook-hacker-cup/hacker-cup-2018-round-3-solutions/2319941004688454/">analysis</a>). Xiao was quite a bit faster than the rest of the pack, qualifying to the onsite finals in style. Congratulations to Xiao and to all finalists!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-C16MZGtYsZI/W-suKXxfbVI/AAAAAAACLdM/on5qzr0pl-8RBOiwVBgWikO21bf4gT0UwCLcBGAs/s1600/cf505top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="269" data-original-width="1149" height="148" src="https://3.bp.blogspot.com/-C16MZGtYsZI/W-suKXxfbVI/AAAAAAACLdM/on5qzr0pl-8RBOiwVBgWikO21bf4gT0UwCLcBGAs/s640/cf505top5.png" width="640" /></a></div>Finally, another VK Cup-based Codeforces Round 505 wrapped up the week (<a href="http://codeforces.com/contest/1025">problems</a>, <a href="http://codeforces.com/contest/1025/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/61323">analysis</a>). Once again the hardest problem remained unsolved, and once again it took solving all remaining problems plus finding a few challenges to earn a victory — and Swistakk did just that.<br /><br />Thanks for reading, and check back for more!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/Cs_n6DDVmE8" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2018/11/a-birdie-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-13958302423104589362018-11-13T22:54:00.000+03:002018-11-13T23:33:29.811+03:00A Toronto week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-2e-gSORwP0g/W-slDhxzxTI/AAAAAAACLcU/fys2CYBqRmslRkt92zoGJIw0Ey9dlKOAQCLcBGAs/s1600/dcj18finalstop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="314" data-original-width="1279" height="156" src="https://2.bp.blogspot.com/-2e-gSORwP0g/W-slDhxzxTI/AAAAAAACLcU/fys2CYBqRmslRkt92zoGJIw0Ey9dlKOAQCLcBGAs/s640/dcj18finalstop5.png" width="640" /></a></div>The Aug 6 - Aug 12 week was the Google Code Jam final week, onsite in Toronto. Distributed Code Jam 2018 Finals has opened the event on Thursday (<a href="https://codejam.withgoogle.com/codejam/contest/8404486/dashboard#s=p1">problems</a>, <a href="https://codejam.withgoogle.com/codejam/contest/8404486/scoreboard#vt=1">results</a>, top 5 on the left, <a href="https://codejam.withgoogle.com/codejam/contest/8404486/dashboard#s=a">analysis</a>). The contestants pursued wildly varying sets of problems, but in the end only Radewoosh, kevinsogo, tczajka and fagu could solve more than one full problem. Congratulations to all four, and especially to Radewoosh on the win!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-pdHhwlGwSWw/W-smf5AooXI/AAAAAAACLcg/X_8lWe4AeSw9tPCkIq_HWUFCSB4dRIjeQCLcBGAs/s1600/gcj18finalstop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="355" data-original-width="1500" height="150" src="https://1.bp.blogspot.com/-pdHhwlGwSWw/W-smf5AooXI/AAAAAAACLcg/X_8lWe4AeSw9tPCkIq_HWUFCSB4dRIjeQCLcBGAs/s640/gcj18finalstop5.png" width="640" /></a></div>The more traditional Code Jam 2018 Finals followed a day later (<a href="https://codejam.withgoogle.com/2018/challenges/0000000000007766/dashboard/000000000004da97">problems</a>, <a href="https://codejam.withgoogle.com/2018/challenges/0000000000007766/scoreboard">results</a>, top 5 on the left, <a href="https://codejam.withgoogle.com/2018/challenges/0000000000007766/analysis">analysis</a>). Once again the sets of problems of the top contestants were very different, but this time only one participant managed to get three full problems: Gennady.Korotkevich. Congratulations on the victory!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-VEqld00ISQE/W-sofA0JB4I/AAAAAAACLcs/-Jh2ysVfNBYF8P5fH8LchACVr69uZ2fcQCLcBGAs/s1600/cf503top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="273" data-original-width="1117" height="156" src="https://1.bp.blogspot.com/-VEqld00ISQE/W-sofA0JB4I/AAAAAAACLcs/-Jh2ysVfNBYF8P5fH8LchACVr69uZ2fcQCLcBGAs/s640/cf503top5.png" width="640" /></a></div>Codeforces Round 503 took place on Saturday (<a href="http://codeforces.com/contest/1019">problems</a>, <a href="http://codeforces.com/contest/1019/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/61161">analysis</a>). This time it was top four participants on four problems, with Marcin_smu barely claiming the first plce thanks to having only one pretests failure compared to Radewoosh's five. Well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-M8nB-uarHgg/W-sqKokeqbI/AAAAAAACLc4/GBBhM_jqrkcTa5iUHev_WtI7lV_hxaXXQCLcBGAs/s1600/vk2018finaltop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="291" data-original-width="1103" height="168" src="https://3.bp.blogspot.com/-M8nB-uarHgg/W-sqKokeqbI/AAAAAAACLc4/GBBhM_jqrkcTa5iUHev_WtI7lV_hxaXXQCLcBGAs/s640/vk2018finaltop5.png" width="640" /></a></div>Finally, VK Cup 2018 Final onsite in St Petersburg wrapped up the week on Sunday (<a href="http://codeforces.com/contest/951">problems</a>, <a href="http://codeforces.com/contest/951/standings">results</a>, top 5 on the left). The heavy pre-round favorite "Нижний Магазин SU: BZ" was a lot faster than everybody else to solve the first five problems, but the system test failure meant that they had to settle for third. Team "120 Minutes Adventure" was more careful and thus claimed the victory. Congratulations!<br /><br />Thanks for reading, and check back for more!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/Tyrf1w78ZGM" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com2http://petr-mitrichev.blogspot.com/2018/11/a-toronto-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-70011371356022637802018-11-02T20:10:00.000+03:002018-11-13T22:12:23.363+03:00A unit week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-6ZiRtot-87c/W9xv_nBnY5I/AAAAAAACLG8/RQjuDkukc0c5PXcHYd89aA5SuAwKpaDJQCLcBGAs/s1600/cf500top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="273" data-original-width="1117" height="155" src="https://1.bp.blogspot.com/-6ZiRtot-87c/W9xv_nBnY5I/AAAAAAACLG8/RQjuDkukc0c5PXcHYd89aA5SuAwKpaDJQCLcBGAs/s640/cf500top5.png" width="640" /></a></div>The Jul 30 - Aug 5 competitive week started early with Codeforces Round 500 on Monday (<a href="http://codeforces.com/contest/1012">problems</a>, <a href="http://codeforces.com/contest/1012/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/60920">analysis</a>). There were a few strategy options on the table, as the last two problems had the same point value and some people went for E and some for F: E turned out to be the right choice. Congratulations to Um_nik on the win!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-j9HlnZD1FUY/W9xxe3iJAqI/AAAAAAACLHI/dvRsbPrH6g0zxk9LV-PNQ2UF1LxD3UldQCLcBGAs/s1600/fbhc2018r2top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="418" data-original-width="946" height="282" src="https://2.bp.blogspot.com/-j9HlnZD1FUY/W9xxe3iJAqI/AAAAAAACLHI/dvRsbPrH6g0zxk9LV-PNQ2UF1LxD3UldQCLcBGAs/s640/fbhc2018r2top5.png" width="640" /></a></div>Facebook Hacker Cup 2018 Round 2 followed on Saturday (<a href="https://www.facebook.com/hackercup/problem/988017871357549/">problems</a>, <a href="https://www.facebook.com/hackercup/scoreboard/211051912693116/?filter=everyone">results</a>, top 5 on the left, <a href="https://www.facebook.com/notes/facebook-hacker-cup/hacker-cup-2018-round-2-solutions/2286692684679953/">analysis</a>, <a href="https://youtu.be/pKQJRGj-4Ic">my screencast</a>). Getting into the top 200 was the main goal, but there was some competition for the top spots as well, where Alex was a bit faster than everybody else. Well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-VlVbhGneICI/W9x5zcBmyyI/AAAAAAACLHo/MPSmOEXA_T0Z2BXeB8E1GS4MMUfTMbTxwCLcBGAs/s1600/IMG_20180716_082302.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="920" data-original-width="1600" height="368" src="https://2.bp.blogspot.com/-VlVbhGneICI/W9x5zcBmyyI/AAAAAAACLHo/MPSmOEXA_T0Z2BXeB8E1GS4MMUfTMbTxwCLcBGAs/s640/IMG_20180716_082302.jpg" width="640" /></a></div>In <a href="https://petr-mitrichev.blogspot.com/2018/10/the-week-of-14.html">my previous summary</a>, you are given a program for a drawing robot consisting of at most 250000 commands. Each command is either F "move forward by 1 unit, drawing a line", L "turn left by 90 degrees", or R "turn right by 90 degrees". The drawn polyline splits the plane into multiple regions, some finite, some infinite. Your goal is to return the list of the areas of all finite regions.<br /><br />There's a somewhat well-known approach to the general problem of finding faces of a planar graph which is described in <a href="https://www.topcoder.com/blog/tco18-round-4-editorial/">the official analysis</a>. However, I've used the specifics of the problem and went with a different approach that I found less bug-prone.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-dXymPmkK3qs/W9yEmB_MRJI/AAAAAAACLIs/rKLfU6KZIqk6SxIE8dTKfFnmEHyBYjmzQCKgBGAs/s1600/IMG_20181102_100633.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" data-original-height="1600" data-original-width="1294" height="400" src="https://4.bp.blogspot.com/-dXymPmkK3qs/W9yEmB_MRJI/AAAAAAACLIs/rKLfU6KZIqk6SxIE8dTKfFnmEHyBYjmzQCKgBGAs/s400/IMG_20181102_100633.jpg" width="322" /></a></div>Let's imagine the plane as a grid, split the polyline into unit segments, and look at the vertical unit segments for now. Every row of the plane will be split into two infinite blocks plus some finite <i>k</i> times 1 blocks by the vertical unit segments. The overall number of finite blocks is at most 250000.<br /><br />Now let's put those blocks into a <a href="https://en.wikipedia.org/wiki/Disjoint-set_data_structure">disjoint-set data structure</a>, and merge the blocks that are adjacent vertically. In order to find the latter, we need to iterate over pairs of adjacent rows with two pointers, and not forget to take the horizontal polyline unit segments between those rows into account.<br /><br />While the general planar graph algorithm is not harder than this one, I found that this approach allows to sidestep all corner cases, for example: what if there is a vertex of degree 1? What if there's more than one connected component of the polyline (not possible in this problem)?<br /><br />Thanks for reading, and check back for more!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/zxsXFrq56sI" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2018/11/a-unit-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-70682487672767627732018-10-31T16:11:00.000+03:002018-10-31T16:13:25.773+03:00A week of 14<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-LBkUWDXms0s/W9miopQ8XWI/AAAAAAACLFc/WPm6kkaoTNAODD5TwiN6vJ1Dlu8I5LZzQCLcBGAs/s1600/cf499to5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="274" data-original-width="1101" height="158" src="https://4.bp.blogspot.com/-LBkUWDXms0s/W9miopQ8XWI/AAAAAAACLFc/WPm6kkaoTNAODD5TwiN6vJ1Dlu8I5LZzQCLcBGAs/s640/cf499to5.png" width="640" /></a></div>The Jul 23 - Jul 29 week warmed up with Codeforces Round 499 on Thursday (<a href="http://codeforces.com/contest/1010">problems</a>, <a href="http://codeforces.com/contest/1010/standings">results</a>, top 5 on the left, <a href="https://youtu.be/mJi3yem1pk0">my screencast</a>, <a href="https://codeforces.com/blog/entry/60851">analysis</a>). Without taking the challenges into account the top of the scoreboard would be quite packed, but the challenges are of course taken into account, skyrocketing Kostroma and cki86201 to clear first two places. Well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-c4-Y9rwd4zo/W9mkv_BuFyI/AAAAAAACLFo/JgID8k1w4NswaCB5MralMu9nWO5h6xkJACLcBGAs/s1600/tco18r4top14.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="241" data-original-width="630" src="https://2.bp.blogspot.com/-c4-Y9rwd4zo/W9mkv_BuFyI/AAAAAAACLFo/JgID8k1w4NswaCB5MralMu9nWO5h6xkJACLcBGAs/s1600/tco18r4top14.png" /></a></div>The main event of the week took place on Saturday, with TopCoder Open 2018 Round 4 selecting 14 finalists that would go to Texas (<a href="http://community.topcoder.com/stat?c=round_overview&er=5&rd=17226">problems</a>, <a href="http://community.topcoder.com/stat?c=round_stats_sorted&rd=17226&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 14 on the left, <a href="http://community.topcoder.com/stat?c=round_stats_sorted&rd=17228&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">parallel round results</a>, <a href="https://youtu.be/QvQ_nu1OuO4">my screencast</a>, <a href="https://www.topcoder.com/blog/tco18-round-4-editorial/">analysis</a>). Both harder problems were approachable, but nobody was able to get all three, resulting in a fairly diverse scoreboard. Kankuro was still considerably faster than everybody else,<br />and has also cemented his lead with a successful challenge. Congratulations to Vladislav and to everybody who qualified for the onsite round!<br /><br />I found <a href="http://community.topcoder.com/stat?c=problem_statement&pm=14993&rd=17226">the medium problem</a> in this round quite educational, if a bit standard. You are given a program for a drawing robot consisting of at most 250000 commands. Each command is either F "move forward by 1 unit, drawing a line", L "turn left by 90 degrees", or R "turn right by 90 degrees". The drawn polyline splits the plane into multiple regions, some finite, some infinite. Your goal is to return the list of the areas of all finite regions.<br /><br />Thanks for reading, and check back soon for the solution!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/KTvQ7cqeXGE" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2018/10/the-week-of-14.htmltag:blogger.com,1999:blog-1953325079793449971.post-43525947742174953782018-10-29T22:03:00.001+03:002018-10-29T22:30:11.894+03:00A decision tree week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-aE3EjWdySQA/W9dEB1qYWRI/AAAAAAACLAk/esUZvmND0BM2tZXeW1shnlX0tRbWz4FtQCLcBGAs/s1600/tco18r3btop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="152" data-original-width="786" height="122" src="https://4.bp.blogspot.com/-aE3EjWdySQA/W9dEB1qYWRI/AAAAAAACLAk/esUZvmND0BM2tZXeW1shnlX0tRbWz4FtQCLcBGAs/s640/tco18r3btop5.png" width="640" /></a></div>The Jul 16 - Jul 22 week provided the second and last chance to progress to the round of 100 in the TopCoder Open 2018, with 50 more advancers chosen in Round 3B (<a href="http://community.topcoder.com/stat?c=round_overview&er=5&rd=17205">problems</a>, <a href="http://community.topcoder.com/stat?c=round_stats_sorted&rd=17205&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="http://community.topcoder.com/stat?c=round_stats_sorted&rd=17206&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">parallel round results</a>, <a href="https://www.topcoder.com/blog/2018-tco-algorithm-round-3b-editorials/">analysis</a>). qwerty787788 was the only one to solve all three problems correctly, and thus won the first place with quite a margin — congratulations to Borys and to everybody who advanced!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-NXmNY_XnxOc/W9dIki3r7jI/AAAAAAACLAw/K20t1tbcaMwyDtH_FjQZZ9Vehp8jIxuzACLcBGAs/s1600/fbhc2018r1top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="415" data-original-width="976" height="270" src="https://2.bp.blogspot.com/-NXmNY_XnxOc/W9dIki3r7jI/AAAAAAACLAw/K20t1tbcaMwyDtH_FjQZZ9Vehp8jIxuzACLcBGAs/s640/fbhc2018r1top5.png" width="640" /></a></div>Facebook Hacker Cup 2018 Round 1 took place over the weekend of that week (<a href="https://www.facebook.com/hackercup/problem/180494849326631/">problems</a>, <a href="https://www.facebook.com/hackercup/scoreboard/1825345887684301/?filter=everyone">results</a>, top 5 on the left, <a href="https://www.facebook.com/notes/facebook-hacker-cup/hacker-cup-2018-round-1-solutions/2267977239884831/">analysis</a>). Being fast was not a requirement this time, as the penalty time did not factor into advancement, but of course a competition is always a competition :) Congratulations to Kevin (are you ksun48?..) on the win!<br /><br /><div class="separator" style="clear: both; text-align: center;"></div><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-XI3YupU-Uw0/W9de9aJ7FCI/AAAAAAACLBo/SOnrytWTYBQJk6YJbjNQ-eOS3Tc7UHv9wCLcBGAs/s1600/IMG_20180715_201815_horizon.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1200" data-original-width="1600" height="480" src="https://2.bp.blogspot.com/-XI3YupU-Uw0/W9de9aJ7FCI/AAAAAAACLBo/SOnrytWTYBQJk6YJbjNQ-eOS3Tc7UHv9wCLcBGAs/s640/IMG_20180715_201815_horizon.jpg" width="640" /></a></div>In <a href="https://petr-mitrichev.blogspot.com/2018/09/a-skyglow-week.html">my previous summary</a>, I have mentioned a very nice AtCoder problem: two players play a game on an array of integers <i>a<sub>i</sub></i> with at most 300000 elements. The players make alternating turns, and on each turn a player takes a number from the array that is not previously taken. Moreover, when possible, a player must take a number adjacent to a number taken by the other player on the last turn. When taking such adjacent number is not possible (on first turn, or after a player has taken a number which has both neighbors either taken or nonexistent), any number can be taken. The game ends when all numbers have been taken, and each player tries to maximize the sum of the numbers they take. Which sum will each player get if both play optimally?<br /><br />Let's color all numbers with alternating colors, first one is red, second one is blue, third one is red, and so on. First, suppose the total amount of numbers is even, in other words the last number is blue. The first player has a few options:<br /><ul style="text-align: left;"><li>Take the first number. Then the rest of the moves is uniquely determined, they will take all numbers from first to last, the first player taking all red numbers, and the second player taking all blue numbers.</li><li>Take the last number. In this case everything is determined as well, but the first player gets all blue numbers, and the second player gets all red numbers.</li><li>Take a number in the middle. In this case the second player has choices as well, so let's study this case more carefully.</li></ul>Suppose the first player starts by picking a red number that is not the first number. The second player has two choices now: go left or right. If they go left, they will collect all blue numbers to the left, and the first player will collect all red numbers. Since the first number is red, the first player will be the last to move in this chain, and the second player will be able to pick any number. First key observation is that they can then take the last number, and thus collect all remaining blue numbers. So if the first player picks a red number, the second player can always take all blue numbers.<br /><br />Similarly, if the first player starts by picking a blue number, the second player can take all red numbers. So the second player can always guarantee at <i>least</i> the minimum of the two sums: all red numbers or all blue numbers. However, the first player can force the second player to get at <i>most</i> that minimum (by taking the first or the last number). Hence with optimal play the second player will get <i>exactly</i> that minimum (and thus the first player will get the maximum of the two sums).<br /><br />Note how we didn't have to explore all possibilities here — for example we didn't consider the case where the first player starts with a red number and the second player moves to the right. We don't need to: by finding an upper bound and a lower bound for the second player's score that match, we have proven that other options will not change the answer. This observation will also be key to solving the harder case, where the overall amount of numbers is odd.<br /><br />When the overall amount of numbers is odd, both first and last numbers are red, and the first player can still take all red numbers by taking the first number. However, there's no way for the first player to do the opposite and take all blue numbers. Let's again consider the other options the first player has:<br /><ul style="text-align: left;"><li>Take a red number that is not the first or last. Then the second player can still collect all blue numbers as in the even case, and since the first player can force the second player to take all blue numbers, we have matching upper and lower bounds again, and we don't need to investigate other second player's strategies in this branch.</li><li>Take a blue number. In this case the second player chooses a side, and takes all red numbers on that side, and then the first player is again first to play on the other (remaining) side, which once again has an odd amount of numbers.</li></ul>The first player can continue picking blue numbers when they have a choice for some time, until they decide to pick a red number in some remaining segment. Then the second player will have gotten all red numbers outside this remaining segment, and all blue numbers inside this segment.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-5HWfEa67_VA/W9dZUvxQwlI/AAAAAAACLBI/KLnOyj4-C0EMOR_G-5T5xre8R15Ibj6ogCLcBGAs/s1600/IMG_20181029_115757%257E2.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" data-original-height="1600" data-original-width="1320" height="640" src="https://1.bp.blogspot.com/-5HWfEa67_VA/W9dZUvxQwlI/AAAAAAACLBI/KLnOyj4-C0EMOR_G-5T5xre8R15Ibj6ogCLcBGAs/s640/IMG_20181029_115757%257E2.jpg" width="528" /></a></div>Can the first player choose this segment arbitrarily? No, since the second player decides whether we go left or right every time the first player picks a blue number. In fact, we can imagine the optimal strategy for the first player like a decision tree: we start by picking a certain blue number. If the second player takes all red numbers to the left, we are left with the right part, and will pick a certain blue number there; if we have the left part, we will pick a certain blue number there, and so on. Ultimately, each branch ends with us (first player) picking all red numbers in the segment.<br /><br />Now we can notice that the decision tree structure actually does not matter much. The blue numbers used for branching in the decision tree split the other numbers into segments. In the end, the second player gets all blue numbers from one of those segments, and all red numbers from the rest. The first player can split all numbers into such segments arbitrarily, and the second player effectively gets to choose the segment it gets blue numbers from.<br /><br />Note that we did not find an arbitrary strategy for both players — we have shown that the <i>optimal</i> strategy for them must look like this. The only remaining question is: how should the first player split all numbers into segments?<br /><br />This is another cool side of the problem: after solving the "more mathematical" strategy part, the remaining "algorithmic" part is also interesting to solve! We have an array of numbers of odd length, with first, third, ... numbers colored red and the rest colored blue. We need to choose a set of blue numbers in such a way that minimizes the maximum of (sum of blue numbers minus sum of red numbers) over the segments between the chosen blue numbers.<br /><br />There's a straightforward quadratic dynamic programming solution which finds the optimal way to split each prefix of our array, and iterates over all possible positions of the last taken blue number in each prefix.<br /><br />In order to speed it up, we have to slow it down first. Let's add an outside binary search for the answer. Now instead of minimizing the maximum, we just need to check if there's a split such that on each segment the difference is below the threshold. This can still be done using a similar dynamic programming, for the overall runtime of O(<i>n</i><sup>2</sup>*log<i>n</i>).<br /><br />But now we can notice that in this simplified dynamic programming if position X of the last taken blue number is better than position Y for some prefix, it will be better for all bigger prefixes as well, since what happened before X/Y does not matter anymore (it just needs to be under the threshold), and the only thing that matters is the difference between blue and red numbers after X/Y. Whichever is smaller once will keep being smaller, since we add the same new numbers to both. So instead of trying all possible positions for the last taken blue number, we can try just two possibilities: the best position for the previous prefix, or just the previous blue number (which was not considered for the previous prefix because it was not there). This makes the solution run in overall O(<i>n</i>*log<i>n</i>) time.<br /><br />Here is my entire solution from the contest:<br /><br /><pre style="background-color: white; font-family: "Courier New"; font-size: 7.2pt;"><span style="color: navy; font-weight: bold;">int </span>n = in.nextInt();<br /><span style="color: navy; font-weight: bold;">int</span>[] a = <span style="color: navy; font-weight: bold;">new int</span>[n];<br /><span style="color: navy; font-weight: bold;">for </span>(<span style="color: navy; font-weight: bold;">int </span>i = <span style="color: blue;">0</span>; i < n; ++i) a[i] = in.nextInt();<br /><span style="color: navy; font-weight: bold;">int </span>s1 = <span style="color: blue;">0</span>;<br /><span style="color: navy; font-weight: bold;">int </span>s2 = <span style="color: blue;">0</span>;<br /><span style="color: navy; font-weight: bold;">for </span>(<span style="color: navy; font-weight: bold;">int </span>i = <span style="color: blue;">0</span>; i < n; ++i) {<br /> <span style="color: navy; font-weight: bold;">if </span>(i % <span style="color: blue;">2 </span>== <span style="color: blue;">0</span>)<br /> s1 += a[i];<br /> <span style="color: navy; font-weight: bold;">else</span><br /> s2 += a[i];<br />}<br /><span style="color: navy; font-weight: bold;">if </span>(n % <span style="color: blue;">2 </span>== <span style="color: blue;">0</span>) {<br /> out.println(Math.<span style="font-style: italic;">max</span>(s1, s2) + <span style="color: green; font-weight: bold;">" " </span>+ Math.<span style="font-style: italic;">min</span>(s1, s2));<br /> <span style="color: navy; font-weight: bold;">return</span>;<br />}<br /><span style="color: navy; font-weight: bold;">int </span>left = s1 - s2;<br /><span style="color: navy; font-weight: bold;">int </span>right = s1 + s2 + <span style="color: blue;">1</span>;<br />outer: <span style="color: navy; font-weight: bold;">while </span>(right - left > <span style="color: blue;">1</span>) {<br /> <span style="color: navy; font-weight: bold;">int </span>middle = (left + right) / <span style="color: blue;">2</span>;<br /> <span style="color: navy; font-weight: bold;">long </span>bestSoFar = s1 - s2;<br /> <span style="color: navy; font-weight: bold;">int </span>r1 = s1;<br /> <span style="color: navy; font-weight: bold;">int </span>r2 = s2;<br /> <span style="color: navy; font-weight: bold;">for </span>(<span style="color: navy; font-weight: bold;">int </span>i = <span style="color: blue;">1</span>; i <= n; i += <span style="color: blue;">2</span>) {<br /> r1 -= a[i - <span style="color: blue;">1</span>];<br /> <span style="color: navy; font-weight: bold;">long </span>cost = bestSoFar - (r1 - r2);<br /> <span style="color: navy; font-weight: bold;">if </span>(i < n) r2 -= a[i];<br /> <span style="color: navy; font-weight: bold;">if </span>(cost >= middle) {<br /> <span style="color: navy; font-weight: bold;">if </span>(i == n) {<br /> left = middle;<br /> <span style="color: navy; font-weight: bold;">continue </span>outer;<br /> } <span style="color: navy; font-weight: bold;">else </span>{<br /> bestSoFar = Math.<span style="font-style: italic;">max</span>(bestSoFar, r1 - r2);<br /> }<br /> }<br /> }<br /> right = middle;<br />}<br />out.println((s2 + left) + <span style="color: green; font-weight: bold;">" " </span>+ (s1 - left));</pre><br />Thanks for reading, and check back for more!<br /><br /></div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/zhnty1NgpVg" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2018/10/a-decision-tree-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-53457026624621132722018-09-02T23:20:00.001+03:002018-09-02T23:20:36.412+03:00A Skyglow week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-TUuqbY_5IvQ/W4xCQtBNgrI/AAAAAAACJck/gsPESFLFNsczKDREpzmbgzvCvkyMGFbNgCLcBGAs/s1600/cf497top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="274" data-original-width="1103" height="158" src="https://4.bp.blogspot.com/-TUuqbY_5IvQ/W4xCQtBNgrI/AAAAAAACJck/gsPESFLFNsczKDREpzmbgzvCvkyMGFbNgCLcBGAs/s640/cf497top5.png" width="640" /></a></div>Codeforces Round 497 took place during the Jul 9 - Jul 15 week (<a href="http://codeforces.com/contest/1007">problems</a>, <a href="http://codeforces.com/contest/1007/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/60572">analysis</a>). The last 3 problems were, shall we say, more challenging than usual: only 9 accepted solutions for C, 3 for D, and 0 for E. Yosupo was one of those 12 people, and he solved the right set of problems in the right order to claim the first place. Congratulations!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-KQBW5oxkYzY/W4xDuNVmyjI/AAAAAAACJcw/-O6AqCKFSGk47ur5DgSCrkBH265KQ4-jACLcBGAs/s1600/agc026top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="448" data-original-width="1178" height="242" src="https://3.bp.blogspot.com/-KQBW5oxkYzY/W4xDuNVmyjI/AAAAAAACJcw/-O6AqCKFSGk47ur5DgSCrkBH265KQ4-jACLcBGAs/s640/agc026top5.png" width="640" /></a></div>Just a day later, AtCoder held its Grand Contest 026 (<a href="https://agc026.contest.atcoder.jp/assignments">problems</a>, <a href="https://agc026.contest.atcoder.jp/standings#page_1">results</a>, top 5 on the left, <a href="https://img.atcoder.jp/agc026/editorial.pdf">analysis</a>). yutaka1999 was unbeatable on the day, finishing all problems more than half an hour before anybody else. Congratulations on the dominant win!<br /><br />I found the last problem very nice: two players play a game on an array of integers <i>a<sub>i</sub></i> with at most 300000 elements. The players make alternating turns, and on each turn a player takes a number from the array that is not previously taken. Moreover, when possible, a player must take a number adjacent to a number taken by the other player on the last turn. When taking such adjacent number is not possible (on first turn, or after a player has taken a number which has both neighbors either taken or nonexistent), any number can be taken. The game ends when all numbers have been taken, and each player tries to maximize the sum of the numbers they take. Which sum will each player get if both play optimally?<br /><br />Thanks for reading, and check back for the solution!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/PmpniEa3nV4" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2018/09/a-skyglow-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-66431923755265004122018-09-02T13:57:00.000+03:002018-09-02T13:57:18.098+03:00A week without centroids<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-blofOkYAgFc/W4uyUaSbmlI/AAAAAAACJcM/ITTV1Bp3FLoMspUnTUHEP0v6OtR6XjKsACLcBGAs/s1600/tco18r3atop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="98" data-original-width="637" src="https://1.bp.blogspot.com/-blofOkYAgFc/W4uyUaSbmlI/AAAAAAACJcM/ITTV1Bp3FLoMspUnTUHEP0v6OtR6XjKsACLcBGAs/s1600/tco18r3atop5.png" /></a></div>The Jul 2 - Jul 8 week upped the stakes in the TopCoder Open 2018 race: only the top 50 would advance from Round 3A on Saturday (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=17198">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17198&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17199&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">parallel round results</a>, <a href="https://www.topcoder.com/blog/tco18-algorithm-round-3a-editorials/">analysis</a>). With <a href="https://community.topcoder.com/stat?c=problem_statement&pm=14909&rd=17198">the hard problem</a> having a much simpler solution than the one the problemsetters have anticipated, the scores were a lot higher than usual, and seeing this simple solution quickly was the key to victory. Congratulations to Blue.Mary on the win!<br /><div><br /></div><div><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-6K4vxmTyEuQ/W4vBKGOR82I/AAAAAAACJcY/PKmlz6xzCPg7FRhhfvPm8WcI8R6Qw2D3wCLcBGAs/s1600/IMG_20180630_162219.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1200" data-original-width="1600" height="480" src="https://2.bp.blogspot.com/-6K4vxmTyEuQ/W4vBKGOR82I/AAAAAAACJcY/PKmlz6xzCPg7FRhhfvPm8WcI8R6Qw2D3wCLcBGAs/s640/IMG_20180630_162219.jpg" width="640" /></a></div>In <a href="https://petr-mitrichev.blogspot.com/2018/08/a-week-in-memory-of-leo.html">my previous summary</a>, I have mentioned a Codeforces problem: you are given a tree with <i>n</i><=2000 vertices. How many cycles of length 1, 2, ..., <i>k</i> (<i>k</i><=75) does it have, modulo 998244353? A tree does not have simple cycles, so we're interested in non-simple cycles of course. Two cycles that differ only by choosing the starting point and direction are still considered <i>different</i>.<br /><br />The general approach is somewhat on the surface: let's do dynamic programming that would count said cycles for each subtree. When we're processing the subtree rooted at some vertex <i>v</i>, each cycle either doesn't touch <i>v</i>, in which case it's a cycle in one of the smaller subtrees, or it does touch <i>v</i>, in which case it looks like <i>v</i>-><i>u</i> (some child of <i>v</i>)->some cycle passing through <i>u</i>-><i>u</i>-><i>v</i>->...<br /><br />In order to be able to count the cycles of each length passing through <i>v</i>, we need to know the number of cycles of each length passing through each of its children, so we need to compute two things in our dynamic programming for each subtree: the total number of cycles, and the number of cycles passing through the root of the subtree.<br /><br />This gives a rough overview of the solution, but the details of the dynamic programming transition are still unclear: how do we make sure we correctly count the cycles differing only by the starting point?<br /><br />Each cycle passing through <i>v</i> can decomposed into blocks between consecutive occurrences of v in the cycle. Each such block is obtained by taking a cycle passing through some child <i>u</i> of <i>v</i>, and adding a <i>v</i>-><i>u</i> edge in the beginning and a <i>u</i>-><i>v</i> edge in the end, so for a child cycle of length <i>x</i> the block has <i>x</i>+2 edges.<br /><br />Actually, to make the previous statement entirely correct in the world where cycles differing by the starting point are considered different, we need to adjust it a bit: replace "cycle passing through <i>v</i>" and "cycle passing through <i>u</i>" by "cycle starting and finishing in <i>v</i>" and "cycle starting and finishing in <i>u</i>". Then our dynamic programming checks out, and we can find the answer for <i>v</i> given the answers for all its children by first adding up the answers for children to obtain the number of blocks of each size, and then doing an inner knapsack-style dynamic programming that counts the ways to combine the blocks.<br /><br />However, since we have changed the definition of what we compute, we can no longer just add up those numbers to get the overall number of cycles in the tree. Here comes the most magic part of the solution in my opinion: in order to get the overall number of cycles in the subtree passing through <i>v</i> from the number of cycles that start and end in <i>v</i>, we need to just multiply that number by the size of the last block in the inner knapsack dynamic programming!<br /><br />Indeed, this way we count the ways to choose the starting point within the last block. Why must it be within the last block? Because the cases where the starting point is in another block will be counted when we consider a cyclical shift of the blocks. To look at this from another angle, any cycle passing through <i>v</i> can be transformed into a cycle starting and ending in <i>v</i> by cyclically shifting it so that the first occurrence of <i>v</i> becomes the beginning of the cycle, and the number of ways to get each cycle doing this is equal to the size of the last block.<br /><br />Here's the relevant part from my solution during the round:<br /><br /><pre style="background-color: white; font-family: "Courier New"; font-size: 9pt;"><span style="color: navy; font-weight: bold;">static class </span>Vertex {<br /> List<vertex> <span style="color: #660e7a; font-weight: bold;">adj </span>= <span style="color: navy; font-weight: bold;">new </span>ArrayList<>();<br /><br /> <span style="color: navy; font-weight: bold;">public </span>Description doit(Vertex skip, <span style="color: navy; font-weight: bold;">int </span>k) {<br /> Description res = <span style="color: navy; font-weight: bold;">new </span>Description();<br /> res.<span style="color: #660e7a; font-weight: bold;">overallCycles </span>= <span style="color: navy; font-weight: bold;">new long</span>[k + <span style="color: blue;">1</span>];<br /> res.<span style="color: #660e7a; font-weight: bold;">cyclesFromRoot </span>= <span style="color: navy; font-weight: bold;">new long</span>[k + <span style="color: blue;">1</span>];<br /> res.<span style="color: #660e7a; font-weight: bold;">cyclesFromRoot</span>[<span style="color: blue;">0</span>] = <span style="color: blue;">1</span>;<br /> res.<span style="color: #660e7a; font-weight: bold;">overallCycles</span>[<span style="color: blue;">0</span>] = <span style="color: blue;">1</span>;<br /> <span style="color: navy; font-weight: bold;">long</span>[] singleStep = <span style="color: navy; font-weight: bold;">new long</span>[k + <span style="color: blue;">1</span>];<br /> <span style="color: navy; font-weight: bold;">for </span>(Vertex child : <span style="color: #660e7a; font-weight: bold;">adj</span>) {<br /> <span style="color: navy; font-weight: bold;">if </span>(child == skip) <span style="color: navy; font-weight: bold;">continue</span>;<br /> Description desc = child.doit(<span style="color: navy; font-weight: bold;">this</span>, k);<br /> <span style="color: navy; font-weight: bold;">for </span>(<span style="color: navy; font-weight: bold;">int </span>i = <span style="color: blue;">0</span>; i <= k; ++i) {<br /> res.<span style="color: #660e7a; font-weight: bold;">overallCycles</span>[i] = (res.<span style="color: #660e7a; font-weight: bold;">overallCycles</span>[i] + desc.<span style="color: #660e7a; font-weight: bold;">overallCycles</span>[i]) % <span style="color: #660e7a; font-style: italic; font-weight: bold;">MODULO</span>;<br /> <span style="color: navy; font-weight: bold;">if </span>(i + <span style="color: blue;">2 </span><= k) singleStep[i + <span style="color: blue;">2</span>] = (singleStep[i + <span style="color: blue;">2</span>] + desc.<span style="color: #660e7a; font-weight: bold;">cyclesFromRoot</span>[i]) % <span style="color: #660e7a; font-style: italic; font-weight: bold;">MODULO</span>;<br /> }<br /> }<br /> <span style="color: navy; font-weight: bold;">for </span>(<span style="color: navy; font-weight: bold;">int </span>old = <span style="color: blue;">0</span>; old <= k; ++old) {<br /> <span style="color: navy; font-weight: bold;">long </span>w = res.<span style="color: #660e7a; font-weight: bold;">cyclesFromRoot</span>[old];<br /> <span style="color: navy; font-weight: bold;">for </span>(<span style="color: navy; font-weight: bold;">int </span>a = <span style="color: blue;">2</span>; old + a <= k; ++a) {<br /> res.<span style="color: #660e7a; font-weight: bold;">cyclesFromRoot</span>[old + a] = (res.<span style="color: #660e7a; font-weight: bold;">cyclesFromRoot</span>[old + a] + w * singleStep[a]) % <span style="color: #660e7a; font-style: italic; font-weight: bold;">MODULO</span>;<br /> res.<span style="color: #660e7a; font-weight: bold;">overallCycles</span>[old + a] = (res.<span style="color: #660e7a; font-weight: bold;">overallCycles</span>[old +a] + w * singleStep[a] % <span style="color: #660e7a; font-style: italic; font-weight: bold;">MODULO </span>* a) % <span style="color: #660e7a; font-style: italic; font-weight: bold;">MODULO</span>;<br /> }<br /> }<br /> <span style="color: navy; font-weight: bold;">return </span>res;<br /> }<br />}</vertex></pre></div><div><br />Thanks for reading, and check back for more!</div></div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/kLiwR9D4j7c" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com3http://petr-mitrichev.blogspot.com/2018/09/a-week-without-centroids.htmltag:blogger.com,1999:blog-1953325079793449971.post-88586645974995333992018-08-12T22:08:00.000+03:002018-08-12T22:08:00.869+03:00A week in memory of Leo<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-QV-WgGQf2qI/W3Bk2ZgSp8I/AAAAAAACIOw/Jf80LfOq4oEiDKtzoPb4VHEyuNTtaU6oQCLcBGAs/s1600/tco18r2ctop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="146" data-original-width="779" height="118" src="https://3.bp.blogspot.com/-QV-WgGQf2qI/W3Bk2ZgSp8I/AAAAAAACIOw/Jf80LfOq4oEiDKtzoPb4VHEyuNTtaU6oQCLcBGAs/s640/tco18r2ctop5.png" width="640" /></a></div>The Jun 25 - Jul 1 week presented the last of the last chances to progress in TopCoder Open 2018 with its Round 2C on Tuesday (<a href="https://community.topcoder.com/stat?c=round_overview&rd=17191">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17191&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17190&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">parallel round results with 2/3 shared problems</a>, <a href="https://www.topcoder.com/blog/single-round-match-735-editorials/">analysis</a>). This round was ran in honor of Leopoldo Taravilse, who has tragically passed away recently. It was really sad to hear this news, and I express my sincere sympathy to Leopoldo's family and friends.<br /><br />fruwajacybyk has squeezed out the first place through challenges from Min,lu and tozangezan who led after the coding phase. Well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-o-CV-3x9yQE/W3B66gEK3_I/AAAAAAACIPc/hlI8LA-eCdAMejjBS05zF4XjouXM2ry8ACLcBGAs/s1600/cf493top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="272" data-original-width="1103" height="156" src="https://3.bp.blogspot.com/-o-CV-3x9yQE/W3B66gEK3_I/AAAAAAACIPc/hlI8LA-eCdAMejjBS05zF4XjouXM2ry8ACLcBGAs/s640/cf493top5.png" width="640" /></a></div>Codeforces held its Round 493 on Sunday (<a href="http://codeforces.com/contest/997">problems</a>, <a href="http://codeforces.com/contest/997/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/60357">analysis</a>). fjzzq2002 dominated the proceedings, solving all problems with 20 minutes to spare while everybody else could manage at most four. Congratulations on the impressive performance!<br /><br /><a href="http://codeforces.com/contest/997/problem/D">Problem D</a>, after removing a somewhat artificial complication, boiled down to the following cute combinatorial puzzle: you are given a tree with <i>n</i><=2000 vertices. How many cycles of length 1, 2, ..., <i>k</i> (<i>k</i><=75) does it have, modulo 998244353? A tree does not have simple cycles, so we're interested in non-simple cycles of course. Two cycles that differ only by choosing the starting point and direction are still considered <i>different</i>.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-TA4mwuzB45Y/W3CFczR5V_I/AAAAAAACIQg/04EOuA16BXo9aN8EIHQsO2a9yxZAeqolQCLcBGAs/s1600/IMG_20180630_133323.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1043" data-original-width="1600" height="416" src="https://1.bp.blogspot.com/-TA4mwuzB45Y/W3CFczR5V_I/AAAAAAACIQg/04EOuA16BXo9aN8EIHQsO2a9yxZAeqolQCLcBGAs/s640/IMG_20180630_133323.jpg" width="640" /></a></div>In <a href="https://petr-mitrichev.blogspot.com/2018/07/a-too-simple-week.html">my previous summary</a>, I have mentioned another Codeforces problem: you are given a prime modulo <i>p</i> up to 10<sup>9</sup> and two numbers <i>u</i> and <i>v</i> between 0 and <i>p</i>-1. In one step, you can either add one modulo <i>p</i>, subtract one modulo <i>p</i>, or take inverse modulo <i>p</i>. You need to obtain <i>v</i> from <i>u</i> in at most 200 steps (the solution doesn't need to be the shortest).<br /><br />This problem allows many approaches, so I'd like to share a bit more how my thinking went. I've started to write down which numbers we can get in a few steps, like <i>u</i>+1 or 1/(<i>u</i>+1) or 1+1/(<i>u</i>+1)=(<i>u</i>+2)/(<i>u</i>+1). Then I've noticed that if we represent our current number as <i>x</i>/<i>y</i>, then the three operations we have are <i>x</i>-><i>x</i>-<i>y</i>, <i>x</i>-><i>x</i>+<i>y</i>, and swap(<i>x</i>,<i>y</i>). This has strongly resembled the Euclidean algorithm, which can go from (<i>x</i>,<i>y</i>) to (0,gcd(<i>x</i>,<i>y</i>)) using those operations. Now I had a sketch of the solution: we'll represent <i>u</i> as (<i>u*k</i> mod <i>p)</i>/<i>k</i>, then apply the Euclidean algorithm to go from <i>u</i> to 0. Now we do the same for <i>v</i>, and since all operations are reversible, we can now go from <i>u</i> to 0 to <i>v</i>.<br /><br />However, the Euclidean algorithm takes a small (logarithmic) number of steps only if we have the modulo operation available. With just subtraction, it can take a lot of steps - for example, if we pick <i>k</i>=1, then we'll start with <i>u</i>/1 and need <i>u</i> steps to get to 0 just subtracting 1 every time. So we need to choose <i>k</i> wisely so that the number of steps to get from <i>u</i> to 0 will not exceed 100.<br /><br />First I tried to find <i>k</i> so that (<i>u</i>*<i>k</i> mod <i>p</i>)/<i>k</i> is as close to the golden ratio as possible, as the golden ratio is the case where the Euclidean algorithm proceeds in the fastest way. However, this did not work as sometimes just being close is not enough, and on last steps we still start making too many subtractions. But then I've realized that I can just try random values of <i>k</i> until I find one that works, and this ended up working flawlessly.<br /><br />Thanks for reading, and check back for more!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/cCoXrxtMNuI" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com1http://petr-mitrichev.blogspot.com/2018/08/a-week-in-memory-of-leo.htmltag:blogger.com,1999:blog-1953325079793449971.post-61497570424214670972018-07-28T14:34:00.001+03:002018-07-28T14:34:39.190+03:00A too simple week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-TPvosme_DdQ/W1xBVbC1B7I/AAAAAAACGeM/pIYwBeuUKZwEI9t5IQm6aSu08iaJueRawCLcBGAs/s1600/cf492top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="357" data-original-width="1101" height="206" src="https://3.bp.blogspot.com/-TPvosme_DdQ/W1xBVbC1B7I/AAAAAAACGeM/pIYwBeuUKZwEI9t5IQm6aSu08iaJueRawCLcBGAs/s640/cf492top5.png" width="640" /></a></div><div class="separator" style="clear: both; text-align: center;"></div>The Jun 18 - Jun 24 week had Codeforces Round 492 (<a href="http://codeforces.com/contest/995">problems</a>, <a href="http://codeforces.com/contest/995/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/60217">analysis</a>). I've also included myself in the standings on the left to highlight the fact that OO0OOO00O0OOO0O00OOO0OO's performance was so amazing that he got all 6 problems accepted before I got any one of those :) Well done!<br /><br />Right after this round, Scott Wu and Andrew He streamed a post-contest discussion on twitch (<a href="http://codeforces.com/blog/entry/60176">CF post</a>). Unfortunately the recording is no longer available, but the concept is exciting and I've enjoyed listening to a part of it.<br /><br />The round had a few mathy problems, but I'd like to highlight <a href="http://codeforces.com/contest/995/problem/E">problem E</a> which had a more algorithmic flavor: you are given a prime modulo <i>p</i> up to 10<sup>9</sup> and two numbers <i>u</i> and <i>v</i> between 0 and <i>p</i>-1. In one step, you can either add one modulo <i>p</i>, subtract one modulo <i>p</i>, or take inverse modulo <i>p</i>. You need to obtain <i>v</i> from <i>u</i> in at most 200 steps (the solution doesn't need to be the shortest). Do you see a way?<br /><br />Thanks for reading, and check back for more!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/M0o-FI1jZ7o" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com2http://petr-mitrichev.blogspot.com/2018/07/a-too-simple-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-85360419176475541832018-07-25T22:04:00.003+03:002018-07-25T22:04:54.798+03:00A week without automorphisms<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-oAWn35cfQ0E/W1gU1nARLCI/AAAAAAACFrM/78qzoUXMXz45t0bKJ0RlKk_mm-XHQeXaACLcBGAs/s1600/tco18r2btop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="147" data-original-width="781" height="120" src="https://3.bp.blogspot.com/-oAWn35cfQ0E/W1gU1nARLCI/AAAAAAACFrM/78qzoUXMXz45t0bKJ0RlKk_mm-XHQeXaACLcBGAs/s640/tco18r2btop5.png" width="640" /></a></div>The Jun 11 - Jun 17 week was supposed to present the last chance to qualify for further TopCoder Open 2018 rounds in Round 2B (<a href="https://community.topcoder.com/stat?c=round_overview&rd=17181">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17181&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17182&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">parallel round results</a>, <a href="https://www.topcoder.com/blog/2018-tco-algorithm-round-2b-editorials/">analysis</a>). However, because of technical issues an extra Round 2C was added two weeks later. Those issues notwithstanding, congratulations to gs14004 on creating just enough cushion during the coding phase to withstand the challenge push from maroon_kuri, sky_love_high and FizzyDavid! sky_love_high in particular <a href="https://community.topcoder.com/stat?c=coder_room_stats&rd=17181&rm=331354&cr=23040298">actually had</a> 1262.53 points after four minutes of the challenge phase, which would be enough for the first place.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-WG3K4qcy0Dw/W1gYdD291fI/AAAAAAACFrY/z2o6bPEZJv0xnW-_ydk_jD9kBApBgBemgCLcBGAs/s1600/cf488top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="272" data-original-width="1098" height="158" src="https://2.bp.blogspot.com/-WG3K4qcy0Dw/W1gYdD291fI/AAAAAAACFrY/z2o6bPEZJv0xnW-_ydk_jD9kBApBgBemgCLcBGAs/s640/cf488top5.png" width="640" /></a></div>Codeforces had its own share of issues with Round 488 on Saturday (<a href="http://codeforces.com/contest/993">problems</a>, <a href="http://codeforces.com/contest/993/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/60047">analysis</a>), this time not technical but with an incorrect reference solution for the hardest problem. It turned out that the test data was luckily correct anyway, so this ended up being <a href="http://codeforces.com/blog/entry/60047?#comment-437914">a somewhat theoretical discussion</a> that did not affect the round. Congratulations to Um_nik and Errichto on solving all problems!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-2QZGqEiBV2c/W1jJq0cc05I/AAAAAAACFyA/1D8LtuFtVYkBpW8zxlCN0TTZH5e0nM5YACLcBGAs/s1600/IMG_20180624_134905.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1200" data-original-width="1600" height="480" src="https://1.bp.blogspot.com/-2QZGqEiBV2c/W1jJq0cc05I/AAAAAAACFyA/1D8LtuFtVYkBpW8zxlCN0TTZH5e0nM5YACLcBGAs/s640/IMG_20180624_134905.jpg" width="640" /></a></div>In <a href="https://petr-mitrichev.blogspot.com/2018/07/an-obtuse-week.html">my previous summary</a>, I have mentioned <a href="https://codejam.withgoogle.com/2018/challenges/0000000000007707/dashboard/000000000004ba29">an exciting Code Jam problem</a>. You are given a number <i>n</i> between 10 and 50, and need to print a connected simple undirected graph with <i>n</i> vertices, and each vertex having degree exactly 4. The interactor will then randomly permute the vertices of your graph and give it back to you, and you need to then restore the permutation that was used. In other words, you need to find such graph without automorphisms, and be able to identify its vertices after they're shuffled.<br /><br />This is another example where there are two main ways: either solve it "on paper", or try various random-looking things at the computer until one works. Since there are only 41 possible inputs, it's quite easy to verify if an approach works or not.<br /><br />It turns out that in this problem even the expected solution went the random way. First, we have to come up with a way we'll use to identify the vertices. Then, we'll try random connected graphs with all degrees equal to 4 until we can uniquely identify all vertices in one. Of course, this last step also requires some way of generating such graphs.<br /><br />As a way to identify the vertices, we can use an iterative approach: initially all vertices start with the same label. Then we compute some function for all vertices that depends on the existing labels and the structure of the graph, but does not change when we permute the vertices. In case the values of the function for some vertices is different, we can update their labels to be different, and repeat the process. Eventually we need for all labels to become different.<br /><br />The function we compute can't just depend on the neighbors of the node: since every node has exactly 4 neighbors, and initially they all have the same values, we will never get different function values. However, we can look further and for example check how many of those 4 neighbors are connected to each other, or what set of labels we have at distance 2,3,... from the vertex, and then one of those ideas will be enough to find a solution for all 41 possible testcases (see <a href="https://codejam.withgoogle.com/2018/challenges/0000000000007707/analysis/000000000004ba29">the official analysis</a> for more details).<br /><br />Finally, in order to quickly generate such graphs, we can also use various approaches. I find the following one the most logical: start with any such graph, and then repeatedly apply random local modifications that don't change the degrees of the vertices (again, check out <a href="https://codejam.withgoogle.com/2018/challenges/0000000000007707/analysis/000000000004ba29">the official analysis</a> for more details).<br /><br />I have also enjoyed the way this problem used the interactive problem paradigm to encode the "challenge-response" setup that is not usually seen in programming contests.<br /><br />Thanks for reading, and check back for more!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/XnwMSwN9Rvk" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com2http://petr-mitrichev.blogspot.com/2018/07/a-week-without-automorphisms.htmltag:blogger.com,1999:blog-1953325079793449971.post-78896178304591822812018-07-24T19:25:00.002+03:002018-07-24T19:25:57.940+03:00An obtuse week<div dir="ltr" style="text-align: left;" trbidi="on">The Jun 4 - Jun 10 week was the week of the Google Code Jam: the onsite advancers were determined both in the normal and in the distributed competition.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-tmUW_nDHc2c/W1dEkGJQ9JI/AAAAAAACFpU/AXB7SYvuoBAzO21_QaAotd5x6FxojF7vQCLcBGAs/s1600/gcj18r3top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="347" data-original-width="1270" height="174" src="https://1.bp.blogspot.com/-tmUW_nDHc2c/W1dEkGJQ9JI/AAAAAAACFpU/AXB7SYvuoBAzO21_QaAotd5x6FxojF7vQCLcBGAs/s640/gcj18r3top5.png" width="640" /></a></div>First off, the Google Code Jam 2018 Round 3 took place on Saturday (<a href="https://codejam.withgoogle.com/2018/challenges/0000000000007707/dashboard">problems</a>, <a href="https://codejam.withgoogle.com/2018/challenges/0000000000007707/scoreboard">results</a>, top 5 on the left, <a href="https://codejam.withgoogle.com/2018/challenges/0000000000007707/analysis">analysis</a>). Somewhat surprisingly, none of the full scores stood during the system testing. Errichto.rekt and ifsmirnov lost the least points at that stage :) Congratulations!<br /><br />I found the problem <a href="https://codejam.withgoogle.com/2018/challenges/0000000000007707/dashboard/000000000004ba29">Name-Preserving Network</a> really exciting. You are given a number <i>n</i> between 10 and 50, and need to print a connected simple undirected graph with <i>n</i> vertices, and each vertex having degree exactly 4. The interactor will then randomly permute the vertices of your graph and give it back to you, and you need to then restore the permutation that was used. In other words, you need to find such graph without automorphisms, and be able to identify its vertices after they're shuffled. How would you approach this one?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-8YhF-fvUZ5w/W1dGYZGnAvI/AAAAAAACFpg/n3dE4GvukfQrlmpzXMVrYuULzm2Z15bVQCLcBGAs/s1600/dcj18onlinetop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="309" data-original-width="1301" height="152" src="https://3.bp.blogspot.com/-8YhF-fvUZ5w/W1dGYZGnAvI/AAAAAAACFpg/n3dE4GvukfQrlmpzXMVrYuULzm2Z15bVQCLcBGAs/s640/dcj18onlinetop5.png" width="640" /></a></div>The Distributed Code Jam 2018 Online Round followed a day later (<a href="https://code.google.com/codejam/contest/9254486/dashboard#s=p1">problems</a>, <a href="https://code.google.com/codejam/contest/9254486/scoreboard">results</a>, top 5 on the left, <a href="https://code.google.com/codejam/contest/9254486/dashboard#s=a">analysis</a>). Errichto.rekt was at the top for the second day in a row, thanks to being one of only two solvers of the hardest problem E. Well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/--fl-UkBdQ04/W1dSwlhp5rI/AAAAAAACFp0/nJVmp353SLcT2UMBUwnSgrMZOReUQKhQwCLcBGAs/s1600/IMG_20180604_111106.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="963" data-original-width="1600" height="384" src="https://1.bp.blogspot.com/--fl-UkBdQ04/W1dSwlhp5rI/AAAAAAACFp0/nJVmp353SLcT2UMBUwnSgrMZOReUQKhQwCLcBGAs/s640/IMG_20180604_111106.jpg" width="640" /></a></div>In <a href="https://petr-mitrichev.blogspot.com/2018/07/an-extra-log-week.html">my previous summary</a>, I have mentioned an unusual TopCoder problem: You are given 3<i>n</i> sticks with lengths <i>a</i>, <i>a</i>+1, ..., <i>a</i>+3<i>n</i>-1. You need to find any way to split them into <i>n</i> triples in such a way that each triple forms a non-degenerate obtuse triangle, or report that there isn't one. <i>n</i> is up to 500, <i>a</i> is an integer between 1 and 10.<br /><br />There are a few principal approaches to this kind of problem (did I already enumerate those on the blog? Please share a link, and also please add ones that I missed):<br /><br /><ul style="text-align: left;"><li>Just solve the problem on paper, in other words come up with a direct explicit construction.</li><li>Solve the problem on paper in two steps a-la induction: come up with a way to solve the problem for small instances of the problem, and also come up with a way to change a solution for <i>n</i> to a solution for <i>n</i>+5 (for some value of 5).</li><li>Only do the second inductive part on paper, and use brute force to find solutions to small instances.</li><li>Also replace the inductive part with something less formal: do some kind of greedy for most of the solution, and use brute force when the remaining problem is small enough.</li></ul><div>The official analysis suggests to use the third approach, while I went with the last one since it requires the least amount of thinking :)</div><div><br /></div><div>I like to code such solutions as a brute force that runs even for large values of <i>n</i>, with the greedy part being implicit by the order the brute force tries the possibilities: since for most of the decisions, we will never have time to come back to them, the first decision we try in the brute force is effectively the greedy decision. This way I don't have to explicitly choose the boundary between the greedy and the brute force, and thus can try different ideas faster.</div><div><br /></div><div>You can take a look at <a href="http://community.topcoder.com/stat?c=problem_solution&rm=331308&rd=17166&pm=14886&cr=10574855">my solution from the round</a> for more details, but in short, the ordering that worked was: as the first attempt, try to pair the smallest remaining stick with the 1/3-rd and 2/3-rd ones in sorted order, and then go from those in both directions.</div><div><br /></div><div>Thanks for reading, and check back for more!</div></div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/XwnP_sIlKk8" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com4http://petr-mitrichev.blogspot.com/2018/07/an-obtuse-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-20319414795958052022018-07-22T14:36:00.001+03:002018-08-12T22:12:15.312+03:00An extra log week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-6sdOTMU7w90/W1Rh-gqLq_I/AAAAAAACFiY/NNlanqpTdEA3Akr2xtV64QMRjolQJdplgCLcBGAs/s1600/cf485to5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="311" data-original-width="1216" height="163" src="https://1.bp.blogspot.com/-6sdOTMU7w90/W1Rh-gqLq_I/AAAAAAACFiY/NNlanqpTdEA3Akr2xtV64QMRjolQJdplgCLcBGAs/s640/cf485to5.png" width="640" /></a></div>Codeforces Round 485 got the May 28 - Jun 3 week going (<a href="http://codeforces.com/contest/986">problems</a>, <a href="http://codeforces.com/contest/986/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/59758">analysis</a>). OO0OOO00O0OOO0O00OOO0OO has tried an unusual problem solving order, but it didn't really help as tourist was faster overall and got the well-deserved first place. Congratulations!<br /><br />The <a href="http://codeforces.com/blog/entry/59720">round thread</a> is also notable for discussions about modern problemsetting practices (search for Um_nik's replies and surrounding comments).<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-9XVj2GLDjIo/W1Rn47YK_QI/AAAAAAACFik/amEyRRKo0wkSSZa4F_j5L8PwXq_9YOCkACLcBGAs/s1600/tco18r2top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="149" data-original-width="783" height="120" src="https://1.bp.blogspot.com/-9XVj2GLDjIo/W1Rn47YK_QI/AAAAAAACFik/amEyRRKo0wkSSZa4F_j5L8PwXq_9YOCkACLcBGAs/s640/tco18r2top5.png" width="640" /></a></div>On Saturday, TopCoder Open 2018 Round 2A saw the top-rated participants enter the competition (<a href="http://community.topcoder.com/stat?c=round_overview&rd=17166">problems</a>, <a href="http://community.topcoder.com/stat?c=round_stats_sorted&rd=17166&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="http://community.topcoder.com/stat?c=round_stats_sorted&rd=17167&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">parallel round results</a>, <a href="https://www.topcoder.com/blog/2018-tco-algorithm-round-2a-editorials/">analysis</a>, <a href="https://youtu.be/8-cGp3QGTMs">my screencast</a>). A lot of solutions failed challenges and system test in this round, and after the dust has settled it turned out that bmerry both had the highest coding phase score, and has protected the lead very well by adding 100 challenge points. Well done!<br /><br /><a href="http://community.topcoder.com/stat?c=problem_statement&pm=14886&rd=17166">The hardest problem</a> in this round allowed one to get quite creative. You are given 3<i>n</i> sticks with lengths <i>a</i>, <i>a</i>+1, ..., <i>a</i>+3<i>n</i>-1. You need to find any way to split them into <i>n</i> triples in such a way that each triple forms a non-degenerate obtuse triangle, or report that there isn't one. <i>n</i> is up to 500, <i>a</i> is an integer between 1 and 10.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-BUG7MBffTd0/W1RrE5gOE_I/AAAAAAACFi0/Tb0gYvuT5I08RIOwsSAwGvXWX_5bx_OLACLcBGAs/s1600/agc025to5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="447" data-original-width="1175" height="242" src="https://3.bp.blogspot.com/-BUG7MBffTd0/W1RrE5gOE_I/AAAAAAACFi0/Tb0gYvuT5I08RIOwsSAwGvXWX_5bx_OLACLcBGAs/s640/agc025to5.png" width="640" /></a></div>Finally, AtCoder Grand Contest 025 wrapped up the week on Sunday (<a href="https://agc025.contest.atcoder.jp/assignments">problems</a>, <a href="https://agc025.contest.atcoder.jp/standings">results</a>, top 5 on the left, <a href="https://img.atcoder.jp/agc025/editorial.pdf">analysis</a>). Only Stonefeang was able to solve all problems, and thus got a clear first place. Contestants behind him solved quite varied subsets of problems in an attempt to score most points in the limited time available, but it did not really matter in the end. Congratulations to Stonefeang!<br /><br />Thanks for reading, and check back for more.</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/SkWbTxStwbw" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2018/07/an-extra-log-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-44145127724487542842018-07-20T23:45:00.002+03:002018-07-20T23:45:40.331+03:00A deterministic week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-ZoN58Jxc1v8/W1ITs0bHhDI/AAAAAAACFOU/DOuEYH6uJsAE9dUEEgKAsDTbjmJe9UxBgCLcBGAs/s1600/avito2018top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="314" data-original-width="1280" height="156" src="https://4.bp.blogspot.com/-ZoN58Jxc1v8/W1ITs0bHhDI/AAAAAAACFOU/DOuEYH6uJsAE9dUEEgKAsDTbjmJe9UxBgCLcBGAs/s640/avito2018top5.png" width="640" /></a></div>Codeforces hosted the Avito Code Challenge 2018 during the May 21 - May 27 week (<a href="http://codeforces.com/contest/981">problems</a>, <a href="http://codeforces.com/contest/981/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/59713">analysis</a>). While OO0OOO00O0OOO0O00OOO0OO and tourist were very close during most of the contest, tourist was much faster with solving the hardest problem, and thus won with a comfortable margin in the end — well done!<br /><div class="separator" style="clear: both; text-align: center;"></div><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-jytO3h4Ti4Y/W1JJEeB-DsI/AAAAAAACFPY/bHRZVwX-fmIC9UPy1-Rzt7w10LryjQDuACLcBGAs/s1600/IMG_20180511_194357-EFFECTS.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1042" data-original-width="1600" height="416" src="https://3.bp.blogspot.com/-jytO3h4Ti4Y/W1JJEeB-DsI/AAAAAAACFPY/bHRZVwX-fmIC9UPy1-Rzt7w10LryjQDuACLcBGAs/s640/IMG_20180511_194357-EFFECTS.jpg" width="640" /></a></div>In <a href="https://petr-mitrichev.blogspot.com/2018/07/a-penalty-week.html">my previous summary</a>, I have mentioned <a href="https://contest.yandex.ru/algorithm2018/contest/8254/problems/E/">an interactive Yandex problem</a>, which required one to locate the number <i>n</i> in a permutation of integers between 1 and <i>n</i>. You are given just the number <i>n</i> and can send queries to learn the permutation. Each query is a number <i>k</i> between 1 and <i>n</i>, and means "increase the number in <i>k</i>-th position in the array by 1". After performing the requested action, the system tells you the number of distinct values in the array (which initially contains the permutation), and you can send the next query which will be applied to the new array (which is not a permutation anymore). You must tell the original location of the number <i>n</i> after at most 50<i>n</i> queries.<br /><br />The <a href="https://codeforces.com/blog/entry/59730">official analysis</a> mentions a nice randomized solution, but there's actually a similar deterministic one as well. Let's increment all numbers by one in some order, for example from left to right, and for each number record the delta between the number of distinct elements after and before incrementing it. Two things happen for the number <i>x</i>:<br /><br />1) If the number <i>x</i>-1 does not exist or was not yet incremented, then we lose <i>x</i> from the set of distinct numbers, this contributes -1 to the delta.<br /><br />2) If the number <i>x</i>+1 does not exist or was already incremented, then we add <i>x</i>+1 to the set of distinct numbers, this contributes +1 to the delta.<br /><br />If both of those things happen, the contributions add up, and the delta is 0.<br /><br />Now let's once again increment all numbers one by one, but in reverse order to the first pass, and add the delta for each position to the delta we already remember for it. The "was already incremented" conditions will flip since we iterate in reverse order now, and thus for all numbers except 1 and <i>n</i> we will get exactly one -1 and exactly one +1, so the total delta will be 0.<br /><br />For the number <i>n</i>, however, the second condition always holds, so we'll get one -1 and two +1's, for the total of +1. Similarly, for the number 1 we'll get the total of -1. This easily identifies the location of the number <i>n</i> after just 2<i>n</i> queries.<br /><br />Thanks for reading, and check back for more!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/fWABpm8yKcY" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2018/07/a-deterministic-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-36161056106161315912018-07-19T20:25:00.002+03:002018-07-19T20:25:35.875+03:00A penalty week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-6Bv9SkSfQkA/W1Bhn_lfrNI/AAAAAAACFJU/kcKMrQEWSrMuh3Ny-EHf-Xsp8cJ3ZqpEACLcBGAs/s1600/cf483top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="313" data-original-width="1209" height="164" src="https://3.bp.blogspot.com/-6Bv9SkSfQkA/W1Bhn_lfrNI/AAAAAAACFJU/kcKMrQEWSrMuh3Ny-EHf-Xsp8cJ3ZqpEACLcBGAs/s640/cf483top5.png" width="640" /></a></div>The competitive May 14 - May 20 week started with Codeforces Round 483 on Tuesday (<a href="http://codeforces.com/contest/983">problems</a>, <a href="http://codeforces.com/contest/983/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/59484">analysis</a>). Problem D turned out to be almost unsolvable, and skipping it was the key to victory. Congratulations to fateice on solving all remaining problems in just under an hour!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-NBPwupgHitA/W1CjI6S5Q6I/AAAAAAACFKQ/NWwxli3LNkoFUPXCcPWDLCVFhBAngR1-ACLcBGAs/s1600/srm734top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="148" data-original-width="774" height="122" src="https://3.bp.blogspot.com/-NBPwupgHitA/W1CjI6S5Q6I/AAAAAAACFKQ/NWwxli3LNkoFUPXCcPWDLCVFhBAngR1-ACLcBGAs/s640/srm734top5.png" width="640" /></a></div>TopCoder SRM 734 followed on Thursday (<a href="https://community.topcoder.com/stat?c=round_overview&rd=17158">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17158&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://www.topcoder.com/blog/single-round-match-734-editorials/">analysis</a>). The round has feature three relatively standard problems, in particular the last two problems should be good dynamic programming practice.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-rocMn9mfmVs/W1CppgYmjqI/AAAAAAACFK0/HboSqXDhwj4C33Ze7hlfQ0T8ZUqY2VoDACLcBGAs/s1600/gcj18r2top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="350" data-original-width="1294" height="172" src="https://4.bp.blogspot.com/-rocMn9mfmVs/W1CppgYmjqI/AAAAAAACFK0/HboSqXDhwj4C33Ze7hlfQ0T8ZUqY2VoDACLcBGAs/s640/gcj18r2top5.png" width="640" /></a></div>On Saturday Google Code Jam 2018 Round 2 narrowed the field to just 1000 competitors (<a href="https://codejam.withgoogle.com/2018/challenges/0000000000007706/dashboard">problems</a>, <a href="https://codejam.withgoogle.com/2018/challenges/0000000000007706/scoreboard">results</a>, top 5 on the left, <a href="https://codejam.withgoogle.com/2018/challenges/0000000000007706/analysis">analysis</a>). Getting into the top 1000 does not usually present a big challenge for the top competitors, so they can focus on competing for fun. This time Um_nik was the fastest to solve all problems, but he allowed one incorrect attempt and Gennady.Korotkevich claimed the first place. Congratulations to both!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-OEdDuNKRIOg/W1CqpLwC_xI/AAAAAAACFK8/blCCFNraH_I3mpc_zD36Q1NVLnEpnLJAwCLcBGAs/s1600/ya2018finaltop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="389" data-original-width="1099" height="226" src="https://2.bp.blogspot.com/-OEdDuNKRIOg/W1CqpLwC_xI/AAAAAAACFK8/blCCFNraH_I3mpc_zD36Q1NVLnEpnLJAwCLcBGAs/s640/ya2018finaltop5.png" width="640" /></a></div>Yandex.Algorithm 2018 Final Round took place in St Petersburg and online early on Sunday (<a href="https://contest.yandex.ru/algorithm2018/contest/8254/problems/">problems with Yandex login</a>, <a href="https://contest.yandex.ru/algorithm2018/contest/8254/standings/">results</a>, top 5 on the left, <a href="https://youtu.be/jFwQdvj87CA">my screencast</a>, <a href="https://codeforces.com/blog/entry/59730">analysis</a>). The top 2 did not change from the Code Jam round, although this time Gennady has actually left the door wide open by solving the first five problems a lot slower than Um_nik and accumulating some penalty time — Um_nik just needed to get the last problem accepted before the end of the contest, but it did not happen. Congratulations to Gennady on the victory!<br /><br />The easiest problem of the round, <a href="https://contest.yandex.ru/algorithm2018/contest/8254/problems/E/">Problem E</a>, required one to locate the number <i>n</i> in a permutation of integers between 1 and <i>n</i>. You are given just the number <i>n</i> and can send queries to learn the permutation. Each query is a number <i>k</i> between 1 and <i>n</i>, and means "increase the number in <i>k</i>-th position in the array by 1". After performing the requested action, the system tells you the number of distinct values in the array (which initially contains the permutation), and you can send the next query which will be applied to the new array (which is not a permutation anymore). You must tell the original location of the number <i>n</i> after at most 50<i>n</i> queries.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-tT2igFN2b3A/W1DE85jmO9I/AAAAAAACFLM/jClNN3rp0O0vv59h6LSpwTDkGMei5YOigCLcBGAs/s1600/agc024top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="445" data-original-width="1174" height="242" src="https://3.bp.blogspot.com/-tT2igFN2b3A/W1DE85jmO9I/AAAAAAACFLM/jClNN3rp0O0vv59h6LSpwTDkGMei5YOigCLcBGAs/s640/agc024top5.png" width="640" /></a></div>And finally, AtCoder Grand Contest 024 wrapped up the week (<a href="https://agc024.contest.atcoder.jp/assignments">problems</a>, <a href="https://agc024.contest.atcoder.jp/standings#page_1">results</a>, top 5 on the left, <a href="https://youtu.be/8WvLTM0pH98">my screencast</a>, <a href="https://img.atcoder.jp/agc024/editorial.pdf">analysis</a>). This time it was actually me who was the fastest to finish all problems, but I paid the price for the three incorrect attempts. Congratulations to Gennady on the victory!<br /><br />I found <a href="https://agc024.contest.atcoder.jp/tasks/agc024_f">problem F</a> in this round quite educational: you are given a set of strings of length <=20 (possibly all such strings — see the problem statement for the input format that makes it possible to read the input quickly) and a number <i>k</i>. You need to find the longest string that is a <i>subsequence</i> of at least <i>k</i> of the given strings. In case there are many, you need to find the lexicographically smallest one.<br /><br />Thanks for reading, and check back for more!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/5g5Wxbm1s_U" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com3http://petr-mitrichev.blogspot.com/2018/07/a-penalty-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-60298486847735488202018-05-26T21:03:00.002+03:002018-05-26T21:03:50.697+03:00An unpublished week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-143Ss0I7Vqk/WwmhVpYoiaI/AAAAAAACDPA/UcZPOFWy9_MP_CAZBDiKT1pJeCTSCoD2ACLcBGAs/s1600/IMG_20180420_173326.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="868" data-original-width="1600" height="346" src="https://3.bp.blogspot.com/-143Ss0I7Vqk/WwmhVpYoiaI/AAAAAAACDPA/UcZPOFWy9_MP_CAZBDiKT1pJeCTSCoD2ACLcBGAs/s640/IMG_20180420_173326.jpg" width="640" /></a></div>The May 7 - May 13 week was the time for the first regional event of TopCoder Open 2018 in Warsaw. The problems and results seem to be unavailable on the TopCoder website, but you can read the recap <a href="https://www.topcoder.com/blog/tco18-warsaw-regional-event-recap/">here</a>.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-bYU6XXkmjak/WwhHV8orCgI/AAAAAAACDM4/38Ke9DKd94EMdAEYZEEpXM5gz8jgDzjwgCLcBGAs/s1600/oc1718bashkortostantop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="360" data-original-width="1583" height="144" src="https://2.bp.blogspot.com/-bYU6XXkmjak/WwhHV8orCgI/AAAAAAACDM4/38Ke9DKd94EMdAEYZEEpXM5gz8jgDzjwgCLcBGAs/s640/oc1718bashkortostantop5.png" width="640" /></a></div>On Sunday of the same week the 2017-18 season of the Open Cup was wrapped up with the Grand Prix of Bashkortostan (<a href="https://official.contest.yandex.ru/opencupXVIII/contest/8217/standings/">results with Open Cup login</a>, top 5 on the left). The overall season standings are not yet available, but there's no doubt about the first place of team Past Glory. In this round they have reiterated how huge the gap between them and the rest of the field really is, solving all problems from first attempt in 2 hours and 24 minutes, and having almost half the penalty time of the second-placed team. Huge congratulations!<br /><br />Problem I in this round was relatively standard, and yet there was a lot of room for coming up with a solution that is easy to implement, as the constraints were relatively low. You are given the coordinates of the vertices of a convex polyhedron in three-dimensional space. You need to determine the horizontal plane that separates the polyhedron's volume 1:9. The number of vertices is at most 100. How would you implement this?<br /><br />Thanks for reading, and check back for more!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/OArKyUvE9d4" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2018/05/an-unpublished-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-88665604288830527252018-05-25T20:14:00.001+03:002018-05-25T20:14:35.959+03:00A prefix xor week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-5Bj3ZwMnHQI/WwfzuRN5YTI/AAAAAAACDKg/rBH9cqdMYXQksnbaicxJ1XglA2jnZKe4gCLcBGAs/s1600/tco18r1btop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="146" data-original-width="778" height="120" src="https://3.bp.blogspot.com/-5Bj3ZwMnHQI/WwfzuRN5YTI/AAAAAAACDKg/rBH9cqdMYXQksnbaicxJ1XglA2jnZKe4gCLcBGAs/s640/tco18r1btop5.png" width="640" /></a></div>The Apr 30 - May 6 week was about early qualification rounds for the major tournaments. TopCoder Open 2018 Round 1B took place on Thursday (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=17147">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17147&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17148&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">parallel round results</a>, <a href="https://www.topcoder.com/blog/2018-tco-algorithm-round-1b-editorials/">analysis</a>). The medium problem provided ample challenge opportunities, and Michael_Levin has capitalized on those and earned the top spot with quite some margin — congratulations!<br /><br />In the parallel round, kotamanegi was able to find even more challenges, and thus earned the top spot in <a href="http://community.topcoder.com/stat?&c=highest_totals&dn=1">the all-time high score list</a> — congratulations as well :)<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-SKN2Ot4zg-A/Wwf2r3C3AVI/AAAAAAACDKs/JUIBUEK53qMvpZ7OmBTGeCOKDVbIVC2tQCLcBGAs/s1600/gcj18r1ctop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="320" data-original-width="927" height="220" src="https://4.bp.blogspot.com/-SKN2Ot4zg-A/Wwf2r3C3AVI/AAAAAAACDKs/JUIBUEK53qMvpZ7OmBTGeCOKDVbIVC2tQCLcBGAs/s640/gcj18r1ctop5.png" width="640" /></a></div>Google Code Jam 2018 Round 1C followed on Saturday (<a href="https://codejam.withgoogle.com/2018/challenges/0000000000007765/dashboard">problems</a>, <a href="https://codejam.withgoogle.com/2018/challenges/0000000000007765/scoreboard">results</a>, top 5 on the left, <a href="https://codejam.withgoogle.com/2018/challenges/0000000000007765/analysis">analysis</a>). The somewhat unusual <a href="https://codejam.withgoogle.com/2018/challenges/0000000000007765/dashboard/000000000003e068">interactive second problem</a> did not delay Eryx much, as he finished the round in just over 35 minutes (8 seconds faster than austrin in 3rd place). Well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-nZPPhDyRZWg/WwgZVu7gAPI/AAAAAAACDLQ/Lnox1K0yhh4Rp1NF79XBLj7pcRO_JRLnQCLcBGAs/s1600/IMG_20180415_165839.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1200" data-original-width="1600" height="480" src="https://4.bp.blogspot.com/-nZPPhDyRZWg/WwgZVu7gAPI/AAAAAAACDLQ/Lnox1K0yhh4Rp1NF79XBLj7pcRO_JRLnQCLcBGAs/s640/IMG_20180415_165839.jpg" width="640" /></a></div>In <a href="https://petr-mitrichev.blogspot.ch/2018/05/a-uniform-combination-week.html">my previous summary</a>, I have mentioned a cute AtCoder problem: you are given a tree with 200000 vertices, each containing a number, either 0 or 1. We need to put all its vertices in some order in such a way that each vertex except the root appears to the right of its parent. We will then write out a sequence of 0s and 1s corresponding to numbers in the vertices in this order. What is the minimum possible number of inversions in this sequence? An inversion is a pair of positions such that the number in the left position is 1, and the number in the right position is 0.<br /><br />The key idea that is widely applicable in this type of problems is called the <i>exchange argument</i>. Suppose we have some way to put the vertices in order, which results in some sequences of 1s and 0s. Let's consider two consecutive blocks of numbers in the resulting sequence, for example one block contains <i>a</i> 1s and <i>b</i> 0s, and the following block contains <i>c</i> 1s and <i>d</i> 0s. What happens to the number of inversions if we swap those blocks? It will change by <i>cb</i>-<i>ad</i>. Thus in an optimal sequence for every pair of consecutive blocks that are swappable (with respect to the parent-child constraint) we must have <i>cb</i>-<i>ad</i>>=0, which we can rewrite as <i>c</i>/<i>d</i>-<i>a</i>/<i>b</i>>=0.<br /><br />Now suppose we have identified the optimal sequence for all children of some vertex, and want to find the optimal sequence for the vertex itself. The number for this vertex needs to go first, and then we need to interleave the sequences for the children somehow. In theory we could also reorder the optimal sequences for the children, but intuitively it is not necessary, and it will become clearer after we complete the solution.<br /><br />Interleaving the sequences for the children can be viewed as splitting each child sequence into blocks, and then interleaving those blocks. From the exchange argument above, we need to take the block with the lowest fraction of 1s every time (lowest value of <i>a</i>/<i>b</i>).<br /><br />There are many ways to split each child sequence into blocks, but we can notice that the first block must be at least the prefix <i>p</i> with the lowest fraction of 1s: in case we take a smaller prefix, the remaining part of <i>p</i> has an even lower fraction of 1s, and thus by the exchange argument above we'll be able to drag it to the beginning and improve the solution.<br /><br />By applying the same argument repeatedly, we arrive at the following solution: each child sequence is split into blocks by taking the prefix with the lowest fraction of 1s as the first block, then the prefix with the lowest fraction of 1s of the remaining sequence as the second block, and so on. It's not hard to see that the fractions of 1s in those blocks for one child sequence will be nondecreasing, so in order to interleave those blocks we just sort them by the fraction, and blocks within one sequence will keep the same order.<br /><br />It is however too slow to split each child sequence into blocks for every vertex, as potentially each sequence has a linear number of blocks, so the overall algorithm would be quadratic. However, since we interleave the blocks in nondecreasing order of fraction, we can notice that the sequence of blocks for each vertex is obtained by interleaving the sequences for the children — we don't need to re-split it. Then we prepend either a 0 or a 1 in the beginning. If it's a 0, we can simply make it a separate block and we'll still get a nondecreasing sequence. If it's a 1, it will "eat" a few following blocks until our sequence becomes nondecreasing.<br /><br />This leads to the following approach: for each vertex, we'll build a sequence of blocks, ordered by the fraction of 1s, stored as a balanced search tree or a priority queue. In order to build the sequence for a vertex, we need to merge the sequences from its children, and add a new block in the beginning corresponding to the value in the vertex, and then repeatedly merge that block with the next block while its fraction is higher. When merging, we apply another relatively standard trick and insert blocks from the smaller sequence into the larger sequence, which guarantees that each block would be inserted at most log(<i>n</i>) times, and thus overall running time would be O(<i>n</i>*log<sup>2</sup>(<i>n</i>)).<br /><br />I derive additional pleasure from the fact that while building this solution, we have essentially understood the mechanics of the problem in great detail: while initially we had a great deal of freedom in writing out the sequence, and it was not clear why we can even find the optimal sequence in polynomial time, now we realize that we just interleave blocks and merge them.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-XTtMVsVYkEM/WwhD9qpJ-7I/AAAAAAACDMo/yNlTBR7goMYze78-Ia05WSo6h34XsOhSQCLcBGAs/s1600/IMG_20180416_145445.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="747" data-original-width="1600" height="298" src="https://1.bp.blogspot.com/-XTtMVsVYkEM/WwhD9qpJ-7I/AAAAAAACDMo/yNlTBR7goMYze78-Ia05WSo6h34XsOhSQCLcBGAs/s640/IMG_20180416_145445.jpg" width="640" /></a></div>I have also mentioned a Codeforces problem: you are given 100000 numbers <i>a<sub>i</sub></i>, each up to 2<sup>60</sup>. You need to put them in such order that the xors of all prefixes of the resulting sequence form a strictly increasing sequence themselves.<br /><br />The solution to this problem is quite the opposite to the previous one: instead of building a detailed understanding, we come up with an argument that works somewhat magically. It is not hard to prove that the solution works, but it keeps looking unexpected and magical.<br /><br />Let's look at the highest bit set in at least one of <i>a<sub>i</sub></i>'s. Suppose it is set in some subset of numbers. Then the prefix xors will have 0 in this bit before the first such number, 1 in this bit after the first such number but before the second such number, 0 in this bit after the second such number, and so on. Since the resulting sequence must be non-decreasing, we must actually have exactly one such number. Let's start forming our resulting sequence by putting just this number there. Now we have two parts of the sequence, before this number and after it (including the number itself), which are somewhat independent: no matter which numbers go to the before part, its xor has 0 in the highest bit, and after xoring in our number the highest bit becomes 1, so we're guaranteed to have a strict increase on the boundary of the parts.<br /><br />Now let's look at the next highest bit set in at least one of the remaining <i>a<sub>i</sub></i>'s, and look at the numbers where this bit is set. Just as before, the prefix xors will have 0 in this bit before the first such number, 1 in this bit after the first such number but before the second such number, 0 in this bit after the second such number, and so on. The only difference is that the set of numbers with this bit set might include the number that we already have in the sequence. If this is the case, then even though our bit will change from 1 to 0, we'd still have an increasing sequence, since a higher bit will change from 0 to 1 at the same point. So in case the already placed number has 1 in our bit, we can add two numbers with our bit as the highest bit: one in the beginning, and one after the already placed number. And in case the already placed number has 0 in our bit, we can add at most one number with our bit as the highest bit. Once again, after doing that, our sequence is guaranteed to be increasing at the boundaries of already placed numbers no matter what we insert between them.<br /><br />A general step of our algorithm looks like this: we already have all numbers with highest bit higher than <i>x</i> placed, and want to place the numbers where the highest bit is <i>x</i>. We insert one such number in the beginning, and one after each already placed number where bit <i>x</i> is set, going from left to right, until we have no more numbers where the highest bit is <i>x</i>. If we run out of places before we run out of such numbers, there's no solution.<br /><br />Note that the solution works just barely: for example, we can't put the new numbers after any subset of already placed numbers where bit <i>x</i> is set: we must go from left to right instead, to guarantee that the prefix xor does not have bit <i>x</i> set at each insertion point. That's why I can't get rid of the feeling that this solution works almost by accident.<br /><br />Thanks for reading, and check back for more!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/NtPoLA4rkKc" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com4http://petr-mitrichev.blogspot.com/2018/05/a-prefix-xor-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-64786701588301197262018-05-14T00:55:00.001+03:002018-05-14T01:12:11.090+03:00A uniform combination week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-QmvBzeWEl78/WvinoGUwKRI/AAAAAAACCjw/jg73-0vsIkcnY98SBLf8iFmbnXPaIfkTQCLcBGAs/s1600/agc023top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="424" data-original-width="1176" height="230" src="https://3.bp.blogspot.com/-QmvBzeWEl78/WvinoGUwKRI/AAAAAAACCjw/jg73-0vsIkcnY98SBLf8iFmbnXPaIfkTQCLcBGAs/s640/agc023top5.png" width="640" /></a></div>Most teams have returned home from Beijing by the end of the Apr 23 - Apr 29 week, and the other contests returned in full swing. AtCoder Grand Contest 023 took place on Saturday (<a href="https://agc023.contest.atcoder.jp/assignments">problems</a>, <a href="https://agc023.contest.atcoder.jp/standings#page_1">results</a>, top 5 on the left, <a href="https://img.atcoder.jp/agc023/editorial.pdf">analysis</a>). The round was won by none other than the newly minted World Champion cospleermusora (also known as V--o_o--V and overtroll). yutaka1999 was also able to solve all problems, but required 30 more minutes to do so. Congratulations to both!<br /><br /><a href="https://agc023.contest.atcoder.jp/tasks/agc023_f">Problem F</a> was very cute. You are given a tree with 200000 vertices, each containing a number, either 0 or 1. We need to put all its vertices in some order in such a way each vertex except the root appears to the right of its parent. We will then write out a sequence of 0s and 1s corresponding to numbers in the vertices in this order. What is the minimum possible number of inversions in this sequence? An inversion is a pair of positions such that the number in the left position is 1, and the number in the right position is 0.<br /><br />Maybe I enjoyed this problem because I have set <a href="https://codejam.withgoogle.com/codejam/contest/3224486/dashboard#s=p1">a problem</a> in the past which involved the same strategy for producing a string from a tree.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-W4BfigQ4aI0/Wvi3pWpziWI/AAAAAAACCkw/lyLl4hj5pMsdyNw4_HIMJzUutvgrpJ7BgCLcBGAs/s1600/vk2018r3top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="270" data-original-width="1108" height="154" src="https://3.bp.blogspot.com/-W4BfigQ4aI0/Wvi3pWpziWI/AAAAAAACCkw/lyLl4hj5pMsdyNw4_HIMJzUutvgrpJ7BgCLcBGAs/s640/vk2018r3top5.png" width="640" /></a></div>VK Cup 2018 Round 3 happened on Sunday (<a href="http://codeforces.com/contest/925">problems</a>, <a href="http://codeforces.com/contest/925/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/contest/966/standings">parallel round results</a>, <a href="http://codeforces.com/blog/entry/59173">analysis</a>). The ICPC champions, this time two of them, kept with their champion-y ways and solved two more problems than everybody else. Unbelievable!<br /><br />I found <a href="http://codeforces.com/contest/966/problem/C">problem C</a> exceedingly beautiful. You are given 100000 numbers up to 2<sup>60</sup>. You need to put them in such order that the xors of all prefixes of the resulting sequence form a strictly increasing sequence themselves.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-v-6gauJZYEo/Wvis3uM758I/AAAAAAACCkI/mxNsmuYj4W4Otnamx4mclNobu9JiElA0wCLcBGAs/s1600/gcj18r1btop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="322" data-original-width="1078" height="190" src="https://3.bp.blogspot.com/-v-6gauJZYEo/Wvis3uM758I/AAAAAAACCkI/mxNsmuYj4W4Otnamx4mclNobu9JiElA0wCLcBGAs/s640/gcj18r1btop5.png" width="640" /></a></div>Right after the Codeforces round ended, Google ran Code Jam 2018 Round 1B (<a href="https://codejam.withgoogle.com/2018/challenges/0000000000007764/dashboard">problems</a>, <a href="https://codejam.withgoogle.com/2018/challenges/0000000000007764/scoreboard">results</a>, top 5 on the left, <a href="https://codejam.withgoogle.com/2018/challenges/0000000000007764/analysis">analysis</a>). overtroll has continued his impressive form (see above) with another victory, this time with a healthy margin of 12 minutes. Well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-z2oSFTVacxw/WvizMk4WyjI/AAAAAAACCkY/x7ZM5pCt-OIBGdqhQn7c1I6tbIhqGfgbwCLcBGAs/s1600/00001IMG_00001_BURST20180414150420_COVER.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1200" data-original-width="1600" height="480" src="https://3.bp.blogspot.com/-z2oSFTVacxw/WvizMk4WyjI/AAAAAAACCkY/x7ZM5pCt-OIBGdqhQn7c1I6tbIhqGfgbwCLcBGAs/s640/00001IMG_00001_BURST20180414150420_COVER.jpg" width="640" /></a></div>In <a href="https://petr-mitrichev.blogspot.com/2018/05/an-alma-mater-week.html">my previous summary</a>, I have mentioned a World Finals problem: there are <i>n</i> people, each starting with 1 gem. The following operation is repeated <i>d</i> times: take one of the gems uniformly at random, and split it into two gems (so the person holding it will have one more gem). After doing all that we order all people by the number of gems they have in decreasing order, and add up the number of gems of the first <i>r</i> people in that order. What is the expected value of that sum? <i>n</i> and <i>d</i> are at most 500.<br /><br />The first part of the solution is understanding the sequence generation process. At the first sight, it looks rather complicated, with the probability to get a new gem for each person changing along the way. However, let's look at the process from the following angle: let's put all gems for all people in one sequence, and every time a gem is divided we'll insert a new gem to the right of it. We'll also distinguish the <i>original</i> gems — the ones people start with — from the newly generated ones.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-QTyfr6EOUG8/Wvizt_WHvpI/AAAAAAACCkg/OG3sQBozJnYDl_Sg6M9aDgcthG_qGoGVgCLcBGAs/s1600/IMG_20180513_144831.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" data-original-height="581" data-original-width="1451" height="160" src="https://2.bp.blogspot.com/-QTyfr6EOUG8/Wvizt_WHvpI/AAAAAAACCkg/OG3sQBozJnYDl_Sg6M9aDgcthG_qGoGVgCLcBGAs/s400/IMG_20180513_144831.jpg" width="400" /></a></div>We start by having <i>n</i> original gems, and we can notice now that at each step we simply insert a new gem into a position in our sequence that is picked uniformly at random, except from the position before the first original gem which is never used. This in turn makes it clear that the resulting sequence starts with an original gem, and then has a sequence of <i>n</i>-1 original gems and <i>d</i> new gems picked uniformly at random from all C(<i>n</i>-1+<i>d</i>,<i>d</i>) such sequences. Each person gets all gems from their original gem to the next original gem in this sequence.<br /><br />A uniformly chosen combination is a well-known object which is easy to work with, which allows us to proceed with solving the problem using either dynamic programming or more combinatorics, as outlined in <a href="http://www.csc.kth.se/~austrin/icpc/finals2018solutions.pdf">the semi-official analysis</a>.<br /><br />Thanks for reading, and check back around the next weekend for more!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/0J76T3h-Wgg" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com2http://petr-mitrichev.blogspot.com/2018/05/a-uniform-combination-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-55109284842683898302018-05-13T23:54:00.000+03:002018-05-13T23:54:05.583+03:00An alma mater week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-prVtA6QEaOk/Wvia0rzC6VI/AAAAAAACCjI/b1LFGWGXkegqyE5iw815QZdLRQ8gjBAtQCLcBGAs/s1600/cf475top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="271" data-original-width="1102" height="156" src="https://4.bp.blogspot.com/-prVtA6QEaOk/Wvia0rzC6VI/AAAAAAACCjI/b1LFGWGXkegqyE5iw815QZdLRQ8gjBAtQCLcBGAs/s640/cf475top5.png" width="640" /></a></div>The Sächsilüüte week started with Codeforces Round 475 (<a href="http://codeforces.com/contest/963">problems</a>, <a href="http://codeforces.com/contest/963/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/58991">analysis</a>). Three contestants managed to solve all problems, but some were faster than the others :) In particular, V--o_o--V has finished after just 81 minutes, and thus won with a 500-point margin. Well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-fgW5HXAQlYo/Wvicor07MDI/AAAAAAACCjU/g-Eo90aXArEU7hv89KIYjd8LrEqBh7rMQCLcBGAs/s1600/icpc2018top13.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="745" data-original-width="1514" height="314" src="https://2.bp.blogspot.com/-fgW5HXAQlYo/Wvicor07MDI/AAAAAAACCjU/g-Eo90aXArEU7hv89KIYjd8LrEqBh7rMQCLcBGAs/s640/icpc2018top13.png" width="640" /></a></div>One of the main competitive programming events of the year, ACM ICPC 2018 World Finals took place on Thursday (<a href="https://icpc.baylor.edu/download/worldfinals/problems/icpc2018.pdf">problems</a>, <a href="https://icpc.baylor.edu/scoreboard/?static=1">results</a>, top 13 on the left, <a href="https://youtu.be/nF3tSkNWRVQ">our screencast with commentary</a>, <a href="https://youtu.be/LpIT35y33WY">official broadcast</a>, <a href="http://www.csc.kth.se/~austrin/icpc/finals2018solutions.pdf">analysis</a>). The deciding events of the competition happened in the last few minutes, when the Moscow State University team managed to squeeze in a solution to roblem E with an extra log factor by changing the number of iterations in binary search and getting something like TLE-TLE-TLE-OK-WA-WA-WA from seven attempts with different values of the magic constant.<br /><br />That OK might well turn out to be TLE or WA as well, but fortune favors the bold, and what essentially happened was that the Moscow State University team did great in using all their resources and creativity up to the last minute and got a well-deserved victory. Really happy for the team and for my alma mater to finally get the cup that I and many others could not deliver in the past :)<br /><br />Big congratulations to all other medalists on the great result, too!<br /><br />Problem D brought the most excitement for me in this problemset. There are <i>n</i> people, each starting with 1 gem. The following operation is repeated <i>d</i> times: take one of the gems uniformly at random, and split it into two gems (so the person holding it will have one more gem). After doing all that we order all people by the number of gems they have in decreasing order, and add up the number of gems of the first <i>r</i> people in that order. What is the expected value of that sum? <i>n</i> and <i>d</i> are at most 500.<br /><br />I'm also really interested in hearing what do you think about our stream and about the official broadcasts, if you had a chance to check them out, and I'm sure the ICPCLive team is very interested as well. Please share your observations or ideas!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-cFNgLVKTO68/WviksUkoaPI/AAAAAAACCjk/2SW1olze0IocKM6eAObG7_4IcOjWOUnxQCLcBGAs/s1600/tco18r1atop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="150" data-original-width="764" height="124" src="https://1.bp.blogspot.com/-cFNgLVKTO68/WviksUkoaPI/AAAAAAACCjk/2SW1olze0IocKM6eAObG7_4IcOjWOUnxQCLcBGAs/s640/tco18r1atop5.png" width="640" /></a></div>Finally, TopCoder Open 2018 Round 1A took place on Saturday (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=17144">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17144&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://www.topcoder.com/blog/2018-tco-algorithm-round-1a-editorials/">analysis</a>). With the problems quite a bit on the easy side, the challenge phase was instrumental in determining the winner — congratulations to Dembel on finding the +125 and the victory!<br /><br />Thanks for reading, and check back for more!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/cxSFTDYWFoQ" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2018/05/an-alma-mater-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-45747481545793730902018-05-13T23:01:00.000+03:002018-05-13T23:01:39.941+03:00Changes to commenting system<div dir="ltr" style="text-align: left;" trbidi="on">I've changed the commenting system in this blog from HyperComments (thanks to its authors for making it!) to built-in Blogger comments, because HyperComments is discontinuing free usage. In the past years Blogger has added support for threaded replies which was the main motivation for me to switch to HyperComments in the past, and using an external commenting system brought its own pains, so switching back to the default seems to be the logical thing to do.<br /><br />Please tell if you encounter some issues with commenting using the new (old?) system!<br /><br />One side effect is that all comments made through HyperComments are not visible now. I have an xml export of all of them, but it's not clear at this point how to import those back into the Blogger system. Please share ideas if you have them :)</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/dR1QYQXCfH8" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com2http://petr-mitrichev.blogspot.com/2018/05/changes-to-commenting-system.htmltag:blogger.com,1999:blog-1953325079793449971.post-82458868699144272522018-05-13T22:45:00.001+03:002018-05-13T22:48:28.312+03:00A +300 week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-FEQo53qz4so/WviSJsv1t0I/AAAAAAACCik/BEctxGa566ckf9HlA6yUbht-n-7Dvt_nwCLcBGAs/s1600/gcj18r1atop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="315" data-original-width="999" height="200" src="https://4.bp.blogspot.com/-FEQo53qz4so/WviSJsv1t0I/AAAAAAACCik/BEctxGa566ckf9HlA6yUbht-n-7Dvt_nwCLcBGAs/s640/gcj18r1atop5.png" width="640" /></a></div>The week before the ICPC World Finals featured two competitions, both on Saturday. First off, Google Code Jam 2018 Round 1A took place very early (<a href="https://codejam.withgoogle.com/2018/challenges/0000000000007883/dashboard">problems</a>, <a href="https://codejam.withgoogle.com/2018/challenges/0000000000007883/scoreboard">results</a>, top 5 on the left, <a href="https://codejam.withgoogle.com/2018/challenges/0000000000007883/analysis">analysis</a>). This was the first round under complete new rules, as the penalty time did not matter in the qualification. The optimal strategy, of course, stayed more or less the same — just solve all problems quickly and without bugs :) vepifanov has executed it really well, congratulations on the victory!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-55P6YIXzzzI/WviUBQTO_TI/AAAAAAACCi4/qpR9L2tBlFMkqlETRXe3KzPnAZaQOrt5ACLcBGAs/s1600/srm733top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="149" data-original-width="778" height="122" src="https://4.bp.blogspot.com/-55P6YIXzzzI/WviUBQTO_TI/AAAAAAACCi4/qpR9L2tBlFMkqlETRXe3KzPnAZaQOrt5ACLcBGAs/s640/srm733top5.png" width="640" /></a></div>TopCoder SRM 733 followed later that day (<a href="https://community.topcoder.com/stat?c=round_overview&rd=17140">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17140&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://www.topcoder.com/blog/single-round-match-733-editorials/">analysis</a>). Kriii has really dominated the proceedings, spending a bit over 18 minutes on all three problems in total Compare that to a bit over 41 minutes that kuniavski needed, and he came in second! Amazing performance by Kriii.<br /><br />This was the third SRM which doesn't list cgy4ever in its authors, marking the transition to misof as the new TopCoder problem coordinator. Congratulations to misof on the new role, looking forward to the next SRMs!<br /><br />Thanks for reading this [short] post, check back soon for more!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/ItrfGfMjRqw" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2018/05/a-300-week.html