tag:blogger.com,1999:blog-19533250797934499712017-04-23T23:59:50.853+03:00Algorithms Weekly by Petr MitrichevPetr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.comBlogger297125PetrMitrichevhttps://feedburner.google.comtag:blogger.com,1999:blog-1953325079793449971.post-27096012581152710182017-04-09T01:32:00.001+03:002017-04-09T23:28:14.253+03:00A dominator week<div dir="ltr" style="text-align: left;" trbidi="on">First of all, please note that there's still a bit more than 3 hours left in the <a href="https://code.google.com/codejam/contest/3264486/dashboard">Google Code Jam qualification</a>. You can still hop on the Code Jam train!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-F52NSojq9YQ/WOlR50PGBcI/AAAAAAAByyE/maj-AwMqtcseIbkIPL6dM2oojJiNlQNXACLcB/s1600/cf407top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="158" src="https://1.bp.blogspot.com/-F52NSojq9YQ/WOlR50PGBcI/AAAAAAAByyE/maj-AwMqtcseIbkIPL6dM2oojJiNlQNXACLcB/s640/cf407top5.png" width="640" /></a></div>The last week was of the extremely busy type. First off, Codeforces Round 407 took place on Wednesday (<a href="http://codeforces.com/contest/788">problems</a>, <a href="http://codeforces.com/contest/788/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/51312">analysis</a>). -XraY- and Um_nik stood out from the pack by solving all problems, and slightly better speed has earned -XraY- his first - but definitely not his last - victory of the week. Congratulations!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-AGaOSv7NDXo/WOlSSJP3WvI/AAAAAAAByyI/SNw65B-rzSkXum-SMJmMgwmeatvWb2WCwCLcB/s1600/hc22017top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="247" src="https://4.bp.blogspot.com/-AGaOSv7NDXo/WOlSSJP3WvI/AAAAAAAByyI/SNw65B-rzSkXum-SMJmMgwmeatvWb2WCwCLcB/s320/hc22017top5.png" width="320" /></a></div>A Swiss-resident-only Helvetic Coding Contest 2017 took place on Saturday (<a href="http://hc2.ch/scoreboard.html">results</a>, top 5 on the left). Just like last year, the problems will be used for an online mirror some time later, so I will not spoil you the fun of solving them.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-LGFI36HMmcg/WOlS1RcYckI/AAAAAAAByyU/6235WD0R2-wuGpPtURKV6d25TZOq7nHwgCLcB/s1600/agc012top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="313" src="https://4.bp.blogspot.com/-LGFI36HMmcg/WOlS1RcYckI/AAAAAAAByyU/6235WD0R2-wuGpPtURKV6d25TZOq7nHwgCLcB/s640/agc012top5.png" width="640" /></a></div>AtCoder Grand Contest 012 took place at the same time (<a href="http://agc012.contest.atcoder.jp/assignments">problems</a>, <a href="http://agc012.contest.atcoder.jp/standings">results</a>, top 5 on the left, <a href="https://atcoder.jp/img/agc012/editorial.pdf">analysis</a>). -XraY-'s second (but still not his last) victory was more clear-cut than the first one, as he managed to solve five problems fifteen minutes faster than everybody else, and was the only one at the top without any penalty minutes. Well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-FzyOiHu8Gcw/WOlTZaKH4vI/AAAAAAAByyY/a8jGsk7Pb7ccafbgxXLqu2OWe4wAanc0wCLcB/s1600/tco17r1atop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="82" src="https://3.bp.blogspot.com/-FzyOiHu8Gcw/WOlTZaKH4vI/AAAAAAAByyY/a8jGsk7Pb7ccafbgxXLqu2OWe4wAanc0wCLcB/s640/tco17r1atop5.png" width="640" /></a></div>A few hours later TopCoder Open 2017 has taken off with its Round 1A (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=16899">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=16899&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left). With the top 250 active coders receiving a bye into Round 2, the contest has once again given semi-retired veterans a chance to shine, and it seems that ACRush did not forget how to win TopCoder rounds :) Congratulations!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-4vFQYbojEEA/WOlT5gETemI/AAAAAAAByyc/5HrS9wIbpFIfJvsichat2k5uot3vPB6KwCLcB/s1600/oc1617tatarstantop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="154" src="https://1.bp.blogspot.com/-4vFQYbojEEA/WOlT5gETemI/AAAAAAAByyc/5HrS9wIbpFIfJvsichat2k5uot3vPB6KwCLcB/s640/oc1617tatarstantop5.png" width="640" /></a></div>Sunday took off with Open Cup 2016-17 Grand Prix of Tatarstan (<a href="http://opencup.ru/files/och/gp14/problems1-e.pdf">problems</a>, <a href="http://opencup.ru/index.cgi?data=macros/stage&head=index&menu=index&stg=14&region=main&ncup=och&class=och">results</a>, top 5 on the left), where -XraY- has earned his third and final victory of the week, this time together with his team - amazing!<br /><br />Problem E was of the kind that I prefer to give on my own contests, as it makes preparing the testcases very easy: with just two numbers in the input :) On a more serious side, here's what it was about: you are given two numbers <i>n</i> and <i>k</i>. You need to choose the smallest amount of pairs (<i>a</i>,<i>b</i>) such that <i>1</i><=<i>a</i>,<i>b</i><=<i>k</i> for each pair, and such that any sequence of <i>n</i> not necessarily distinct numbers, each between 1 and <i>k</i>, will contain at least one of your chosen pairs as a <i>subsequence</i>.<br /><br />Can you see the solution? Can you prove it?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-fPVecVE0TTY/WOlUSBxTKWI/AAAAAAAByyg/zScLOjukDJw-5NHl7nKXPhJQ8B4V7coNgCLcB/s1600/rcc2017q1top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="265" src="https://1.bp.blogspot.com/-fPVecVE0TTY/WOlUSBxTKWI/AAAAAAAByyg/zScLOjukDJw-5NHl7nKXPhJQ8B4V7coNgCLcB/s640/rcc2017q1top5.png" width="640" /></a></div>Finally, Russian Code Cup 2017 Qualification Round 1 wrapped up the week on Sunday evening (<a href="http://www.russiancodecup.ru/en/championship/round/61/">problems</a>, <a href="http://www.russiancodecup.ru/en/championship/result/61/">results</a>, top 5 on the left, <a href="http://www.russiancodecup.ru/en/press/razbor-zadach-1-go-kvalifikacionnogo-raunda-rcc-2017/">analysis</a>). Even though the main goal here was to get into the top 200, there was still a scoreboard and it was possible to get the first place - which eatmore did thanks to flawless execution without any incorrect attempts. Way to go!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-2gAWUEtoq6Q/WOlj6ch88rI/AAAAAAAByzE/p_GxJzVlkVcpxy2G-g6uKOV9A9b94FX8ACKgB/s1600/IMG_20170409_002555.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="273" src="https://2.bp.blogspot.com/-2gAWUEtoq6Q/WOlj6ch88rI/AAAAAAAByzE/p_GxJzVlkVcpxy2G-g6uKOV9A9b94FX8ACKgB/s320/IMG_20170409_002555.jpg" width="320" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2017/04/a-moejy0viiiiiv-week.html">my previous summary</a>, I have mentioned a couple of problems. The first one went like this: you are given 300 trees on the same set of 300 vertices. You want to pick exactly one edge in each tree, remove those, then add the edge you removed from <i>i</i>-th tree to the (<i>i</i>+1)-th tree, for all <i>i</i> (the edge from the last tree is added to the first one), in such a way that the resulting graphs are still trees. How many ways are there to do that, modulo 10<sup>9</sup>+7?<br /><br />Let's say we picked the edge <i>x</i>-<i>y</i> in the first tree. After we add it to the second tree, a cycle consisting of this edge and the (only) simple path from <i>x</i> to <i>y</i> in the second tree will be formed, so we need to remove any edge in the said simple path to obtain a tree again. This edge in turn will define a path on the third tree where we need to pick an edge to remove, and so on. After we make a full cycle, we need to get back to the first edge.<br /><br />If we fix the edge we pick in the first tree, we can use dynamic programming to find the number of ways to pick the edge to remove in the first <i>a</i> trees, such that <i>b</i>-th edge of the <i>a</i>-th tree is removed. This dynamic programming has O(<i>n</i><sup>2</sup>) states, each state can be processed in O(<i>n</i>) (we need to traverse the corresponding path in the next tree), and we have O(<i>n</i>) outside iterations for the edge of the first tree, so the total running time is O(<i>n</i><sup>4</sup>).<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-RDWj7kb3LfY/WOlj_Lm8mbI/AAAAAAAByzI/Mzkc_XtLbrkOKzH5s_g9MbOD0x75BbK7wCKgB/s1600/IMG_20170409_002601.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" height="315" src="https://4.bp.blogspot.com/-RDWj7kb3LfY/WOlj_Lm8mbI/AAAAAAAByzI/Mzkc_XtLbrkOKzH5s_g9MbOD0x75BbK7wCKgB/s400/IMG_20170409_002601.jpg" width="400" /></a></div>However, we can notice that the innermost O(<i>n</i>) is used to support an operation "add a constant to all edges of the tree along the given path". Here's how we can do it faster. Every path in a tree always goes towards the root until we reach the <i>lowest common ancestor</i>, then away from root. Now, instead of having values on edges and adding a constant <i>c</i> to the entire path from <i>x</i> to <i>y</i>, we can have values in vertices in such a way that the value for each edge is computed as the sum of values of vertices in the corresponding subtree, and then in order to add a constant to a path we need to add <i>c</i> to vertices <i>x</i> and <i>y</i>, and subtract 2<i>c</i> from <i>lca</i>(<i>x</i>, <i>y</i>) - just 3 numbers to be updated. This makes handling of each dynamic programming state O(1), and the total running time is now 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/-TaVeU5sMrP4/WOlktP5u2cI/AAAAAAAByzQ/cLOb7iyBaTsa9aZcY1HAu4i3JM9sK-BhACLcB/s1600/IMG_20170408_163729.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="480" src="https://1.bp.blogspot.com/-TaVeU5sMrP4/WOlktP5u2cI/AAAAAAAByzQ/cLOb7iyBaTsa9aZcY1HAu4i3JM9sK-BhACLcB/s640/IMG_20170408_163729.jpg" width="640" /></a></div>The second problem was: you are given a directed acyclic graph with 200000 vertices and 500000 arcs. We're going to remove one of its arcs. For each vertex <i>v</i> of the graph, you have to answer a question: is it true that <i>v</i> is guaranteed to be reachable from vertex 1, no matter which arc we remove?<br /><br />This problem is closely related to the concept of <a href="https://en.wikipedia.org/wiki/Dominator_(graph_theory)">dominator tree</a>. Here, we would define that arc <i>a</i> <i>dominates</i> vertex <i>v</i>, if one must pass through <i>a</i> when going from 1 to <i>v</i>. Our goal is to tell if there are any dominating arcs for each vertex.<br /><br />It turns out the following approach (corrected by Shubham in comments below - thanks!) works: assuming we have topologically sorted our graph from left to right, let's compute the leftmost dominating arc (or the fact there's no dominating arc) for each vertex. The computation will also go from left to right, and work like this for vertex <i>u</i>: if for each vertex reachable from 1 that have arcs into <i>u</i> the leftmost dominating arc is the same, then this arc is the leftmost dominating arc for <i>u</i> as well. If that's not the case, but there's just one vertex <i>v</i> reachable from 1 that has an arc into <i>u</i>, then the arc from <i>v</i> to <i>u</i> is the leftmost dominating arc for <i>u</i> (note that in this case <i>v</i> has no dominating arcs).<br /><br />So far, everything is somewhat intuitive and easy to prove, but here comes the insight: in all other cases, there are no dominating arcs for <i>u</i>! Suppose it's not the case, and some arc <i>a</i> dominates <i>u</i>. We have at least two vertices reachable from 1 that have arcs into <i>u</i>, and the don't have the same dominating arc. Thus <i>a</i> can't be directly incoming to <i>u</i>, and at least one of the vertices that have arcs to <i>u</i> doesn't have <i>a</i> as its dominating arc, which leads to a contradiction since then we can bypass <i>a</i> on our way to <i>u</i>, too.<br /><br />Thanks for reading, and check back next week!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/9GEsf6gu4lw" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/04/a-dominator-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-57619968483540608382017-04-01T11:41:00.000+03:002017-04-01T11:41:19.205+03:00A moejy0viiiiiv 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/-s25_2Uf23dY/WN9H6H-_i3I/AAAAAAAByis/cjPaonouvoU9rqIQARVHWaoFz2AMnSgKwCLcB/s1600/cf406top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="160" src="https://4.bp.blogspot.com/-s25_2Uf23dY/WN9H6H-_i3I/AAAAAAAByis/cjPaonouvoU9rqIQARVHWaoFz2AMnSgKwCLcB/s640/cf406top5.png" width="640" /></a></div>Last week's contests started with Codeforces Round 406 on Thursday (<a href="http://codeforces.com/contest/786">problems</a>, <a href="http://codeforces.com/contest/786/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/51163">analysis</a>). Quite surprisingly, this time the winning strategy involved going with the cheaper problem in the end instead of the more expensive one, although that <a href="http://codeforces.com/blog/entry/51083?#comment-350525">might have involved</a> squeezing through a solution that was not supposed to pass :) Nevertheless, congratulations to moejy0viiiiiv on his amazing non-asymptotic optimization skills!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-IfMmK5rYn8o/WN9HxBGvnEI/AAAAAAAByio/tltLQdzUMmgybcxqRr_cA4UeCRE3ncC1QCLcB/s1600/srm711top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="82" src="https://4.bp.blogspot.com/-IfMmK5rYn8o/WN9HxBGvnEI/AAAAAAAByio/tltLQdzUMmgybcxqRr_cA4UeCRE3ncC1QCLcB/s640/srm711top5.png" width="640" /></a></div>TopCoder SRM 711 took place on Saturday (<a href="https://community.topcoder.com/stat?c=round_overview&rd=16880">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=16880&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://youtu.be/ovKNm_LytjU">my screencast</a>). This time I've recorded the usual silent screencast, but it didn't seem to improve my results :) There was a moment with about 30 minutes left in the coding phase when I had 1224 points, which would be enough for the second place in this SRM. However, there was quite a bit of uncertainty: the solution I've submitted for the hardest problem was theoretically O(<i>n</i><sup>4</sup>) with <i>n</i> up to 300, although it seemed to behave more like O(<i>n</i><sup>3</sup>) on random testcases, and even that already took 1.5 seconds.<br /><br />I've tried to come up with a case where it would time out, could not do that, but it seemed very likely that such cases exist, so I've decided that the authors would see the obvious O(<i>n</i><sup>4</sup>) approach and make sure it fails, and implemented and submitted a true O(<i>n</i><sup>3</sup>) solution losing lots of points but avoiding the possible loss of all points for that problem. After the contest ended, I've submitted my possibly-O(<i>n</i><sup>4</sup>) solution in the practice room, and guess what? It passed the system tests as well. I could have pulled a moejy0viiiiiv :)<br /><br />The natural question, of course, is this: can you challenge that solution? It should be available in the practice room, submitted by me. The problemsetter <a href="http://codeforces.com/blog/entry/50573?#comment-350891">mentions</a> a possible idea that could make this solution fail, but I'm wondering if it actually fails in practice.<br /><br />I should also mention that even without the resubmission I could not challenge rng_58 for the first place, and his solution for that problem was O(<i>n</i><sup>3</sup>) from the start. Congratulations on the well-deserved victory!<br /><br />Here's <a href="https://community.topcoder.com/stat?c=problem_statement&pm=14506&rd=16880">the actual problem</a> I've talked so much about. You are given 300 trees on the same set of 300 vertices. You want to pick exactly one edge in each tree, remove those, then add the edge you removed from <i>i</i>-th tree to the (<i>i</i>+1)-th tree, for all <i>i</i> (the edge from the last tree is added to the first one), in such a way that the resulting graphs are still trees. How many ways are there to do that, modulo 10<sup>9</sup>+7?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-7leJkbDszbs/WN9I99p0AuI/AAAAAAAByiw/3Kfk3FWT1NAK5lkjbo4jaCso3gpyudnhACLcB/s1600/oc1617polandtop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="160" src="https://1.bp.blogspot.com/-7leJkbDszbs/WN9I99p0AuI/AAAAAAAByiw/3Kfk3FWT1NAK5lkjbo4jaCso3gpyudnhACLcB/s640/oc1617polandtop5.png" width="640" /></a></div>Open Cup 2016-17 Grand Prix of Poland has wrapped up the week on Sunday (<a href="http://opentrains.snarknews.info/~ejudge/res/res10373">results</a>, top 5 on the left). Makoto continued to be on fire, winning a team contest right after winning the individual one on Saturday. Congratulations again!<br /><br />This round had several nice problems, but if I have to pick one, it would be problem C. You are given a directed acyclic graph with 200000 vertices and 500000 arcs. We're going to remove one of its arcs. For each vertex <i>v</i> of the graph, you have to answer a question: is it true that <i>v</i> is guaranteed to be reachable from vertex 1, no matter which arc we remove?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-HvwMVKfNMck/WN9KUyhm43I/AAAAAAAByi0/gzRHNx-2Jhk1j0V_VSJLYTrj0DTjQvLRgCLcB/s1600/IMG_20170319_111737.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="480" src="https://3.bp.blogspot.com/-HvwMVKfNMck/WN9KUyhm43I/AAAAAAAByi0/gzRHNx-2Jhk1j0V_VSJLYTrj0DTjQvLRgCLcB/s640/IMG_20170319_111737.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2017/04/a-week-with-two-rows.html">my previous summary</a>, I have mentioned a Codeforces problem. You are given a grid with two rows and <i>n</i> columns, each cell containing a (not necessarily positive) integer. Your goal is to find as many non-intersecting rectangles on this grid as possible, such that each rectangle has a sum of 0. <i>n</i> is up to 300000.<br /><br />First, we can find all rectangles with zero sum. Of course, there might be too many of those, but we can notice that for each "type" of rectangle (row 1, row 2, or both rows) we can find the partial sums from column 0 to column <i>i</i>, and a zero-sum rectangle corresponds to two equal partial sums, and since in the maximum answer there would never be a rectangle that can be split into two, we only need to consider pairing each partial sum with one previous occurrence of the same value, and thus have at most <i>n</i> useful rectangles per type, at most one ending in each column.<br /><br />That observation yields a straightforward O(<i>n</i><sup>2</sup>) dynamic programming solution: we'll compute <i>a<sub>ij</sub></i> - the maximum number of rectangles that we can choose in the first <i>i</i> cells of the first row, and in the first <i>j</i> cells of the second row. In order to compute this value, we consider whether we take the single-row rectangles ending in columns <i>i</i> and <i>j</i>, and also the double-row rectangle in case <i>i</i>=<i>j</i>. But O(<i>n</i><sup>2</sup>) is obviously too slow with <i>n</i>=300000, so how to speed this up further?<br /><br />The next idea is based on the fact that we currently have too much leeway in constructing the optimal solution. Whenever we pick the single-row rectangles between two double-row ones, we can pick them in any order, and the current solution effectively considers all such ways. But let's assume we always pick them "from right to left": if our current state is (<i>i</i>,<i>j</i>) and <i>i</i>><i>j</i>, then we'll consider what happens with cell i in the first row, and if <i>i</i><<i>j</i>, we'll consider what happens with cell <i>j</i> in the second row. If we do that, then the states that are important for computing the final answer have a peculiar property: if <i>i</i><<i>j</i>, then <i>a<sub>jj</sub></i>-1<=<i>a<sub>ij</sub></i><=<i>a<sub>jj</sub></i> (and similar for <i>i</i>><i>j</i>), because if <i>a<sub>ij</sub></i><=<i>a<sub>jj</sub></i>-2, we could have skipped the last rectangle we took in the first row (that led us to <i>i</i>), and get a better answer.<br /><br />Because of this, we just need to compute the "diagonal" <i>a<sub>jj</sub></i> of the matrix, and also for each <i>j</i> find the smallest <i>i</i> that <i>a<sub>ij</sub></i> is still equal to <i>a<sub>jj</sub></i>, and the smallest <i>i</i> that that <i>a<sub>ji</sub></i> is still equal to <i>a<sub>jj</sub></i>, which we can do with binary search to obtain a O(<i>n</i>log<i>n</i>) solution.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-vYNLbuFsvjQ/WN9LEjNvE-I/AAAAAAAByi4/Bkkjh92QzMMeq6gTOFFS5e-60ianSPW1wCLcB/s1600/2016.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="310" src="https://1.bp.blogspot.com/-vYNLbuFsvjQ/WN9LEjNvE-I/AAAAAAAByi4/Bkkjh92QzMMeq6gTOFFS5e-60ianSPW1wCLcB/s400/2016.png" width="400" /></a></div>Finally, please note that <a href="https://code.google.com/codejam/">Google Code Jam 2017</a> is just around the corner - the qualification round starts on April 7! I'm setting some of the problems this year, and I hope you'll find them interesting. </div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/ODFaeLEXHP0" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/04/a-moejy0viiiiiv-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-22030669504971962192017-04-01T09:10:00.000+03:002017-04-01T09:10:09.268+03:00A week with two rows<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/-y5NcQKyQAEY/WN88aATzkxI/AAAAAAAByiU/yva3DSA061I3mrASufpCB3ajuJCfO-KugCLcB/s1600/vk2017r1top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="166" src="https://2.bp.blogspot.com/-y5NcQKyQAEY/WN88aATzkxI/AAAAAAAByiU/yva3DSA061I3mrASufpCB3ajuJCfO-KugCLcB/s640/vk2017r1top5.png" width="640" /></a></div>On the Mar 13 - Mar 19 week, VK Cup 2017 started with its Round 1 (<a href="http://codeforces.com/contest/771">problems</a>, <a href="http://codeforces.com/contest/771/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/contest/790/standings">parallel Codeforces round results</a>, <a href="https://youtu.be/9dTLvhv5U44">my screencast of the Codeforces round with commentary</a>, <a href="http://codeforces.com/blog/entry/51068">analysis</a>). Congratulations to Zlobober and zemen on the win!<br /><br />I've made a second attempt at explaining myself to the camera during the competition, and this time it it went even worse. I've managed to implement an incorrect solution for C before realizing it and rewriting from scratch, and if that wasn't bad enough followed up with doing the same - implementing an incorrect solution that needs to be dropped on the floor - <i>twice</i> for problem D. Maybe talking <i>is</i> indeed incompatible with critical thinking?..<br /><br />Here is <a href="http://codeforces.com/contest/790/problem/D">problem D</a> that has stopped me in my tracks. You are given a grid with two rows and <i>n</i> columns, each cell containing a (not necessarily positive) integer. Your goal is to find as many non-intersecting rectangles on this grid as possible, such that each rectangle has a sum of 0. <i>n</i> is up to 300000.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-0uQmmpGeEA4/WN9CwgHYx9I/AAAAAAAByig/x2S9b5HQgcEfCMr92k4unty8_yWRYhaywCLcB/s1600/IMG_20170226_175414.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="480" src="https://2.bp.blogspot.com/-0uQmmpGeEA4/WN9CwgHYx9I/AAAAAAAByig/x2S9b5HQgcEfCMr92k4unty8_yWRYhaywCLcB/s640/IMG_20170226_175414.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2017/03/a-speaking-week.html">my previous summary</a>, I have mentioned a cute AtCoder problem. You are given a huge number n with at most 500000 (decimal) digits, and need to find the smallest number <i>k</i> such that <i>n</i> can be represented as a sum of <i>k</i> numbers with non-decreasing decimal representation (for example, 1157888).<br /><div><br /></div><div>The approach I talk about in my screencast is a bit vague, and I like the approach from the editorial more. First, we notice that numbers with non-decreasing decimal representation are exactly those numbers that can be represented as a sum of 9 numbers which consist only of ones (like 1 or 1111; we will also count 0 as such a number with zero ones) - the main Young diagram trick strikes back :) So our goal is to represent <i>n</i> as a sum of 9<i>k</i> such numbers.</div><div><br /></div><div>Each such number is equal to (10<sup><i>m</i></sup>-1)/9 for some <i>m</i>, so we actually need to represent 9<i>n</i>+9<i>k</i> as a sum of exactly 9<i>k</i> numbers of form 10<sup><i>m</i></sup>. The smallest amount of such numbers needed to achieve 9<i>n</i>+9<i>k</i> is naturally given by the sum of digits in the decimal representation of 9<i>n</i>+9<i>k</i>, and is divisible by 9. We can then repeatedly replace a power of 10 with ten smaller powers to get any bigger amount divisible by 9, up to 9<i>n</i>+9<i>k</i> (when the sum is all ones). We need to achieve 9<i>k</i> which is also divisible by 9, so we just need to check if the sum of digits in the decimal representation of 9<i>n</i>+9<i>k</i> is less than or equal to 9<i>k</i>.<br /><br />Now that we know how to check any given <i>k</i>, we can use binary search to find the minimum possible value of <i>k</i>. VoilĂ !<br /><br />Thanks for reading, and check back soon for the last week's summary.</div></div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/ZC_FDB_CqzI" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/04/a-week-with-two-rows.htmltag:blogger.com,1999:blog-1953325079793449971.post-87954269586861801052017-03-27T21:47:00.000+03:002017-03-28T16:33:17.687+03:00A speaking week<div dir="ltr" style="text-align: left;" trbidi="on">Before I switch to the Mar 6 - Mar 12 week, let me correct a mistake in my previous summary: there was in fact a Codeforces round on Sunday, March 5 - but it somehow disappeared from <a href="http://clist.by/">clist.by</a>, and my memory turned out to be too short :)<br /><div><br /></div><div><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-TKUJjZbEPt0/WNlb77LQAUI/AAAAAAAByfA/THu2nJ-aZ_Md-3_i61aiJNuaNTffossFQCLcB/s1600/cf403top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="156" src="https://4.bp.blogspot.com/-TKUJjZbEPt0/WNlb77LQAUI/AAAAAAAByfA/THu2nJ-aZ_Md-3_i61aiJNuaNTffossFQCLcB/s640/cf403top5.png" width="640" /></a></div>Codeforces Round 403 was the forgotten round (<a href="http://codeforces.com/contest/781">problems</a>, <a href="http://codeforces.com/contest/781/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/50854">analysis</a>). Right after the round, I was sure that I needed a lot more debugging to get the last problem accepted - but it turned out that I was super close: the only issue was the often forgotten case of <i>a</i>=0 when solving a quadratic inequality <i>ax</i><sup>2</sup>+<i>bx</i>+<i>c</i><=0. In absence of people solving the last problem during the round it was the speed on the first five that mattered, and V--o_o--V was the quickest - congratulations!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-CXv8E58c42E/WNlcF0XUXMI/AAAAAAAByfE/0nMjYRvyueUFS3IKEM35bY9FhBb5f9T-gCLcB/s1600/srm710top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="82" src="https://2.bp.blogspot.com/-CXv8E58c42E/WNlcF0XUXMI/AAAAAAAByfE/0nMjYRvyueUFS3IKEM35bY9FhBb5f9T-gCLcB/s640/srm710top5.png" width="640" /></a></div>Now we can go back to the subject week. Early on Friday, TopCoder SRM 710 took place (<a href="https://community.topcoder.com/stat?c=round_overview&rd=16879">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=16879&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/50572?#comment-348227">analysis</a>). Just like the previous round, the hardest problem did not budge, and the round was decided on the first two. Congratulations to al13n on the victory!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-IICuwk6P6GM/WNlcs3YBrbI/AAAAAAAByfM/ZO5Whsg08Ek5yU5usjajMvqtMg7l_N1AwCLcB/s1600/agc011top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="242" src="https://2.bp.blogspot.com/-IICuwk6P6GM/WNlcs3YBrbI/AAAAAAAByfM/ZO5Whsg08Ek5yU5usjajMvqtMg7l_N1AwCLcB/s640/agc011top5.png" width="640" /></a></div>And finally, AtCoder held its Grand Contest 011 on Sunday (<a href="http://agc011.contest.atcoder.jp/assignments">problems</a>, <a href="http://agc011.contest.atcoder.jp/standings#page_1">results</a>, top 5 on the left, <a href="https://youtu.be/rsm4XDlcbRE">my screencast with commentary</a>, <a href="https://atcoder.jp/img/agc011/editorial.pdf">analysis</a>). Egor has won the contest thanks to a superior strategy, as he went for the hardest problem in the last minutes of the contest instead of the second hardest. Well done!<br /><br />I have attempted something new for this round: in addition to the screen content, I've included a camera feed in the screencast, and tried to explain aloud what I'm thinking and doing. I had two big hopes when I decided to do that: that I would actually be able to come up with more polished solutions that take less time to code if I explain them aloud first, and that my mumbling will be interesting to the viewers. The results of the round show that the first hope was likely unfounded, so now I'm really curious about the second one :)<br /><br />As far as problems go, let me highlight <a href="http://agc011.contest.atcoder.jp/tasks/agc011_e">problem E</a>. You are given a huge number <i>n</i> with at most 500000 (decimal) digits, and need to find the smallest number <i>k</i> such that <i>n</i> can be represented as a sum of <i>k</i> numbers with non-decreasing decimal representation (for example, 1157888).<br /><br />Thanks for reading, and check back soon for the next week's contests!</div></div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/Q08biq7Lr04" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/03/a-speaking-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-1374546190210552672017-03-27T15:35:00.001+03:002017-03-27T15:35:32.733+03:00An all-black 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/-DSAt1aQAv0c/WNkGbWMF0wI/AAAAAAAByeI/5QVVkJeVLbkq7-IFwgcRhTKNg_GuXNtBACKgB/s1600/IMG_20170218_152755.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="480" src="https://1.bp.blogspot.com/-DSAt1aQAv0c/WNkGbWMF0wI/AAAAAAAByeI/5QVVkJeVLbkq7-IFwgcRhTKNg_GuXNtBACKgB/s640/IMG_20170218_152755.jpg" width="640" /></a></div>In stark contrast to the previous week, the Feb 27 - Mar 5 week had no contests that I'd like to mention. However, we can of course still discuss the problems I mentioned in <a href="http://petr-mitrichev.blogspot.com/2017/02/a-7x-week.html">my previous summary</a>.<br /><br /><a href="http://mujin-pc-2017.contest.atcoder.jp/tasks/mujin_pc_2017_b">The AtCoder one</a> was concerned with a square <i>n</i> times <i>n</i> matrix with each cell either black or white. In one step, you could take an arbitrary row of the matrix, and replace an arbitrary column of the matrix with the values from the chosen row. Your goal is to make all cells black. What is the minimum number of steps required to achieve that?<br /><br />First, we can notice that if a certain column of the matrix is already all black, there's never a need to replace it, since it satisfies the final condition, and it's also the most optimal for other operations as the corresponding cell in all rows will be black.<br /><br />Second, any other column can become all black only if we have a row that is all black. Moreover, as soon as we have a row that is all black, we should immediately start replicating it to all non-all-black columns (note that the number of non-all-black columns stays constant up to this point). So the problem has been reduced to: what is the minimum number of steps required to make one row all-black?<br /><br />Now, each operation changes only one cell in each row. So if a row has <i>k</i> white cells, we will require at least <i>k</i> operations to make it all-black. Moreover, if each column has at least one black cell, then we require <i>exactly</i> <i>k</i> operations to make it all-black (since for each cell in this row we can replicate the row that has a black cell in the corresponding column). We can iterate over all rows and pick the one where this number is minimized. So the only unsolved case is when there's one or more all-white columns.<br /><br />For each all-white column, we need at least one operation to put at least one black cell in it. If the column corresponding to the row we're making all-black has at least one black cell, then we have a row which serves two purposes: when replicating it to an all-white column, we both make it not-all-white, and also put a black cell in the row we're making all-black, so in that case no extra move is needed and we can still make the row all-black in exactly <i>k</i> operations.<br /><br />Now, the very specific remaining case is: we want to make a certain row all-black, and the corresponding column is initially all-white. Then if we look at the first move that replaces this column, it's clear that the cell on the intersection of the all-black-to-be row and this column will stay white, meaning that we waste 1 move and require at least <i>k</i>+1 operation to make the row all-black. But it's easy to waste exactly one move: we just replicate any non-all-white row to the problematic column as the first move. Of course, if the board is initially all-white then there's no solution.<br /><br />That completes the solution for this problem. As you can see, each particular step is relatively straightforward and not very hard to come up with. However, one has to stitch together quite a few of those, and that's where the difficulty - and beauty - of this problem lies.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-QdYpnQTOnAo/WNkGrbTE1aI/AAAAAAAByeM/ULVEs-0cr7Q-Ajbt3o4CDZvJsOr_iH5PACKgB/s1600/IMG_20170225_104622.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" height="480" src="https://2.bp.blogspot.com/-QdYpnQTOnAo/WNkGrbTE1aI/AAAAAAAByeM/ULVEs-0cr7Q-Ajbt3o4CDZvJsOr_iH5PACKgB/s640/IMG_20170225_104622.jpg" width="640" /></a></div>The Open Cup problem was concerned with a permutation of size <i>n</i>. For each number, we can compute its radius: the largest number <i>r</i> such that <i>r</i> numbers to the left of our number, and <i>r</i> numbers to the right of our number, are all smaller than that number. For example, for the permutation "1 3 2 6 4 5" the radii are "0 1 0 2 0 0". Given the sequence of radii, how many different permutations correspond to it?<br /><br />The solution depends on one main insight: let's look for <i>n</i> (the largest number) in the permutation. Since it is the largest number, it "stops" all other radii, and thus the problem decomposes into two independent problems to the left and to the right of this number. Just this idea leads to a O(<i>n</i><sup>3</sup>) dynamic programming solution which solves the problem for each segment and tries all positions of the largest number.<br /><br />Since this was a tiny bit too slow, one needed to optimize this approach. Since the radius of the largest number always reaches either to the left or to the right boundary, and no other radius should cover the largest number, in each segment there are at most two candidates for the largest number: the rightmost position with radius reaching the left boundary, and the leftmost position with radius reaching the right boundary. Since now we have just 2 candidates to check for each segment instead of <i>n</i>, the solution works in O(<i>n</i><sup>2</sup>) which is fast enough.<br /><br />Thanks for reading, and check back soon for the next week's summary!<br /><br /></div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/N8lRRLKLIAc" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/03/an-all-black-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-44171573093718956662017-02-26T23:37:00.001+03:002017-02-26T23:37:45.999+03:00A 7x week<div dir="ltr" style="text-align: left;" trbidi="on">This week was extremely packed with competitions - I think this might be the new record for the number of scoreboards in one summary. Consequently, there were a couple nice problems, so if you haven't solved all of this week's competitions (:P), read on!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-t_dI4ic1zaQ/WLMqAZui_qI/AAAAAAABwgM/B9PN6KCdjfULMQzWZTU7FQHBu6ULC8uNQCLcB/s1600/cf399top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="156" src="https://4.bp.blogspot.com/-t_dI4ic1zaQ/WLMqAZui_qI/AAAAAAABwgM/B9PN6KCdjfULMQzWZTU7FQHBu6ULC8uNQCLcB/s640/cf399top5.png" width="640" /></a></div>First off, Codeforces held its Round 399 on Monday (<a href="http://codeforces.com/contest/768">problems</a>, <a href="http://codeforces.com/contest/768/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/50550">analysis</a>). y0105w49 and W4yneb0t had a fiery challenge competition and have managed to overtake the only contestant who solved all problems, V--o_o--V. Congratulations to all three!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-OsjomGxa7PE/WLMpCG49p0I/AAAAAAABwgI/sTYl5yXwKA4L1afS9zOsWj7r7-Dy53OEwCLcB/s1600/srm709top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" src="https://2.bp.blogspot.com/-OsjomGxa7PE/WLMpCG49p0I/AAAAAAABwgI/sTYl5yXwKA4L1afS9zOsWj7r7-Dy53OEwCLcB/s1600/srm709top5.png" /></a></div>TopCoder SRM 709 on Tuesday offered the deceptively little 800 points for the hard problem (<a href="https://community.topcoder.com/stat?c=round_overview&rd=16853">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=16853&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://youtu.be/eHGm-UL1ctQ">my screencast</a>). Just 3 competitors have managed to grab (some part of) those points, and thus -XraY-'s dominating victory is even more impressive!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-iJlXGiYI8lc/WLMqbn-ze7I/AAAAAAABwgQ/-3_zou4d7uc8nOKkqRoi6SCc_jpZXPj7ACLcB/s1600/cf400top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="158" src="https://3.bp.blogspot.com/-iJlXGiYI8lc/WLMqbn-ze7I/AAAAAAABwgQ/-3_zou4d7uc8nOKkqRoi6SCc_jpZXPj7ACLcB/s640/cf400top5.png" width="640" /></a></div>Codeforces Round 400 on Thursday continued the non-stop week (<a href="http://codeforces.com/contest/776">problems</a>, <a href="http://codeforces.com/contest/776/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/50622">analysis</a>). The challenges were not in abundance this time, and thus the coding speed and accuracy came to the forefront. ainta was a tiny bit faster this time, and made fewer submissions that didn't pass pretests - congratulations on the win!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-aYhRFqXz4Yo/WLMr5rEOSsI/AAAAAAABwgY/wAwi7f8wqmEATvdmIMh3rVPgQmkirU4qgCLcB/s1600/mujin2017top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="308" src="https://1.bp.blogspot.com/-aYhRFqXz4Yo/WLMr5rEOSsI/AAAAAAABwgY/wAwi7f8wqmEATvdmIMh3rVPgQmkirU4qgCLcB/s640/mujin2017top5.png" width="640" /></a></div>On Saturday, Mujin Programming Challenge 2017 on AtCoder offered monetary prizes for the top performers (<a href="http://mujin-pc-2017.contest.atcoder.jp/assignments">problems</a>, <a href="http://mujin-pc-2017.contest.atcoder.jp/standings#page_1">results</a>, top 5 on the left, <a href="https://atcoder.jp/img/mujin-pc-2017/editorial.pdf">analysis</a>, <a href="https://youtu.be/zUwfNf0cQFw">my screencast</a>). Tourist has claimed the first prize by being way ahead of everybody on the hardest problem - well done!<br /><br />I think <a href="http://mujin-pc-2017.contest.atcoder.jp/tasks/mujin_pc_2017_b">problem B</a> in this round provided a nice way to practice one's skill for dissecting a problem step by step until it becomes trivial. You were given a square <i>n</i> times <i>n</i> matrix with each cell either black or white. In one step, you could take an arbitrary row of the matrix, and replace an arbitrary column of the matrix with the values from the chosen row. Your goal is to make all cells black. What is the minimum number of steps required to achieve that?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-RiM2e14ejS4/WLMtsSY0StI/AAAAAAABwgo/yL7Sr_jglQgqfbnD8UWdZut2weGeKvZTACLcB/s1600/codechefltime45top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="176" src="https://4.bp.blogspot.com/-RiM2e14ejS4/WLMtsSY0StI/AAAAAAABwgo/yL7Sr_jglQgqfbnD8UWdZut2weGeKvZTACLcB/s640/codechefltime45top5.png" width="640" /></a></div>Right after the AtCoder round ended, Codechef held its February Lunchtime 2017 competition (<a href="https://www.codechef.com/LTIME45">problems</a>, <a href="https://www.codechef.com/rankings/LTIME45">results</a>, top 5 on the left, <a href="https://youtu.be/XWAxqcs7_5U">my screencast</a>). The problems were a bit easier than in other competitions mentioned in this summary, but still provided a nice challenge!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-nVM5uNyG1nc/WLMs-snV2YI/AAAAAAABwgg/hsayGEo9fng3DsE7pYVpxpEBsmmueIncwCLcB/s1600/cf402top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="184" src="https://2.bp.blogspot.com/-nVM5uNyG1nc/WLMs-snV2YI/AAAAAAABwgg/hsayGEo9fng3DsE7pYVpxpEBsmmueIncwCLcB/s640/cf402top5.png" width="640" /></a></div>Codeforces Round 402 started at the same time with the Open Cup round (<a href="http://codeforces.com/contest/778">problems</a>, <a href="http://codeforces.com/contest/778/standings">results</a>, top 6 on the left). As a result, many active ACM ICPC participants have skipped the Codeforces Round, but the competition remained fierce. Congratulations to bmerry on finding a unique set of problems to solve and winning thanks to that strategy!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-Bh3dQkS1x5I/WLMta7h3qdI/AAAAAAABwgk/8abMc5wFDpgpwspuSWfNQP8lwVkzIyWhQCLcB/s1600/oc2017wroclawtop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="170" src="https://4.bp.blogspot.com/-Bh3dQkS1x5I/WLMta7h3qdI/AAAAAAABwgk/8abMc5wFDpgpwspuSWfNQP8lwVkzIyWhQCLcB/s640/oc2017wroclawtop5.png" width="640" /></a></div>Finally, the aforementioned Open Cup 2016-17 Grand Prix of Wroclaw also took place today (<a href="http://opentrains.snarknews.info/~ejudge/res/res10372">results</a>, top 5 on the left). Problem F was right in the middle by difficulty level, and required a nice observation to come up with a O(<i>n</i><sup>2</sup>) solution.<br /><br />Consider a permutation of size <i>n</i>. For each number, we can compute its <i>radius</i>: the largest number <i>r</i> such that <i>r</i> numbers to the left of our number, and <i>r</i> numbers to the right of our number, are all smaller than that number. For example, for the permutation "1 3 2 6 4 5" the radii are "0 1 0 2 0 0". Given the sequence of radii, how many different permutations correspond to it?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-JQq1-dBsbkU/WLMx5aNRoVI/AAAAAAABwg4/OWrY-7Q-fXERRIJUkLT4MDzisb_EpSC_wCLcB/s1600/IMG_20170218_124053.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="480" src="https://2.bp.blogspot.com/-JQq1-dBsbkU/WLMx5aNRoVI/AAAAAAABwg4/OWrY-7Q-fXERRIJUkLT4MDzisb_EpSC_wCLcB/s640/IMG_20170218_124053.jpg" width="640" /></a></div>Thanks for reading, and check back next week! (which promises to be much calmer)</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/VS3J0uP6-Qg" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/02/a-7x-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-61208127337315431702017-02-20T00:58:00.001+03:002017-02-20T00:58:24.190+03:00A casino 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/-kaFrcwIlcmg/WKoOLPkEVtI/AAAAAAABwL0/qaydHhvX4-AvPxxuRYNfgAh4ws-8S9IgwCLcB/s1600/cf397top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="156" src="https://1.bp.blogspot.com/-kaFrcwIlcmg/WKoOLPkEVtI/AAAAAAABwL0/qaydHhvX4-AvPxxuRYNfgAh4ws-8S9IgwCLcB/s640/cf397top5.png" width="640" /></a></div>Codeforces Round 397 was the highlight of this week (<a href="http://codeforces.com/contest/765">problems</a>, <a href="http://codeforces.com/contest/765/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/50456">analysis</a>). Merkurev has created a comfortable margin for himself thanks to fast solutions of the first five problems and two successful challenges - congratulations on the victory!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-CxkSLdRtk5o/WKoUIwmoTrI/AAAAAAABwME/x_jFDtH5Nv0BA2I8kDkO1DhgKYInNRc4ACLcB/s1600/IMG_20170129_125629.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="480" src="https://2.bp.blogspot.com/-CxkSLdRtk5o/WKoUIwmoTrI/AAAAAAABwME/x_jFDtH5Nv0BA2I8kDkO1DhgKYInNRc4ACLcB/s640/IMG_20170129_125629.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2017/02/a-spanning-week.html">my previous summary</a>, I have mentioned two interesting problems. The first was a TopCoder problem about distinguishing optimal strategy and random play: you are playing a betting game in a casino. You start with <i>a</i> dollars, and your goal is to reach <i>b</i> dollars. You can play at most <i>k</i> rounds. In each round, you bet some integer (possibly zero) amount of dollars not exceeding the amount you have now, then with probability 50% you lose that amount, and with probability 50% you gain that amount. As soon as you reach your goal (have at least <i>b</i> dollars), you leave the casino.<br /><br />There are of course many strategies to place your bets. In this problem we're concerned with two of them: one is an <i>optimal</i> strategy, where you place each bet to maximize the probability that you will reach your goal by the end of the <i>k</i>-th round or earlier. Note that there might still be several choices for each bet in an optimal strategy that all lead to the same probability of achieving the goal. One of the optimal strategies can be somewhat easily googled. The other strategy we're concerned with is the <i>fully random</i> one: for each bet, we choose the number of dollars between 0 and our amount of money uniformly at random.<br /><br />Now, you've chosen to use the fully random strategy, and played it to completion (end of <i>k</i>-th round, or getting at least <i>b</i> dollars). An outside observer (who knows the values of <i>a</i>, <i>b</i> and <i>k</i>), however, was assuming that you're actually following an optimal strategy - and did not find evidence otherwise observing your fully random play (in other words, each time you randomly chose a bet that leads to the maximum probability of achieving the goal). What is the probability of such situation?<br /><br /><i>a</i> and <i>b</i> are up to 100000, and <i>k</i> is at most 5.<br /><br />A quadratic dynamic programming solution is straightforward: given the amount of money we have and the number of rounds remaining, we will compute what's the probability of winning, and what's the probability that a random play will look optimal. In order to compute those probabilities, we will iterate over all possible bets and see what state to we get into if we win and if we lose.<br /><br />The key insight required to speed it up is: the probability of winning is always a rational number with denominator 2<sup><i>k</i> </sup>(because our play consists of <i>k</i> events each with 50-50 chances). Because of this, it has at most 2<sup><i>k</i></sup><complete id="goog_1567086616">+1 </complete>possible values. On the other hand, it's not hard to see that this probability will not decrease if we increase the amount of money we have. That means that for a fixed <i>k</i>, the probabilities of winning for each <i>a</i> form a set of at most 2<sup><i>k</i></sup><complete id="goog_1567086616">+1 </complete>segments, each with the same value. And that, in turn, allows to speed up the dynamic programming: instead of considering possible bets one by one, we will consider them in groups: a group is determined by which segments on level <i>k</i>-1 we land on if we win, and if we lose. There will be at most 2*(2<sup><i>k-1</i></sup><complete id="goog_1567086616">+1) such groups, and thus the total running time will be O(<i>b</i>*<i>k</i>*</complete>2<sup><i>k</i></sup>) which is fast enough.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-k7-kf3igAtY/WKoUkCURmPI/AAAAAAABwMI/falGrYBrDu0KIpAJjiQhHvddgJShyIkvQCLcB/s1600/IMG_20170129_142440.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="480" src="https://4.bp.blogspot.com/-k7-kf3igAtY/WKoUkCURmPI/AAAAAAABwMI/falGrYBrDu0KIpAJjiQhHvddgJShyIkvQCLcB/s640/IMG_20170129_142440.jpg" width="640" /></a></div>The second problem from the previous summary was a purely mathematical puzzle: you are given an undirected graph with at most 200000 vertices and at most 200000 edges. Consider its <i>spanning</i> subsets of edges: such subsets of its edges that connect all its vertices. Is the number of such subsets odd or even?<br /><br />The solution here is completely magical. It turns out that the number of spanning subsets of edges is odd <i>if and only if</i> the graph is bipartite. A couple of different proofs can be found in <a href="http://codeforces.com/blog/entry/50380?#comment-342897">this Codeforces thread</a>, but I think they don't fully answer the natural question: what is the intuition behind this fact? How to come up with it without knowing it in advance? I would be grateful if the readers could shed some light here.<br /><br />Thanks for reading, and check back next week!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/yvj-BwPkPdk" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/02/a-casino-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-48029002382658077942017-02-19T22:41:00.002+03:002017-02-19T22:41:27.721+03:00A spanning 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/-TKqnPnEqr9w/WKnmBfhsdFI/AAAAAAABwKY/Ju791c5chDAXWjuTfWbApFB9fk_mxH04wCLcB/s1600/srm708top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" src="https://4.bp.blogspot.com/-TKqnPnEqr9w/WKnmBfhsdFI/AAAAAAABwKY/Ju791c5chDAXWjuTfWbApFB9fk_mxH04wCLcB/s1600/srm708top5.png" /></a></div>TopCoder SRM 708 took place in the middle of last week (<a href="https://community.topcoder.com/stat?c=round_overview&rd=16852">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=16852&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://youtu.be/pQv2rYX2dsk">my screencast</a>, <a href="http://codeforces.com/blog/entry/49910?#comment-342631">analysis</a>). rng_58 returned to winning ways in his second SRM after the November TCO victory - congratulations!<br /><br />The victory is mostly thanks to the high score on <a href="https://community.topcoder.com/stat?c=problem_statement&pm=14525&rd=16852">the hard problem</a> (moreover, as you can see from the top 5 this problem decided all five places, not just the winner). It went like this: you are playing a betting game in a casino. You start with <i>a</i> dollars, and your goal is to reach <i>b</i> dollars. You can play at most <i>k</i> rounds. In each round, you bet some integer (possibly zero) amount of dollars not exceeding the amount you have now, then with probability 50% you lose that amount, and with probability 50% you gain that amount. As soon as you reach your goal (have at least <i>b</i> dollars), you leave the casino.<br /><br />There are of course many strategies to place your bets. In this problem we're concerned with two of them: one is an <i>optimal</i> strategy, where you place each bet to maximize the probability that you will reach your goal by the end of the <i>k</i>-th round or earlier. Note that there might still be several choices for each bet in an optimal strategy that all lead to the same probability of achieving the goal. One of the optimal strategies can be somewhat easily googled. The other strategy we're concerned with is the <i>fully random</i> one: for each bet, we choose the number of dollars between 0 and our amount of money uniformly at random.<br /><br />Now, you've chosen to use the fully random strategy, and played it to completion (end of <i>k</i>-th round, or getting at least <i>b</i> dollars). An outside observer (who knows the values of <i>a</i>, <i>b</i> and <i>k</i>), however, was assuming that you're actually following an optimal strategy - and did not find evidence otherwise observing your fully random play (in other words, each time you randomly chose a bet that leads to the maximum probability of achieving the goal). What is the probability of such situation?<br /><br /><i>a</i> and <i>b</i> are up to 100000, and <i>k</i> is at most 5. Can you solve it as fast as Makoto?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-NZMrM96LqwY/WKnm4IUtsCI/AAAAAAABwKg/wbn92jcjt1USQee3gJoStch92f11efTxQCLcB/s1600/oc2017chinatop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="175" src="https://3.bp.blogspot.com/-NZMrM96LqwY/WKnm4IUtsCI/AAAAAAABwKg/wbn92jcjt1USQee3gJoStch92f11efTxQCLcB/s640/oc2017chinatop5.png" width="640" /></a></div>Open Cup 2016-17 Grand Prix of China on the weekend provided another set of tough problems (<a href="http://opentrains.snarknews.info/~ejudge/res/res10371">results</a>, top 5 on the left). The reigning ICPC world champions from SPb SU continued their winning streak - well done!<br /><br />Problem B in this round was a cute purely mathematical puzzle. You are given an undirected graph with at most 200000 vertices and at most 200000 edges. Consider its <i>spanning</i> subsets of edges: such subsets of its edges that connect all its vertices. Is the number of such subsets odd or even?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-pFdpFjXJCbQ/WKn0tEnzdbI/AAAAAAABwLQ/0OTm_HdcvLgXSqKjNed7cwUu7zcwkvVhQCLcB/s1600/IMG_20170122_154110.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="480" src="https://3.bp.blogspot.com/-pFdpFjXJCbQ/WKn0tEnzdbI/AAAAAAABwLQ/0OTm_HdcvLgXSqKjNed7cwUu7zcwkvVhQCLcB/s640/IMG_20170122_154110.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2017/02/a-gomel-week.html">my last summary</a>, I have mentioned two nice problems. The first one came from AtCoder: two players are playing a game on a tree where each node has some amount of stones. There's also a chip in one of the vertices of the tree. They make moves in turn, and each move consists of removing one stone from the vertex where the chip is, and then moving the chip to an adjacent vertex. When there's no more stones in the vertex where the chip is, the player that needs to make the next move is unable to do so, and thus loses the game. How to determine who will win with optimal play?<br /><br />The key idea needed to solve this problem is: if the vertex <i>a</i> the chip is currently on has less or the same amount of stones as its adjacent vertex <i>b</i>, then the second player can force the game to never go beyond <i>b</i> in the tree. If the first player moves the chip to <i>b</i>, the second player can return it to <i>a</i>, and after repeating this a few times <i>a</i> will run out of stones earlier than <i>b</i>, so if the first player doesn't want to lose, he will have to pick a vertex other than <i>b</i> to move to.<br /><br />Because of this, we can see that the outcome of the game does not change if we only ever allow to move from a vertex to a vertex with strictly fewer stones. The latter game is acyclic, and thus it's very easy to determine the winner in just a few lines of code.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-RkY8IOuMILE/WKn0Cez4yII/AAAAAAABwLE/J8fAkgKT_44K-u8hpWRJ0LYgBkvZmAmpQCKgB/s1600/IMG_20170219_203626.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="310" src="https://2.bp.blogspot.com/-RkY8IOuMILE/WKn0Cez4yII/AAAAAAABwLE/J8fAkgKT_44K-u8hpWRJ0LYgBkvZmAmpQCKgB/s640/IMG_20170219_203626.jpg" width="640" /></a></div>Another problem I mentioned was from Gennady's contest: <i>n</i><=400 people have participated in a programming contest, and will receive <i>x</i><=10<sup>9</sup> roubles of prize money in total. You do not know what is the prize for each place, you only know that each prize is an integer amount of roubles, that they add up to <i>x</i>, and that the prize amounts are in non-increasing order as we go through the ranking list. Given a subset of places in the ranking list (for example the 1st place, the 5th place and the 8th place), what is the smallest possible total prize for those places?<br /><br />The main idea here is to realize that the prizes essentially form <a href="https://en.wikipedia.org/wiki/Young_tableau">a Young diagram</a>, and as it is often the case, reading the diagram column-by-column after writing it row-by-row proves super useful. Without abstract mathematical terms, one could just say that we can view the distribution of the prize money as the following process: we repeatedly pick a number <i>m<sub>i</sub></i><=<i>n</i>, and give 1 dollar to the top <i>m<sub>i</sub></i> finishers. All <i>m<sub>i</sub></i> must add up to <i>x</i>.<br /><br />Now, giving 1 dollar to the top <i>m<sub>i</sub></i> finishers gives some concrete amount <i>f</i>(<i>m<sub>i</sub></i>) dollars to the finishers in our chosen subset of places. Now we can see that we have a classical knapsack problem instance where the weight of each item is relatively small (<i>m<sub>i</sub></i><=400), each item has a cost <i>f</i>(<i>m<sub>i</sub></i>), and we want to pick a multiset of items with the given total weight <i>x</i> and the smallest possible cost. This problem is solved by noticing that we must use the item with the smallest cost-to-weight ratio for most of the total weight - more precisely, we can keep using that item until the remaining total weight is below 400<sup>2</sup>=160000. And for such small total weight we can then solve the knapsack problem using the standard dynamic programming.<br /><br />The proof of the fact that we only need to run the dynamic programming up to 400<sup>2</sup> is based on the following lemma: in a set of <i>n</i> numbers, there's always a non-empty subset with sum divisible by <i>n</i>.<br /><br />Thanks for reading, and check back soon for this week's summary!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/XRJj2qnCh2Y" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/02/a-spanning-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-45608365876381202772017-02-11T20:21:00.001+03:002017-02-11T20:21:07.120+03:00A Gomel 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/-7Zdi7dmqfqc/WJ7bbgWCL6I/AAAAAAABu70/lpXjIEV5ccII8c2oZIxWQLT2MSKaLsaUACLcB/s1600/srm707top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="84" src="https://1.bp.blogspot.com/-7Zdi7dmqfqc/WJ7bbgWCL6I/AAAAAAABu70/lpXjIEV5ccII8c2oZIxWQLT2MSKaLsaUACLcB/s640/srm707top5.png" width="640" /></a></div>Last week started with the early morning TopCoder SRM 707 on Tuesday (<a href="https://community.topcoder.com/stat?c=round_overview&rd=16851">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=16851&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left). Nobody has managed to solve all three problems correctly - but not just because the hard problem was on the difficult side: <a href="https://community.topcoder.com/stat?c=problem_statement&pm=14527&rd=16851">the medium problem</a> had an unusually low 19% success rate, with a deceptively simple statement but quite a few corner cases.<br /><br />The winner Kriii also couldn't get the medium right, but has managed to get some compensation by successfully challenging two other medium solutions. Congratulations on the win!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-tCZAC8ne3e8/WJ7avS6QmhI/AAAAAAABu7s/uZoxKVHu2zwYJVg5rDQTBkUXkV4oEQkzwCLcB/s1600/cf395top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="158" src="https://1.bp.blogspot.com/-tCZAC8ne3e8/WJ7avS6QmhI/AAAAAAABu7s/uZoxKVHu2zwYJVg5rDQTBkUXkV4oEQkzwCLcB/s640/cf395top5.png" width="640" /></a></div>Codeforces Round 395 took place on Thursday (<a href="http://codeforces.com/contest/763">problems</a>, <a href="http://codeforces.com/contest/763/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/50205">analysis</a>). moejy0viiiiiv has solved everything with 24 minutes to spare, while nobody else was able to get all five. That's a very convincing victory!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-E-KT-K4ZW3o/WJ7aSRuh26I/AAAAAAABu7o/zbLn3PhTIqgX30xlKB1fbV0q9QnsSxvvACLcB/s1600/agc010top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="312" src="https://4.bp.blogspot.com/-E-KT-K4ZW3o/WJ7aSRuh26I/AAAAAAABu7o/zbLn3PhTIqgX30xlKB1fbV0q9QnsSxvvACLcB/s640/agc010top5.png" width="640" /></a></div>AtCoder Grand Contest 010 on Saturday has gathered the top three rated contestants among others, and it was exactly those three contestants who occupied the top of the scoreboard (<a href="http://agc010.contest.atcoder.jp/assignments">problems</a>, <a href="http://agc010.contest.atcoder.jp/standings#page_1">results</a>, top 5 on the left, <a href="https://atcoder.jp/img/agc010/editorial.pdf">analysis</a>). Congratulations to Um_nik on being 8 minutes faster than everybody else!<br /><br /><a href="http://agc010.contest.atcoder.jp/tasks/agc010_f">The last problem</a> turned out a bit easier than the organizers have expected. Two players are playing a game on a tree where each node has some amount of stones. There's also a chip in one of the vertices of the tree. They make moves in turn, and each move consists of removing one stone from the vertex where the chip is, and then moving the chip to an adjacent vertex. When there's no more stones in the vertex where the chip is, the player that needs to make the next move is unable to do so, and thus loses the game. How to determine who will win with optimal play?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-w_UvN9kK1Us/WJ7ZNE3pHNI/AAAAAAABu7c/AnTDJrk6D4oxgYCYHlx4pNIQzxjUKa5lwCLcB/s1600/oc2017gomeltop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="175" src="https://3.bp.blogspot.com/-w_UvN9kK1Us/WJ7ZNE3pHNI/AAAAAAABu7c/AnTDJrk6D4oxgYCYHlx4pNIQzxjUKa5lwCLcB/s640/oc2017gomeltop5.png" width="640" /></a></div>And finally, OpenCup 2016-17 Grand Prix of Gomel resumed the Open Cup season on Sunday, featuring Gennady as the problemsetter (<a href="http://opentrains.snarknews.info/~ejudge/res/res10370">results</a>, top 5 on the left). The reigning ACM ICPC world champions SPb SU Base were significantly faster than other teams, and thus found time to solve the hardest problem C in the last hour - great job!<br /><br />Problem D has disguised a relatively standard idea behind an unusual but very natural background. <i>n</i><=400 people have participated in a programming contest, and will receive <i>x</i><=10<sup>9</sup> roubles of prize money in total. You do not know what is the prize for each place, you only know that each prize is an integer amount of roubles, that they add up to <i>x</i>, and that the prize amounts are in non-increasing order as we go through the ranking list. Given a subset of places in the ranking list (for example the 1st place, the 5th place and the 8th place), what is the smallest possible total prize for those places?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-ZCbhmm5NkGQ/WJ9En2ZBr3I/AAAAAAABvC0/QWmqhSc7240usjmmw7BTZi1EKRUlDIIzQCLcB/s1600/IMG_20170122_105631.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="480" src="https://2.bp.blogspot.com/-ZCbhmm5NkGQ/WJ9En2ZBr3I/AAAAAAABvC0/QWmqhSc7240usjmmw7BTZi1EKRUlDIIzQCLcB/s640/IMG_20170122_105631.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2017/02/a-k-ary-week.html">my previous summary</a>, I have mentioned a Hacker Cup problem: you are given a sequence of <i>n</i> positive integers <i>h<sub>i</sub></i>, and a number <i>k</i>. You're allowed to do the following <i>k</i> times: take an integer, and decrease it by 1 (but it must remain positive). After you do this, we compute the maximum value of <i>h<sub>i</sub></i>+<i>h<sub>j</sub></i>+abs(<i>i</i>-<i>j</i>). How small can this maximum value be?<br /><br />The first idea is to start with a binary search. Given a value <i>m</i>, can we achieve <i>h<sub>i</sub></i>+<i>h<sub>j</sub></i>+abs(<i>i</i>-<i>j</i>)<=<i>m</i> for all <i>i</i> not equal to <i>j</i>? Since abs(<i>i</i>-<i>j</i>)=max(<i>i</i>-<i>j</i>,<i>j</i>-<i>i</i>), this is equivalent to <i>h<sub>i</sub></i>+<i>h<sub>j</sub></i>+<i>i</i>-<i>j</i><=<i>m</i> and <i>h<sub>i</sub></i>+<i>h<sub>j</sub></i>+<i>j</i>-<i>i</i><=<i>m</i>. The second inequality is obtained from the first by swapping <i>i</i> and <i>j</i>, so they're equivalent and we can keep just one: <i>h<sub>i</sub></i>+<i>h<sub>j</sub></i>+<i>i</i>-<i>j</i><=<i>m</i>. We can now rewrite it as (<i>h<sub>i</sub></i>+<i>i</i>)+(<i>h<sub>j</sub></i>-<i>j</i>)<=<i>m</i>.<br /><br />Now, if we didn't have the constraint that <i>i</i> is not equal to <i>j</i>, we could define <i>a</i>=max(<i>h<sub>i</sub></i>+<i>i</i>), <i>b</i>=(<i>h<sub>j</sub></i>-<i>j</i>), and simply check if we can make <i>a</i>+<i>b</i><=<i>m</i>. If we fix the value of <i>a</i>, then we know the (maximum value of) <i>b</i>, and thus know how much each height needs to be decreased, and thus can check if <i>k</i> decreases are enough. Of course we can't check all possible values of <i>a</i> this way, but we can notice that if we go through values of <i>a</i> in increasing order, the contribution of each <i>h<sub>i</sub></i> to the total required decrease will be piecewise-linear with at most 5 pieces, and thus we can add all those piecewise-linear curves together in O(<i>n</i>log<i>n</i>) time.<br /><br />Now, what to do with the additional constraint that <i>i</i> is not equal to <i>j</i>? It turns out that it doesn't matter in most cases. More specifically, for this constraint to matter both max(<i>h<sub>i</sub></i>+<i>i</i>) and max(<i>h<sub>j</sub></i>-<i>j</i>) must be achieved in the same point, and only in that point. In that case we have one <i>h<sub>i</sub></i> that is significantly bigger than all others, and thus decreasing this <i>h<sub>i</sub></i> will result in the answer decreasing as well. Because of this, we can always "transfer" one more decrease from any other number to that <i>h<sub>i</sub></i> without making the answer worse, unless all <i>k</i> decreases have been applied to it. And that means that in addition to the piecewise-linear sum mentioned above, it suffices to check just one more case: when all <i>k</i> decreases are applied to the maximum <i>h<sub>i</sub></i>.<br /><br />Thanks for reading, and check back next week!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/AKiunjO4I44" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/02/a-gomel-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-20517672334342688542017-02-03T17:14:00.002+03:002017-02-03T18:07:00.273+03:00A k-ary week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-T1DLx5rD9-k/WJSOdz7ywxI/AAAAAAABu2Q/fCyXbN_QiW0NvwgeTf7FFO259h20cQTbQCLcB/s1600/fbhc2017r3top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="275" src="https://2.bp.blogspot.com/-T1DLx5rD9-k/WJSOdz7ywxI/AAAAAAABu2Q/fCyXbN_QiW0NvwgeTf7FFO259h20cQTbQCLcB/s640/fbhc2017r3top5.png" width="640" /></a></div>Last week, the 200 participants of Facebook Hacker Cup Round 3 were fighting for the 25 spots in the Seattle onsite (<a href="https://www.facebook.com/hackercup/problem/1834377036809994/">problems</a>, <a href="https://www.facebook.com/hackercup/scoreboard/1198810003536974/?filter=everyone">results</a>, top 5 on the left, <a href="https://www.facebook.com/notes/facebook-hacker-cup/hacker-cup-2017-round-3-solutions/1617058738310021">analysis</a>). This time double- and triple-checking was not the best approach, as one needed to solve the first three problems quite quickly to get through. Congratulations to Egor on the victory!<br /><br /><a href="https://www.facebook.com/hackercup/problem/637797413079757/">The hardest problem</a> required both a careful implementation and several key insights. You are given a sequence of <i>n</i> positive integers <i>h<sub>i</sub></i>, and a number <i>k</i>. You're allowed to do the following <i>k</i> times: take an integer, and decrease it by 1 (but it must remain positive). After you do this, we compute the maximum value of <i>h<sub>i</sub></i>+<i>h<sub>j</sub></i>+abs(<i>i</i>-<i>j</i>). How small can this maximum value be?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-AposeOXvCW4/WJSPFfpVVQI/AAAAAAABu2c/VHakTpzkAPoOQyTpMsykT_S8pdd0l9PkACLcB/s1600/IMG_20170108_111040.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="480" src="https://1.bp.blogspot.com/-AposeOXvCW4/WJSPFfpVVQI/AAAAAAABu2c/VHakTpzkAPoOQyTpMsykT_S8pdd0l9PkACLcB/s640/IMG_20170108_111040.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2017/02/a-limak-week.html">my previous summary</a>, I have mentioned two interesting problems. The first one, coming from TopCoder, asked to find any sequence of 500 positive integers up to 10<sup>18</sup>, such that any two adjacent numbers in this sequence are coprime, and any two non-adjacent numbers in this sequence are not coprime.<br /><br />As usual with such "constructive" problems, a lot of different approaches are possible. I think the most beautiful approach is the randomized one, as described in <a href="http://codeforces.com/blog/entry/49002?#comment-338806">the analysis</a>. Let's take the first <i>n</i> primes, and each of the 500 numbers will be a product of some <i>k</i> of them. To build the sequence, we will pick each number at random from all possible products of some <i>k</i> of those primes that do not include the <i>k</i> primes used to build the previous number. This will guarantee that adjacent numbers will be coprime. After generating each number, we will also verify if it's coprime with any other number except the one directly preceding it. If yes, we'll regenerate it again at random, and so on until this number fits, then move on to the next number.<br /><br />Why does this work, and how to pick <i>n</i> and <i>k</i>? I can only offer some advice partly based on intuition here. Obviously <i>k</i> must be chosen in such a way that the product of the largest <i>k</i> of the first <i>n</i> primes does not exceed 10<sup>18</sup>. Also, <i>k</i> must be close to <i>n</i>/2, but not too close :) Basically, the higher is <i>k</i>, the more likely it is for two random numbers with <i>k</i> bits out of <i>n</i> to share a common bit. However, when <i>k</i> approaches <i>n</i>/2 a different mechanic comes into play: the bits (primes used) in the sequence start to alternate, and thus the numbers at an odd distance are more likely to be coprime. Practically speaking, <i>n</i>=23 and <i>k</i>=10 seems to work with a comfortable margin. Still, it's not entirely clear to me how to expect this solution to work before trying it out - I think it requires the right kind of statistical intuition.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-aIGatlRyzUE/WJSQGqTldxI/AAAAAAABu24/FcEWbcoySwElH0ICZXJA9_NHQG1uGrxPgCKgB/s1600/IMG_20170203_171209.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="300" src="https://1.bp.blogspot.com/-aIGatlRyzUE/WJSQGqTldxI/AAAAAAABu24/FcEWbcoySwElH0ICZXJA9_NHQG1uGrxPgCKgB/s400/IMG_20170203_171209.jpg" width="400" /></a></div>The other problem I mentioned was from AtCoder: you start with <i>n</i> zeros and <i>m</i> ones on a blackboard, and you're also given a number <i>k</i> such that <i>k</i>-1 divides <i>n</i>+<i>m</i>-1. You repeatedly pick any <i>k</i> numbers on the blackboard, erase them, and instead write their arithmetic mean (which is not necessarily an integer). Since <i>k</i>-1 divides <i>n</i>+<i>m</i>-1, you will eventually end up with just one number. How many different values can this last number have? <i>n</i> and <i>m</i> are up to 2000.<br /><br />The right approach to this problem is to build a rigorous mental model of what's going on. We can view the computation as a rooted tree: the root of the tree corresponds to the final value, each non-leaf node has exactly <i>k</i> children corresponding to the values used to obtain the value of this node, and there are <i>n</i>+<i>m</i> leaf nodes corresponding to the original numbers, each containing either 0 or 1, with exactly <i>m</i> 1s. There will be <i>d</i>=(<i>n</i>+<i>m</i>-1)/(<i>k</i>-1) inner nodes in the tree.<br /><br />We can then notice that the final value is uniquely determined by the depths of each 1 leaf node. More precisely, a 1 at distance <i>p</i> from root contributes 1/<i>k</i><sup><i>p</i></sup> to the final value. Now it's clear that the final value must be representable as <i>x</i>/<i>k</i><sup><i>q</i></sup>, where <i>q</i><=<i>d.</i> For a given value, let's pick the minimum such <i>q</i>. How do we determine if it's representable given <i>x</i> and <i>q</i>?<br /><br />Representing <i>x</i>/<i>k</i><sup><i>q</i></sup> as a sum of <i>m</i> terms of form 1/<i>k</i><sup><i>p</i></sup> is equivalent to representing <i>x</i> as a sum of <i>m</i> terms of form <i>k</i><sup><i>q-p</i></sup>. In other words, we need to represent <i>x</i> in <i>k</i>-ary system with sum of digits equal to <i>m</i>, but where each digit can be arbitrarily big. It's not hard to see that the minimum sum of digits is achieved if we use the standard representation of <i>x</i> in <i>k</i>-ary system, and all other representations are obtained by replacing one of the 1s with <i>k</i> smaller 1s. We can make at most <i>d</i>-<i>q</i> such replacements (since <i>q</i> out of <i>d</i> tree nodes are already used for the initial representation).<br /><br />To summarize, for each <i>q</i><=<i>d</i> we just need to count the amount of numbers <i>x </i>with <i>q</i> digits in <i>k</i>-ary system with sum of digits equal to <i>m</i>-(<i>k</i>-1)*<i>y</i>, where 0<=<i>y</i><=<i>d</i>-<i>q</i>, and with nonzero last digit. This is now a standard dynamic programming task, and note that we didn't need to have any insights or magical ideas to arrive at it - just gradually expanding our understanding of the problem domain.<br /><br />Thanks for reading, and check back next week!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/AxMeU0C8eZE" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/02/a-k-ary-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-30083728722050917392017-02-03T16:36:00.000+03:002017-02-03T16:36:22.792+03:00A Limak 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/-wm4KYnQ3AN8/WI5xasI1sjI/AAAAAAABuwQ/dW8Yw98b89kJOhR-y6opqOzeh3N8eNGeACLcB/s1600/srm706top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" src="https://4.bp.blogspot.com/-wm4KYnQ3AN8/WI5xasI1sjI/AAAAAAABuwQ/dW8Yw98b89kJOhR-y6opqOzeh3N8eNGeACLcB/s1600/srm706top5.png" /></a></div>TopCoder SRM 706 kicked off the activity-packed weekend of the Jan 16 - Jan 22 week (<a href="https://community.topcoder.com/stat?c=round_overview&rd=16850">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=16850&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/49002?#comment-338806">analysis</a>, <a href="https://youtu.be/k65MkV38RSk">my screencast</a>). Our old friend, bear Limak, promised the reliably high quality of Errichto's problems, and the contest did not disappoint. I had other reasons to be disappointed, though, not being able to maintain the first place through the challenge phase. Kudos to ainta for the decisive +50!<br /><br /><a href="https://community.topcoder.com/stat?c=problem_statement&pm=14495&rd=16850">The hardest problem</a> had a deceptively easy statement: you need to find any sequence of 500 positive integers up to 10<sup>18</sup>, such that any two adjacent numbers in this sequence are coprime, and any two non-adjacent numbers in this sequence are not coprime. Can you see the way?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-iCxrO2rxFIU/WI5yiWIvzuI/AAAAAAABuwc/c9LjAGuOxIAU9ovqxJNlki4D7GAx87CHwCLcB/s1600/fbhc2017r2top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="292" src="https://4.bp.blogspot.com/-iCxrO2rxFIU/WI5yiWIvzuI/AAAAAAABuwc/c9LjAGuOxIAU9ovqxJNlki4D7GAx87CHwCLcB/s640/fbhc2017r2top5.png" width="640" /></a></div>Right after the end of the SRM, Facebook Hacker Cup 2017 Round 2 narrowed the list of contenders for the cup to just 200 algorithmists (<a href="https://www.facebook.com/hackercup/problem/371325719893664/">problems</a>, <a href="https://www.facebook.com/hackercup/scoreboard/742957399195355/?filter=everyone">results</a>, top 5 on the left, <a href="https://www.facebook.com/notes/facebook-hacker-cup/hacker-cup-2017-round-2-solutions/1607098535972708">analysis</a>, <a href="https://youtu.be/0cIPGx7IWSg">my screencast</a>). Given the extremely harsh judging system and the fact that the 1st and the 200th place were similarly useful, one had to find the right balance between double- and triple-checking the solutions, and moving on to the next problem. Congratulations to all 200 algorithmists who got this right, and to Marek for being the fastest!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-B-_6ks4CPwA/WI5zFWeK9BI/AAAAAAABuwg/EJa4vC3BHrEouzxyxJPw_RBK0s2dF36BwCLcB/s1600/agc009top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="312" src="https://2.bp.blogspot.com/-B-_6ks4CPwA/WI5zFWeK9BI/AAAAAAABuwg/EJa4vC3BHrEouzxyxJPw_RBK0s2dF36BwCLcB/s640/agc009top5.png" width="640" /></a></div>On Sunday, AtCoder Grand Contest 009 has gathered roughly the same crowd again (<a href="http://agc009.contest.atcoder.jp/assignments">problems</a>, <a href="http://agc009.contest.atcoder.jp/standings">results</a>, top 5 on the left, <a href="https://atcoder.jp/img/agc009/editorial.pdf">analysis</a>). w4yneb0t has continued his string of excellent results, winning this round and cementing his second place in <a href="https://atcoder.jp/ranking">the overall AtCoder rating list</a> - well done!<br /><br /><a href="http://agc009.contest.atcoder.jp/tasks/agc009_e">The last problem</a> was a great example of the type where after developing a good understanding of the mechanics described in the problem statement, coming up with the actual solution is very straightforward. You start with <i>n</i> zeros and <i>m</i> ones on a blackboard, and you're also given a number <i>k</i> such that <i>k</i>-1 divides <i>n</i>+<i>m</i>-1. You repeatedly pick any <i>k</i> numbers on the blackboard, erase them, and instead write their arithmetic mean (which is not necessarily an integer). Since <i>k</i>-1 divides <i>n</i>+<i>m</i>-1, you will eventually end up with just one number. How many different values can this last number have? <i>n</i> and <i>m</i> are up to 2000.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-qiVp9dF7PyU/WI5zxJ8ZcEI/AAAAAAABuwo/QJUlkfh4QiMenvxWZagVi4fcKARx8qhYgCLcB/s1600/8vc2017finaltop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="156" src="https://1.bp.blogspot.com/-qiVp9dF7PyU/WI5zxJ8ZcEI/AAAAAAABuwo/QJUlkfh4QiMenvxWZagVi4fcKARx8qhYgCLcB/s640/8vc2017finaltop5.png" width="640" /></a></div>And finally, Codeforces 8VC Venture Cup 2017 Final Round gave the contestants a shot at monetary prizes (<a href="http://codeforces.com/contest/756">problems</a>, <a href="http://codeforces.com/contest/756/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/contest/759/standings">parallel round results</a>, <a href="http://codeforces.com/blog/entry/49946">analysis</a>). V--o_o--V, previously known as overtroll, was super fast through the first four problems, and has managed to solve the extremely tedious problem E, to win the first prize with a comfortable margin. Congratulations!<br /><br />Thanks for reading, and check back soon for the last week's summary!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/0KlQOPpo0uo" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/02/a-limak-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-62525292078591296362017-01-16T18:57:00.000+03:002017-01-16T19:59:08.183+03:000.636 of a year<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/-XP-_U9UgQ9o/WHzo3uZQinI/AAAAAAAA--E/d97lc39z__UxkUTw8SHERpT2nAstoqm6QCLcB/s1600/srm705top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" src="https://1.bp.blogspot.com/-XP-_U9UgQ9o/WHzo3uZQinI/AAAAAAAA--E/d97lc39z__UxkUTw8SHERpT2nAstoqm6QCLcB/s1600/srm705top5.png" /></a></div>Very early on Wednesday, TopCoder SRM 705 set the pace for the competitions in 2017 (<a href="https://community.topcoder.com/stat?c=round_overview&rd=16856">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=16856&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left). Tourist would have been in the 7th place even if all his solutions failed the system test, thanks to an impressive challenge phase performance. And as usual, none of the solutions did fail, so he achieved an extremely commanding victory. Congratulations!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-j6D5pz9juek/WHzo8NNXnGI/AAAAAAAA--I/J4wwrGIigeACDX3kfTyQFUogyuXJv-19ACLcB/s1600/cf391top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="154" src="https://3.bp.blogspot.com/-j6D5pz9juek/WHzo8NNXnGI/AAAAAAAA--I/J4wwrGIigeACDX3kfTyQFUogyuXJv-19ACLcB/s640/cf391top5.png" width="640" /></a></div>Later that day, Codeforces held its own opening contest of 2017 - Codeforces Round 391 (<a href="http://codeforces.com/contest/757">problems</a>, <a href="http://codeforces.com/contest/757/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/49743">analysis</a>). Once again tourist has combined excellent solving with excellent challenging to claim a win, but the competition was much closer this time. Well done to tourist and to his competitors!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-gSOK5kY6Kbg/WHzpNA5lJoI/AAAAAAAA--M/HxOFzFoVyIU8Ocm1bfOp6EFQIS9SOEqvQCLcB/s1600/eightvcelim2016top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="156" src="https://2.bp.blogspot.com/-gSOK5kY6Kbg/WHzpNA5lJoI/AAAAAAAA--M/HxOFzFoVyIU8Ocm1bfOp6EFQIS9SOEqvQCLcB/s640/eightvcelim2016top5.png" width="640" /></a></div>On Sunday, Codeforces held one more round: 8VC Venture Cup 2017 Elimination Round (<a href="http://codeforces.com/contest/755">problems</a>, <a href="http://codeforces.com/contest/755/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/49793">analysis</a>). In case you have not noticed the pattern of the new year, it was tourist at the top once again. Impressive consistency!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-oDGD-TvKP_Y/WHzs0LRKpII/AAAAAAAA--g/3r3Pgerv0L8PtbyfLNEdN16kQchOGCyIgCLcB/s1600/IMG_20170107_122451-PANO.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="268" src="https://4.bp.blogspot.com/-oDGD-TvKP_Y/WHzs0LRKpII/AAAAAAAA--g/3r3Pgerv0L8PtbyfLNEdN16kQchOGCyIgCLcB/s640/IMG_20170107_122451-PANO.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2017/01/a-week-of-five.html">my last summary</a>, I have organized a vote between top 5 problems of 2016 (of course, only according to my taste). Here are its results:<br /><br />5. The problem about recovering the seed used for shuffling a permutation twice - <a href="http://petr-mitrichev.blogspot.com/2016/11/an-unshuffle-week.html">post with solution</a>. 13 votes, author: Ivan Kazmenko.<br />4. The problem about turning one string into another using two operations: replace one letter, or replace all occurrences of the same letter - <a href="http://petr-mitrichev.blogspot.com/2016/05/a-polish-week.html">post with solution</a>. 17 votes, author: Adam Karczmarz.<br />3. The problem about exploring a cave with identical rooms interactively - <a href="http://petr-mitrichev.blogspot.com/2016/12/a-dfs-week.html">post with solution</a>. 21 vote, author: Georgiy Korneev.<br />2. The problem about implementing binary search that's takes at most log(n+1)+0.1 on average, not ceil(log(n)) - <a href="http://petr-mitrichev.blogspot.com/2016/04/a-binary-week.html">post with solution</a>. 29 votes, author: Vasiliy Mokin (not sure, please tell if it's not correct).<br />1. The problem about turning a matching in the plane into a non-intersecting one that's at least 0.636x as long - <a href="http://petr-mitrichev.blogspot.com/2016/05/a-26x26-week.html">post with solution</a>. 37 votes, author: Gaoyuan Chen.<br /><br />Big thanks to the authors of these and all other 2016 problems!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/tJFtuF0YdMA" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/01/0636-of-year.htmltag:blogger.com,1999:blog-1953325079793449971.post-7316115506978585132017-01-08T23:12:00.002+03:002017-01-08T23:12:58.806+03:00A week of five<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/-4KjOJq74vlU/WHKcmD2mn0I/AAAAAAAA-qo/-2rdTZR6eZ4SYNWL0BKuPmwF5ZS5PJFrwCLcB/s1600/IMG_20161229_171807.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="480" src="https://2.bp.blogspot.com/-4KjOJq74vlU/WHKcmD2mn0I/AAAAAAAA-qo/-2rdTZR6eZ4SYNWL0BKuPmwF5ZS5PJFrwCLcB/s640/IMG_20161229_171807.jpg" width="640" /></a></div>In my <a href="http://petr-mitrichev.blogspot.com/2017/01/a-random-walk-week.html">last week's summary</a>, I have mentioned an educational Codeforces problem: you were given a string of digits <i>s</i> of length 200000, and at most 200000 queries, each query being a certain substring <i>q<sub>i</sub></i> of this string. For each query, you need to remove the smallest number of characters from this substring <i>q<sub>i</sub></i> in such a way that the resulting string contains 2017 <i>as a subsequence</i>, but does not contain 2016 as a subsequence.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-k_2d7rZBh8Q/WHKCsfaUqtI/AAAAAAAA-qI/P7CyE6u5pp4XGxlfZscmucVyV3ccklo7ACKgB/s1600/IMG_20170108_191813.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" height="138" src="https://4.bp.blogspot.com/-k_2d7rZBh8Q/WHKCsfaUqtI/AAAAAAAA-qI/P7CyE6u5pp4XGxlfZscmucVyV3ccklo7ACKgB/s400/IMG_20170108_191813.jpg" width="400" /></a></div>First, suppose there were no queries and no removed characters, just one string and the need to check if it contains 2017 and 2016 as a subsequence. That would be an extremely easy problem which allows many solutions. There's one solution, however, that lends itself well to the complications of the full problem: we will build a <a href="https://en.wikipedia.org/wiki/Deterministic_finite_automaton">deterministic finite automaton</a> that accepts only strings that contain 2017 but not 2016 as a subsequence. You can find this automaton pictured on the right, all transitions not explicitly mentioned in the picture lead from a vertex to itself. It has 6 states, A is the starting state, and E is the final state.<br /><br />In order to solve the full problem, we will create a segment tree (not the one from Wikipedia, but <a href="https://www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor/#Segment_Trees">this one</a>). For each segment of the given string, and for each pair of states of the automaton <i>s</i> and <i>t</i>, we will remember: what is the smallest number of characters that needs to be removed from this segment in order for the automaton to reach state <i>t</i>, if it starts in state <i>s</i>? In other words, each node of the segment tree will store a 6x6 matrix, and in order to combine the matrices for two child nodes, a process similar to matrix multiplication is needed.<br /><br />Note that this approach would work for any deterministic finite automaton, not just for the one pictured above.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-sz-Z-s5SR44/WHKcvKQnZwI/AAAAAAAA-qs/wJWqJwd8Gp8BWg5jrMRpjha80zP_1fwpACLcB/s1600/IMG_20170101_161650.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="480" src="https://3.bp.blogspot.com/-sz-Z-s5SR44/WHKcvKQnZwI/AAAAAAAA-qs/wJWqJwd8Gp8BWg5jrMRpjha80zP_1fwpACLcB/s640/IMG_20170101_161650.jpg" width="640" /></a></div>This post wraps up the solutions for problems posted in 2016. As such, it is a good time to take a look back and find the best problem of last year! I've taken a look at the 38 problems for which I've explained the solutions in my blog, and picked 5 that appeal the most to my taste. In chronological order:<br /><br />The problem about implementing binary search that's takes at most log(<i>n</i>+1)+0.1 on average, not ceil(log(<i>n</i>)) - <a href="http://petr-mitrichev.blogspot.com/2016/04/a-binary-week.html">post with solution</a>.<br />The problem about turning a matching in the plane into a non-intersecting one that's at least 0.636x as long - <a href="http://petr-mitrichev.blogspot.com/2016/05/a-26x26-week.html">post with solution</a>.<br />The problem about turning one string into another using two operations: replace one letter, or replace all occurrences of the same letter - <a href="http://petr-mitrichev.blogspot.com/2016/05/a-polish-week.html">post with solution</a>.<br />The problem about recovering the seed used for shuffling a permutation twice - <a href="http://petr-mitrichev.blogspot.com/2016/11/an-unshuffle-week.html">post with solution</a>.<br />The problem about exploring a cave with identical rooms interactively - <a href="http://petr-mitrichev.blogspot.com/2016/12/a-dfs-week.html">post with solution</a>.<br /><br />Could you help me pick one? <br /><br /><iframe allowtransparency="true" frameborder="0" height="211px" name="poll-widget-4248165688735669481" src="https://www.google.com/reviews/polls/display/-4248165688735669481/blogger_template/run_app?txtclr=%23666666&lnkclr=%235588aa&chrtclr=%235588aa&font=normal+normal+100%25+Georgia,+Serif&hideq=true&purl=http://petr-mitrichev.blogspot.com/" style="border: none; width: 100%;"></iframe> Thanks for reading, and check back next week!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/ovYYMZZ1jl8" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/01/a-week-of-five.htmltag:blogger.com,1999:blog-1953325079793449971.post-43319757277940559872017-01-02T01:49:00.000+03:002017-01-09T22:41:23.224+03:00A random walk 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/-6Rtyamm3D-c/WGl2L84zG9I/AAAAAAAA-Ls/uBH8M6kywHU6CQJMe_Fw9to69kYyXaMugCEw/s1600/srm704top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" src="https://3.bp.blogspot.com/-6Rtyamm3D-c/WGl2L84zG9I/AAAAAAAA-Ls/uBH8M6kywHU6CQJMe_Fw9to69kYyXaMugCEw/s1600/srm704top5.png" /></a></div>The New Year week featured contests from the two usual platforms. First off, TopCoder held its SRM 704 on Thursday (<a href="https://community.topcoder.com/stat?c=round_overview&rd=16849">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=16849&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://youtu.be/EYN-_3pltOE">my screencast</a>). I have almost shot myself in the foot by blindly challenging sky58's medium with a big testcase at the start of the challenge phase on the ground that he has been compiling and testing this problem right up to the end of the coding phase, suggesting he found a testcase where his solution fails but could not fix it in time. I got -25, but luckily Swistakk has returned the favor a couple of minutes later with a -25 of his own, and I was again within one challenge of the top which I was able to find in the remaining minutes.<br /><br />To be completely honest, I have made another unsuccessful attempt at shooting myself in the foot during this match. <a href="https://community.topcoder.com/stat?c=problem_statement&pm=14470&rd=16849">The hard problem</a> was about constructing a directed graph with at most 20 vertices with the given amount <i>k</i> (up to 100000) of Hamiltonian paths from the first vertex to the last one. I was having a hard time trying to come up with a working approach, so I've decided to fall back to one of the standard approaches that often work in this kind of constructive problems: a random walk. We start with some graph, then repeatedly add random edges while it has too little Hamiltonian paths, or remove random edges while it has too many, until we happen to get the exact amount.<br /><br />However, just finding the number of Hamiltonian paths in an arbitrary graph with 20 vertices would require exponential time, which practically meant that I could make only a few random steps in the allotted two seconds, which was clearly not enough. So I've tried to find a family of graphs where, on one hand, I could find the number of Hamiltonian paths quickly, and on the other hand, the family should be rich enough that it can have any number of Hamiltonian paths up to 100000, and preferably have any number of paths achievable in very many different ways, in order for the random walk to be able to stumble upon one.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-PLYrfPPC7Qk/WGmBcvlrXiI/AAAAAAAA-MM/YWBcXAS-2ssGlwpdw3KpM7TAkUcHYtIFACKgB/s1600/IMG_20170101_232142.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="116" src="https://1.bp.blogspot.com/-PLYrfPPC7Qk/WGmBcvlrXiI/AAAAAAAA-MM/YWBcXAS-2ssGlwpdw3KpM7TAkUcHYtIFACKgB/s640/IMG_20170101_232142.jpg" width="640" /></a></div>I was able to find such family relatively quickly: it would be almost acyclic graphs, where we have arcs from each vertex <i>i </i>to vertex <i>i</i>-1, and all other arcs go "to the right" - from each vertex i to vertices with numbers <i>j</i>><i>i</i>. Counting the number of Hamiltonian paths in such graph is a relatively straightforward dynamic programming task, because whenever we make a "jump" vertex <i>j</i> when previously the largest visited vertex was <i>i</i><<i>j-</i>1, we have to immediately go to the left through vertices <i>j</i>-1, <i>j</i>-2, ..., <i>i</i>+1 in this order, as we have no way of reaching them later. And the family seems reasonably expressive - for example, if we take all possible edges to the right, the number of paths would be 2<sup><i>n</i>-3</sup> (we choose the subset of vertices we "jump" to), and if we take only edges from each <i>i</i> to <i>i</i>+1, there's just one path, with other configurations falling somewhere in between and hopefully covering each number many times.<br /><br />I was so happy to find this family that I rushed to code this solution immediately, and submitted it as soon as I realized that it seems to work fast enough (always less than a second) at least on random inputs. However, I was by no means certain that it works in all cases - it might well be that some specific number of paths is harder to achieve, and since I only had a 2x-4x margin, a moderately higher number of random steps required would cause my solution to time out.<br /><br />The shooting oneself in the foot aspect is that it's really easy to come up with a deterministic solution for the problem within this family of graphs. In fact, the fact that the maximum graph has the number of paths equal to a power of two strongly points toward that deterministic solution. And indeed, all other accepted solutions for this problem do exactly that. Somehow it didn't even occur to me to think in this direction during the round :) Can you see this final step?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-rM1_oltd3bw/WGl2RswwuvI/AAAAAAAA-Lw/dWqHzS8zl2E6qlTKEWO_w2dm3pc01b4FACLcB/s1600/goodbye2016top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="156" src="https://4.bp.blogspot.com/-rM1_oltd3bw/WGl2RswwuvI/AAAAAAAA-Lw/dWqHzS8zl2E6qlTKEWO_w2dm3pc01b4FACLcB/s640/goodbye2016top5.png" width="640" /></a></div>One day later, Codeforces held its traditional Good Bye 2016 round (<a href="http://codeforces.com/contest/750">problems</a>, <a href="http://codeforces.com/contest/750/standings">results</a>, top 5 on the left, <a href="https://youtu.be/WqafwPqZG2M">my screencast</a>). It was Gennady's turn to shoot himself in the foot this time, as he was not careful enough when challenging and earned -50 points for an unsuccessful attempt that proved decisive.<br /><br />This round had a few interesting problems, but I think <a href="http://codeforces.com/contest/750/problem/E">problem E</a> was the most educational - it did not require much beyond putting together several standard approaches, but required a good understanding of those approaches to do so. You were given a string of digits <i>s</i> of length 200000, and at most 200000 queries, each query being a certain substring <i>q<sub>i</sub></i> of this string. For each query, you need to remove the smallest number of characters from this substring <i>q<sub>i</sub></i> in such a way that the resulting string contains 2017 <i>as a subsequence</i>, but does not contain 2016 as a subsequence.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-0s9DNHBBWlY/WGmG_peAfFI/AAAAAAAA-M0/oYta_vwe2GEjKwn-xglmqbiR_bI4hF9LgCLcB/s1600/IMAG1766-EFFECTS.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="362" src="https://1.bp.blogspot.com/-0s9DNHBBWlY/WGmG_peAfFI/AAAAAAAA-M0/oYta_vwe2GEjKwn-xglmqbiR_bI4hF9LgCLcB/s640/IMAG1766-EFFECTS.jpg" width="640" /></a></div>Finally, let me turn your attention to another traditional contest that is still running: <a href="https://contest.yandex.com/newyear2017/contest/3641/enter/">the Prime New Year Contest</a> at SnarkNews. <a href="http://petr-mitrichev.blogspot.com/2013/01/prime-contest-on-snarknews.html">As usual</a>, it includes only problems that were given in a team contest in 2016 but were not solved by any team there. You have plenty of time to try your hand at the hardest problems of 2016, as the contest runs until January 10. The solutions for three problems were described in this blog, so you can get a head start :)<br /><br />Thanks for reading, and check back next week!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/IbCR6b2aqWs" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/01/a-random-walk-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-1238403657902718492016-12-28T18:44:00.000+03:002016-12-28T18:44:11.949+03:00A black radius week<div dir="ltr" style="text-align: left;" trbidi="on">Last week was very calm, as most algorithmic competition websites have called it a year or are busy preparing special New Year-themed competitions.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-zN361fbldhc/WGPTIsd-pmI/AAAAAAAA91Q/XeSpalLRHocxqKE5THpu5gSBZAvvEKVlgCLcB/s1600/agc008top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="318" src="https://2.bp.blogspot.com/-zN361fbldhc/WGPTIsd-pmI/AAAAAAAA91Q/XeSpalLRHocxqKE5THpu5gSBZAvvEKVlgCLcB/s640/agc008top5.png" width="640" /></a></div>Nevertheless, AtCoder held its Grand Contest 008 right on Christmas Day (<a href="http://agc008.contest.atcoder.jp/assignments">problems</a>, <a href="http://agc008.contest.atcoder.jp/standings#page_1">results</a>, top 5 on the left, <a href="https://atcoder.jp/img/agc008/editorial.pdf">analysis</a>). In breaking with AGC tradition, the problems were quite technical and tedious this time. Big congratulations to apiad who has managed to get all of them accepted and won!<br /><br />I have spent all 110 minutes on the attractive-looking <a href="http://agc008.contest.atcoder.jp/tasks/agc008_f">problem F</a>, severely underestimating the amount of things that can go wrong in its solution (I got it accepted after about 5 more minutes of debugging after the end of the contest). The problem simply asks: given a tree with some subset of its vertices colored black, consider all subsets of its vertices defined as "all vertices at distance at most <i>d</i> from some black vertex <i>a</i>" (for all combinations of <i>d</i> and <i>a</i>), and return the number of different such subsets. When the same subset is defined through several combinations of <i>d</i> and <i>a</i>, it must still be counted only once.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-8_n1nVyLb3Q/WGPYKX-XUDI/AAAAAAAA91k/OUpvy5KyFc8kGq9vLC1Z4aLgI9LcQ4B4ACKgB/s1600/IMAG1861.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="362" src="https://1.bp.blogspot.com/-8_n1nVyLb3Q/WGPYKX-XUDI/AAAAAAAA91k/OUpvy5KyFc8kGq9vLC1Z4aLgI9LcQ4B4ACKgB/s640/IMAG1861.jpg" width="640" /></a></div>(Moscow Christmas on the left - compare to <a href="http://petr-mitrichev.blogspot.com/2015/12/a-christmas-week.html">last year</a> :)) In <a href="http://petr-mitrichev.blogspot.com/2016/12/an-amazon-week.html">my previous summary</a>, I have mentioned an interactive Open Cup problem: you needed to give a checkmate to a lone king on a 8x8 chessboard using just one piece - <a href="https://en.wikipedia.org/wiki/Amazon_(chess)">the amazon</a>, that can move both as a queen and as a knight. To makes things harder, you are playing blindfolded and do not know the king's position or moves. More precisely, you are given the initial position of the amazon, and need to output such sequence of at most 50 moves that the king that starts in any position that is not checked by the amazon and makes any legal moves will eventually be checkmated at some point in this sequence, and will not be stalemated before that.<br /><br />There are multiple approaches described in <a href="http://codeforces.com/blog/entry/49169">the post-match discussion</a>, highlighting the fact that the problem allowed one's creativity to shine. However, the solution described by Endagorion also allows to answer the extra question I posted last week: how short can such sequence of moves be if the amazon starts at <i>a1</i>?<br /><br />It turns out this shortest sequence is "a1 a2 b3 b4 c5 c6 c5 d4 d3 d4 e5 e6 e5 f4 f3 e5 f6" (16 moves). And to prove this, Endagorion simply runs a breadth-first search over all reachable states of the game. The state of the game, in this case, is the position of the amazon plus the set of positions where the opposite king <i>can</i> be. At first glance it seems like we might get 64*2<sup>64</sup> states, but in practice the number of reachable states is much, much lower - most likely because the set of reachable squares for the king fills any unattacked area reasonably quickly, and thus we get much fewer possibilities (just 312400 states are reachable, and only 54520 of those are traversed before we find a way to checkmate definitely).<br /><br />Thanks for reading, and check back in 2017! Happy New Year!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/_FOxX8PyM9w" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2016/12/a-black-radius-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-44594143469005838102016-12-19T01:22:00.000+03:002016-12-19T01:22:05.514+03:00An amazon 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/-f2N-FjdX4tM/WFcCeBOgZpI/AAAAAAAA9pg/bvHAHNpJu5AuyqL8EWbGJMN651Rr1WLQACEw/s1600/srm703top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" src="https://4.bp.blogspot.com/-f2N-FjdX4tM/WFcCeBOgZpI/AAAAAAAA9pg/bvHAHNpJu5AuyqL8EWbGJMN651Rr1WLQACEw/s1600/srm703top5.png" /></a></div>On Wednesday, TopCoder SRM 703 - the first TopCoder round after the TCO - took place (<a href="https://community.topcoder.com/stat?c=round_overview&rd=16848">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=16848&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left). Endagorion has claimed the victory thanks for an amazingly fast solution for the 1000 - he submitted it in just over 7 minutes! It turns out that a similar problem <a href="http://codeforces.com/blog/entry/48849?#comment-330337">has appeared before</a>, and he could reuse most of the code. Nevertheless, congratulations on the flawless execution!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-MH1T2RzISaQ/WFcEmsrnIEI/AAAAAAAA9po/rKcwLcKWNPQtMRqEzlKWV-M3yNik_ULHQCLcB/s1600/cf385top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="166" src="https://1.bp.blogspot.com/-MH1T2RzISaQ/WFcEmsrnIEI/AAAAAAAA9po/rKcwLcKWNPQtMRqEzlKWV-M3yNik_ULHQCLcB/s640/cf385top5.png" width="640" /></a></div>Codeforces Round 385 on Saturday has gathered 8 nutella-rated participants, including the top 3 (<a href="http://codeforces.com/contest/744">problems</a>, <a href="http://codeforces.com/contest/744/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/49126">analysis</a>). Tourist has guaranteed himself the first place in just over an hour, but couldn't solve everything because of extremely tricky geometric problem D. Congratulations on the win!<br /><br />Here's <a href="http://codeforces.com/contest/744/problem/E">problem E</a> which has propelled him to the top, in a slightly simplified form: you are given <i>n</i> words with total length up to <i>m</i>, and need to check whether there exists a <i>cyclic string</i> that has at least two different decompositions into those words, in O(<i>nm</i>) time. For example, for a set {"aa", "aba", "ba", "bab"} the cyclic string "ababa"="babaa" has two decompositions: "aba" + "ba", and "bab" + "aa".<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-wqRlb8rQ4CY/WFcIYG1Y4gI/AAAAAAAA9p4/rgogvfTqfVY5ZVOlO1dqGk_-Fi0nMfwOACLcB/s1600/oc1617r9top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="170" src="https://1.bp.blogspot.com/-wqRlb8rQ4CY/WFcIYG1Y4gI/AAAAAAAA9p4/rgogvfTqfVY5ZVOlO1dqGk_-Fi0nMfwOACLcB/s640/oc1617r9top5.png" width="640" /></a></div>Finally, Open Cup 2016-17 Grand Prix of Peterhof has (probably?) wrapped up 2016 for many ACM ICPC teams (<a href="http://opentrains.snarknews.info/~ejudge/res/res10359">results</a>, top 5 on the left). Problem E was the most unusual and thus the most creative: you needed to give a checkmate to a lone king on a 8x8 chessboard using just one piece: <a href="https://en.wikipedia.org/wiki/Amazon_(chess)">the amazon</a>, that can move both as a queen and as a knight. To makes things harder, you are playing blindfolded and do not know the king's position or moves. More precisely, you are given the initial position of the amazon, and need to output such sequence of at most 50 moves that the king that starts in any position that is not checked by the amazon and makes any legal moves will eventually be checkmated at some point in this sequence, and will not be stalemated before that. Can you figure out how to do it? How short can such sequence of moves be if the amazon starts at <i>a1</i>?<br /><br />Thanks for reading, and check back next week!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/LGdOd1s_n6M" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2016/12/an-amazon-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-16567155685540032702016-12-18T01:13:00.000+03:002016-12-18T01:13:51.087+03:00A dfs 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/-xeYEyKX3Se8/WFWviWsocmI/AAAAAAAA9oE/LJUadeKahiMRCfMVKaGJCF-xQ7URfBsNgCLcB/s1600/cf383top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="164" src="https://1.bp.blogspot.com/-xeYEyKX3Se8/WFWviWsocmI/AAAAAAAA9oE/LJUadeKahiMRCfMVKaGJCF-xQ7URfBsNgCLcB/s640/cf383top5.png" width="640" /></a></div>Codeforces Round 383 was the main event of the last week (<a href="http://codeforces.com/contest/741">problems</a>, <a href="http://codeforces.com/contest/741/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/48871">analysis</a>). TooDifficult has regained the second place in the overall rankings thanks to his victory; his 2017 ACM ICPC World Finals rival mnbvmar is now ranked sixth thanks to his second place in this round. Well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-8zQ9otnlh6M/WFW4SfhKlbI/AAAAAAAA9ok/RrabFZtt69Uv3AMlxo7KkCyRNZ2gEOxEwCLcB/s1600/IMAG1788.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="362" src="https://2.bp.blogspot.com/-8zQ9otnlh6M/WFW4SfhKlbI/AAAAAAAA9ok/RrabFZtt69Uv3AMlxo7KkCyRNZ2gEOxEwCLcB/s640/IMAG1788.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2016/12/a-maze-week.html">my previous summary</a>, I have mentioned an unsolved NEERC 2016 problem where your program explores a maze with at most 20 rooms which look exactly the same. Each room of the maze has the same amount <i>m</i> (also at most 20) of outgoing one-way passages which also look exactly like one another, arranged in a circle. The only way not to get completely lost in this maze is to use the fact that each room also has a movable rock. Initially there's a rock is in the center of each room. When you leave a room, you can put the rock next to any outgoing passage, and moreover, you can choose whether to put it to the left or to the right of this passage (that means that there are 2<i>m</i> ways to put it). If you ever arrive in this room again, you will see whether the rock is placed to the left or to the right of a passage - but since all passages look the same, you won't have any other information! So now you will be able express the number of the passage to take, and the number of the passage to move the rock to by the number in clockwise order starting from the one marked with the rock when you arrive. Your goal is to visit all rooms in at most 20000 steps.<br /><br />The solution is explained with pictures in <a href="http://neerc.ifmo.ru/archive/2016/neerc-2016-review.pdf">the published analysis PDF</a> (problem I), but let me repeat the outline here. We will implement a depth-first traversal of our graph. However, depth-first traversal sometimes needs to go back, and we can't do that since the passages are one-way. However, since the graph is strongly connected (it looks like I forgot to mention this property in the problem statement summary), there's always some way to get back. The main idea is: when leaving the vertex for the last time, mark the passage that leads as high up as possible in the depth first search tree. This way when we find ourselves in an already processed vertex, we can just follow the marked passages to get back to the current depth first search path. And inside that path, we will mark the passages that lead down this path, so that when we return to this path, we can then get down to the vertex that's being currently processed by the dfs. We can use left/right positioning of the rock to distinguish the vertices on the path ("grey") and the already processed vertices ("black"). There are some more technical details to the solution, but all ideas are above.<br /><br />I find this problem very appealing for multiple reasons, one of them being that the solution is "tight": the amount of information we can store in the visited rooms turns out to be barely enough to perform the traversal. How can one come up with such tight problems?</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/UWFvwH6Bj44" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2016/12/a-dfs-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-31813824967121935512016-12-05T23:35:00.000+03:002016-12-05T23:35:40.905+03:00A maze 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/-9SCdIBOS5Es/WEXNNBFRgzI/AAAAAAAA9bQ/zGDntRQZAWgFLgTGv66otYaIEuh5oxyHgCLcB/s1600/codefestival2016grandfinaltop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="272" src="https://1.bp.blogspot.com/-9SCdIBOS5Es/WEXNNBFRgzI/AAAAAAAA9bQ/zGDntRQZAWgFLgTGv66otYaIEuh5oxyHgCLcB/s640/codefestival2016grandfinaltop5.png" width="640" /></a></div>Last week was quite a bit calmer than its predecessors. On Monday, Code Festival 2016 wrapped up the festivities with its Grand Final (<a href="http://cf16-exhibition-final.contest.atcoder.jp/assignments">problems</a>, <a href="http://cf16-exhibition-final.contest.atcoder.jp/standings">results</a>, top 5 on the left, <a href="http://cf16-exhibition-final-open.contest.atcoder.jp/standings">online mirror results</a>, <a href="https://goo.gl/Ntgoek">analysis</a>). It was W4yneb0t's day, as he managed to deny tourist a somewhat expected victory by solving the same amount of problems, but a more expensive set of them. Big congratulatons!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-yTS09R7RveE/WEXNniQz45I/AAAAAAAA9bU/MOXlydlFtuYBIxcTn_3zE2i8nH7NO4FDwCLcB/s1600/neerc2016top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="136" src="https://3.bp.blogspot.com/-yTS09R7RveE/WEXNniQz45I/AAAAAAAA9bU/MOXlydlFtuYBIxcTn_3zE2i8nH7NO4FDwCLcB/s640/neerc2016top5.png" width="640" /></a></div>I did not cover a lot of ACM ICPC regionals this season, but now is a good time to start :) ACM ICPC 2016-17 NEERC took place on Sunday in St Petersburg, Barnaul, Tbilisi and Almaty (<a href="http://neerc.ifmo.ru/information/problems.pdf">problems</a>, <a href="http://neerc.ifmo.ru/information/standings.html">results</a>, top 5 on the left). One of the main events of the year for most of ex-USSR algorithmic competition community, and the main event of their entire algorithmic competition career for many teams who practice for multiple years for this one chance to advance to the World Finals. One can experience a very wide spectrum of emotions just by watching the NEERC award ceremony where some teams are full of joy and are not at all shy to share that moment with everybody, while others ruminate over the far-reaching consequences of just one bad day. Nevertheless, the community stays very close and friendly, and kudos to everybody for keeping the spirit going! And last but not the least, congratulations to the team SPb SU Base on the victory!<br /><br />Problem I was left unsolved in the onsite competition, and it's a pity since I find it really beautiful. It's an interactive problem where your program explores a maze with at most 20 rooms which look exactly the same. Each room of the maze has the same amount <i>m</i> (also at most 20) of outgoing one-way passages which also look exactly like one another, arranged in a circle. The only way not to get completely lost in this maze is to use the fact that each room also has a movable rock. Initially there's a rock is in the center of each room. When you leave a room, you can put the rock next to any outgoing passage, and moreover, you can choose whether to put it to the left or to the right of this passage (that means that there are 2<i>m</i> ways to put it). If you ever arrive in this room again, you will see whether the rock is placed to the left or to the right of a passage - but since all passages look the same, you won't have any other information! So now you will be able express the number of the passage to take, and the number of the passage to move the rock to by the number in clockwise order starting from the one marked with the rock when you arrive. Your goal is to visit all rooms in at most 20000 steps.<br /><br />The problem statement is quite abstract, so I encourage you to read in full in <a href="http://neerc.ifmo.ru/information/problems.pdf">the PDF</a> (problem I), especially the sample input/output. After you understand what's going on, however, I find it really exciting to solve!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-tPY94Qs03CY/WEXO5n6-KQI/AAAAAAAA9bo/5i_9b7UFiOkKl84VI1ftp7st9e67Zbp4wCLcB/s1600/IMAG1742.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="362" src="https://2.bp.blogspot.com/-tPY94Qs03CY/WEXO5n6-KQI/AAAAAAAA9bo/5i_9b7UFiOkKl84VI1ftp7st9e67Zbp4wCLcB/s640/IMAG1742.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2016/12/a-makoto-week.html">my previous summary</a>, I have mentioned a CERC problem that had to do with bipartite matchings. You were given a bipartite graph with at most 20 vertices in each part (40 together). A set <i>s</i> of its vertices was called <i>nice</i> if there existed a matching that covers it - in other words, such that for every vertex from <i>s</i> there was an adjacent edge that belongs to the matching. Note that it's not necessary for each end of the matching edges to be in <i>s</i>. Each vertex also had an integer weight. Your goal was to count the number of nice sets (out of at most 2<sup>40</sup> total sets) with total weight exceeding the given threshold <i>t</i>.<br /><br />I won't describe its detailed solution, but I will mention the main idea that makes this problem tractable. At first sight, we have 2<sup>40</sup> sets which is way too much to handle one-by-one. However, it turns out that a set <i>s</i> consisting of some set <i>x</i> of vertices of the first part and some set <i>y</i> of vertices of the second part can be covered by a matching <i>if and only if</i> both <i>x</i> can be covered by a matching and <i>y</i> can be covered by a matching (but those don't have to be the same matching)! This idea allows to reduce the number of sets to consider to 2<sup>20</sup>, which is tractable.<br /><br />Thanks for reading, and check back for this week's summary! </div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/d53CzpKWb9g" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2016/12/a-maze-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-85035569166716996142016-12-05T23:22:00.000+03:002016-12-05T23:22:39.472+03:00A Makoto 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/-G2GBsJZRTM4/WEVVT7rhDsI/AAAAAAAA9ac/5lOxlJ144-c4VLfX4kX4ahPP4Y3-_kgywCLcB/s1600/tco16finalstop6.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" src="https://1.bp.blogspot.com/-G2GBsJZRTM4/WEVVT7rhDsI/AAAAAAAA9ac/5lOxlJ144-c4VLfX4kX4ahPP4Y3-_kgywCLcB/s1600/tco16finalstop6.png" /></a></div>TopCoder Open 2016 Final fell on the Nov 21 - Nov 27 week (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=16842">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats&rd=16842&dn=1">results</a> on the left, <a href="http://blog.brucemerry.org.za/2016/11/tco-2016-finals.html">analysis by Bruce</a>). The final results have all finalists sorted by rating, with one notable exception: rng_58 has completely dominated the field, already winning on the first two problems but also adding the 1000-pointer to make it clear that others don't stand a chance. Extremely well done! With this result, Makoto is 3 out of 3 for TCO finals.<br /><br />Here's what <a href="https://community.topcoder.com/stat?c=problem_statement&pm=14250&rd=16842">the 1000-pointer</a> was about. You are given an undirected graph with at most 14 vertices. You make at most 50000 copies of this graph, without any edges between them, to obtain a bigger graph (with at most 14*50000 vertices). Then, you replace the resulting graph with its complement: for each pair of vertices connected by an edge, you remove that edge, and for each pair of vertices that don't have a connecting edge, you add one. How many Hamiltonian paths does the complementary graph have, modulo 998244353?<br /><br /><div class="separator" style="clear: both; text-align: center;"></div><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-4giWwqGxf_A/WEXJ7U7RbEI/AAAAAAAA9a0/1EGfYZAl-VAjoiLAaNdAj-duXg8hk_Q4ACLcB/s1600/cf381top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="166" src="https://4.bp.blogspot.com/-4giWwqGxf_A/WEXJ7U7RbEI/AAAAAAAA9a0/1EGfYZAl-VAjoiLAaNdAj-duXg8hk_Q4ACLcB/s640/cf381top5.png" width="640" /></a></div>Codeforces resumed its contests after a month-long break with Round 381 on Wednesday (<a href="http://codeforces.com/contest/739">problems</a>, <a href="http://codeforces.com/contest/739/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/48582">analysis</a>). TooDifficult continued his streak of victories, adding this round to the last two TopCoder SRMs. Amazing consistency!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-U9SFBI-gesU/WEXKArzy3_I/AAAAAAAA9a4/JefYAh2do287ww3J0UuiWCqA8TVTmOADgCLcB/s1600/codefestival2016finaltop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="282" src="https://1.bp.blogspot.com/-U9SFBI-gesU/WEXKArzy3_I/AAAAAAAA9a4/JefYAh2do287ww3J0UuiWCqA8TVTmOADgCLcB/s640/codefestival2016finaltop5.png" width="640" /></a></div>On Saturday, a brand new international onsite competition called Code Festival and ran by AtCoder took off in Tokyo. It has featured a diverse set of competitions, with the Code Festival 2016 Final being the closest to traditional rounds (<a href="http://cf16-final.contest.atcoder.jp/assignments">problems</a>, <a href="http://cf16-final.contest.atcoder.jp/standings">results</a>, top 5 on the left, <a href="http://cf16-final-open.contest.atcoder.jp/standings">online mirror results</a>, <a href="https://goo.gl/kpgYqj">analysis</a>). Only current and recent university students were allowed to join, nevertheless the field was top-notch. Facing very tough competition, tourist rose to the challenge and won in style by being the only one to solve all tasks. Congratulations!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-ps-VgWBxPyc/WEXKHiW80nI/AAAAAAAA9a8/7AfSC42Loz8GyBW8-INtVi8bXYp9aVbawCLcB/s1600/oc1617r8top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="164" src="https://4.bp.blogspot.com/-ps-VgWBxPyc/WEXKHiW80nI/AAAAAAAA9a8/7AfSC42Loz8GyBW8-INtVi8bXYp9aVbawCLcB/s640/oc1617r8top5.png" width="640" /></a></div>Open Cup 2016-17 Grand Prix of Europe on Sunday has completed the run of 5 consecutive Open Cup weekends (<a href="http://opencup.ru/files/och/gp8/problems1-e.pdf">problems</a>, <a href="http://opentrains.snarknews.info/~ejudge/res/res10358">results</a>, top 5 on the left, <a href="http://cerc.hsin.hr/index.php?page=results">CERC results on the same problems</a>, <a href="https://dl.dropboxusercontent.com/u/1909330/CERC%202016-%20Presentation%20of%20solutions.pdf">analysis</a>). This time ITMO 1 was head and shoulders above everybody, winning 11-9 (11-10 if you take CERC into account) - really unbelievable result! My team in particular got stuck after solving 8 problems in 3 hours, and couldn't solve any of the remaining 4 tasks in the last 2 hours. Also notable is Makoto solving 9 problems single-handedly. He was really on a roll that week :)<br /><br />Problem B in this round relied on a sound yet not widely known theoretical fact. You were given a bipartite graph with at most 20 vertices in each part (40 together). A set <i>s</i> of its vertices was called <i>nice</i> if there existed a matching that covers it - in other words, such that for every vertex from <i>s</i> there was an adjacent edge that belongs to the matching. Note that it's not necessary for each end of the matching edges to be in <i>s</i>. Each vertex also had an integer weight. Your goal was to count the number of nice sets (out of at most 2<sup>40</sup> total sets) with total weight exceeding the given threshold <i>t</i>.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-DHWo3Dvt8t8/WEXKl5N6EXI/AAAAAAAA9bA/vhdGR8Ezi40YotRbP8Kma0rcyCU-XvT0wCLcB/s1600/cf382top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="162" src="https://4.bp.blogspot.com/-DHWo3Dvt8t8/WEXKl5N6EXI/AAAAAAAA9bA/vhdGR8Ezi40YotRbP8Kma0rcyCU-XvT0wCLcB/s640/cf382top5.png" width="640" /></a></div>Finally, Codeforces Round 382 wrapped up the week on Sunday night (<a href="http://codeforces.com/contest/736">problems</a>, <a href="http://codeforces.com/contest/736/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/48659">analysis</a>). The coders in places from 3rd to 5th could've grabbed the first place if they could simply finish solving all problems in time, and that seems to have been quite doable, with more than 30 minutes left for Haghani and overtroll, and more than an hour left for MainDullMoeHand for just one problem - but they couldn't, and jcvb submitted his last problem with just 5 minutes to go to claim the victory. Well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-Vs9TwmZeoWM/WEXLwjgJ-dI/AAAAAAAA9bI/RcU1Cz--QxQG9oKqT0Rj0fyvGy8GgHDSgCLcB/s1600/20161122_123057.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="360" src="https://1.bp.blogspot.com/-Vs9TwmZeoWM/WEXLwjgJ-dI/AAAAAAAA9bI/RcU1Cz--QxQG9oKqT0Rj0fyvGy8GgHDSgCLcB/s640/20161122_123057.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2016/12/an-and-clique-week.html">my previous summary</a>, I have mentioned the problem that threw TCO 2016 Semifinal 2 into turmoil. You are given 1000 positive integers up to 10<sup>18</sup>. You need to find any subset of those integers with the following two properties:<br /><br /><ol style="text-align: left;"><li>Bitwise <i>and</i> of all integers in the subset is zero.</li><li>For any two integers in the subset, their bitwise <i>and</i> is not zero.</li></ol><br />The problem statement sounds so simple, and yet the solution is very hard to spot, so let me describe it. Since the bitwise and of all integers in the sought subset is zero, for every bit (position in the binary representation) at least one of the numbers in the subset doesn't have it set. Here comes the key idea: if there exists any such subset, then there exists such subset and a bit such that <i>exactly </i>one of the numbers in the subset doesn't have this bit set. Why? Because when for each bit at least two numbers don't have it, we can remove any number from the subset without violating properties 1 or 2.<br /><br />Now the problem becomes polynomial instead of exponential. Let's iterate over which bit will be present in all numbers except one, and which number will not have it. Which other numbers could we take into the subset? The numbers that have the chosen bit set and also have non-zero bitwise and with the chosen number. Property 2 will then always hold since all of those numbers have the chosen bit and thus non-zero bitwise ands, And for property 1, more numbers is always better, so we can afford to just take <i>all</i> numbers described above! We just need to check if their overall bitwise and (together with the first chosen number) is zero, and if yes, we have found our answer.<br /><br />One reason this solution seems quite hard to spot is that it operates in a counter-intuitive manner. On the first step, we're <i>reducing </i>our subset to achieve the desired property. But on the second step, we're actually <i>expanding</i> it back.<br /><br />Thanks for reading, and check back soon for the last week's summary!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/qVK4BbqjjBI" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2016/12/a-makoto-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-39918712550230075712016-12-04T14:50:00.000+03:002016-12-04T14:50:07.196+03:00An and-clique 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/-6p-EzYTuAH4/WEQAKUgrmUI/AAAAAAAA9ZM/BsdyLuYA1tolwIQeFaWl6OKwtbdRkP5WwCLcB/s1600/srm702top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="78" src="https://3.bp.blogspot.com/-6p-EzYTuAH4/WEQAKUgrmUI/AAAAAAAA9ZM/BsdyLuYA1tolwIQeFaWl6OKwtbdRkP5WwCLcB/s640/srm702top5.png" width="640" /></a></div>The Nov 14 - Nov 20 week was busier. TopCoder SRM 702 on Tuesday was the last chance to practice before the TopCoder Open weekend (<a href="https://community.topcoder.com/stat?c=round_overview&rd=16832">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=16832&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://apps.topcoder.com/wiki/display/tc/SRM+702">analysis</a>). xudyh won the second SRM in a row, and was the only one to solve all three problems. Congratulations!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-oALwO5ipFXI/WEQAnwvMJfI/AAAAAAAA9ZQ/KNliecGOpfYF5UUka79V0EoIiOolHaMDQCLcB/s1600/tco16semi1top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="106" src="https://4.bp.blogspot.com/-oALwO5ipFXI/WEQAnwvMJfI/AAAAAAAA9ZQ/KNliecGOpfYF5UUka79V0EoIiOolHaMDQCLcB/s640/tco16semi1top5.png" width="640" /></a></div>The onsite event of TopCoder Open 2016, one of the main tournaments of the year, started with Semifinal 1 on Saturday (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=16839">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats&rd=16839&dn=1">results</a> on the left, <a href="http://blog.brucemerry.org.za/2016/11/topcoder-open-2016-semifinal-1.html">analysis by Bruce</a>). Top 3 advanced to the final round next Monday, and everything was essentially decided by the speed on <a href="https://community.topcoder.com/stat?c=problem_statement&pm=14297&rd=16839">the 500-pointer</a>. The problem statement was extremely simple: one needs to construct any weighted directed graph with at most 20 vertices that has exactly the given amount <i>k</i> of different minimum cuts. <i>k</i> is up to 1000.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/--2DhdohovX4/WEQA6Xs7yII/AAAAAAAA9ZU/aDyNAU6mEXU_sU79hr83ssbQOby6WYaJwCLcB/s1600/oc1617r7top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="174" src="https://3.bp.blogspot.com/--2DhdohovX4/WEQA6Xs7yII/AAAAAAAA9ZU/aDyNAU6mEXU_sU79hr83ssbQOby6WYaJwCLcB/s640/oc1617r7top5.png" width="640" /></a></div>Open Cup 2016-17 Grand Prix of Dolgoprudny took place early on Sunday (<a href="http://opencup.ru/files/och/gp7/problems1-e.pdf">problems</a>, <a href="http://opentrains.snarknews.info/~ejudge/res/res10357">results</a>, top 5 on the left). Team Past Glory retook the ground they lost to ITMO 1 in the overall standings a week ago - well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-6SurXNGmrT0/WEQBPw3ibUI/AAAAAAAA9Zc/6BvJAdxuaO0-Je9db283keq1b5A2aM9VwCLcB/s1600/tco16semi2top4.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="106" src="https://1.bp.blogspot.com/-6SurXNGmrT0/WEQBPw3ibUI/AAAAAAAA9Zc/6BvJAdxuaO0-Je9db283keq1b5A2aM9VwCLcB/s640/tco16semi2top4.png" width="640" /></a></div>Finally, TopCoder Open 2016 Semifinal 2 determined 3 more finalists (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=16841">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats&rd=16841&dn=1">results</a> on the left, <a href="http://blog.brucemerry.org.za/2016/11/tco-2016-semifinal-2-solutions.html">analysis by Bruce</a>). Unlike the first semifinal, which went more or less normal, this round was very unusual. For the first 10-15 minutes none of the participants, and almost none of the observers, could figure out how to solve the easiest 250-pointer problem. Because of that, the advancement in this round hinged on the ability to give up on a problem and clear one's head before the next one. It's worth mentioning that the 500-pointer was also in no way obvious. Congratulations to Enot on successfully navigating the tricky round and coming out on top!<br /><br />Here's <a href="https://community.topcoder.com/stat?c=problem_statement&pm=14448&rd=16841">the problem</a> that puzzled everybody. You are given 1000 positive integers up to 10<sup>18</sup>. You need to find any subset of those integers with the following two properties:<br /><br /><ol style="text-align: left;"><li>Bitwise <i>and</i> of all integers in the subset is zero.</li><li>For any two integers in the subset, their bitwise <i>and</i> is not zero.</li></ol>Can you see the key solution idea?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-k96Qv4WWPfQ/WEQCyR0MlLI/AAAAAAAA9Z4/CFRHNbgq84cKGbM9BsklRvkLAJ38sIWZwCLcB/s1600/IMAG1562.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="362" src="https://4.bp.blogspot.com/-k96Qv4WWPfQ/WEQCyR0MlLI/AAAAAAAA9Z4/CFRHNbgq84cKGbM9BsklRvkLAJ38sIWZwCLcB/s640/IMAG1562.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2016/12/a-cosplay-week.html">my previous summary</a>, I have mentioned an easy problem: you are given an <i>n</i> times <i>n</i> grid of uppercase English characters, where <i>n</i> is at least 3. This grid was built in the following way: first, we fill it with <i>n</i> different characters in such a way that each row and each column has exactly one occurrence of each character. Then, we replace exactly one character in the entire grid with another character. Your goal is to figure out which character has been replaced, and what was there originally.<br /><br />Here's a solution that's very easy to implement. First, we count the number of times each letter appears in the grid, and find letters that appear at least twice. Those are the original letters. Then, for each row and column of the grid we check if they contain at least one appearance of those letters. We will find exactly one row and exactly one column that will be missing one of those letters - and those are precisely the row, column and letter that we need to output.<br /><br />Thanks for reading, and check back later for more!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/29mv0mtCTHw" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2016/12/an-and-clique-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-42166427645533973852016-12-03T15:13:00.000+03:002016-12-03T15:13:30.933+03:00A cosplay 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/-3q8leDh4kzg/WEKxxCtZIgI/AAAAAAAA81Y/37DtkgjIv4I7Fo4ZY5cpj8fdRjUmGsJpgCLcB/s1600/agc007top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="244" src="https://1.bp.blogspot.com/-3q8leDh4kzg/WEKxxCtZIgI/AAAAAAAA81Y/37DtkgjIv4I7Fo4ZY5cpj8fdRjUmGsJpgCLcB/s640/agc007top5.png" width="640" /></a></div>The Nov 7 - Nov 13 week woke up late with AtCoder Grand Contest 007 on Saturday (<a href="http://agc007.contest.atcoder.jp/assignments">problems</a>, <a href="http://agc007.contest.atcoder.jp/standings">results</a>, top 5 on the left, <a href="http://agc007.contest.atcoder.jp/data/agc/007/editorial.pdf">analysis</a>). The problemset seems quite well-rounded, offering competitors a choice of different strategies. cospleermusora has figured out the winning strategy this time - start with the three hardest problems since they're worth a lot more points, and then solve whichever easy problems there's time for. Great idea and execution!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-LAZCNIqo6tQ/WEKzMaRbAOI/AAAAAAAA81o/o-07t2il-zENaH8YVhlGsBMlfvr8MtXSACLcB/s1600/oc1617r6top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="186" src="https://4.bp.blogspot.com/-LAZCNIqo6tQ/WEKzMaRbAOI/AAAAAAAA81o/o-07t2il-zENaH8YVhlGsBMlfvr8MtXSACLcB/s640/oc1617r6top5.png" width="640" /></a></div>Open Cup 2016-17 Czech Grand Prix took the usual Sunday spot (<a href="http://opencup.ru/index.cgi?data=macros/stage&head=index&menu=index&stg=6&region=main&ncup=och&class=och">results</a>, top 5 on the left). The ITMO 1 team won again and started to create quite a gap at the top of the overall standings. Amazing performance!<br /><br />Problem J in this round was very easy, and yet it required some thinking to avoid too many special cases in code. You are given an <i>n</i> times <i>n</i> grid of uppercase English characters, where <i>n</i> is at least 3. This grid was built in the following way: first, we fill it with <i>n</i> different characters in such a way that each row and each column has exactly one occurrence of each character. Then, we replace exactly one character in the entire grid with another character. Your goal is to figure out which character has been replaced, and what was there originally.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-Zrbz3PhJbIc/WEKzcMWzN3I/AAAAAAAA81s/Um23oZ5l00wI0qzQunaFlMfuXxegUOuOgCKgB/s1600/IMAG1757.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="200" src="https://3.bp.blogspot.com/-Zrbz3PhJbIc/WEKzcMWzN3I/AAAAAAAA81s/Um23oZ5l00wI0qzQunaFlMfuXxegUOuOgCKgB/s200/IMAG1757.jpg" width="193" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2016/11/yet-another-triangle-week.html">my previous summary</a>, I've mentioned an interactive Open Cup problem: the judging program has a hidden non-degenerate triangle. The coordinates of its vertices are integers not exceeding 1000 by absolute value. You're allowed to make at most 1000 queries, and your goal is to determine the coordinates of the vertices of the triangle. In each query, you choose a line (more precisely, a half-plane), and you're told the areas of the two parts this line splits the triangle into (one of them can be 0 if it doesn't intersect the triangle).<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-HzVcpzI2KQ8/WEKzreiN-zI/AAAAAAAA810/_-lOfVrEBCwfd5IYBfMjHjycTzYkPLK1ACKgB/s1600/IMAG1758.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" height="178" src="https://4.bp.blogspot.com/-HzVcpzI2KQ8/WEKzreiN-zI/AAAAAAAA810/_-lOfVrEBCwfd5IYBfMjHjycTzYkPLK1ACKgB/s200/IMAG1758.jpg" width="200" /></a></div>Here is the solution of our team, which we've created together with Michael Levin: first, we figure out the bounding box of the triangle, using binary search with horizontal and vertical half-planes. At least one of the corners of the bounding box is a vertex of the triangle, which we can find using a 45-degree half-plane which cuts off just one small corner from the bounding box.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-TNTL38Oz6Qs/WEK2mUx2j7I/AAAAAAAA82g/6Jg-y-nJ1dUEjsLacU4WfO4qdJlTA9oDgCKgB/s1600/IMAG1759.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="172" src="https://2.bp.blogspot.com/-TNTL38Oz6Qs/WEK2mUx2j7I/AAAAAAAA82g/6Jg-y-nJ1dUEjsLacU4WfO4qdJlTA9oDgCKgB/s200/IMAG1759.jpg" width="200" /></a></div>When we know a vertex and a 90 degree angle containing the rest, we can use binary search by angle using lines passing through this vertex to find the lines containing the two sides. Finally, we can find the remaining two vertices by binary searching along one of the lines with half-planes parallel to the other line.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-4R-qCaPye-I/WEK2p66TpNI/AAAAAAAA82k/849DiQ8NAeMNKvVnhSMf8TR7V-wz4w2-QCKgB/s1600/IMAG1760.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" height="195" src="https://4.bp.blogspot.com/-4R-qCaPye-I/WEK2p66TpNI/AAAAAAAA82k/849DiQ8NAeMNKvVnhSMf8TR7V-wz4w2-QCKgB/s200/IMAG1760.jpg" width="200" /></a></div>This solution has 4 steps, with the first and last step sharing the same binary search problem (given a direction, find the first half-plane with this direction that has non-zero intersection area), so one needed to implement 3 different functions for the interaction. On the good side, the solution doesn't have any special casing at all.<br /><br />Do you know a simpler approach?</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/pC-qN-LaYMI" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2016/12/a-cosplay-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-13810166974358815082016-11-20T19:16:00.001+03:002016-11-20T19:21:03.949+03:00Yet another triangle 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/-f1wzs8vyvmo/WDG8elui-jI/AAAAAAAA8hg/Oxx_LuNjRXwrN_aiGdWSHmOOKN7OpJ-dACLcB/s1600/oc1617r5top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="170" src="https://1.bp.blogspot.com/-f1wzs8vyvmo/WDG8elui-jI/AAAAAAAA8hg/Oxx_LuNjRXwrN_aiGdWSHmOOKN7OpJ-dACLcB/s640/oc1617r5top5.png" width="640" /></a></div>The first November week included the fifth stage of the 2016-17 Open Cup, the Grand Prix of Siberia (<a href="http://opencup.ru/files/och/gp5/problems1-e.pdf">problems</a>, <a href="http://opentrains.snarknews.info/~ejudge/res/res10355">results</a>, top 5 on the left). Team Havka-papstvo dominated the proceedings, and topped the cake with the only passing solution for the very tedious problem 10 - congratulations!<br /><br />I'd like to highlight the interactive problem 3, which turned out to be the second most difficult. The judging program has a hidden non-degenerate triangle. The coordinates of its vertices are integers not exceeding 1000 by absolute value. You're allowed to make at most 1000 queries, and your goal is to determine the coordinates of the vertices of the triangle. In each query, you choose a line (more precisely, a half-plane), and you're told the areas of the two parts this line splits the triangle into (one of them can be 0 if it doesn't intersect the triangle). There are two steps to solving this one: figuring out how to do it, and then figuring out how to do it in such a way that the implementation isn't a nightmare :)<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-nk5G0uQwzzQ/WDHMVYmZdaI/AAAAAAAA8iI/wu-lAvdYYD8TWWaFzc2dni6dYIa4tfSLQCLcB/s1600/IMAG1473.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="362" src="https://3.bp.blogspot.com/-nk5G0uQwzzQ/WDHMVYmZdaI/AAAAAAAA8iI/wu-lAvdYYD8TWWaFzc2dni6dYIa4tfSLQCLcB/s640/IMAG1473.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2016/11/a-triangle-week.html">my previous summary</a>, I've described another triangle problem: you are given 200000 points on the plane which are guaranteed to be randomly placed within a bounding box, and need to find three points which form a triangle with the largest area.<br /><br />The solution is surprisingly straightforward: we find the convex hull of the given points, and then try all triangles with vertices from the convex hull to determine the largest one. It is correct because it's not hard to see that when we fix 2 out of 3 vertices of the triangle, the third one needs to be as far from that line as possible, which means it's a farthest point in some direction, which means it's a vertex of the convex hull. And it is fast enough because it turns out that a set of random points has only O(logn) points on average on its convex hull (see <a href="http://valis.cs.uiuc.edu/~sariel/papers/notes/rand_hull.ps">this paper</a>).<br /><br />Thanks for reading, and check back soon for the next week's summary!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/ekmfuMTw3EA" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2016/11/yet-another-triangle-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-24078153200469649252016-11-20T18:02:00.002+03:002016-11-20T18:57:40.876+03:00A triangle 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/-LNLiXkHZ82Y/WDG2y-wsh-I/AAAAAAAA8hI/CSVrS-B-p04JMG7baoN7L4qvAGXu4S__wCLcB/s1600/srm701top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="80" src="https://4.bp.blogspot.com/-LNLiXkHZ82Y/WDG2y-wsh-I/AAAAAAAA8hI/CSVrS-B-p04JMG7baoN7L4qvAGXu4S__wCLcB/s640/srm701top5.png" width="640" /></a></div>The last week of October was relatively busy. First off, TopCoder SRM 701 took place on Wednesday (<a href="https://community.topcoder.com/stat?c=round_overview&rd=16822">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=16822&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://apps.topcoder.com/wiki/display/tc/SRM+701">analysis</a>). The top 3 could be a foreshadowing for the upcoming TCO 2016 Semifinal 2, but unfortunately xudyh could not make it to Washington (does anybody know why?). Nevertheless, congratulations on the SRM victory!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-SRPkiLckMWo/WDG4BhwnRTI/AAAAAAAA8hU/maIoYotoue0hWSaC8_aCQrH1LZE9DbQBgCLcB/s1600/agc006top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="244" src="https://1.bp.blogspot.com/-SRPkiLckMWo/WDG4BhwnRTI/AAAAAAAA8hU/maIoYotoue0hWSaC8_aCQrH1LZE9DbQBgCLcB/s640/agc006top5.png" width="640" /></a></div>Then, AtCoder held its Grand Contest 006 on Saturday (<a href="http://agc006.contest.atcoder.jp/assignments">problems</a>, <a href="http://agc006.contest.atcoder.jp/standings#page_1">results</a>, top 5 on the left, <a href="http://agc006.contest.atcoder.jp/data/agc/006/editorial.pdf">analysis</a>). apiad has dominated the field by being the only one to solve all problems, and he has also demonstrated an unorthodox strategy by starting from the hardest problems - so he would've been first even if he didn't finish the 3 easier ones!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-DjlqngsHiME/WDG5I4AG-SI/AAAAAAAA8hY/TpCLDiQiDg4uEV_ANIMXFrH6J7eMWEJfACLcB/s1600/oc1617r4top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="172" src="https://3.bp.blogspot.com/-DjlqngsHiME/WDG5I4AG-SI/AAAAAAAA8hY/TpCLDiQiDg4uEV_ANIMXFrH6J7eMWEJfACLcB/s640/oc1617r4top5.png" width="640" /></a></div>And finally, Open Cup 2016-17 Eastern Grand Prix took place on Sunday (<a href="http://opencup.ru/files/och/gp4/problems1-e.pdf">problems</a>, <a href="http://opentrains.snarknews.info/~ejudge/res/res10354">results</a>, top 5 on the left). SPb ITMO 1 team has jumped into a big lead in the overall standings after this round - congratulations!<br /><br />Problem B was on the boundary of "oh, beautiful observation" and "oh, nasty trick" :) Which feeling does it leave you with? You are given 200000 points on the plane which are guaranteed to be randomly placed within a bounding box, and need to find three points which form a triangle with the largest area.<br /><br />Thanks for reading, and check back soon for the November news!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/1cp4LORA9DU" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2016/11/a-triangle-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-55957863078728287262016-11-20T17:40:00.002+03:002016-11-20T17:40:33.180+03:00A Canada 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/-TKY5JMD9TvA/WDG004PLcxI/AAAAAAAA8g4/tqtd-iH8PVg5MlDuUbV6rcROKzHtj14oACLcB/s1600/canadacup2016top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="166" src="https://3.bp.blogspot.com/-TKY5JMD9TvA/WDG004PLcxI/AAAAAAAA8g4/tqtd-iH8PVg5MlDuUbV6rcROKzHtj14oACLcB/s640/canadacup2016top5.png" width="640" /></a></div>The Oct 17 - Oct 23 week featured just the Canada Cup by Codeforces (<a href="http://codeforces.com/contest/725">problems</a>, <a href="http://codeforces.com/contest/725/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/47974">analysis</a>). If not for challenges, just 5 points would've separated eatmore and tzupengwang - congratulations to both! I could not make this round, so I don't have anything to share about its problems.<div><br /></div><div>Check back soon for the hopefully longer summary of the following week :)</div></div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/CQEvJrkxDTI" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2016/11/a-canada-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-24059742787853678572016-11-20T00:40:00.000+03:002016-11-20T00:40:00.923+03:00An unshuffle 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/-zs65FYZYt7A/WDC9BC3QatI/AAAAAAAA8b0/xylCXONdCYUpSNYpNXJ-Fhf-lNH42OXEwCLcB/s1600/srm700top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="78" src="https://1.bp.blogspot.com/-zs65FYZYt7A/WDC9BC3QatI/AAAAAAAA8b0/xylCXONdCYUpSNYpNXJ-Fhf-lNH42OXEwCLcB/s640/srm700top5.png" width="640" /></a></div>During the Oct 10 - Oct 16 week, TopCoder has hit its next milestone: SRM 700 (<a href="https://community.topcoder.com/stat?c=round_overview&rd=16821">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=16821&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://apps.topcoder.com/wiki/display/tc/SRM+700">analysis</a>). Despite the starting time of 4am, the first three spots were occupied by contestants from St Petersburg and Moscow. The first place went to _aid, who has recently joined the ACM ICPC World Champion team SPbSU Base - so all other teams will not have an easy time at 2017 World Finals :) Congratulations!<br /><div><br /></div><div><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-3WQF3AcYunU/WDDGbtbImsI/AAAAAAAA8cQ/ec3FF_YHEG4sT7Lu0kinWDRNqwK0sPJjgCLcB/s1600/IMAG1397.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="362" src="https://2.bp.blogspot.com/-3WQF3AcYunU/WDDGbtbImsI/AAAAAAAA8cQ/ec3FF_YHEG4sT7Lu0kinWDRNqwK0sPJjgCLcB/s640/IMAG1397.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2016/11/a-fourier-combination-week.html">my previous summary</a>, I have mentioned a problem in the trademark style of Ivan Kazmenko: You're given the following random number generator, an implementation of the Fischer-Yates shuffle, and a program using them:</div><div><br /></div><div><span style="font-family: "courier new" , "courier" , monospace;">Function random (range):</span></div><div><span style="font-family: "courier new" , "courier" , monospace;"> state := (state * 1664525 + 1013904223) mod 2<sup>32</sup>;</span></div><div><span style="font-family: "courier new" , "courier" , monospace;"> return (state * range) div 2<sup>32</sup>;</span></div><div><span style="font-family: "courier new" , "courier" , monospace;"><br /></span></div><div><span style="font-family: "courier new" , "courier" , monospace;">Function shuffle (array):</span></div><div><span style="font-family: "courier new" , "courier" , monospace;"> n := length of array;</span></div><div><span style="font-family: "courier new" , "courier" , monospace;"> for i := 0, 1, 2, ..., n - 1:</span></div><div><span style="font-family: "courier new" , "courier" , monospace;"> j := random (i + 1);</span></div><div><span style="font-family: "courier new" , "courier" , monospace;"> swap(array[i], array[j]);</span></div><div><span style="font-family: "courier new" , "courier" , monospace;"> return array;</span></div><div><span style="font-family: "courier new" , "courier" , monospace;"><br /></span></div><div><span style="font-family: "courier new" , "courier" , monospace;">state := seed;</span></div><div><span style="font-family: "courier new" , "courier" , monospace;">n := 10000;</span></div><div><span style="font-family: "courier new" , "courier" , monospace;">array := [1, 2, ..., n];</span></div><div><span style="font-family: "courier new" , "courier" , monospace;">array := shuffle (array);</span></div><div><span style="font-family: "courier new" , "courier" , monospace;">array := shuffle (array);</span></div><div><br /></div><div>In other words, we shuffle the numbers from 1 to n twice. The particular generator used here is well-known, so no particular weaknesses could be expected except of course the fact that it's a linear congruential generator. The task is: given the final state of the array, find what the seed was.</div><div><br /></div><div>There are two main ideas necessary to solve this problem. The first idea is: if we know the numbers that the generator returned on two concrete calls (i.e., on <i>p</i>-th step and on <i>q</i>-th step), there are only so many (on the order of 100) possibilities for the seed that we can try them all, and moreover, we can enumerate all of them efficiently.<br /><br />In order to enumerate them, we can notice that the value of the <i>state</i> variable on <i>p</i>-th step is a linear function of the initial seed. Because of this, having two return values fixed leads to two inequalities that look like <i>l</i> <= <i>seed</i> * <i>a</i> <= <i>r </i>(mod 2<sup>32</sup>)<i>.</i> We can solve this system of inequalities using an algorithm similar to the Euclidean one.<br /><br />The second idea is that it's not actually that hard to find two concrete return values of the generator. During each shuffle, each number participates in at least one swap: when the variable <i>i</i> passes through the cell containing it. It's also not hard to see that on average quite a few numbers will participate in exactly one swap. And because this set of numbers is fairly random for each of the two shuffles, there will be a significant amount of numbers that have participated in exactly two swaps overall. And since we know the starting and ending position for each number, we just need to guess which was its "middle" position after the first swap.<br /><br />So here's the overall solution structure: we iterate over all numbers from <i>n</i> to 1 that have moved to the left after two shuffles. For each of those numbers, we iterate over the "middle" position between the final positions and the starting position. We find all seeds that would make this number do the corresponding jumps, and then check if each of those seeds leads to the overall result we see. We expect to find the seed after trying just a few initial numbers.<br /><br />Thanks for reading, and wish me luck in today's TopCoder Open semifinal (<a href="https://www.timeanddate.com/worldclock/fixedtime.html?msg=TopCoder+Open+2016+Algo+Semifinal+1&iso=20161119T20&p1=263&ah=2">starting time</a>, <a href="https://www.twitch.tv/topcoder_official">broadcast link</a>)!</div></div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/fgCwQjypn2c" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2016/11/an-unshuffle-week.html