tag:blogger.com,1999:blog-19533250797934499712018-08-18T09:03:17.999+03:00Algorithms Weekly by Petr MitrichevPetr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.comBlogger371125PetrMitrichevhttps://feedburner.google.comtag: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.htmltag:blogger.com,1999:blog-1953325079793449971.post-87511130662092868822018-05-11T12:44:00.000+03:002018-05-11T12:44:20.237+03:00An elimination 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/-_3v3tEIN1hw/Wtc7kmGa_GI/AAAAAAACBSY/wVtGCgEOMCIYS82qegVYeOkofZwlgglZwCLcBGAs/s1600/cf474top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="279" data-original-width="1106" height="160" src="https://4.bp.blogspot.com/-_3v3tEIN1hw/Wtc7kmGa_GI/AAAAAAACBSY/wVtGCgEOMCIYS82qegVYeOkofZwlgglZwCLcBGAs/s640/cf474top5.png" width="640" /></a></div>The Apr 2 - Apr 8 week had a couple of competitions on the weekend. Codeforces Round 474 took place on Saturday (<a href="http://codeforces.com/contest/960">problems</a>, <a href="http://codeforces.com/contest/960/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/58802">analysis</a>). Solving eight problems correctly in just over two hours is an amazing feat — OO0OOO00O0OOO0O00OOO0OO was on top of his game this time. Well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-hbaJjfPeNS8/WtrfX_54dnI/AAAAAAACBZw/mLyu5oY-pGs_gHLLmIX10lXthI5xTdO0wCLcBGAs/s1600/ya2018r3top6.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="442" data-original-width="1198" height="236" src="https://3.bp.blogspot.com/-hbaJjfPeNS8/WtrfX_54dnI/AAAAAAACBZw/mLyu5oY-pGs_gHLLmIX10lXthI5xTdO0wCLcBGAs/s640/ya2018r3top6.png" width="640" /></a></div>Yandex.Algorithm 2018 Round 3 on Sunday (<a href="https://contest.yandex.com/algorithm2018/contest/7989/problems/">problems with Yandex login</a>, <a href="https://contest.yandex.com/algorithm2018/contest/7989/standings/">results</a>, top 6 on the left, <a href="https://yadi.sk/i/6m40Qql53UDQSv">analysis</a>) has completed the Elimination stage. Unlike the first two rounds, this time blind submissions were actually necessary for the victory — congratulations to Merkurev for pulling four of those off !<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-r6HtRSKBa9M/Wtr_IDMlk1I/AAAAAAACBaI/ScJyirOLF7kFN2U6CTMVdRahTw_zpcQgQCLcBGAs/s1600/ya2018elimtop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="270" data-original-width="1160" height="148" src="https://1.bp.blogspot.com/-r6HtRSKBa9M/Wtr_IDMlk1I/AAAAAAACBaI/ScJyirOLF7kFN2U6CTMVdRahTw_zpcQgQCLcBGAs/s640/ya2018elimtop5.png" width="640" /></a></div>Here is the final <a href="https://contest.yandex.com/algorithm2018/algo-results/">Elimination stage scoreboard</a> (top 5 on the left), with top 25 advancing to the finals held both online and in St Petersburg.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-983ww0XCAQc/WvVktVjyQTI/AAAAAAACCHw/fADbq9kOAEINmMlkb5d_OsLLb3PJdb1HwCLcBGAs/s1600/oc1718warsawtop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="271" data-original-width="919" height="188" src="https://3.bp.blogspot.com/-983ww0XCAQc/WvVktVjyQTI/AAAAAAACCHw/fADbq9kOAEINmMlkb5d_OsLLb3PJdb1HwCLcBGAs/s640/oc1718warsawtop5.png" width="640" /></a></div>Also on Sunday, Open Cup 2017-18 continued its streak with the Grand Prix of Warsaw (<a href="http://opencup.ru/index.cgi?data=macros/stage&head=index&menu=index&stg=18&region=main&ncup=oci&class=oci">results</a>, top 5 on the left). SPb ITMO U 1 team demonstrated impressive form, solving all 11 problems at the moment when all other teams had at most 9. Three other teams got to 10 problems in the remaining time, but nobody could approach the first place. Congratulations to the ITMO 1 team!<br /><br />Thanks for reading, and check back for more!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/PNcOs3s4J-k" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2018/05/an-elimination-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-4538308596607615582018-04-18T15:19:00.002+03:002018-04-18T15:19:34.842+03:00A second extremal 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/-Ftsw9-zIAYg/WtcqgfE6WyI/AAAAAAACBRo/EEFkJSldNNsistKAHl64zS4QOzEj8r6qACLcBGAs/s1600/srm732top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="148" data-original-width="782" height="120" src="https://4.bp.blogspot.com/-Ftsw9-zIAYg/WtcqgfE6WyI/AAAAAAACBRo/EEFkJSldNNsistKAHl64zS4QOzEj8r6qACLcBGAs/s640/srm732top5.png" width="640" /></a></div>The last week of March featured more contests from the regular platforms. First off, TopCoder SRM 732 took place very early on Friday (<a href="https://community.topcoder.com/stat?c=round_overview&rd=17103">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17103&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left). Both the medium and the hard problem involved asymmetric games requiring quite some insight to solve, and thus only two contestants were able to solve each (top 4 in the table to the left). Congratulations to all four, and especially to pashka on the win!<br /><div><br /></div><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-wS_axcop5bk/Wtcs-HmBjHI/AAAAAAACBR0/bDzvInxcniUbt6ScGBtElWD9gwimc4QqACLcBGAs/s1600/agc022top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="426" data-original-width="1174" height="232" src="https://3.bp.blogspot.com/-wS_axcop5bk/Wtcs-HmBjHI/AAAAAAACBR0/bDzvInxcniUbt6ScGBtElWD9gwimc4QqACLcBGAs/s640/agc022top5.png" width="640" /></a></div><div>Then AtCoder held its Grand Contest 022 on Saturday (<a href="https://agc022.contest.atcoder.jp/assignments">problems</a>, <a href="https://agc022.contest.atcoder.jp/standings#page_1">results</a>, top 5 on the left, <a href="https://img.atcoder.jp/agc022/editorial.pdf">analysis</a>). The contest had three relatively easy problems, and three very hard ones. Only a few contestants were able to solve one of the three (I couldn't solve any, for that matter), so it is extremely impressive that Um_nik got all three — huge congratulations on very well deserved victory!<br /><br /><a href="https://agc022.contest.atcoder.jp/tasks/agc022_e">Problem E</a> was the most approachable of the three. Consider a string of <span style="font-family: Courier New, Courier, monospace;">0</span>s, <span style="font-family: Courier New, Courier, monospace;">1</span>s and <span style="font-family: Courier New, Courier, monospace;">?</span>s of odd length up to 300000. First, we need to replace each <span style="font-family: Courier New, Courier, monospace;">?</span> with a <span style="font-family: Courier New, Courier, monospace;">0</span> or a <span style="font-family: Courier New, Courier, monospace;">1</span>. Then, we repeatedly do the following operation: take any 3 consecutive characters, and replace them with the most frequent character among them. For example, <span style="font-family: Courier New, Courier, monospace;">001</span> is replaced with <span style="font-family: Courier New, Courier, monospace;">0</span>. In the end we end up with a string of length 1, and our goal is to get the string <span style="font-family: "Courier New", Courier, monospace;">1</span><span style="font-family: inherit;">. How many ways are there to replace the </span><span style="font-family: "Courier New", Courier, monospace;">?</span><span style="font-family: inherit;">s so that it's possible to get the </span><span style="font-family: "Courier New", Courier, monospace;">1</span><span style="font-family: inherit;"> after all reductions?</span></div><div><br /></div><div>And finally, Open Cup 2017-18 Grand Prix of Moscow on Sunday wrapped up the week, but its results have not yet been published.<br /><br /></div><div></div><div><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-JoJ72EtwRio/Wtc3Sk9fLmI/AAAAAAACBSI/b8R3sxi_prU1zZpaGchd3TWaBQThXogygCLcBGAs/s1600/IMG_20180408_151726.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/-JoJ72EtwRio/Wtc3Sk9fLmI/AAAAAAACBSI/b8R3sxi_prU1zZpaGchd3TWaBQThXogygCLcBGAs/s640/IMG_20180408_151726.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2018/04/a-group-embedding-week.html">my previous summary</a>, I have mentioned an Open Cup problem: you are given <i>n</i> points <i>p</i><sub>1</sub>, <i>p</i><sub>2</sub>, ..., <i>p<sub>n</sub></i> on the plane and <i>q</i> queries (<i>n</i>, <i>q</i> <= 100000). Each query is defined by two numbers <i>a</i>, <i>b</i>, and you need to print the size of the smallest square with sides parallel to coordinate axes that contains all points from <i>a</i>-th to <i>b</i>-th (from the list <i>p</i><sub><i>a</i></sub>, <i>p</i><sub><i>a</i>+1</sub>, ..., <i>p<sub>b</sub></i>) <i>except maybe one</i>.<br /><br />Assuming we forget about "except maybe one" part, we need to find the bounding box of a segment of points, which can be done by finding the leftmost, rightmost, topmost and bottom-most points using interval trees in O(<i>n</i>*log(<i>n</i>)).<br /><br />Now we can notice that when the skipped point is not one of the four extremal points, then the bounding box does not change, so we need to check at most four possibilities for the skipped point. In order to be able to find extremal points after skipping one point, our interval trees will need hold two extremal points instead of one, but otherwise the solution stays the same.<br /><br />Thanks for reading, and check back for more!</div></div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/O79vv3yU2jI" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2018/04/a-second-extremal-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-65994091070690635072018-04-18T10:48:00.000+03:002018-04-18T10:48:19.913+03:00ACM ICPC 2018 World Finals stream on Twitch<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/-Bsdpz-Rdmq4/Wtb4HHF5FFI/AAAAAAACBQ8/r--5_rTm5uQIo75a0QJcoz3ZSxmipY0RQCKgBGAs/s1600/IMG_20180418_151848.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="663" data-original-width="1600" height="264" src="https://1.bp.blogspot.com/-Bsdpz-Rdmq4/Wtb4HHF5FFI/AAAAAAACBQ8/r--5_rTm5uQIo75a0QJcoz3ZSxmipY0RQCKgBGAs/s640/IMG_20180418_151848.jpg" width="640" /></a></div>We have figured out a working setup for our stream, so tune in to <a href="https://www.twitch.tv/petrmitrichev">https://www.twitch.tv/petrmitrichev</a> around <a href="https://www.timeanddate.com/worldclock/fixedtime.html?msg=ACM+ICPC+2018+World+Finals&iso=20180419T10&p1=33&ah=5">10:00 Beijing time</a> tomorrow!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/jX5Ufrk7PUs" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2018/04/acm-icpc-2018-world-finals-stream-on.htmltag:blogger.com,1999:blog-1953325079793449971.post-43583119972488884622018-04-17T19:24:00.001+03:002018-04-17T19:24:27.172+03:00A group embedding 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/-dhUK1alK9hw/WtXDQbcpF7I/AAAAAAACBIs/8IEqR_3Ruukj17q6UeHEyNTfLsdJVxlZgCLcBGAs/s1600/vk2018r2top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="269" data-original-width="1098" height="156" src="https://3.bp.blogspot.com/-dhUK1alK9hw/WtXDQbcpF7I/AAAAAAACBIs/8IEqR_3Ruukj17q6UeHEyNTfLsdJVxlZgCLcBGAs/s640/vk2018r2top5.png" width="640" /></a></div>VK Cup 2018 Round 2 took place during the The Mar 19 - Mar 25 week (<a href="http://codeforces.com/contest/924">problems</a>, <a href="http://codeforces.com/contest/924/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/contest/956/standings">parallel round results</a>, <a href="http://codeforces.com/blog/entry/58544">analysis</a>). Team Нижний Магазин SU: BZ would be first by far even without solving the last problem, but getting all problems accepted in the final minutes of the contest was of course the icing on the cake. Congratulations!<br /><div><br /></div><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-Rz0ZxdumdUE/WtXFKI3S_3I/AAAAAAACBI4/z-xZASUfP4MUc1YFVo_OniRa88IhSYqcACLcBGAs/s1600/oc1718americatop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="212" data-original-width="814" height="166" src="https://4.bp.blogspot.com/-Rz0ZxdumdUE/WtXFKI3S_3I/AAAAAAACBI4/z-xZASUfP4MUc1YFVo_OniRa88IhSYqcACLcBGAs/s640/oc1718americatop5.png" width="640" /></a></div><div>Open Cup 2017-18 Grand Prix of America wrapped up that week (<a href="http://opentrains.snarknews.info/~ejudge/res/res10416">results</a>, top 5 on the left, <a href="https://naipc18.kattis.com/standings">parallel round results</a>), with another two World Finals favorites in top 5: SPb ITMO 1 and Moscow SU Red Panda. The first place, however, went to team Past Glory — once again thanks to their incredible accuracy. Congratulations!<br /><br />Problem K in this round was quite educational, if a bit professional. You are given <i>n</i> points <i>p</i><sub>1</sub>, <i>p</i><sub>2</sub>, ..., <i>p<sub>n</sub></i> on the plane and <i>q</i> queries (<i>n</i>, <i>q</i> <= 100000). Each query is defined by two numbers <i>a</i>, <i>b</i>, and you need to print the size of the smallest square with sides parallel to coordinate axes that contains all points from <i>a</i>-th to <i>b</i>-th (from the list <i>p</i><sub><i>a</i></sub>, <i>p</i><sub><i>a</i>+1</sub>, ..., <i>p<sub>b</sub></i>) <i>except maybe one</i>. Can you dissect this problem into standard pieces?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-sRLUZPFiRxI/WtYfboq3j4I/AAAAAAACBM8/1LruwZOKP40HnF-hVzA49OomQjsLHNeYgCLcBGAs/s1600/IMG_20180408_121656%257E2.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1025" data-original-width="1600" height="408" src="https://2.bp.blogspot.com/-sRLUZPFiRxI/WtYfboq3j4I/AAAAAAACBM8/1LruwZOKP40HnF-hVzA49OomQjsLHNeYgCLcBGAs/s640/IMG_20180408_121656%257E2.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2018/04/a-favorites-week.html">my previous summary</a>, I have mentioned a Yandex.Algorithm problem: you are given a string <i>s</i> with 100000 characters, each <span style="font-family: "courier new" , "courier" , monospace;">a</span>, <span style="font-family: "courier new" , "courier" , monospace;">b</span> or <span style="font-family: "courier new" , "courier" , monospace;">c</span>. You must swap exactly two distinct letters to obtain a new string <i>t</i>. How many ways are there to do that in such a way that the string <i>t</i> is good? In this problem we define a <i>good</i> string somewhat similarly to a valid parentheses sequence: empty string is good, if a string <i>u</i> is good then the strings <span style="font-family: "courier new" , "courier" , monospace;">a</span><i>u</i><span style="font-family: "courier new" , "courier" , monospace;">a</span><span style="font-family: inherit;">, </span><span style="font-family: "courier new" , "courier" , monospace;">b</span><i>u</i><span style="font-family: "courier new" , "courier" , monospace;">b</span>, <span style="font-family: "courier new" , "courier" , monospace;">c</span><i>u</i><span style="font-family: "courier new" , "courier" , monospace;">c</span> are good as well, and if two strings <i>u</i> and <i>v</i> are good, then their concatenation <i>uv</i> is also good.<br /><br />The key insight in this problem is to learn to check if a string is good easily. Let's pick a group and 3 elements of order 2 in it: <span style="font-family: "courier new" , "courier" , monospace;">a</span><span style="font-family: "courier new" , "courier" , monospace;">a</span><span style="font-family: inherit;">=1, </span><span style="font-family: "courier new" , "courier" , monospace;">bb</span><span style="font-family: inherit;">=1, </span><span style="font-family: "courier new" , "courier" , monospace;">cc</span><span style="font-family: inherit;">=1. We will then map each string to the product of the corresponding elements of the group. We can see that any <i>good </i>string will map to 1. Moreover, if our group is general enough, in other words does not have any other non-derived products that are equal to 1 (or if such products are simply unlikely to be equal to 1), then the opposite is also true: when a string maps to 1, it is good. As an example group that works in this problem we can use the group of movements of 3D space that keep the origin fixed, where </span><span style="font-family: "courier new" , "courier" , monospace;">a</span><span style="font-family: inherit;">, </span><span style="font-family: "courier new" , "courier" , monospace;">b</span><span style="font-family: inherit;"> and </span><span style="font-family: "courier new" , "courier" , monospace;">c</span><span style="font-family: inherit;"> correspond to reflections through three random planes passing through origin. This way, we obtain a compressed representation for a string of any length as a single 3x3 matrix (modulo some prime number, to avoid dealing with floating point).</span><br /><br />We can then use the divide-and-conquer approach: we start by splitting our string in two in the middle, and consider the case where the two positions being swapped are in different halves. If we also try all 6 possibilities for the letters being swapped, we have a sub-problem of the following kind: we have two strings, and need to replace a single a with <span style="font-family: "courier new" , "courier" , monospace;">b</span> in the first string, and a single <span style="font-family: "courier new" , "courier" , monospace;">b</span> with <span style="font-family: "courier new" , "courier" , monospace;">a</span> in the second string, so that after doing those replacements and concatenating the strings we get a good one.<br /><br /><span style="font-family: inherit;">We can compute the compressed representation of each candidate for the first half using prefix and suffix products, then compute the compressed representation of each candidate for the second half in the same way, and then for each representation of first half find its inverse element in the second half, thus processing the case where the swapped elements are in different halves in O(<i>n</i>).</span><br /><span style="font-family: inherit;"><br /></span><span style="font-family: inherit;">In order to handle the case where both swapped elements are in the same half, we follow the divide-and-conquer approach and recursively execute the same algorithm for each half, with the only difference that the target product in each half we want to get is not 1, but rather the inverse of the product of the other half. This allows to complete the solution of the entire problem in O(<i>n</i>*log(<i>n</i>)).</span><br /><span style="font-family: inherit;"><br /></span><span style="font-family: inherit;">Thanks for reading, and check back soon!</span></div></div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/9rdul-z1H0E" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2018/04/a-group-embedding-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-53245832675712908602018-04-17T18:30:00.000+03:002018-04-17T18:30:27.028+03:00A favorites 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/-BGYi4WECh0c/WtWz-YdtybI/AAAAAAACBHw/kuWwuu3T3884RZZmpnCWEL6fkasItz-0wCLcBGAs/s1600/ya2018r2top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="380" data-original-width="1190" height="204" src="https://3.bp.blogspot.com/-BGYi4WECh0c/WtWz-YdtybI/AAAAAAACBHw/kuWwuu3T3884RZZmpnCWEL6fkasItz-0wCLcBGAs/s640/ya2018r2top5.png" width="640" /></a></div>The Mar 12 - Mar 18 week started with Yandex.Algorithm Round 2 on Tuesday (<a href="https://contest.yandex.ru/contest/7736/problems/">problems with Yandex login</a>, <a href="https://contest.yandex.ru/contest/7736/standings/">results</a>, top 5 on the left, <a href="https://youtu.be/shoK2wIdurA">my screencast</a>). <a href="https://contest.yandex.ru/contest/7736/problems/A/">The hardest problem A</a> was left unsolved despite 78 attempts, and yet the actual implementation is quite straightforward once one gets the idea. You are given a string <i>s</i> with 100000 characters, each <span style="font-family: "courier new" , "courier" , monospace;">a</span>, <span style="font-family: "courier new" , "courier" , monospace;">b</span> or <span style="font-family: "courier new" , "courier" , monospace;">c</span>. You must swap exactly two distinct letters to obtain a new string <i>t</i>. How many ways are there to do that in such a way that the string <i>t</i> is good? In this problem we define a <i>good</i> string somewhat similarly to a valid parentheses sequence: empty string is good, if a string <i>u</i> is good then the strings <span style="font-family: "courier new" , "courier" , monospace;">a</span><i>u</i><span style="font-family: "courier new" , "courier" , monospace;">a</span><span style="font-family: inherit;">, </span><span style="font-family: "courier new" , "courier" , monospace;">b</span><i>u</i><span style="font-family: "courier new" , "courier" , monospace;">b</span>, <span style="font-family: "courier new" , "courier" , monospace;">c</span><i>u</i><span style="font-family: "courier new" , "courier" , monospace;">c</span> are good as well, and if two strings <i>u</i> and <i>v</i> are good, then their concatenation <i>uv</i> is also good.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-CF9QD80y7Lk/WtW0uWOrRAI/AAAAAAACBH4/WXM8KajAmKYryf1c6p42JAXwRarmdvAQACLcBGAs/s1600/srm731top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="150" data-original-width="779" height="122" src="https://4.bp.blogspot.com/-CF9QD80y7Lk/WtW0uWOrRAI/AAAAAAACBH4/WXM8KajAmKYryf1c6p42JAXwRarmdvAQACLcBGAs/s640/srm731top5.png" width="640" /></a></div>TopCoder SRM 731 took place on Saturday (<a href="https://community.topcoder.com/stat?c=round_overview&rd=17095">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17095&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left). mjhun was the fastest during the coding phase, but Gassa was close enough to require just one successful challenge to climb into the first place. Congratulations to both of you!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-LzgtRG6o1P4/WtW2glgJ-UI/AAAAAAACBIE/c8vK9dNqi6Ed3ApzzIAsK4hYdDBiyX8TACLcBGAs/s1600/oc1718belarustop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="271" data-original-width="871" height="198" src="https://2.bp.blogspot.com/-LzgtRG6o1P4/WtW2glgJ-UI/AAAAAAACBIE/c8vK9dNqi6Ed3ApzzIAsK4hYdDBiyX8TACLcBGAs/s640/oc1718belarustop5.png" width="640" /></a></div>Finally, the Open Cup 2017-18 Grand Prix of Belarus happened on Sunday (<a href="http://opencup.ru/files/oci/gp15/problems1-e.pdf">problems</a>, <a href="http://opencup.ru/index.cgi?data=macros/stage&head=index&menu=index&stg=15&region=main&ncup=oci&class=oci">results</a>, top 5 on the left). Team Past Glory was once again the fastest — well done! This round also provided a World Finals prediction perspective, as there are two teams in the top 5 who will be competing in Beijing: Seoul NU and Peking U. This year's World Finals looks to be extremely competitive, with top teams like Seoul NU, Peking U, SPb ITMO, Moscow SU, Warsaw U all of comparable strength (did I miss a team that you think is one of the favorites to win? Sorry, and please share in comments!) I'm looking forward to the final showdown on Thursday!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-WHQolsJxd48/WtW_8b7CkII/AAAAAAACBIg/5bDquGqasj40EArIoR6S8ekAG94w_NHfACLcBGAs/s1600/IMG_20180316_142300.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1600" data-original-width="1200" height="640" src="https://2.bp.blogspot.com/-WHQolsJxd48/WtW_8b7CkII/AAAAAAACBIg/5bDquGqasj40EArIoR6S8ekAG94w_NHfACLcBGAs/s640/IMG_20180316_142300.jpg" width="480" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2018/04/a-binary-block-week.html">my previous summary</a>, I have mentioned a cute Open Cup problem: you are given a <i>n</i> times <i>n</i> matrix <i>A</i> of integers modulo a prime number <i>p</i>. You need to find the smallest positive integer <i>k</i> such that <i>A<sup>k</sup></i>=0 (modulo <i>p</i>), or report that it does not exist, in O(<i>n</i><sup>3</sup>).<br /><br />The answer never exceeds <i>n</i>, which in very rough terms can be derived from looking at <a href="https://en.wikipedia.org/wiki/Jordan_normal_form">Jordan normal forms</a> (is there a simpler argument?..), which enables the following O(<i>n</i><sup>4</sup>) approach: just compute the first <i>n</i> powers of <i>A</i>. It can be sped up to O(<i>n</i><sup>3</sup>*log(<i>n</i>)) by using binary search, since once a power of <i>A</i> is zero, all following powers are zero as well.<br /><br />In order to speed it up to O(<i>n</i><sup>3</sup>), we need to come up with a beautiful idea: instead of computing just <i>A<sup>k</sup></i>, we will compute <i>A<sup>k</sup></i><i>*v</i> for some vector <i>v</i> of size n. In case <i>A<sup>k</sup></i>=0, then <i>A<sup>k</sup></i><i>*v</i>=0 as well. It turns out the opposite is almost always true: <i>A<sup>k</sup></i><i>*v</i> over all <i>v</i> defines a linear subspace, which has at least one dimension in case <i>A<sup>k</sup></i> is not zero, and thus we can just pick v randomly and the probability of <i>A<sup>k</sup></i><i>*v</i> being zero will not exceed 1/<i>p</i>.<br /><br />Since we can multiply a matrix by a vector in O(<i>n</i><sup>2</sup>), we can compute <i>v</i>, <i>A</i>*<i>v</i>, <i>A<sup>2</sup></i><i>*v</i>, ..., <i>A<sup>n</sup></i><i>*v</i> in sequence in O(<i>n</i><sup>3</sup>) overall.<br /><br />Thanks for reading, and check back for more!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/OUOL0P4YGRc" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2018/04/a-favorites-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-91396420733339005932018-04-17T10:58:00.000+03:002018-04-17T10:58:33.765+03:00ACM ICPC 2018 World Finals stream<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/-vgnnUdGVxPI/WtQG4sH17qI/AAAAAAACA9Q/bLAMDTiABjcoFWfjp-E8CBeC5nJfDuDKQCLcBGAs/s1600/team.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="540" data-original-width="960" height="360" src="https://2.bp.blogspot.com/-vgnnUdGVxPI/WtQG4sH17qI/AAAAAAACA9Q/bLAMDTiABjcoFWfjp-E8CBeC5nJfDuDKQCLcBGAs/s640/team.jpg" width="640" /></a></div>ACM ICPC 2018 World Finals take place this Thursday at 10:00 Beijing time (<a href="https://www.timeanddate.com/worldclock/fixedtime.html?msg=ACM+ICPC+2018+World+Finals&iso=20180419T10&p1=33&ah=5">click for other timezones</a>). Just like <a href="http://petr-mitrichev.blogspot.com/2017/05/acm-icpc-2017-world-finals-stream.html">last year</a>, we'll try to solve it in parallel with tourist and Endagorion, and stream the process, assuming the problems will be available for submission <a href="https://online.acmicpc.org/problems">on Kattis</a>.<br /><br />I'm not yet sure if it's going to be on Youtube, which does not work well in China, or somewhere else. I will post an update here and <a href="https://twitter.com/PetrMitrichev">in Twitter</a> once we figure out the right setup. Stay tuned!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/4Mu0f9cA6eE" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2018/04/acm-icpc-2018-world-finals-stream.htmltag:blogger.com,1999:blog-1953325079793449971.post-52059547937622645182018-04-14T17:10:00.001+03:002018-04-14T17:10:33.978+03:00A binary block 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/-EeQLmtKhxyI/WtH3nRcqDdI/AAAAAAACA5Y/UCla8Ocr_b4jNYg-WsQCpwfpADbq3pW5QCLcBGAs/s1600/cf469top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="271" data-original-width="1098" height="156" src="https://3.bp.blogspot.com/-EeQLmtKhxyI/WtH3nRcqDdI/AAAAAAACA5Y/UCla8Ocr_b4jNYg-WsQCpwfpADbq3pW5QCLcBGAs/s640/cf469top5.png" width="640" /></a></div>The Mar 5 - Mar 11 week had two Codeforces rounds. Round 469 took place on Friday (<a href="http://codeforces.com/contest/949">problems</a>, <a href="http://codeforces.com/contest/949/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/58291">analysis</a>). Since I'm writing this post on the plane to Beijing for ICPC 2018 World Finals, I can't help but look at the scoreboard from the ICPC angle: the winner dotorya will be participating in the Seoul NU team, and the third-placed Syloviaely is part of the host Peking U team. Congratulations on the great Codeforces result, and best of luck in the World Finals!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-q90tCx3HFx8/WtH5h2TwsEI/AAAAAAACA5k/OEIIz7Y7jLAI00eSRN9N9_6XU8vwNphZgCLcBGAs/s1600/vk2018r1top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="278" data-original-width="1102" height="160" src="https://3.bp.blogspot.com/-q90tCx3HFx8/WtH5h2TwsEI/AAAAAAACA5k/OEIIz7Y7jLAI00eSRN9N9_6XU8vwNphZgCLcBGAs/s640/vk2018r1top5.png" width="640" /></a></div>VK Cup 2018 Round 1 took place one day later (<a href="http://codeforces.com/contest/923">problems</a>, <a href="http://codeforces.com/contest/923/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/contest/947/standings">parallel round results</a>, <a href="http://codeforces.com/blog/entry/58286">analysis</a>). Team VK Cup 24329020081766400008 from Saratov was already among the fastest in coding, but managed to stand out thanks to the challenges, even despite their solution for the hardest problem failing systests. Well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-K7f7vjenzeU/WtH9qdPUkwI/AAAAAAACA5w/cz5-gNQ0K60VIcOfvyjSs_qEaFZ4dW7rQCLcBGAs/s1600/oc1718baltictop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="268" data-original-width="819" height="208" src="https://3.bp.blogspot.com/-K7f7vjenzeU/WtH9qdPUkwI/AAAAAAACA5w/cz5-gNQ0K60VIcOfvyjSs_qEaFZ4dW7rQCLcBGAs/s640/oc1718baltictop5.png" width="640" /></a></div>Finally, after a week's hiatus the Open Cup came back for another five-week marathon which started with the Grand Prix of Baltic (<a href="http://opencup.ru/files/oci/gp14/problems-e.pdf">problems</a>, <a href="http://opencup.ru/index.cgi?data=macros/stage&head=index&menu=index&stg=14&region=main&ncup=oci&class=oci">results</a>, top 5 on the left). Team Past Glory was not as fast as t.me/umnik_team, but they were more accurate, and thus won by a few penalty minutes. Congratulations to both teams on the great performance!<br /><br />Problem E had a very simple statement and a very cute solution. You are given a <i>n</i> times <i>n</i> matrix <i>A</i> of integers modulo a prime number <i>p</i>. You need to find the smallest positive integer <i>k</i> such that <i>A<sup>k</sup></i>=0 (modulo <i>p</i>), or report that it does not exist. It is relatively straightforward to do in O(<i>n</i><sup>3</sup>*log(<i>n</i>)), but your solution needs to run in O(<i>n</i><sup>3</sup>).<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-EaFiCN9Z6hI/WtIJ-qDIUqI/AAAAAAACA6A/VZavrweDmIIMWYDRu7lPCIFb1rlAseykQCLcBGAs/s1600/IMG_20180308_153117.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/-EaFiCN9Z6hI/WtIJ-qDIUqI/AAAAAAACA6A/VZavrweDmIIMWYDRu7lPCIFb1rlAseykQCLcBGAs/s640/IMG_20180308_153117.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2018/03/a-power-of-two-week.html">my previous summary</a>, I have mentioned a difficult Codeforces problem: consider an unknown binary string of length <i>k</i>, <i>k</i> is up to a billion. You're given up to 100000 segments [<i>a</i><i><sub>i</sub></i>,<i>b</i><i><sub>i</sub></i>], and know that each of those segments contains at least one 0. In a similar vein, you're also given up to 100000 segments [<i>c</i><i><sub>i</sub></i>,<i>d</i><i><sub>i</sub></i>], and know that each of those segments contains at least one 1. How many such binary strings exist, modulo 10<sup>9</sup>+7?<br /><br />First, how can we approach this problem if we forget that <i>k</i> is very big? Let's split our string into blocks of 0s and 1s, and compute <i>p</i><i><sub>j</sub></i> — the number of ways to choose the first j characters ending with a block of 0s, and <i>q</i><i><sub>j</sub></i> — the number of ways to choose the first j characters ending with a block of 1s. To compute <i>p</i><i><sub>j</sub></i>, we iterate over the ending point <i>t</i> of previous block of 1s, and we see that <i>p</i><i><sub>j</sub></i> is a sum of <i>q</i><i><sub>t</sub></i>. <i>t</i> must be at most j-1, and at least max(<i>c</i><i><sub>i</sub></i>) over all i such that <i>d</i><i><sub>i</sub></i><=<i>j</i>, to make sure that no [<i>c</i><i><sub>i</sub></i>,<i>d</i><i><sub>i</sub></i>] segment only contains 0s. We can compute <i>q</i><i><sub>j</sub></i> in a symmetric way.<br /><br />Since max(<i>c</i><i><sub>i</sub></i>) only ever increases as we increase <i>j</i>, we can maintain a sliding window of <i>q</i><i><sub>t</sub></i>'s together with their sum, and thus obtain a O(<i>k</i>) amortized time solution.<br /><br />Now let's look more closely at this process in case we don't encounter any new segment endpoints. Suppose we have just found <i>p</i><i><sub>j</sub></i> and <i>q</i><i><sub>j</sub></i>, and now are looking to find <i>p</i><i><sub>j+1</sub></i> and <i>q</i><i><sub>j+1</sub></i> while the left boundaries of our summation max(<i>a</i><i><sub>i</sub></i>) and max(<i>c</i><i><sub>i</sub></i>) stay the same. <i>p</i><i><sub>j+1 </sub></i>is the same sum as <i>p</i><i><sub>j</sub></i>, but with extra term <i>q</i><i><sub>j </sub></i>added, so <i>p</i><i><sub>j+1</sub></i>=<i>p</i><i><sub>j</sub></i>+<i>q</i><i><sub>j</sub></i>. Similarly, <i>q</i><i><sub>j+1</sub></i>=<i>p</i><i><sub>j</sub></i>+<i>q</i><i><sub>j</sub></i> as well. So we got two equal numbers at (<i>j</i>+1)-th step, and on each further step these numbers will just keep multiplying by two until we encounter a new segment endpoint and summation left boundaries change.<br /><br />This allows to obtain a O(<i>n</i>log<i>n</i>) solution, where n is the number of segments: instead of computing all individual values of <i>p</i><i><sub>j</sub></i> and <i>q</i><i><sub>j</sub></i>, we will split our string into blocks between the segment endpoints, and in each block we will only store the first number, and all following numbers will be 2x the previous number. The formula for the sum of a geometric progression allows to handle such segments quickly.<br /><br />Thanks for reading, and check back soon for more summaries and for some ICPC blogging!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/JT4j2oqvwSQ" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2018/04/a-binary-block-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-6286456693107879302018-04-08T00:39:00.000+03:002018-04-08T00:39:08.272+03:00Google Code Jam qualification - last chance<div dir="ltr" style="text-align: left;" trbidi="on">There's about 4 hours left in <a href="https://codejam.withgoogle.com/2018/challenges/00000000000000cb/dashboard">the Google Code Jam 2018 qualification round</a>. There were some stability issues with the new system earlier in the day, but they seem to have been resolved, so now's your chance to join the Code Jam if you haven't already. As usual I'm setting some problems this year, and I hope you'll find them interesting!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/f8Qe7DxUyUM" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2018/04/google-code-jam-qualification-last.htmltag:blogger.com,1999:blog-1953325079793449971.post-83886234334845185572018-03-05T00:58:00.001+03:002018-03-05T00:58:31.632+03:00A power of two 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/-_OX1545KgyE/WpvESMq5ZhI/AAAAAAAB_OY/_ZM3S3TLKcMGsspuJ12JIJjK0eUGfmgJACLcBGAs/s1600/ya2018r1top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="391" data-original-width="1193" height="208" src="https://1.bp.blogspot.com/-_OX1545KgyE/WpvESMq5ZhI/AAAAAAAB_OY/_ZM3S3TLKcMGsspuJ12JIJjK0eUGfmgJACLcBGAs/s640/ya2018r1top5.png" width="640" /></a></div>This week's contests were concentrated on the weekend. First, Yandex.Algorithm 2018 Round 1 has brought back the "open/blind" submission format on Saturday (<a href="https://contest.yandex.com/algorithm2018/contest/7636/problems/">problems with Yandex login</a>, <a href="https://contest.yandex.com/algorithm2018/contest/7636/standings/">results</a>, top 5 on the left, <a href="https://youtu.be/2OhhyMS_v4U">my screencast</a>, <a href="http://codeforces.com/blog/entry/58135">analysis</a>). It turned out that it doesn't really matter whether to choose open or blind if one gets all problems correct from the first try, and is the only one to solve everything :) Congratulations to tourist!<br /><br /><a href="https://contest.yandex.com/algorithm2018/contest/7636/problems/E/">Problem E</a> has a deceptively easy solution in the analysis, and yet it seems really hard to come up with. You are given a sequence of 100000 positive integers up to a billion. You need to find any integer <i>k</i> such that it's possible to transform our sequence into a strictly increasing sequence of positive integers by subtracting some of its elements from k (in other words, by replacing <i>x<sub>i</sub></i> by <i>k</i>-<i>x<sub>i</sub></i> for some set of <i>i</i>'s). Can you see why this problem is actually quite simple?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-GpES1erWEWA/Wpxc9303JnI/AAAAAAAB_TI/NcisX8hwvhQJxElR6PcZ_9Q5H0aqz51ggCLcBGAs/s1600/cf468top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="273" data-original-width="1106" height="156" src="https://2.bp.blogspot.com/-GpES1erWEWA/Wpxc9303JnI/AAAAAAAB_TI/NcisX8hwvhQJxElR6PcZ_9Q5H0aqz51ggCLcBGAs/s640/cf468top5.png" width="640" /></a></div>On Sunday Codeforces hosted its Round 468 (<a href="http://codeforces.com/contest/930">problems</a>, <a href="http://codeforces.com/contest/930/standings">results</a>, top 5 on the left, <a href="https://youtu.be/MDeRGstm8Zg">my screencast</a>). It was V--o_o--V's turn to be head and shoulders above the competition, finishing all problems in less than an hour. Well done!<br /><br />The hardest <a href="http://codeforces.com/contest/930/problem/E">problem E</a> involved finding an appropriate dynamic programming angle that allows "coordinate compression" to work. Consider an unknown binary string of length <i>k</i>, <i>k</i> is up to a billion. You're given up to 100000 segments [<i>a</i><i><sub>i</sub></i>,<i>b</i><i><sub>i</sub></i>], and know that each of those segments contains at least one 0. In a similar vein, you're also given up to 100000 segments [<i>c</i><i><sub>i</sub></i>,<i>d</i><i><sub>i</sub></i>], and know that each of those segments contains at least one 1. How many such binary strings exist, modulo 10<sup>9</sup>+7?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-FWvRIagDnVM/WpxrUBmwX8I/AAAAAAAB_Tc/VINNZW-pd8oAZ2kpjGzEMqJsZwMyPfXSgCLcBGAs/s1600/IMG_20180208_145857.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="909" data-original-width="1600" height="362" src="https://3.bp.blogspot.com/-FWvRIagDnVM/WpxrUBmwX8I/AAAAAAAB_Tc/VINNZW-pd8oAZ2kpjGzEMqJsZwMyPfXSgCLcBGAs/s640/IMG_20180208_145857.jpg" width="640" /></a></div><a href="http://petr-mitrichev.blogspot.com/2018/02/an-infinite-ratio-week.html">Last week</a>, I have mentioned a TopCoder combinatorics problem: find the sum of 2<sup><i>x</i><sub>1</sub></sup> (two to the power of the minimum number) over all possible ways to choose <i>k</i> distinct positive integers up to <i>n</i>: 1<=<i>x</i><sub>1</sub><<i>x</i><sub>2</sub><...<<i>x</i><sub><i>k</i></sub><=<i>n</i>, where <i>n</i> is up to a billion, and <i>k</i> is up to a million.<br /><br />The key idea is: instead of summing 2<sup><i>x</i><sub>1</sub></sup> for each combination, which seems hard to do, we will further subdivide each combination into 2<sup><i>x</i><sub>1</sub>-1</sup> different objects, so that we just need to count the number of objects and multiply by 2. More specifically, if we have <i>k</i> distinct positive integers, and the smallest is <i>x</i><sub>1</sub>, then there are exactly 2<sup><i>x</i><sub>1</sub>-1</sup> ways to add some subset of numbers between 1 and <i>x</i><sub>1</sub>-1 to it. As a result, we get a set of <i>at least</i> <i>k</i> distinct positive integers. And moreover, we can obtain all such sets: each such set can be obtained by subdividing the set of <i>k</i> its largest numbers. So we need to return 2 times the number of ways to choose at least <i>k</i> objects out of <i>n</i>, which is much easier to compute.<br /><br />Thanks for reading, and check back next week!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/bDPI20Xfu7k" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2018/03/a-power-of-two-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-46551557178935470292018-02-26T00:16:00.001+03:002018-02-26T00:25:49.609+03:00An infinite ratio 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/-PgPU6mih2ao/WpMdEY7N1cI/AAAAAAAB-70/6R7H3gNY_AcGjkF9F9Q8kE65ggw8ySuxgCLcBGAs/s1600/srm730top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="94" data-original-width="637" src="https://1.bp.blogspot.com/-PgPU6mih2ao/WpMdEY7N1cI/AAAAAAAB-70/6R7H3gNY_AcGjkF9F9Q8kE65ggw8ySuxgCLcBGAs/s1600/srm730top5.png" /></a></div>This week had a round from each of the platforms I usually cover. First off, TopCoder held SRM 730 on Tuesday (<a href="https://community.topcoder.com/stat?c=round_overview&rd=17087">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17087&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/57870?#comment-415959">analysis</a>). The competition was ultimately decided during the challenge phase where I was basically very lucky: my room had 8 incorrect solutions for the 250, and I've managed to bring down 4 of those; ACRush had only 4 incorrect solutions in his room, one of those was challenged by somebody else, and he got the other 3. Nevertheless, amazing comeback after an almost half-year break for ACRush!<br /><br />Quite unusually, <a href="https://community.topcoder.com/stat?c=problem_statement&pm=14795&rd=17087">the hard problem</a> was solved by ksun48 in less than 5 minutes. The problem asked to find the sum of 2<sup><i>x</i><sub>1</sub></sup> (two to the power of the minimum number) over all possible ways to choose <i>k</i> distinct positive integers up to <i>n</i>: 1<=<i>x</i><sub>1</sub><<i>x</i><sub>2</sub><...<<i>x</i><sub><i>k</i></sub><=<i>n</i>, where <i>n</i> is up to a billion, and <i>k</i> is up to a million.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-rAf3_VR5Ygk/WpMdovKfd4I/AAAAAAAB-78/P405GKvGYngTz-GOvCldQwWG9C1s8oz6QCLcBGAs/s1600/agc021top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="443" data-original-width="905" height="313" src="https://1.bp.blogspot.com/-rAf3_VR5Ygk/WpMdovKfd4I/AAAAAAAB-78/P405GKvGYngTz-GOvCldQwWG9C1s8oz6QCLcBGAs/s640/agc021top5.png" width="640" /></a></div>Next up was AtCoder Grand Contest 021 on Saturday (<a href="https://agc021.contest.atcoder.jp/assignments">problems</a>, <a href="https://agc021.contest.atcoder.jp/standings">results</a>, top 5 on the left, <a href="https://img.atcoder.jp/agc021/editorial.pdf">analysis</a>, <a href="https://youtu.be/dsqWOAvOsA8">my screencast</a>). tourist was nearly unstoppable this time, earning his first place with about 25 minutes left in the contest. Egor in 3rd place had the most realistic chance to overtake him thanks to a creative strategy, as he decided to avoid spending more time to earn the fairly technical final 300 points in the partial-scoring problem F, and instead focused on problem E which would give 1200 points if solved. Unfortunately 25 minutes were still not enough for that. Nevertheless, congratulations to both!<br /><br /><a href="https://agc021.contest.atcoder.jp/tasks/agc021_b">Problem B</a> was quite cute. You are given 100 points on the plane. For each given point, consider the part of the plane where it is the closest of the given points (a Voronoi diagram). Some of the parts will be finite, and some will be infinite. What are the relative areas of the infinite parts (see the problem statement for the formal description)?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-snYM0Sc0HTc/WpMeFcgE_0I/AAAAAAAB-8A/FlEOgytsT38CQvJKXwcHBruyyRPC7OkrQCLcBGAs/s1600/oc1718saratovtop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="215" data-original-width="835" height="164" src="https://3.bp.blogspot.com/-snYM0Sc0HTc/WpMeFcgE_0I/AAAAAAAB-8A/FlEOgytsT38CQvJKXwcHBruyyRPC7OkrQCLcBGAs/s640/oc1718saratovtop5.png" width="640" /></a></div>Sunday started with the Open Cup Grand Prix of Saratov (<a href="http://opencup.ru/files/oci/gp13/problems1-e.pdf">problems</a>, <a href="http://opentrains.snarknews.info/~ejudge/res/res10413">results</a>, top 5 on the left). Six teams were able to solve 11 this time, but team Past Glory has managed to do that without a single incorrect attempt — amazing!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-SdxoXhNSVrI/WpMeeKZxJII/AAAAAAAB-8M/sm8X9eVo3VwkWvTI6lFEE6rndbRPPNCTACLcBGAs/s1600/cf467top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="272" data-original-width="1105" height="156" src="https://2.bp.blogspot.com/-SdxoXhNSVrI/WpMeeKZxJII/AAAAAAAB-8M/sm8X9eVo3VwkWvTI6lFEE6rndbRPPNCTACLcBGAs/s640/cf467top5.png" width="640" /></a></div>After a short break, Codeforces Round 467 wrapped up the week (<a href="http://codeforces.com/contest/936">problems</a>, <a href="http://codeforces.com/contest/936/standings">results</a>, top 5 on the left, <a href="https://youtu.be/WC8iTUwViOU">my screencast</a>). mnbvmar has earned his first place by solving 4 problems in just over an hour, 15 minutes faster than anybody else — and then protected his lead from Syloviaely's surge by finding 5 successful challenges. Very well done!<br /><br /><a href="http://codeforces.com/contest/936/problem/C">Problem C</a> provided a level playing field for experienced and inexperienced competitors, as it had nothing to do with standard algorithms or even standard ideas. You are given a string <i>s</i> of length 2000, and need to transform it into a string <i>t</i> of the same length using at most 6100 operations, or report that it's impossible. In one operation, you can split the current string into two, reverse the second part, and then put the first part after the reversed second part: for example, you can obtain the string <i>fedcab</i> from the string <i>abcdef</i> in one operation. Either part is allowed to be empty. Can you see a way to do the transformation of length <i>n</i> in at most 3<i>n</i> operations? Somewhat surprisingly, there are many working approaches in this problem.<br /><br />Thanks for reading, and check back next week!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/Fev6opPg9bU" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2018/02/an-infinite-ratio-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-6062008360648049262018-02-18T22:49:00.002+03:002018-02-19T12:16:00.508+03:00A Fenwick bound 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/-awKrgQjT350/WomSwzr2qjI/AAAAAAAB-2M/zVG2IlWG3joqtmemRnDmLo46kp1FI3jzACLcBGAs/s1600/cf462top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="272" data-original-width="1102" height="157" src="https://3.bp.blogspot.com/-awKrgQjT350/WomSwzr2qjI/AAAAAAAB-2M/zVG2IlWG3joqtmemRnDmLo46kp1FI3jzACLcBGAs/s640/cf462top5.png" width="640" /></a></div>Codeforces was quite active this week with two Division 1 rounds. The 462nd one took place on Wednesday (<a href="http://codeforces.com/contest/933">problems</a>, <a href="http://codeforces.com/contest/933/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/57763">analysis</a>). Um_nik was the only one able to solve all problems, submitting one in the last minute — but he would've won without that one anyway. Congratulations on the great performance!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-wPeOFwyYe0w/WomTpEUvugI/AAAAAAAB-2U/iHnypLHmY1UZAPXx4idNdRAsn9hp-iTBQCLcBGAs/s1600/cf463top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="270" data-original-width="1104" height="156" src="https://3.bp.blogspot.com/-wPeOFwyYe0w/WomTpEUvugI/AAAAAAAB-2U/iHnypLHmY1UZAPXx4idNdRAsn9hp-iTBQCLcBGAs/s640/cf463top5.png" width="640" /></a></div>Round 463 took place on Thursday (<a href="http://codeforces.com/contest/932">problems</a>, <a href="http://codeforces.com/contest/932/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/57796">analysis</a>). It was Radewoosh's turn to be the only competitor to solve all problems, with 7 minutes to spare this time. Well done!<br /><br />He <a href="http://codeforces.com/blog/entry/57257">will be representing</a> his university in the upcoming ICPC World Finals in Beijing, along with a few others that you can see in the screenshots on the left, so the competition there promises to be very interesting :)<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-pk4T1lcwi-E/WomWgMWcaxI/AAAAAAAB-2g/ScEKlOCldAY8899XQvtQczwQw5ont7LCQCLcBGAs/s1600/oc1718gomeltop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="208" data-original-width="802" height="164" src="https://4.bp.blogspot.com/-pk4T1lcwi-E/WomWgMWcaxI/AAAAAAAB-2g/ScEKlOCldAY8899XQvtQczwQw5ont7LCQCLcBGAs/s640/oc1718gomeltop5.png" width="640" /></a></div>Finally, the Open Cup Grand Prix of Gomel on Sunday provided another glimpse into full team performances (<a href="http://opentrains.snarknews.info/~ejudge/res/res10412">results</a>, top 5 on the left). Moscow SU team Red Panda has found the winning ways again, this time thanks to being the only team to solve problem I — and doing it in the beginning of the third hour of the contest, which is quite unusual for a problem with only one solver. Congratulations!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-WEfvf-hmRJM/WomYxZ4FE1I/AAAAAAAB-2w/xqqyJFnE1i0b1I_1PVw9XubXs64dTi58QCLcBGAs/s1600/IMG_20180205_124154.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/-WEfvf-hmRJM/WomYxZ4FE1I/AAAAAAAB-2w/xqqyJFnE1i0b1I_1PVw9XubXs64dTi58QCLcBGAs/s640/IMG_20180205_124154.jpg" width="640" /></a></div><a href="http://petr-mitrichev.blogspot.com/2018/02/a-leafy-week.html">Last week</a>, I have mentioned a data structure problem from the Open Cup. <i>n</i> people are coming to lunch and forming a queue. The people are split into disjoint groups. When <i>i</i>-th person comes to the lunch, if there's nobody from their group <i>c<sub>i</sub></i> already in the queue, they stand at the back of the queue. When there is somebody from their group already in the queue, they can also stand next to any such person (directly before or after), but only if they would be cutting in front of at most <i>a<sub>i</sub></i> people by doing so. If they have multiple positions where they can join the queue according to the above restrictions, they always pick the front-most one. Initially the queue is empty. Given the values of <i>c<sub>i</sub></i> and <i>a<sub>i</sub></i> in the order the people come to lunch, how will the final queue look like?<br /><br />One could immediately start thinking about standard approaches applicable in this problem. The fact that we need to be able to run a query against the last <i>a<sub>i</sub></i> people in the queue suggests that we should probably use a balanced tree that supports quick splitting, like a treap, and maintain the size of the subtree plus some additional structures necessary to answer queries in each node. This approach can probably be made to work, but the nice thing about the problem is that we can obtain a much easier to code solution.<br /><br />Since every person only ever joins the queue either in last position, or next to a person from their group, if we maintain the queue as a list of segments of people from the same group, in other words as a list of (group, counter) pairs, then the only operations we need to support is to increment a counter and to add a new group to the end of the list. Now in order to find a place for the next person we need to find the set of groups corresponding to the last <i>a<sub>i</sub></i>+1 people, and then find the first group of the required type in that set.<br /><br />In order to find the boundary on the group level, we need to be able to find the largest prefix for which the sum of counters does not exceed a given value. This can be done in O(log<i>n</i>) by maintaining the counters in <a href="http://petr-mitrichev.blogspot.com/2013/05/fenwick-tree-range-updates.html">a Fenwick tree</a>, I will give more details below.<br /><br />And in order to find the first group of the required kind after the given one, we can simply maintain a vector of indices of groups for each kind. Since we only ever create new groups at the end, these indices never change, and a simple binary search can find the first group of the given kind after a given index.<br /><br />Finally, after we know what happens with groups we know at which position does each person enter the queue, but we still need to output the final order. This can be done using the same Fenwick tree with "largest prefix with sum not exceeding <i>x</i>" operation we already used: we go from the end and maintain the free spots in the Fenwick tree.<br /><br />So instead of a balanced tree with extra information in nodes, we've managed to get by using two very easy to code data structures: a Fenwick tree, and a vector. The solution is O(<i>n</i>log<i>n</i>), and the constant hidden in O() is also really small.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-E6bkp1G9WUQ/WonYDa4qttI/AAAAAAAB-3E/hP1Kq8fxV2cG5V3F8N7peZ0u0O_yJYU1wCLcBGAs/s1600/IMG_20180205_125812.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" data-original-height="1200" data-original-width="1600" height="480" src="https://1.bp.blogspot.com/-E6bkp1G9WUQ/WonYDa4qttI/AAAAAAAB-3E/hP1Kq8fxV2cG5V3F8N7peZ0u0O_yJYU1wCLcBGAs/s640/IMG_20180205_125812.jpg" width="640" /></a></div>This solution used the following non-standard operation on <a href="http://petr-mitrichev.blogspot.com/2013/05/fenwick-tree-range-updates.html">a Fenwick tree</a>: find the largest prefix with sum not exceeding <i>x</i>. A naive implementation using binary search and Fenwick prefix sums would give O(log<sup>2</sup><i>n</i>) complexity, which would most likely still be fast enough to get the problem accepted. However, <a href="http://codeforces.com/profile/tgehr">tgehr</a> has pointed out to me that the standard Fenwick tree allows an extremely simple O(log<i>n</i>) way to answer this question.<br /><br />Suppose our Fenwick tree has <i>n</i> elements, and <i>k</i> is the largest power of 2 not exceeding <i>n</i>. The (2<sup><i>k</i></sup>-1)-th element of the Fenwick tree array contains the sum <i>s</i> of elements on the segment [0;2<sup><i>k</i></sup>-1], so by comparing <i>x</i> with just this number we know if our answer is below or above 2<sup><i>k</i></sup>. Let's suppose it's above 2<sup><i>k</i></sup>. Then we notice that (2<sup><i>k</i></sup>+2<sup><i>k-1</i></sup>-1)-th element of the Fenwick tree array contains the sum of elements on the segment [2<sup><i>k</i></sup>;2<sup><i>k</i></sup>+2<sup><i>k-1</i></sup>-1], so by comparing <i>x</i>-<i>s</i> with just this number we know if our answer is below or above 2<sup><i>k</i></sup>+2<sup><i>k-1</i></sup>. We continue traversing the powers of two in the same manner, and it turns out that the standard Fenwick tree stores exactly the sums needed to execute this binary search! Here's the actual code:<br /><br /><pre style="font-family: "Courier New"; font-size: 9pt;"><span style="color: navy; font-weight: bold;">private int </span>upperBound(<span style="color: navy; font-weight: bold;">int</span>[] f, <span style="color: navy; font-weight: bold;">int </span>x) {<br /> <span style="color: navy; font-weight: bold;">int </span>res = <span style="color: blue;">0</span>;<br /> <span style="color: navy; font-weight: bold;">int </span>max = Integer.<span style="font-style: italic;">numberOfTrailingZeros</span>(<br /> Integer.<span style="font-style: italic;">highestOneBit</span>(f.<span style="color: #660e7a; font-weight: bold;">length</span>));<br /> <span style="color: navy; font-weight: bold;">for </span>(<span style="color: navy; font-weight: bold;">int </span>k = max; k >= <span style="color: blue;">0</span>; --k) {<br /> <span style="color: navy; font-weight: bold;">int </span>p = res + (<span style="color: blue;">1 </span><< k) - <span style="color: blue;">1</span>;<br /> <span style="color: navy; font-weight: bold;">if </span>(p < f.<span style="color: #660e7a; font-weight: bold;">length </span>&& f[p] <= x) {<br /> x -= f[p];<br /> res += <span style="color: blue;">1 </span><< k;<br /> }<br /> }<br /> <span style="color: navy; font-weight: bold;">return </span>res;<br />}</pre><pre style="font-family: "Courier New"; font-size: 9pt;"></pre>Thanks for reading, and check back next week.</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/nDCbo53MML8" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2018/02/a-fenwick-bound-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-77502096597372205262018-02-12T01:33:00.002+03:002018-02-12T01:33:48.754+03:00A leafy 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/-Lc0I4uXSuXk/WoCzS85OQjI/AAAAAAAB-jo/CBZczFflSIEdf5i3u6u9Z9_LLLBej1UDwCLcBGAs/s1600/srm729top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="95" data-original-width="639" height="94" src="https://4.bp.blogspot.com/-Lc0I4uXSuXk/WoCzS85OQjI/AAAAAAAB-jo/CBZczFflSIEdf5i3u6u9Z9_LLLBej1UDwCLcBGAs/s640/srm729top5.png" width="640" /></a></div>This week featured two weekend contests. First, TopCoder SRM 729 took place on Saturday (<a href="https://community.topcoder.com/stat?c=round_overview&rd=17082">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17082&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://youtu.be/Ugf5kbxmV_8">my screencast with commentary</a>). If you sum up the problem columns in the screenshot on the left, you can notice that the sum doesn't match the score column, and that's because the match presented ample opportunities for challenging. You can see on the screencast as I try to prepare an uber-challenge-case for the 450 during the intermission, and spent the beginning of the challenge phase getting it to work, while many solutions were already being challenged. uwi has made the best use of the challenge opportunities and thus claimed the first place. Well done!<br /><br />Most of the challenge opportunities presented themselves in <a href="https://community.topcoder.com/stat?c=problem_statement&pm=14716&rd=17082">the medium problem</a>, which looked very standard at first glance. You are given a 1000x1000 grid. In one jump, you can move from a cell to any other cell that's <i>at least</i> the given distance <i>d</i> away — you can't jump very close. What is the smallest number of jumps required to get from one given cell to another given cell?<br /><br />We could use a standard breadth-first search to solve this problem, but we have 1 million cells and potentially 1 million jumps from each cell, so the total running time would be on the order of 10<sup>12</sup> which is too slow. Can you see at least one way to speed this solution up? (there are many!)<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-LzovCJtgAVM/WoC2if692jI/AAAAAAAB-j0/wo5tqAS8xooSkg_5XqtL1qpxMkl-ivUnwCLcBGAs/s1600/oc1718khamovnikitop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="356" data-original-width="1508" height="150" src="https://3.bp.blogspot.com/-LzovCJtgAVM/WoC2if692jI/AAAAAAAB-j0/wo5tqAS8xooSkg_5XqtL1qpxMkl-ivUnwCLcBGAs/s640/oc1718khamovnikitop5.png" width="640" /></a></div>The other weekend contest was the Open Cup 2017-18 Grand Prix of Khamovniki (<a href="http://opentrains.snarknews.info/~ejudge/res/res10411">results</a>, top 5 on the left). Unlike the previous round, the active ICPC teams from Russia were not at the top of the standings, with only two ICPC teams from Asia and a veteran team Past Glory able to solve 10 problems — congratulations, and especially to Seoul National U 2 team for another Open Cup victory!<br /><br /><a href="https://official.contest.yandex.ru/opencupXVIII/contest/7410/problems/D/">Problem D</a> "Lunch Queue" was from the rare species of data structure problems that I enjoyed solving. <i>n</i> people are coming to lunch and forming a queue. The people are split into disjoint groups. When <i>i</i>-th person comes to the lunch, if there's nobody from their group <i>c<sub>i</sub></i> already in the queue, they stand at the back of the queue. When there is somebody from their group already in the queue, they can also stand next to any such person (directly before or after), but only if they would be cutting in front of at most <i>a<sub>i</sub></i> people by doing so. If they have multiple positions where they can join the queue according to the above restrictions, they always pick the front-most one. Initially the queue is empty. Given the values of <i>c<sub>i</sub></i> and <i>a<sub>i</sub></i> in the order the people come to lunch, how will the final queue look like?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-HrwOnXLaIrQ/WoDEeesX_5I/AAAAAAAB-k8/VSRIGkUmZYI8pxDgyKrQVqF6jC-sJk4MgCLcBGAs/s1600/IMG_20180120_134215.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="817" data-original-width="1600" height="326" src="https://1.bp.blogspot.com/-HrwOnXLaIrQ/WoDEeesX_5I/AAAAAAAB-k8/VSRIGkUmZYI8pxDgyKrQVqF6jC-sJk4MgCLcBGAs/s640/IMG_20180120_134215.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2018/02/a-red-panda-week.html">my previous summary</a>, I have mentioned a hard AtCoder problem: you are given a rooted tree with <i>n</i> vertices, and each vertex contains an integer between 1 and <i>n</i>, each number appearing exactly once. Your goal is to rearrange the numbers in such a way that vertex 1 has number 1, vertex 2 has number 2, and so on. You're allowed to do the following transformation: take the path connecting the root of the tree with any vertex <i>v</i>, and cyclically rotate it, placing the number that was in root into <i>v</i>, the number that was in <i>v</i> into the parent of <i>v</i>, and so on — essentially a generalization of insertion sort from a single path to an arbitrary tree. You need to sort the tree in at most 25000 operations for <i>n</i>=2000.<br /><br />I did not solve the problem myself, so I will describe the solution from the official analysis. First, we can notice that given any leaf, we can put the correct value into it in <=<i>n</i> operations (first pull it up to the root, then put it into the leaf in one rotation, and then never touch this leaf again, so we could sort everything in <i>n</i><sup>2</sup> operations, which is too much.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-yD6nzIjFeMQ/WoDDiLabZlI/AAAAAAAB-kg/cH1yleFlC38Y3YO6x2g5Qht3rCwj4RPTACKgBGAs/s1600/IMG_20180211_231731.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" data-original-height="858" data-original-width="1600" height="213" src="https://1.bp.blogspot.com/-yD6nzIjFeMQ/WoDDiLabZlI/AAAAAAAB-kg/cH1yleFlC38Y3YO6x2g5Qht3rCwj4RPTACKgBGAs/s400/IMG_20180211_231731.jpg" width="400" /></a></div>However, we can notice that in this approach we have quite a lot of freedom for choosing the moves that pull the given number up. We could try to use this freedom to try to pull up the numbers for all leaves, not just for one leaf. But even that would not be enough, as when our rooted tree is a chain it only has one leaf. However, we know that for a chain a simple solution is possible, called the normal insertion sort: we'll do exactly <i>n</i> operations, and after <i>k</i> operations we'd have <i>k</i> bottom numbers of the chain already sorted in correct order, in each turn inserting the new number to the appropriate place.<br /><br />Now we need to combine the ideas of pulling the required number from anywhere in the tree with the idea of filling a chain in one O(<i>n</i>) operation stage in such a way that the number of stages would be O(log(<i>n</i>)) for any rooted tree. More precisely, we will find all <i>leaf chains</i> in the tree — chains that hang at the bottom with nothing else attached to them, and fill them all with correct values in one stage. This guarantees O(log(<i>n</i>)) stages since the number of leaves is divided by at least two after each stage.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-4sdw9pAN-Pk/WoDDnJhsUCI/AAAAAAAB-ko/2oavhsGNvUQzRAw4LjV15sa4KAvGhZ0OwCKgBGAs/s1600/IMG_20180211_232515.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1600" data-original-width="1330" height="640" src="https://2.bp.blogspot.com/-4sdw9pAN-Pk/WoDDnJhsUCI/AAAAAAAB-ko/2oavhsGNvUQzRAw4LjV15sa4KAvGhZ0OwCKgBGAs/s640/IMG_20180211_232515.jpg" width="530" /></a></div>Whenever the root of the tree has a <i>useful</i> value — one that must be in one of the leaf chains — we will send it there, inserting it into the correct place relative to other values that we've sent to the same leaf chain, just like the insertion sort approach above. And when the root has a useless value, we need to send it somewhere, so let's send it to any position which contains a useful number, but such that all its subtree contains either only useless numbers, or useful numbers that are already placed into the corresponding leaf chain (in other words, the numbers that we don't need to get to the root anymore). This will push this useful number towards the root, and create a subtree that doesn't have any numbers that we want to get to the root.<br /><br />Why does this cycle finish eventually, and more importantly why does it run in O(<i>n</i>) operations? Each useful value passes through the root only once. A useless value, after passing through the root, ends up being in a dormant subtree, and would never pass through the root again, unless we need to touch this subtree because we're putting a useful value into it. In each such operation, at most one value moves from a dormant subtree back into circulation, and thus can reach the root again. So the total number of times a useless value that we've already seen once returns to the root does not exceed the total number of times we put a useful value into its place, meaning that the total number of operations for one stage is at most <i>n</i> plus total size of leaf paths, so O(<i>n</i>).<br /><br />Thanks for reading, and check back next week!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/wO-7fBCpt1c" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2018/02/a-leafy-week.html