tag:blogger.com,1999:blog-19533250797934499712017-10-23T18:32:23.558+03:00Algorithms Weekly by Petr MitrichevPetr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.comBlogger320125PetrMitrichevhttps://feedburner.google.comtag:blogger.com,1999:blog-1953325079793449971.post-22810927601672104492017-10-23T17:08:00.000+03:002017-10-23T18:32:23.582+03:00Commentary stream for TopCoder Open 2017 Semifinal 2 with Egor<div dir="ltr" style="text-align: left;" trbidi="on">We'll try to do live commentary of TopCoder Open 2017 Semifinal 2 with Egor on <a href="https://youtu.be/AqpjM86iZlc">https://youtu.be/AqpjM86iZlc</a> - tune in at <a href="https://www.timeanddate.com/worldclock/fixedtime.html?msg=TopCoder+Open+2017+Semifinal+2&iso=20171023T1330&p1=422&ah=2">19:30 CEST</a>!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/Rjcu_fkmBtw" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/10/commentary-stream-for-topcoder-open.htmltag:blogger.com,1999:blog-1953325079793449971.post-355566935453625702017-10-08T17:18:00.002+03:002017-10-08T17:34:58.607+03:00A randomized 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/-tZCoq7UisDQ/WdoVjoTbgbI/AAAAAAAB4wE/lFOZQ8XD0wEkv3Hidob25PCw0sRI7yO6ACLcBGAs/s1600/srm719top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="150" data-original-width="778" height="123" src="https://2.bp.blogspot.com/-tZCoq7UisDQ/WdoVjoTbgbI/AAAAAAAB4wE/lFOZQ8XD0wEkv3Hidob25PCw0sRI7yO6ACLcBGAs/s640/srm719top5.png" width="640" /></a></div>The Aug 14 - Aug 20 week contained the usual suspects: a TopCoder SRM and a Codeforces round. First off, TopCoder SRM 719 took place in the early Tuesday hours (<a href="https://community.topcoder.com/stat?c=round_overview&rd=16956">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=16956&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://www.topcoder.com/blog/single-round-match-719-editorials/">analysis</a>). yanQval was a lot faster than everybody else and won the round - well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-n7YetRQKC-4/WdoW6SWzudI/AAAAAAAB4wQ/BIVWgnenpfIh03hw9mZI5g9l8kA963B6gCLcBGAs/s1600/cf429top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="273" data-original-width="1106" height="156" src="https://1.bp.blogspot.com/-n7YetRQKC-4/WdoW6SWzudI/AAAAAAAB4wQ/BIVWgnenpfIh03hw9mZI5g9l8kA963B6gCLcBGAs/s640/cf429top5.png" width="640" /></a></div>Codeforces Round 429 followed on Friday (<a href="http://codeforces.com/contest/840">problems</a>, <a href="http://codeforces.com/contest/840/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/53943">analysis</a>). anta and LHiC have both solved their final fifth problem with only a few minutes to spare and thus obtained quite a margin at the top of the scoreboard - way to go!<br /><br /><a href="http://codeforces.com/contest/840/problem/D">Problem D</a> in this round allowed for a cute randomized solution that in my view is a bit easier than the one from the official analysis. The problem was: you are given an array of 300000 numbers, and 300000 queries of the following form: a segment [<i>l</i>;<i>r</i>] and a number <i>k</i>, for which you need to find the smallest number that appears on at least 1/<i>k</i> of all positions in the given segment of the array. Note that <i>k</i> is at most 5, so the number must be quite frequent within the segment. Can you see how to use that fact to implement a simple randomized solution?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-dAzBaTW6ctE/WdoauXCD0VI/AAAAAAAB4wc/cjKIFtLZF4Mnfg9sFwkvN-KwGL1Ls8U4wCLcBGAs/s1600/codechefaug17top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="407" data-original-width="1012" height="256" src="https://1.bp.blogspot.com/-dAzBaTW6ctE/WdoauXCD0VI/AAAAAAAB4wc/cjKIFtLZF4Mnfg9sFwkvN-KwGL1Ls8U4wCLcBGAs/s640/codechefaug17top5.png" width="640" /></a></div>And finally, I've checked out CodeChef August 2017 Cook-Off on Sunday (<a href="https://www.codechef.com/COOK85">problems</a>, <a href="https://www.codechef.com/rankings/COOK85">results</a>, top 5 on the left, <a href="https://youtu.be/uDyzufcNu58">my screencast</a>). EgorK was at the top of the standings with 4 problems for quite some time, but gennady.korotkevich has then submitted his fourth and fifth problems in rapid succession and won the competition. Congratulations!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-JwB3-58ZVcg/WdozgRGexQI/AAAAAAAB4w0/N2WYnVs8ab8JZTKiHyoccknj9zOkV1lJACLcBGAs/s1600/IMG_20170910_172204.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1200" data-original-width="1600" height="480" src="https://4.bp.blogspot.com/-JwB3-58ZVcg/WdozgRGexQI/AAAAAAAB4w0/N2WYnVs8ab8JZTKiHyoccknj9zOkV1lJACLcBGAs/s640/IMG_20170910_172204.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2017/09/a-week-of-22.html">my previous summary</a>, I have mentioned a problem that I have set for Google Code Jam 2017 finals: you are given a number <i>k</i> between 3 and 10000. Output any simple undirected graph with at most 22 vertices that has exactly <i>k</i> spanning trees.<br /><br />The approach that works the most frequently in such problems is to learn several transitions that help cover all required numbers. For example, if we could come up with a way to transition from a graph with <i>k</i> spanning trees to graphs with 2<i>k</i> and 2<i>k</i>+1 spanning trees by adding one vertex, the problem would be solved. Alas, this does not seem possible, as it's not clear how to achieve that extra "+1" spanning tree.<br /><br />As explicit construction turns out to be hard to impossible, we have to turn to more experimental approaches. One thing that stands out is that there's an enormous amount of graphs on 22 vertices, and while they have at most 22<sup>20</sup> spanning trees, many have under 10000 spanning trees, and thus we can hope that for each <i>k</i> in the given range there are many possible answers. So the next idea is to try generating random graphs and checking how many spanning trees those graphs have using <a href="https://en.wikipedia.org/wiki/Kirchhoff%27s_theorem">the matrix tree theorem</a>, hoping to find all numbers between 3 and 10000 at least once.<br /><br />It turns out that some amounts of trees are more difficult to achieve than others, so this approach by itself is not sufficient to generate all answers within reasonable time. However, there are numerous different ideas that help it find all required numbers faster, and thus help get the problem accepted. I won't be surprised if everybody who got this problem accepted at the Code Jam has used a different approach :) My experimentation led me down the following path:<br /><br /><ul style="text-align: left;"><li>Since some numbers are hard to get, we try to steer the random graphs towards those numbers. Suppose we have a "goal" number we're trying to achieve. The easiest way to do that is to avoid recreating the graph from scratch, but instead take the graph from the previous attempt, and check if it has less trees than the goal, or more. In the former case, we add a random edge to it, and otherwise remove one. As a result, we're more likely to hit the goal, and as soon as we do it, we pick another goal from the yet unseen numbers and repeat the process.</li><li>This process has an unfortunate bad state: when we remove an edge, we can make the graph disconnected, thus having 0 spanning trees. At this point we start adding random edges, but if the graph stays disconnected, it keeps having 0 spanning trees. Finally, we add an edge that connects the graph back, but since we have added so many other edges in the meantime, suddenly the graph has a lot of spanning trees, way more than we need. So we need to remove a lot of edges to get back to reasonable numbers, and may well jump back to 0 in the process. Having noticed this happening, I've modified the process to never remove an edge that would make the graph disconnected.</li><li>Finally, we get almost all numbers we need! After a minute or so, my solution has generated all numbers between 3 and 10000 except 13 and 22 (if I remember correctly). The final idea is that small numbers can still be generated by an explicit construction: a cycle with <i>k</i> vertices has <i>k</i> spanning trees. Since we're allowed at most 22 vertices, 13 and 22 can be done using a cycle.</li></ul><div>That's all for my solution, but I have one more question for you: why is 22 so hard to get? In particular, does there exist a simple undirected graph with at most 21 vertices that has 22 spanning trees? I strongly suspect that the answer is no, but don't know for sure.</div><div><br /></div><div>Thanks for reading, and check back later!</div></div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/saZD2yA-i1k" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/10/a-randomized-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-26460887927380099542017-09-27T09:46:00.000+03:002017-09-27T09:46:03.083+03:00A week of 22<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/-TI3DQg6p9x8/Wcs59ZJbPxI/AAAAAAAB4as/7DBMGcdJCls4FEZsEeeSKLWQbtwINj9ZACLcBGAs/s1600/dcj2017finaltop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="308" data-original-width="1265" height="154" src="https://4.bp.blogspot.com/-TI3DQg6p9x8/Wcs59ZJbPxI/AAAAAAAB4as/7DBMGcdJCls4FEZsEeeSKLWQbtwINj9ZACLcBGAs/s640/dcj2017finaltop5.png" width="640" /></a></div>The Aug 7 - Aug 13 week was centered around Google Code Jam final rounds. First off, the 21 finalists competed in the Distributed Code Jam final round on Thursday (<a href="https://code.google.com/codejam/contest/5324486/dashboard#s=p1">problems</a>, <a href="https://code.google.com/codejam/contest/5324486/scoreboard#vt=1">results</a>, top 5 on the left, <a href="https://code.google.com/codejam/contest/5324486/dashboard#s=a">analysis</a>). ecnerwala has snatched the first place with just 3 minutes left in the contest on his 6th attempt on D-small - here's for perseverance :) Congratulations!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-RoU0XPOeHoA/Wcs7Syly3ZI/AAAAAAAB4a4/Bi9xP7E_tdoTNvglFiuW9QDbEl1gAHMngCLcBGAs/s1600/gcj2017finaltop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="308" data-original-width="1593" height="122" src="https://3.bp.blogspot.com/-RoU0XPOeHoA/Wcs7Syly3ZI/AAAAAAAB4a4/Bi9xP7E_tdoTNvglFiuW9QDbEl1gAHMngCLcBGAs/s640/gcj2017finaltop5.png" width="640" /></a></div>One day later, the traditional Google Code Jam final round saw its 26 finalists compete for the first place (<a href="https://code.google.com/codejam/contest/6314486/dashboard#s=p2">problems</a>, <a href="https://code.google.com/codejam/contest/6314486/scoreboard?c=6314486#vt=1">results</a>, top 5 on the left, <a href="https://code.google.com/codejam/contest/6314486/dashboard#s=a">analysis</a>, <a href="https://youtu.be/Pq-wdw9TRoI">commentary stream</a>). Gennady.Korotkevich has won the Code Jam for the fourth year in a row - well done! He has given everybody else a chance this time by solving only two large inputs, but his competitors could not catch up for various reasons. SnapDragon was leading going into the system test phase, but he knew himself that his solution for D-large was incorrect as it was not precise enough. Second-placed zemen could have claimed the victory had he solved C instead of E-small or F-small or both in the last hour.<br /><br />I have set the said problem C for this round, which went like this: you are given a number <i>k</i> between 3 and 10000. Output any simple undirected graph with at most 22 vertices that has exactly <i>k</i> spanning trees. I don't think it is solvable just in one's head, but if you have some time to experiment on a computer, I think it's an interesting problem to try!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-_Txk3kP2Wws/WctI0mmNh6I/AAAAAAAB4bM/7ULE2_MQxBwxx_RhnOxR9mnhj80pSyYsQCLcBGAs/s1600/IMG_20170730_124516.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1200" data-original-width="1600" height="480" src="https://1.bp.blogspot.com/-_Txk3kP2Wws/WctI0mmNh6I/AAAAAAAB4bM/7ULE2_MQxBwxx_RhnOxR9mnhj80pSyYsQCLcBGAs/s640/IMG_20170730_124516.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2017/09/a-2-sat-week.html">my previous summary</a>, I have mentioned a TopCoder problem: given a tree with <i>n</i><=250 vertices, you need solve a system of at most 250 equations on this tree with <i>m</i><=250 variables <i>x</i><sub>1</sub>, <i>x</i><sub>2</sub>, ..., <i>x<sub>m</sub></i> , where each variable must correspond to some vertex in the tree. Several variables can correspond to the same vertex. Each equation has the following form: in the path from vertex <i>x<sub>a<sub>i</sub></sub></i> to vertex <i>x<sub>b<sub>i</sub></sub></i> the vertex closest to vertex <i>p<sub>i</sub></i> must be the vertex <i>q<sub>i</sub></i>.<br /><br />If we look at the tree as rooted at vertex <i>p<sub>i</sub></i>, the corresponding equation means that both <i>x<sub>a<sub>i</sub></sub></i> and <i>x<sub>b<sub>i</sub></sub></i> must be in the subtree of the vertex <i>q<sub>i</sub></i>, and there must be no child of <i>q<sub>i</sub></i> such that both <i>x<sub>a<sub>i</sub></sub></i> and <i>x<sub>b<sub>i</sub></sub></i> are in the subtree of this child. At this point one had to strongly suspect this problem will reduce to a <a href="https://en.wikipedia.org/wiki/2-satisfiability">2-SAT</a> instance with boolean variables corresponding to "this variable is in this subtree". The equations are already in 2-SAT form on these boolean variables as described above, but the tricky part is to come up with additional clauses that guarantee that the values of boolean variables are consistent and we can pick one vertex for each variable.<br /><br />First difficulty is that the tree is rooted differently for each equation. However, we can notice that each subtree of any re-rooting of the given tree is either a subtree of this tree when rooted at the first vertex, or a complement of such subtree. So if we have boolean variables for "<i>x<sub>i</sub></i> is in the subtree of vertex <i>y</i> when rooted at vertex 1", then the complementary subtrees can be expressed simply as negations of those variables, as each <i>x<sub>i</sub></i> must go to some vertex.<br /><br />Second difficulty is ensuring that when we look at all subtrees which contain a given <i>x<sub>i</sub></i> according to our boolean variables, they have exactly one vertex in their intersection that we can assign <i>x<sub>i</sub></i> to. It turns out that this can be achieved using simple clauses "if <i>x<sub>i</sub></i> is in the subtree of a vertex, it's also in the subtree of its parent, and not in subtrees of its siblings", which are handily in 2-SAT form. We can then find the deepest vertex containing <i>x<sub>i</sub></i> in its subtree according to the values of the boolean variables, and it's not hard to see that all clauses will be consistent when <i>x<sub>i</sub></i> is placed in that vertex.<br /><br />Thanks for reading, and check back later for more competitive programming news!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/Q_KOurCUyXw" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/09/a-week-of-22.htmltag:blogger.com,1999:blog-1953325079793449971.post-55935214235008737822017-09-24T21:09:00.001+03:002017-09-24T21:09:30.069+03:00A 2-SAT 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/-DXzmncOm73c/WcfhlrM7hmI/AAAAAAAB4Zw/xAp8J0dtRiYEKapNFigp01suuVpIaWmFQCLcBGAs/s1600/ioi2017top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="226" data-original-width="1361" height="106" src="https://1.bp.blogspot.com/-DXzmncOm73c/WcfhlrM7hmI/AAAAAAAB4Zw/xAp8J0dtRiYEKapNFigp01suuVpIaWmFQCLcBGAs/s640/ioi2017top5.png" width="640" /></a></div>The contests of July 31 - Aug 6 week started with the second competition day of IOI 2017 on Tuesday (<a href="http://ioi2017.org/contest/tasks/">problems</a>, <a href="http://scoreboard.ioi2017.org/Ranking.html">overall results</a>, top 5 on the left). As expected, only the three highest scorers of day 1 had a real chance for the first place, and Yuta Takaya has grabbed this chance with the amazing score of 300 out of 300. Well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-1CZuQ_0S3qU/Wcftx8jhrBI/AAAAAAAB4aE/zDgzelUXqPURV-yc_sNA4__V4GLPUvdFQCLcBGAs/s1600/tco17r3atop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="151" data-original-width="772" height="125" src="https://1.bp.blogspot.com/-1CZuQ_0S3qU/Wcftx8jhrBI/AAAAAAAB4aE/zDgzelUXqPURV-yc_sNA4__V4GLPUvdFQCLcBGAs/s640/tco17r3atop5.png" width="640" /></a></div>On Saturday, my fruitless attempts to qualify for the TopCoder Open onsite in Buffalo started with TopCoder Open 2017 Round 3A (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=16963">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=16963&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, analysis). tourist has claimed the first place thanks to solving both the easy and the hard problem - congratulations - but qualification was also possible with easy+challenges, as Scott and Igor have demonstrated.<br /><br />I could not figure out the solution for <a href="https://community.topcoder.com/stat?c=problem_statement&pm=14647&rd=16963">the hard problem</a> in time, even though I suspected it would involve a reduction to 2-SAT from the very beginning. Can you see the way?<br /><br />You were given a tree with <i>n</i><=250 vertices and need solve a system of at most 250 equations on this tree with <i>m</i><=250 variables <i>x</i><sub>1</sub>, <i>x</i><sub>2</sub>, ..., <i>x<sub>m</sub></i> , where each variable must correspond to some vertex in the tree. Several variables can correspond to the same vertex. Each equation has the following form: in the path from vertex <i>x<sub>a<sub>i</sub></sub></i> to vertex <i>x<sub>b<sub>i</sub></sub></i> the vertex closest to vertex <i>p<sub>i</sub></i> must be the vertex <i>q<sub>i</sub></i>.<br /><br />Somewhat orthogonally to this particular problem, I felt like my general skill of reduction to 2-SAT could use some improvement. It seems that there are some common tricks that allow to replace complex conditions with just "or"s of two variables. For example, suppose we want a constraint "at most one of this subset of variables is true". It could naively be translated into n<sup>2</sup> 2-SAT clauses. However, we can introduce auxiliary variables to get by with only O(n) clauses: "<i>b<sub>i</sub></i> must be true when at least one of the first <i>i</i> original variables <i>a<sub>i</sub></i> is true" with clauses <i>b<sub>i</sub></i>-><i>b</i><sub><i>i</i>+1</sub> and <i>a<sub>i</sub></i>-><i>b<sub>i</sub></i>. Disallowing two true variables is then done via the clause <i>b<sub>i</sub></i>->!<i>a<sub>i+1</sub></i>.<br /><br />What are the other cool 2-SAT reduction tricks?<br /><br />Thanks for reading, and check back as I continue to remember August and September :)</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/mwE5SREchII" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/09/a-2-sat-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-31840462641338404202017-07-30T22:46:00.000+03:002017-07-30T22:46:01.325+03:00A week with two trees<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/-OyHFTzZ9pus/WX4k8OBn8AI/AAAAAAAB2mM/dgPEYkAtJpMF0YponzuWTUIPces6-pFqACLcBGAs/s1600/ioi2017r1top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="228" data-original-width="982" height="148" src="https://3.bp.blogspot.com/-OyHFTzZ9pus/WX4k8OBn8AI/AAAAAAAB2mM/dgPEYkAtJpMF0YponzuWTUIPces6-pFqACLcBGAs/s640/ioi2017r1top5.png" width="640" /></a></div>This week's contests were clustered on Sunday. In the morning, the first day of IOI 2017 took place in Tehran (<a href="http://ioi2017.org/contest/tasks/">problems</a>, <a href="http://scoreboard.ioi2017.org/Ranking.html">results</a>, top 5 on the left, <a href="https://youtu.be/10ye1yJeP48">video commentary</a>). The "classical format" problems <i>wiring</i> and <i>train</i> were pretty tough, so most contestants invested their time into the marathon-style problem <i>nowruz</i>. Three contestants have managed to gain a decent score there together with 200 on the other problems, so it's quite likely that they will battle for the crown between themselves on day 2. Congratulations Attila, Yuta and Mingkuan!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-f3AQuUGU04E/WX4lekFpYqI/AAAAAAAB2mQ/vZhhQ7YgU6koNIWWbGm_NLMRBSffc4aUACLcBGAs/s1600/cf426top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="271" data-original-width="1099" height="156" src="https://1.bp.blogspot.com/-f3AQuUGU04E/WX4lekFpYqI/AAAAAAAB2mQ/vZhhQ7YgU6koNIWWbGm_NLMRBSffc4aUACLcBGAs/s640/cf426top5.png" width="640" /></a></div>A few hours later, Codeforces Round 426 gave a chance to people older than 20 :) (<a href="http://codeforces.com/contest/833">problems</a>, <a href="http://codeforces.com/contest/833/standings">results</a>, top 5 on the left). The round contained a bunch of quite tedious implementation problems, and Radewoosh and LHiC have demonstrated that they are not afraid of tedious implementation by solving 4 out of 5. Well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-vQmGWL0aMPQ/WX43OSd5ngI/AAAAAAAB2mw/rpMTtcpxRzImI1mCEj4tMJbP2fekZqQlwCLcBGAs/s1600/IMG_20170722_154123.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1200" data-original-width="1600" height="480" src="https://4.bp.blogspot.com/-vQmGWL0aMPQ/WX43OSd5ngI/AAAAAAAB2mw/rpMTtcpxRzImI1mCEj4tMJbP2fekZqQlwCLcBGAs/s640/IMG_20170722_154123.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2017/07/an-unsportsmanlike-week.html">my previous summary</a>, I have raised a sportsmanship question, asking whether it's OK to bail out of an AtCoder contest without submitting anything. The poll results came back as 42% OK, 28% not OK, and 30% saying that the contest format should be improved. As another outcome of that post, <a href="http://codeforces.com/blog/entry/53457">tourist</a> and <a href="http://codeforces.com/blog/entry/53449?#comment-374942">moejy0viiiiiv</a> have shared their late submission strategies that do not consider bailing out as a benefit, so I was kind of asking the wrong question :) I encourage you to read the linked posts to see how the AtCoder format actually makes the competition more enjoyable.<br /><br />I have also mentioned a bunch of problems in that post, so let me come back to one of them: you are given two rooted trees on the same set of 10<sup>5</sup> vertices. You need to assign integer weights to all vertices in such a way that for each subtree of each of the trees the sum of weights is either 1 or -1, or report that it's impossible.<br /><br />First of all, we can notice that the value assigned to each vertex can be computed as (the sum of its subtree) - (the sum of subtrees of all its children). Since all said sums are either -1 or 1, the parity of this value depends solely on the parity of the number of children. So we can compare said parities in two trees, and if there's a mismatch, then there's definitely no solution.<br /><br />Now, after playing a bit with a few examples, we can start to believe that in case all parities match, there is always a solution. During the actual contest I've implemented a brute force to make sure this is true. Moreover, we can make an even stronger hypothesis: there is always a solution where all values are -1,0 or 1. Again, my brute force has confirmed that this is most likely true.<br /><br />For vertices where the value must be even, we can assume it's 0. For vertices where the value must be odd, we have two choices: -1 or 1. Let's call the latter <i>odd</i> vertices.<br /><br />Our parity check guarantees that each subtree of each tree will have an odd number of odd vertices, in order to be able to get -1 or 1 in total. So we must either have <i>k</i> -1's and <i>k</i>+1 1's, or <i>k</i>+1 -1's and <i>k</i> 1's. Here comes the main idea: in order to achieve this, it suffices to split all odd vertices into pairs in such a way that in each subtree all odd vertices but one form <i>k</i> whole pairs, and each pair is guaranteed to have one 1 and one -1.<br /><br />Having said that idea aloud, we can very quickly find a way to form the pairs: we would just go from leaves to the root of the tree, and each subtree will pass at most one unpaired odd vertex to its parent. There we would pair up as many odd vertices as possible, and send at most one further up.<br /><br />Since we have not one, but two trees, we will get two sets of pairs. Can we still find an assignment of 1's and -1's that satisfies both sets? It turns out we can: the necessary and sufficient condition for such assignment to exist is for the graph formed by the pairs to be bipartite. And sure enough, since the graph has two types of edges, and each vertex has at most one edge of each type, any cycle must necessarily have the edge types alternate, and thus have even length. And when all cycles have even length, the graph is bipartite.<br /><br />Looking back at the whole solution, we can see that the main challenge is to <i>restrict</i> one's solution in the right way. When we work with arbitrary numbers, there are just too many dimensions in the problem. When we restrict the numbers to just -1, 0, and 1, the problem becomes more tractable, and it becomes easier to see which ideas work and which don't. And when we add the extra restriction in form of achieving the necessary conditions by pairing up the vertices, the solution flows very naturally.<br /><br />Thanks for reading, and check back next week!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/wrxwe17YKZU" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/07/a-week-with-two-trees.htmltag:blogger.com,1999:blog-1953325079793449971.post-18368033278887831952017-07-23T22:04:00.000+03:002017-07-23T22:27:19.773+03:00An unsportsmanlike 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/-jwVIqmQ8XcU/WXTeWySsa1I/AAAAAAAB2PI/HQrfCByNUhcxF5KAykqljoueECIB-wDNwCLcBGAs/s1600/ya2017finaltop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="382" data-original-width="1184" height="206" src="https://4.bp.blogspot.com/-jwVIqmQ8XcU/WXTeWySsa1I/AAAAAAAB2PI/HQrfCByNUhcxF5KAykqljoueECIB-wDNwCLcBGAs/s640/ya2017finaltop5.png" width="640" /></a></div>Yandex.Algorithm 2017 Final Round took place both in Moscow and online on Tuesday (<a href="https://contest.yandex.com/algorithm2017/contest/4737/problems/">problems</a>, <a href="https://contest.yandex.com/algorithm2017/contest/4737/standings/">results</a>, top 5 on the left). My contest started like a nightmare: I was unable to solve any of the given problems during the first hour, modulo a quick incorrect heuristic submission on problem F. As more and more people submitted problems D (turned out to be a straightforward dynamic programming) and E (turned out to be about finding n-th Catalan number), I grew increasingly frustrated, but still couldn't solve them. After my wits finally came back to me after an hour, all problems suddenly seemed easy, and I did my best to catch up with the leaders, submitting 5 problems. Unfortunately, one of them turned out to have <a href="http://codeforces.com/blog/entry/53354?#comment-373970">a very small bug</a>, and I was denied that improbable victory :)<br /><br />Congratulations to tourist, W4yneb0t and rng.58 on winning the prizes!<br /><br />Here's the Catalan number problem that got me stumped. Two people are dividing a heap of <i>n</i> stones. They take stones in turns until none are left. At their turn, the first person can take any non-zero amount of stones. The second person can then also take any non-zero amount of stones, but with an additional restriction that the total amount of stones he has after this turn must not exceed the total amount of stones the first person has. How many ways are there for this process to go to completion, if we also want the total amount of stones of each person to be equal in the end?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/--E4Ry_BgS9U/WXTgFfjJ0bI/AAAAAAAB2PQ/fUpkw9xnansIOOxAMEBoyt8cupZO6TXSgCLcBGAs/s1600/tco17r2ctop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="97" data-original-width="631" src="https://1.bp.blogspot.com/--E4Ry_BgS9U/WXTgFfjJ0bI/AAAAAAAB2PQ/fUpkw9xnansIOOxAMEBoyt8cupZO6TXSgCLcBGAs/s1600/tco17r2ctop5.png" /></a></div>TopCoder Open 2017 Round 2C was the first event of the weekend (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=16951">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=16951&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=16952&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">parallel round results</a>, <a href="https://youtu.be/BVBHxDagCjM">my screencast</a>). The final 40 contestants for the Round 3 were chosen, and kraskevich advanced with the most confidence of all, as he was the only contestant to solve all problems. Congratulations!<br /><br />This round contained a very cute <a href="https://community.topcoder.com/stat?c=problem_statement&pm=14651&rd=16951">easy problem</a>. Two teams with <i>n</i> players each are playing a game. Each player has an integer strength. The game lasts <i>n</i> rounds. In the first round, the first player of the first team plays the first player of the second team, and the stronger player wins. In the second round, the first two players of the first team play the first two players of the second team, and the pair with the higher total strength wins. In the <i>i</i>-th round the strengths of the first <i>i</i> players in each team are added up to determine the winner. You know the strengths of each player, and the ordering of the players in the second team. You need to pick the ordering for the players in the first team in such a way that the first team wins exactly <i>k</i> rounds. Do you see the idea?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-YjiEJVJ2fic/WXTfU89O_EI/AAAAAAAB2PM/FiaB-jt-X3MlI2WpFoAGKg_Knpi_9VSuwCLcBGAs/s1600/agc018top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="447" data-original-width="904" height="316" src="https://1.bp.blogspot.com/-YjiEJVJ2fic/WXTfU89O_EI/AAAAAAAB2PM/FiaB-jt-X3MlI2WpFoAGKg_Knpi_9VSuwCLcBGAs/s640/agc018top5.png" width="640" /></a></div>And finally, AtCoder Grand Contest 018 took place on Sunday (<a href="http://agc018.contest.atcoder.jp/assignments">problems</a>, <a href="http://agc018.contest.atcoder.jp/standings#page_1">results</a>, top 5 on the left, <a href="https://atcoder.jp/img/agc018/editorial.pdf">analysis</a>, <a href="https://youtu.be/NfHMqpqQ5-I">my screencast with commentary</a>). tourist has adapted his strategy to the occasion, submitting the first four problems before starting work on the last two, but in the end that wasn't even necessary as he also solved the hardest problem and won with a 15 minute margin. Well done!<br /><br />As you can see in the screencast, I was also trying out this late submission strategy this time, and when I solved the first four and saw that Gennady has already submitted them, I was quite surprised. There was more than an hour left, so surely I'd be able to solve one more problem? And off I went, trying to crack the hardest problem because it gave more points and seemed much more interesting to solve than the previous one.<br /><br />I have made quite a bit of progress, correctly simplifying the problem to the moment where the main idea mentioned in the analysis can be applied, but unfortunately could not come up with that idea. That left me increasingly anxious as the time ran out: should I still submit the four problems I have (which turned out to be all correct in upsolving), earning something like 40th place instead of 10th or so that I would've got had I submitted them right after solving? Or should I avoid submitting anything, thus not appearing in the scoreboard at all and not losing rating, but showing some possibly unsportsmanlike behavior?<br /><br />I have to tell you, this is not a good choice to have. Now I admire people who can pull this strategy off without using the escape hatch even more :) To remind, the benefits of this strategy, as I see them (from comments in a previous post), are:<br />1) Not giving information to other competitors on the difficulty of the problems.<br />2) Not allowing other competitors to make easy risk/reward tradeoffs, as if they know the true scoreboard, they might submit their solutions with less testing when appropriate.<br /><br />I ended up using the escape hatch, which left me feeling a bit guilty, but probably more uncertain than guilty. Do you think this is against the spirit of competition, as PavelKunyavskiy <a href="http://codeforces.com/blog/entry/53431?#comment-374524">suggests</a>? Please share your opinion in comments, and also let's have a vote:<br /><br /><div class="widget Poll" data-version="1" id="Poll1"><b>Is it OK to bail out of a contest after a poor performance with late submit strategy at AtCoder?</b><br /><div class="widget-content"><iframe allowtransparency="true" frameborder="0" height="138px" name="poll-widget-2788262514131840650" src="https://www.google.com/reviews/polls/display/-2788262514131840650/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> <br /><div class="clear"></div>Here's <a href="http://agc018.contest.atcoder.jp/tasks/agc018_f">the hardest problem</a> that led to all this confusion: You are given two rooted trees on the same set of 10<sup>5</sup> vertices. You need to assign integer weights to all vertices in such a way that for <i>each</i> subtree of <i>each</i> of the trees the sum of weights is either 1 or -1, or report that it's impossible. Can you do that?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-SmN3-x90NBs/WXTzCvrJPJI/AAAAAAAB2P0/GE0JUS03pfg5_4DB4frbR03LneMrBKLzACLcBGAs/s1600/IMG_20170722_141424.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1200" data-original-width="1600" height="480" src="https://3.bp.blogspot.com/-SmN3-x90NBs/WXTzCvrJPJI/AAAAAAAB2P0/GE0JUS03pfg5_4DB4frbR03LneMrBKLzACLcBGAs/s640/IMG_20170722_141424.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2017/07/a-red-black-week.html">my previous summary</a>, I have mentioned a hard VK Cup problem. You are given an undirected graph with 10<sup>5</sup> vertices and edges. You need to assign non-negative integer numbers not exceeding 10<sup>6</sup> to the vertices of the graph. The weight of each edge is then defined as the product of the numbers at its ends, while the weight of each vertex is equal to the square of its number. You need to find an assignment such that the total weight of all edges is greater than or equal to the total weight of all vertices, and at least one number is nonzero.<br /><br />The first idea is: as soon as the graph has any cycle, we can assign number 1 to all vertices in the cycle, and 0 to all other vertices, and we'll get what we want. So now we can assume the graph is a forest, and even a tree.<br /><br />Now, consider a leaf in that forest, and assume we know the number <i>x</i> assigned to the only vertex this leaf is connected to. If we now assign number <i>y</i> to this leaf, then the difference between the edge weight and the vertex weight will increase by <i>x</i>*<i>y</i>-<i>y</i>*<i>y</i>. We need to pick <i>y</i> to maximize this difference, which is finding the maximum of a quadratic function, which is achieved when <i>y</i>=<i>x</i>/2, and the difference increases by x<sup>2</sup>/4.<br /><br />Now suppose we have a vertex that is connected to several leaves, and to one other non-leaf vertex for which we know the assigned number <i>x</i>. After we determine the number <i>y</i> for this vertex, all adjacent leaves must be assigned <i>y</i>/2, so we can again compute the difference as the function of <i>y</i> and find its maximum. It will be a quadratic function again, and the solution will look like <i>x</i>*const again.<br /><br />Having rooted the tree in some way, this approach allows us to actually determine the optimal number for all vertices going from leaves to the root as multiples of the root number, and we can check if the overall delta is non-negative or not.<br /><br />There's an additional complication caused by the fact that the resulting weights must be not very big integers. We can do the above computation in rational numbers to make all numbers integer, but they might become quite big. However, if we look at the weight differences that some small trees get, we can notice that almost all trees can get a non-negative difference, and come up with a case study that finds a subtree in a given tree which still has a non-negative difference but can be solved with small numbers. I will leave this last part as an exercise for the readers.<br /><br />Wow, it feels good to have caught up with the times :) Thanks for reading, and check back next week!</div></div></div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/zX2vjqtH2ZM" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/07/an-unsportsmanlike-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-59175169837193928042017-07-23T20:19:00.001+03:002017-07-24T11:40:46.808+03:00A red-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/-Afbi-tOvQoQ/WXTLednXjcI/AAAAAAAB2Ok/b3yFmXtAGiUrhUDk6sW1-7a4tq7f25pTACLcBGAs/s1600/cf423top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="272" data-original-width="1102" height="155" src="https://1.bp.blogspot.com/-Afbi-tOvQoQ/WXTLednXjcI/AAAAAAAB2Ok/b3yFmXtAGiUrhUDk6sW1-7a4tq7f25pTACLcBGAs/s640/cf423top5.png" width="640" /></a></div>Last week, Codeforces presented the problems from the VK Cup finals as two regular contests. First off, Codeforces Round 423 took place on Tuesday (<a href="http://codeforces.com/contest/827">problems</a>, <a href="http://codeforces.com/contest/827/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/53268">analysis</a>). W4yneb0t has continued his string of excellent Codeforces performances with the best possible result - a victory, which has also catapulted him to the second place in the overall rating list. Well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-zhCmu0mUzZc/WXTLtxaynII/AAAAAAAB2Os/ci9YLwfyXn4wIQRZaNLirVPz9sHDYQZHQCLcBGAs/s1600/srm718top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="96" data-original-width="631" src="https://2.bp.blogspot.com/-zhCmu0mUzZc/WXTLtxaynII/AAAAAAAB2Os/ci9YLwfyXn4wIQRZaNLirVPz9sHDYQZHQCLcBGAs/s1600/srm718top5.png" /></a></div>In between the Codeforces rounds, TopCoder held its SRM 718 very early on Thursday (<a href="https://community.topcoder.com/stat?c=round_overview&rd=16933">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=16933&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="http://success.topcoder.com/the-topcoder-blog/single-round-match-718-editorials">anlaysis</a>). The round seems to have been developing in a very exciting manner: three people submitted all three problems during the coding phase, then two of them lost points during the challenge phase, and the last remaining person with three problems failed the system test on the easiest problem! When the dust settled, snuke still remained in the first place thanks for his solution to the hard problem holding. Congratulations on the second SRM victory!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-CCLe6A8F4gE/WXTLj6FSjcI/AAAAAAAB2Oo/ylKp-8vgetkgNKE64tR-MkyUyx_BQt-ewCLcBGAs/s1600/cf424top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="275" data-original-width="1102" height="158" src="https://4.bp.blogspot.com/-CCLe6A8F4gE/WXTLj6FSjcI/AAAAAAAB2Oo/ylKp-8vgetkgNKE64tR-MkyUyx_BQt-ewCLcBGAs/s640/cf424top5.png" width="640" /></a></div>Codeforces Round 424 rounded up the week's contests (<a href="http://codeforces.com/contest/830">problems</a>, <a href="http://codeforces.com/contest/830/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/53302">analysis</a>). TakanashiRikka was the fastest to solve the first four problems, and (probably not a sheer coincidence :)) the only contestant to have enough time to consider all cases in the hardest problem correctly while solving at least one other problem. Congratulations on the well-deserved first place!<br /><br />Here's <a href="http://codeforces.com/contest/830/problem/E">that tricky problem</a>. You are given an undirected graph with 10<sup>5</sup> vertices and edges. You need to assign non-negative integer numbers not exceeding 10<sup>6</sup> to the vertices of the graph. The weight of each edge is then defined as the product of the numbers at its ends, while the weight of each vertex is equal to the square of its number. You need to find an assignment such that the total weight of all edges is greater than or equal to the total weight of all vertices, and at least one number is nonzero.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-oXT6G_wpFOc/WXTaj6zESFI/AAAAAAAB2PA/XXY3SxfgXaogG3KKuiN0As965euXlukhACLcBGAs/s1600/IMG_20170612_143504.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1200" data-original-width="1600" height="480" src="https://2.bp.blogspot.com/-oXT6G_wpFOc/WXTaj6zESFI/AAAAAAAB2PA/XXY3SxfgXaogG3KKuiN0As965euXlukhACLcBGAs/s640/IMG_20170612_143504.jpg" width="640" /></a></div>In my previous summary, I have mentioned a difficult IPSC problem: we start with a deck of 26 red and 26 black cards, and a number <i>k</i> (1<=<i>k</i><=26). The first player takes any <i>k</i> cards from the deck, and arranges them in any order they choose. The second player takes any <i>k</i> cards from the remaining deck, and arranges them in any order they choose, but such that their sequence is different from the sequence of the first player. The remaining 52-2<i>k</i> cards are shuffled and dealt one by one. As soon as the last <i>k</i> dealt cards exactly match one of the player's sequences, that player wins. In case no match happens after the cards run out, we toss a coin, and each player wins with probability 50%. What is the probability of the first player winning, assuming both play optimally?<br /><br />Solving this problem required almost all important programming contest skills: abstract mathematical reasoning, knowledge of standard algorithms, coming up with new ideas, good intuition about heuristics, and of course the programming skill itself.<br /><br />We start off by noticing that the second player has a very simple way to achieve 50% winrate: he can just choose a sequence that is a complement of the first player's sequence (replace red cards by black and vice versa), and then everything is completely symmetric.<br /><br />How can the second player achieve more? He has two resources: first, he can choose a string that is more likely to appear in the sequence of the remaining cards. Second, he can choose a string that, when it appears together with the string of the first player, tends to appear earlier.<br /><br />The strings that are more likely to appear are those that leave an equal proportion of reds and blacks (after taking out the string of the first player once and the string of the second player twice), and have no borders (prefixes that are equal to suffixes). This is because we can count the number of ways a given string can appear by multiplying the number of positions it can appear in by the number of ways to place the remaining characters after the matching part is fixed. The number of ways to place the remaining characters is maximized then the remaining characters have equal numbers of blacks and reds. This slightly overcounts the number of ways because in some cases the string can appear more than once; the lack of borders minimizes the number of such occurrences.<br /><br />The strings that tend to appear earlier when both appear are those which have a suffix which matches a prefix of the first player's string. At best, if the first player string is <i>s</i>+<i>c</i>, where s is a string of length <i>k</i>-1 and <i>c</i> is a character, the second player should pick his string from 'r'+<i>s</i> and 'b'+<i>s</i>. In this case as soon as there's a match of the first player's string not in the first position, we can have a >50% chance to have a match of our string one position before.<br /><br />Now we can already make the first attempt at a solution: let's try likely candidates for the first player's best move - it should likely be among the strings that have the most appearances; the second player should then choose either another string with lots of appearances, or a string that counter-plays the first player's string in the manner described above. However, this is not enough to solve the problem - we will get a wrong answer.<br /><br />As part of implementing the above solution, we had to also implement the function to count the sought probability for the given pair of strings. It's also not entirely trivial, and can be done by using dynamic programming where the state is the number of remaining red and black cards, and the state in the Aho-Corasick automaton of the two strings.<br /><br />So, where do we go from there? Since we already have the function that computes the probability, we can now run it on all pairs of strings for small values of <i>k</i> and try to notice a pattern. We get something like this:<br /><span style="font-family: "courier new" , "courier" , monospace;"><br /></span><span style="font-family: "courier new" , "courier" , monospace;">1 0.5 r b</span><br /><span style="font-family: "courier new" , "courier" , monospace;">2 0.5 rb br</span><br /><span style="font-family: "courier new" , "courier" , monospace;">3 0.3444170488792196 rbr rrb</span><br /><span style="font-family: "courier new" , "courier" , monospace;">4 0.35992624362382514 rrbb rrrb</span><br /><span style="font-family: "courier new" , "courier" , monospace;">5 0.3777939526283981 rrbrb brrbr</span><br /><span style="font-family: "courier new" , "courier" , monospace;">6 0.413011479190688 rbrbrr brbrbr</span><br /><span style="font-family: "courier new" , "courier" , monospace;">7 0.45319632265323256 rrbrrbb brrbrrb</span><br /><span style="font-family: "courier new" , "courier" , monospace;">8 0.4782049196004824 rrbbrrbb brrbbrrb</span><br /><div><br /></div><div>No obvious pattern seems to appear. However, we can notice that for large values of <i>k</i>, more precisely when 3<i>k</i>>52, the answer will be 0.5 simply because there is not enough remaining cards for either string to appear. So we only need to research the values of <i>k</i> between 9 and 17 now.</div><div><br /></div><div>And here comes another key idea: we need to believe that by cutting enough branches early, our exhaustive search solution can run in a few minutes for all those values. At first, this seems improbable. For example, for k=16 we have 65536 candidates for each string, and four billion combinations in total, not to mention the Aho-Corasick on the inside. However, from our previous attempts at a solution we have some leads. More precisely, we know which strings of the second player are the most likely good answers for each string of the first player.</div><div><br /></div><div>This allows us to get a good upper bound on the first player's score for each particular string reasonably quickly, which leads to the following optimization idea: let's run the search for all strings of the first player at the same time, and at each point we will take the "most promising" string - the one with the highest upper bound so far - and make one more step of the search for it, in other words try one more candidate for the second player's string, which may lower its upper bound. We continue this process until we arrive at the state where the most promising candidate does not have anything else to try, because we already ran through all possible second player strings for it - and this candidate then gives us the answer.</div><div><br /></div><div>This search runs relatively fast because for most first player strings, our heuristics will give us an upper bound that is lower than the ultimate answer very quickly, and we will stop considering those strings further. It is still quite slow for larger values of <i>k</i>, so we need a second optimization on top: we can skip the Aho-Corasick part in the simple case where there's simply not enough cards of some color for the second player's string to appear. With those two optimizations, we can finally get all the answers in a few minutes.</div><div><br /></div><div>Thanks for reading, and check back soon for this week's summary!</div></div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/tvuuKLYf97g" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/07/a-red-black-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-20696060729894770732017-07-16T23:20:00.001+03:002017-07-16T23:20:31.272+03:00A postcard 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/-lsmOCQLbFkI/WWvAyXXrVxI/AAAAAAAB1_Q/KdiGqzeGfxc4Km1nXxFIV7YGuUWpnBy6wCLcBGAs/s1600/ipsc2017top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="153" data-original-width="1281" height="76" src="https://2.bp.blogspot.com/-lsmOCQLbFkI/WWvAyXXrVxI/AAAAAAAB1_Q/KdiGqzeGfxc4Km1nXxFIV7YGuUWpnBy6wCLcBGAs/s640/ipsc2017top5.png" width="640" /></a></div>The July 3 - July 9 week had a pretty busy weekend. On Saturday, IPSC 2017 has gathered a lot of current contestants together with veterans that come out of retirement just for this contest every year (<a href="https://ipsc.ksp.sk/2017/real/problems/ipsc2017.pdf">problems</a>, <a href="https://ipsc.ksp.sk/2017/results/">results</a>, top 5 on the left, <a href="https://ipsc.ksp.sk/2017/real/solutions/booklet.pdf">analysis</a>). The (relatively) current contestants prevailed this time, with team Past Glory winning with a solid 2 point gap. Well done!<br /><br />They were one of only two teams who has managed to solve the hardest <a href="https://ipsc.ksp.sk/2017/real/problems/l.html">problem L2</a>. It went like this: we start with a deck of 26 red and 26 black cards, and a number <i>k</i> (1<=<i>k</i><=26). The first player takes any <i>k</i> cards from the deck, and arranges them in any order they choose. The second player takes any <i>k</i> cards from the remaining deck, and arranges them in any order they choose, but such that their sequence is different from the sequence of the first player. The remaining 52-2<i>k</i> cards are shuffled and dealt one by one. As soon as the last <i>k</i> dealt cards exactly match one of the player's sequences, that player wins. In case no match happens after the cards run out, we toss a coin, and each player wins with probability 50%. What is the probability of the first player winning, assuming both play optimally?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-Gfuoenroi5s/WWvC3NHmnqI/AAAAAAAB1_Y/ZIKkXJO3GbQf62_bwbUneqrrGmwKlFpVQCLcBGAs/s1600/tco17r2btop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="151" data-original-width="786" height="122" src="https://2.bp.blogspot.com/-Gfuoenroi5s/WWvC3NHmnqI/AAAAAAAB1_Y/ZIKkXJO3GbQf62_bwbUneqrrGmwKlFpVQCLcBGAs/s640/tco17r2btop5.png" width="640" /></a></div>Just an hour later, TopCoder Open 2017 Round 2B selected another 40 lucky advancers (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=16945">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=16945&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://www.topcoder.com/blog/2017-tco-algorithm-round-2b-editorials/">analysis</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=16946&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">parallel round results</a>, <a href="https://youtu.be/PvrKEjaWgMg">my screencast</a>). dotory1158 had a solid point margin from his solutions, and did not throw it all away during the challenge phase, although the contest became much closer :) Congratulations on the win!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-Au8l-DrxeKw/WWvCj1R82qI/AAAAAAAB1_U/sb7wiwsJEKEDuX087pFoMrlW1-iD51pYQCLcBGAs/s1600/vk2017finaltop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="302" data-original-width="1134" height="170" src="https://4.bp.blogspot.com/-Au8l-DrxeKw/WWvCj1R82qI/AAAAAAAB1_U/sb7wiwsJEKEDuX087pFoMrlW1-iD51pYQCLcBGAs/s640/vk2017finaltop5.png" width="640" /></a></div>The final round of VK Cup 2017 took place in St Petersburg on Sunday (<a href="http://codeforces.com/contest/823">problems</a>, <a href="http://codeforces.com/contest/823/standings">results</a>, top 5 on the left). Continuing the Snackdown trend from the last week, two-person teams were competing. The xray team emerged on top thanks to a very fast start - in fact, they already got enough points for the first place at 1 hour and 38 minutes into the contest, out of 3 hours. Very impressive!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-RlnJvh9-lRQ/WWvDveRgeSI/AAAAAAAB1_c/DGJDZgZWDBg1n1ZM4Df_pu1W_IB1Nel4gCLcBGAs/s1600/agc017top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="446" data-original-width="904" height="315" src="https://3.bp.blogspot.com/-RlnJvh9-lRQ/WWvDveRgeSI/AAAAAAAB1_c/DGJDZgZWDBg1n1ZM4Df_pu1W_IB1Nel4gCLcBGAs/s640/agc017top5.png" width="640" /></a></div>And finally, AtCoder hosted its Grand Contest 017 on Sunday as well (<a href="http://agc017.contest.atcoder.jp/assignments">problems</a>, <a href="http://agc017.contest.atcoder.jp/standings#page_1">results</a>, top 5 on the left, <a href="https://atcoder.jp/img/agc017/editorial.pdf">analysis</a>). Once again the delayed submit strategy has worked very well for tourist, but this time the gap was so huge that the strategy choice didn't really matter. Way to go, Gennady!<br /><br /><a href="http://agc017.contest.atcoder.jp/tasks/agc017_d">Problem D</a> in this round was about the well-known game of <a href="https://en.wikipedia.org/wiki/Hackenbush">Hackenbush</a>, more precisely green Hackenbush: you are given a rooted tree. Two players alternate turns, in each turn a player removes an edge together with the subtree hanging on this edge. When a player can not make a move (only the root remains), he loses. Who will win when both players play optimally?<br /><br />If you haven't seen this game before, then I encourage you to try solving the problem before searching for the optimal strategies in the Internet (which has them). I think the solution is quite beautiful!<br /><br />Thanks for reading, and check back for this week's summary.</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/sZ6h7OPA4xM" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/07/a-postcard-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-50735485258823340652017-07-16T17:43:00.000+03:002017-07-16T22:29:16.341+03:00A hammer 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/-jsyD5hjZcrE/WWslc7x9xwI/AAAAAAAB1-g/w8mzzWMrzsUi2lK-xK-Mkz-ycDXMqMGuwCLcBGAs/s1600/srm716top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="151" data-original-width="778" height="124" src="https://3.bp.blogspot.com/-jsyD5hjZcrE/WWslc7x9xwI/AAAAAAAB1-g/w8mzzWMrzsUi2lK-xK-Mkz-ycDXMqMGuwCLcBGAs/s640/srm716top5.png" width="640" /></a></div>TopCoder has hosted two SRMs during the June 26 - July 2 week. First off, SRM 716 took place on Tuesday (<a href="https://community.topcoder.com/stat?c=round_overview&rd=16931">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=16931&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://www.topcoder.com/blog/single-round-match-716-editorials/">analysis</a>). ACRush came back to the SRMs after more than a year, presumably to practice for the upcoming TCO rounds. He scored more points than anybody else from problem solving - but it was only good enough for the third place, as dotory1158 and especially K.A.D.R shined in the challenge phase. Well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-VHlZeRkZox0/WWsmxT121sI/AAAAAAAB1-o/ptwtePTItegBVgaHi2iXZORqMXqYGsxtACLcBGAs/s1600/cf421top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="273" data-original-width="1101" height="158" src="https://2.bp.blogspot.com/-VHlZeRkZox0/WWsmxT121sI/AAAAAAAB1-o/ptwtePTItegBVgaHi2iXZORqMXqYGsxtACLcBGAs/s640/cf421top5.png" width="640" /></a></div>Later on the same day, Codeforces held its Round 421 (<a href="http://codeforces.com/contest/819">problems</a>, <a href="http://codeforces.com/contest/819/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/52946">analysis</a>). There was a certain amount of <a href="http://codeforces.com/blog/entry/52944">unfortunate controversy</a> with regard to problem A, so the results should be taken with a grain of salt - nevertheless, TakanashiRikka was the best on the remaining four problems and got the first place. Congratulations!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-6z4UnUiT5tg/WWsmJK85A8I/AAAAAAAB1-k/Ld1gTi6WIkgqFt0anKVELxnrQpET9MRcQCLcBGAs/s1600/srm717top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="152" data-original-width="785" height="122" src="https://3.bp.blogspot.com/-6z4UnUiT5tg/WWsmJK85A8I/AAAAAAAB1-k/Ld1gTi6WIkgqFt0anKVELxnrQpET9MRcQCLcBGAs/s640/srm717top5.png" width="640" /></a></div>The second TopCoder round of the week, SRM 717, happened on Friday (<a href="https://community.topcoder.com/stat?c=round_overview&rd=16932">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=16932&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://www.topcoder.com/blog/single-round-match-717-editorials/">analysis</a>, <a href="https://youtu.be/jWaggUufLOA">my screencast</a>). I had my solution for the medium problem fail, but even without that setback I would finish behind Deretin - great job on the convincing win!<br /><br />Here's what <a href="https://community.topcoder.com/stat?c=problem_statement&pm=14563&rd=16932">that problem</a> was about. You are given two numbers <i>n</i> (up to 10<sup>9</sup>) and <i>m</i> (up to 10<sup>5</sup>). For each <i>i</i> between 1 and <i>m</i>, you need to find the number of permutations of <i>n</i>+<i>i</i> objects such that the first <i>i</i> objects are not left untouched by the permutation. As an example, when <i>n</i>=0 we're counting <a href="https://en.wikipedia.org/wiki/Derangement">derangements</a> of each size between 1 and <i>m</i>.<br /><br />My solution for this problem involved Fast Fourier Transformation because, well, I had a hammer, and the problem was not dissimilar enough to a nail :) And it failed because I've reused FFT code from my library, which I've optimized heavily to squeeze under the time limit in a previous Open Cup round, and to which I've introduced a small bug during that optimization :(<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-sJ-tYf6cYg4/WWsnVkdxmMI/AAAAAAAB1-s/CPJEZwAcu8USnToEJCJeVtd7xp_RY5c4wCLcBGAs/s1600/snackdown2017finalstop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="416" data-original-width="1600" height="166" src="https://2.bp.blogspot.com/-sJ-tYf6cYg4/WWsnVkdxmMI/AAAAAAAB1-s/CPJEZwAcu8USnToEJCJeVtd7xp_RY5c4wCLcBGAs/s640/snackdown2017finalstop5.png" width="640" /></a></div>And on the weekend, two-person teams competed for the fame and monetary prizes at the onsite finals of CodeChef Snackdown 2017 (<a href="https://www.codechef.com/SNCKFL17">problems</a>, <a href="https://www.codechef.com/rankings/SNCKFL17">results</a>, top 5 on the left, <a href="https://docs.google.com/presentation/d/1eK2Y2SNn1eggGowUENTf2aTU-FTlYk6gLhwNv2unE-k/edit#slide=id.p">analysis</a>). The last year's winner "Messages compress" were in the lead for long periods of time, but in the last hour they tried to get three problems accepted but got zero, which gave other teams a chance. Team Dandelion have seized that chance and won solving 9 problems out of 10. Way to go!<br /><br />Thanks for reading, and check back for the next week's summary.</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/wVEza2TeA2g" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/07/a-hammer-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-86964426357833077162017-07-16T00:28:00.000+03:002017-07-16T00:30:24.419+03:00FBHC2017 Finals<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/-COvJI2n9F6k/WWqHpdULziI/AAAAAAAB198/iqPAUC51wg0EVlrB9pXOv0Gm9tY5GEVCACLcBGAs/s1600/fbhc2017finaltop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="415" data-original-width="902" height="294" src="https://2.bp.blogspot.com/-COvJI2n9F6k/WWqHpdULziI/AAAAAAAB198/iqPAUC51wg0EVlrB9pXOv0Gm9tY5GEVCACLcBGAs/s640/fbhc2017finaltop5.png" width="640" /></a></div>There was one quite important competition that I forgot to mention <a href="http://petr-mitrichev.blogspot.com/2017/07/an-all-at-once-week.html">two summaries back</a>: Facebook Hacker Cup 2017 onsite finals took place on June 14 (<a href="https://www.facebook.com/hackercup/problem/1703546573272198/">problems</a>, <a href="https://www.facebook.com/hackercup/scoreboard/1799632126966939/?filter=everyone">results</a>, top 5 on the left, <a href="https://www.facebook.com/notes/facebook-hacker-cup/hacker-cup-2017-final-round-solutions/1783707321645161/?fref=mentions">analysis</a>, <a href="https://youtu.be/w8ptIMEyonQ">my screencast</a>). In this round I have managed to make <i>three</i> different bugs in my solution to the second problem and the way those bugs combined led to my program passing the samples almost by accident, but of course it did not pass the final testing. On the bright side, not spending more time on this problem allowed me enough time to solve all other problems, so maybe the three bugs were actually a crucial component of the victory :)<br /><div><br /></div><div>Thanks for reading, and check back for the hopefully more complete next week's summary!</div></div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/1mvqh2CN2Fg" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/07/fbhc2017-finals.htmltag:blogger.com,1999:blog-1953325079793449971.post-38161153273540758302017-07-15T23:29:00.002+03:002017-07-15T23:29:41.860+03:00A dynamic nimber 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/-y7m19ITONlA/WWp7DJpfe3I/AAAAAAAB19w/K27MckyY-XkEhJfwi63PrNkbXmy7RykdwCLcBGAs/s1600/IMG_20170528_123348.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1200" data-original-width="1600" height="480" src="https://3.bp.blogspot.com/-y7m19ITONlA/WWp7DJpfe3I/AAAAAAAB19w/K27MckyY-XkEhJfwi63PrNkbXmy7RykdwCLcBGAs/s640/IMG_20170528_123348.jpg" width="640" /></a></div>The June 19 - June 25 week did not actually have any rounds that I'd like to mention, so let me turn back to <a href="http://agc016.contest.atcoder.jp/tasks/agc016_f">the problem</a> from <a href="http://petr-mitrichev.blogspot.com/2017/07/an-all-at-once-week.html">the previous week's summary</a>.<br /><br />You are given an acyclic directed graph with <i>n</i><=15 vertices and <i>m</i> arcs. Vertices 1 and 2 each contain a chip. Two players take alternating turns, each turn consisting of moving one of the chips along an arc of the graph. The player who can't make a valid move loses. We want to know which player wins if both play optimally. Now consider all 2<sup>m</sup> subsets of the graph's arcs; for how many of them does the first player win if we keep only the arcs from this subset?<br /><br />Without the subset part, the problem is pretty standard. We need to compute <a href="https://en.wikipedia.org/wiki/Nimber">the nimbers</a> for all vertices of the graph, and the first player wins if and only if the nimbers for the first two vertices are different.<br /><br />However, we do not have the time to even iterate over all subsets, and thus we can not apply this naive algorithm. Dynamic programming comes to the rescue, allowing to reuse some computations. The dynamic programming idea that is closest to the surface is: go in a topological ordering, and keep computing the nimbers. The nimber for a vertex depends on which arcs going from this vertex are included in the subset, and on the values of nimbers for the vertices reachable from this one, so our dynamic programming state should include only the values of nimbers for the already processed vertices, reducing the running time from 2<sup>m</sup> to something around the <i>n</i>-th <a href="https://en.wikipedia.org/wiki/Bell_number">Bell number</a>. That is still not too little, but it turns out this approach could be squeezed to pass.<br /><br />However, it turns out there is another beautiful dynamic programming idea that helps us move to the running time on the order of 3<sup>n</sup>. Instead of going vertex-by-vertex, we will now go nimber-by-nimber. For each consecutive nimber, we will try all possibilities for a subset <i>a</i> of vertices having this nimber. What are the requirements on such a subset? From the definition of nimbers we get:<br /><ol style="text-align: left;"><li>For each vertex in this subset, there must be an arc to at least one vertex with each smaller nimber.</li><li>There must be no arcs within this subset.</li></ol>Condition 2 is pretty easy to check, but condition 1 is not. However, we can notice that we can instead check:<br /><ol style="text-align: left;"><li>For each vertex that still has no assigned nimber (and thus will eventually have a higher nimber), there must be an arc <i>to</i> at least one vertex in this subset.</li><li>There must be no arcs within this subset.</li></ol>The new condition 1 guarantees that all higher nimbers will have arcs to all lower nimbers, so by the time we reach a certain nimber, we don't need to care about arcs to lower nimbers anymore. Now we can see that the state of our dynamic programming can simply be the last placed nimber and the set of vertices that do not yet have a nimber.<br /><br />Finally, we can notice that the last placed nimber does not actually take part in the computations at all, so we can reduce the number of states <i>n</i> times more to just remembering the set of vertices that do not yet have a nimber, yielding overall complexity of O(<i>n</i>*3<sup>n</sup>).<br /><br />Thanks for reading, and check back for the next week's summary!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/aG2-2NwBV1Q" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/07/a-dynamic-nimber-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-41729474452381204292017-07-15T23:01:00.001+03:002017-07-16T00:26:59.297+03:00An all-at-once 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/-JB_Q4_naz0g/WWpuXwZAI2I/AAAAAAAB19Q/Z6xJBR7XbdQld7pjokS_pCmfC7siu-UHwCLcBGAs/s1600/cf419top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="274" data-original-width="1106" height="158" src="https://2.bp.blogspot.com/-JB_Q4_naz0g/WWpuXwZAI2I/AAAAAAAB19Q/Z6xJBR7XbdQld7pjokS_pCmfC7siu-UHwCLcBGAs/s640/cf419top5.png" width="640" /></a></div>Codeforces came back during the June 12 - June 18 week with its Round 419 (<a href="http://codeforces.com/contest/815">problems</a>, <a href="http://codeforces.com/contest/815/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/52742">analysis</a>). Only Radewoosh and yutaka1999 could get all problems right, and Radewoosh has booked his (semi-) permanent place on the front page of Codeforces with this victory: he is now in top 10 by rating. Well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-i3_YSYmAXvE/WWpv-GfYnlI/AAAAAAAB19Y/dnQrypbdzDklKEEAuXCyf2XGHpDyeUaTQCLcBGAs/s1600/agc016top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="449" data-original-width="906" height="316" src="https://1.bp.blogspot.com/-i3_YSYmAXvE/WWpv-GfYnlI/AAAAAAAB19Y/dnQrypbdzDklKEEAuXCyf2XGHpDyeUaTQCLcBGAs/s640/agc016top5.png" width="640" /></a></div>AtCoder Grand Contest 016 took place on the next day (<a href="http://agc016.contest.atcoder.jp/assignments">problems</a>, <a href="http://agc016.contest.atcoder.jp/standings#page_1">results</a>, top 5 on the left, <a href="https://atcoder.jp/img/agc016/editorial.pdf">analysis</a>, <a href="https://youtu.be/WliHklt10-0">my screencast</a>). It's not as if tourist needs an unusual strategy to win, but he successfully demonstrated that the AtCoder rules actually make it reasonable to withhold submissions until one has a solution for the last problem they intend to submit. As a theory, here's how this strategy might have helped here: maybe Gennady already had all solutions implemented by the 68-th minute, but he saw that I have an incorrect attempt for one of the problems, and he was not sure in his solution for problem D. So he submitted everything else, and started testing the solution for D more thoroughly, as he knew that he'd have five minutes after I solve my last problem to still get the first place. Gennady, is this theory at least remotely close to reality? :)<br /><br /><a href="http://agc016.contest.atcoder.jp/tasks/agc016_f">The hardest problem</a> of the round presented a peculiar combination of dynamic programming and nimbers, one that I don't recall seeing before. You are given an acyclic directed graph with <i>n</i><=15 vertices and <i>m</i> arcs. Vertices 1 and 2 each contain a chip. Two players take alternating turns, each turn consisting of moving one of the chips along an arc of the graph. The player who can't make a valid move loses. We want to know which player wins if both play optimally. The problem so far would be very simple, of course, so here comes the twist: consider all 2<sup>m</sup> subsets of the graph's arcs; for how many of them does the first player win if we keep only the arcs from this subset?<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/XxCjLG-5rio" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/07/an-all-at-once-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-67223496164680782932017-07-09T22:28:00.001+03:002017-07-09T22:28:10.148+03:00A Dublin week<div dir="ltr" style="text-align: left;" trbidi="on">The June 5 - June 11 week was dominated by the main Google Code Jam elimination rounds.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-MXQOERneLXk/WWJ7z4yCNhI/AAAAAAAB14M/cPSaBH9-ddM-NTaY88ntLD3yBvg6aH1ewCLcBGAs/s1600/gcj2017r3top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="309" data-original-width="1345" height="146" src="https://4.bp.blogspot.com/-MXQOERneLXk/WWJ7z4yCNhI/AAAAAAAB14M/cPSaBH9-ddM-NTaY88ntLD3yBvg6aH1ewCLcBGAs/s640/gcj2017r3top5.png" width="640" /></a></div>First off, Code Jam Round 3 took place on Saturday (<a href="https://code.google.com/codejam/contest/8304486/dashboard">problems</a>, <a href="https://code.google.com/codejam/contest/8304486/scoreboard#vt=1">results</a>, top 5 on the left, <a href="https://code.google.com/codejam/contest/8304486/dashboard#s=a">analysis</a>). The top 26 have qualified for the finals in Dublin, and kevinsogo was the only contestant to solve the very tricky last problem and still have time left for two more - congratulations on the first place!<br /><br />I have contributed to the constructive problem trend with <a href="https://code.google.com/codejam/contest/8304486/dashboard#s=p1">problem B</a>: you are given a directed graph with at most <i>n</i><=1000 vertices, and need to output any <a href="https://en.wikipedia.org/wiki/Nowhere-zero_flow">nowhere-zero flow</a> in it with edge flows not exceeding <i>n</i><sup>2</sup> by absolute value. <a href="http://www.sciencedirect.com/science/article/pii/0095895681900587">Seymour's theorem</a> shows that we can actually make do with values between -6 and 6, but such frugality was not required :)<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-sTVKZmE-FIU/WWKCOItSxTI/AAAAAAAB14U/BXoZn3JqJKkUhHMElx8kqP5pmXR4jh4ngCLcBGAs/s1600/dcj2017r2top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="314" data-original-width="1390" height="144" src="https://4.bp.blogspot.com/-sTVKZmE-FIU/WWKCOItSxTI/AAAAAAAB14U/BXoZn3JqJKkUhHMElx8kqP5pmXR4jh4ngCLcBGAs/s640/dcj2017r2top5.png" width="640" /></a></div>One day later, not just two, but 21 more tickets to Dublin were up for grabs in Distributed Code Jam Round 2 (<a href="https://code.google.com/codejam/contest/3284486/dashboard#s=p1">problems</a>, <a href="https://code.google.com/codejam/contest/3284486/scoreboard#vt=1">results</a>, top 5 on the left, <a href="https://code.google.com/codejam/contest/3284486/dashboard#s=a">analysis</a>). Solving everything was not required to qualify, but it was certainly required to get into the screenshot on the left. Congratulations to fagu on being the fastest!<br /><br />Thanks for reading, and check back for the next week's summary!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/j7NSu56cp7w" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/07/a-dublin-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-4595355959386266202017-07-03T11:45:00.001+03:002017-07-03T11:45:34.415+03:00A week**7<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/-tgKu9RXftV4/WVigGWXqufI/AAAAAAAB1z8/W8ReW9Sr1JEZNgCDP2gwJ5khUy-FBiB8ACLcBGAs/s1600/srm715top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="97" data-original-width="637" height="96" src="https://3.bp.blogspot.com/-tgKu9RXftV4/WVigGWXqufI/AAAAAAAB1z8/W8ReW9Sr1JEZNgCDP2gwJ5khUy-FBiB8ACLcBGAs/s640/srm715top5.png" width="640" /></a></div>TopCoder SRM 715 was the first round of May 29 - June 4 week (<a href="https://community.topcoder.com/stat?c=round_overview&rd=16884">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=16884&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://youtu.be/34mzeqhJ-S0">my screencast</a>). It was nice to reduce the amount of 3am rounds thanks to my United States trip :)<br /><br /><a href="https://community.topcoder.com/stat?c=problem_statement&pm=14591&rd=16884">The medium problem</a> continued the "constructive" trend on TopCoder. You are given four numbers: <i>k</i>, <i>n</i><sub>1</sub>, <i>n</i><sub>2</sub>, <i>n</i><sub>3</sub>. You need to construct a valid Towers of Hanoi configuration that requires exactly <i>k</i> moves to be solved, has <i>n</i><sub>1</sub> disks on the first rod, <i>n</i><sub>2</sub> on the second one, and <i>n</i><sub>3</sub> on the third one.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-H9I_AebaUMU/WVihHDbHz1I/AAAAAAAB10A/V9vdiZdbiWoA9a-HsnrmnX3AWjFO5HzngCLcBGAs/s1600/ya2017r3top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="379" data-original-width="1186" height="204" src="https://2.bp.blogspot.com/-H9I_AebaUMU/WVihHDbHz1I/AAAAAAAB10A/V9vdiZdbiWoA9a-HsnrmnX3AWjFO5HzngCLcBGAs/s640/ya2017r3top5.png" width="640" /></a></div>Yandex.Algorithm 2017 Round 3 wrapped up the week, and also completed the selection of the 25 finalists (<a href="https://contest.yandex.com/algorithm2017/contest/4598/problems/">problems</a>, <a href="https://contest.yandex.com/algorithm2017/contest/4598/standings/">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/52376">analysis</a>, <a href="https://contest.yandex.com/algorithm2017/results/">overall standings</a>). Despite the addition of a marathon round which should theoretically be less correlated with the algorithm rounds, the finalist cutoff just increased more or less proportionally, from 32 points from 3 rounds last year to 40 points from 4 rounds this year. Congratulations to all finalists!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-PDjEV4BjsV4/WVoCYMnB7zI/AAAAAAAB10U/aFoDl-tG0XErTL8Do7XCZIr6IGccrBouACLcBGAs/s1600/IMG_20170526_161553.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1200" data-original-width="1600" height="480" src="https://1.bp.blogspot.com/-PDjEV4BjsV4/WVoCYMnB7zI/AAAAAAAB10U/aFoDl-tG0XErTL8Do7XCZIr6IGccrBouACLcBGAs/s640/IMG_20170526_161553.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2017/05/a-7-time-week.html">my previous summary</a>, I have mentioned a problem from Round 2 of the same competition: consider all sequences of balls of <i>k</i><=15 colors, with exactly <i>a<sub>i</sub></i><=15 balls of <i>i</i>-th color, and no two adjacent balls of the same color. Let's arrange them in lexicographical order. What is the number of the given sequence <i>s</i> in this order?<br /><br />Finding the number of <i>s</i> is equivalent to counting the number of sequences coming before <i>s</i> in lexicographical order. Coming before in lexicographical order, in turn, means that some prefix of the such sequence would be equal to the corresponding prefix of <i>s</i>, and the next number will be smaller than the corresponding number of <i>s</i>. That allows us to split our problem into 15 simpler subproblems, each looking like: how many sequences of balls of <i>k</i> colors exist, with exactly <i>b<sub>i</sub></i><=<i>a<sub>i</sub></i> balls of <i>i</i>-th color, no two adjacent balls of the same color, and the first ball has color less than <i>c</i>, and not equal to <i>d</i>?<br /><br />Here comes the main idea that I keep forgetting. Let's add balls into our sequence color-by-color. In order to not have adjacent balls of the same color in the end, it suffices to simply remember how many pair of adjacent balls of the same color we have. In other words, having placed some amount of colors, for a total of <i>t</i> balls, we have <i>t</i>+1 positions where the balls of the next color can be placed, and some of those positions are <i>special</i>: we must place at least one ball in that position eventually, to avoid having two adjacent balls of the same color in the final position. We need to remember just the number of special positions, and do <i>not</i> need to remember which ones exactly are special.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-9uKURKLhxQg/WVoD73HVMsI/AAAAAAAB10o/iPc4Uu_2XgckJqC1M8JhmahlnTNEi3e4wCKgBGAs/s1600/IMG_20170703_104216.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" data-original-height="1493" data-original-width="1600" height="372" src="https://4.bp.blogspot.com/-9uKURKLhxQg/WVoD73HVMsI/AAAAAAAB10o/iPc4Uu_2XgckJqC1M8JhmahlnTNEi3e4wCKgBGAs/s400/IMG_20170703_104216.jpg" width="400" /></a></div>When placing a new color which has <i>a<sub>i</sub></i> balls, we iterate over the number <i>m</i> of blocks of consecutive balls of this color we're going to have, and the number <i>p</i> of those blocks that will be inserted into special positions. Now we need to multiply several combination numbers (to choose <i>p</i> special positions, to choose <i>m</i>-<i>p</i> non-special positions, and to split <i>a<sub>i</sub></i> balls into <i>m</i> non-empty blocks), and we also know the new number of special positions which changes by -<i>p</i>+(<i>a<sub>i</sub></i>-<i>m</i>).<br /><br />Finally, in order to deal with the requirements on the color of the first ball, we can start by processing the colors the first ball can be, and continue with the colors it can't be, and disallow placing balls into the first position on the second stage, which just reduces the number of available non-special positions by one.<br /><br />Assuming we have <i>k</i> colors and at most <i>a</i> balls of each color, the running time of this approach is a product of:<br /><ul style="text-align: left;"><li><i>k</i>*<i>a</i> for iterating over the position of the first difference,</li><li><i>k</i> for iterating over colors,</li><li><i>k</i>*<i>a</i> for iterating over the number of special positions so far,</li><li><i>a</i> for iterating over the number of blocks we form with the new color,</li><li><i>a</i> for iterating over the amount of said blocks that go into special positions,</li></ul>for a total of O(<i>k</i><sup>3</sup><i>a</i><sup>4</sup>).<br /><br />Thanks for reading, and check back for the next week's summary!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/w-5FekkQZNg" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/07/a-week7.htmltag:blogger.com,1999:blog-1953325079793449971.post-18542647135947626752017-05-30T03:14:00.000+03:002017-05-30T08:30:41.842+03:00A 7-time 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/-EuHcJ7XAX_4/WSyfomRR30I/AAAAAAAB0x0/bqB5_kzzxFYXJ3GhknknTrp-Xsw6pWznACLcB/s1600/icpc2017wftop12v2.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="767" data-original-width="1411" height="346" src="https://1.bp.blogspot.com/-EuHcJ7XAX_4/WSyfomRR30I/AAAAAAAB0x0/bqB5_kzzxFYXJ3GhknknTrp-Xsw6pWznACLcB/s640/icpc2017wftop12v2.png" width="640" /></a></div>ACM ICPC 2017 World Finals headlined the last week (<a href="https://icpc.baylor.edu/worldfinals/problems/icpc2017.pdf">problems</a>, <a href="https://static.kattis.com/icpc/wf2017/">results</a>, top 12 on the left, <a href="https://youtu.be/BZo23gj9ksk">our stream</a>, <a href="http://www.csc.kth.se/~austrin/icpc/finals2017solutions.pdf">text analysis</a>, <a href="https://www.youtube.com/user/ICPCNews/videos">video analysis</a>). The ITMO team was leading for quite some time, but they did not manage to solve problem J in time, which gave a chance to the other teams. They did not take advantage of that chance, however, and ITMO became 7-time world champions. Congratulations!<br /><br />Problem D, while being a bit on the "professional" side, was quite cute. You are given 500000 top-left corners and 500000 bottom-right corners on the plane, and need to pick one of each to obtain a valid rectangle with maximum possible area.<br /><br />Here's its <a href="https://www.youtube.com/watch?v=oZBHAGnCs9U">analysis video</a>, in case you give up :)<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-ziFCsaGe7Yc/WSyvpQvSomI/AAAAAAAB0yI/ld1x_AYg5aUapNe_ACTkTlb9r403F16-ACLcB/s1600/agc015top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="468" data-original-width="903" height="330" src="https://3.bp.blogspot.com/-ziFCsaGe7Yc/WSyvpQvSomI/AAAAAAAB0yI/ld1x_AYg5aUapNe_ACTkTlb9r403F16-ACLcB/s640/agc015top5.png" width="640" /></a></div>AtCoder Grand Contest 015 took place on Saturday, when most World Finals contestants should have already got back home (<a href="http://agc015.contest.atcoder.jp/assignments">problems</a>, <a href="http://agc015.contest.atcoder.jp/standings#page_1">results</a>, top 5 on the left, <a href="https://youtu.be/Qjai7_-BQyE">my screencast with commentary</a>, <a href="https://atcoder.jp/img/agc015/editorial.pdf">analysis</a>). When just two last problems remained, I went for the harder one, and almost got it (got accepted in upsolving after about 5 more minutes) - but not quite. sky58, on the other hand, chose the right strategy and won - congratulations!<br /><br /><a href="http://agc015.contest.atcoder.jp/tasks/agc015_c">Problem C</a> allowed multiple different solutions, each with a non-trivial observation and thus quite exciting to get. You are given a set of blue cells on the 2000x2000 grid that forms a forest with regard to 4-connectivity, and 200000 queries. Each query asks: if we take a certain sub-rectangle of our grid, how many connected components of blue cells are there if we look just at that sub-rectangle?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-ObPZH7RBshs/WSyyZiXQbNI/AAAAAAAB0yU/w0fNMynaBXEVvxed_fdvTm_0NuGCy3b_gCLcB/s1600/ya2017r2top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="382" data-original-width="1187" height="204" src="https://3.bp.blogspot.com/-ObPZH7RBshs/WSyyZiXQbNI/AAAAAAAB0yU/w0fNMynaBXEVvxed_fdvTm_0NuGCy3b_gCLcB/s640/ya2017r2top5.png" width="640" /></a></div>A few hours later, Yandex.Algorithm 2017 Round 2 provided another chance to score place points towards qualification for the final round (<a href="https://contest.yandex.com/algorithm2017/contest/4574/problems/">problems</a>, <a href="https://contest.yandex.com/algorithm2017/contest/4574/standings/">results</a>, top 5 on the left, <a href="https://youtu.be/cPYv28Y-hDk">my screencast</a>, <a href="http://codeforces.com/blog/entry/52223">analysis</a>). Tourist threw all strategy considerations out of the window by solving all problems with 15 minutes remaining, while others have barely managed solve solve 5 out of 6. Amazing performance!<br /><br />The solution to <a href="https://contest.yandex.com/algorithm2017/contest/4574/problems/E/">problem E</a> relied on a standard idea which I forgot, so maybe explaining the solution in my blog will help me remember :) Here's what it was about: consider all sequences of balls of <i>k</i><=15 colors, with exactly <i>a<sub>i</sub></i><=15 balls of <i>i</i>-th color, and no two adjacent balls of the same color. Let's arrange them in lexicographical order. What is the number of the given sequence in this order?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-ikH--eWA6BU/WSy07PO8k-I/AAAAAAAB0yg/-2w2Idy4isYq_EKmQo937cQ8dvJQAFmuQCLcB/s1600/hc22017onlinetop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="343" data-original-width="1158" height="188" src="https://2.bp.blogspot.com/-ikH--eWA6BU/WSy07PO8k-I/AAAAAAAB0yg/-2w2Idy4isYq_EKmQo937cQ8dvJQAFmuQCLcB/s640/hc22017onlinetop5.png" width="640" /></a></div>Finally, Codeforces held the online mirror of Helvetic Coding Contest 2017 which I have <a href="http://petr-mitrichev.blogspot.com/2017/04/a-dominator-week.html">mentioned earlier</a> (<a href="http://codeforces.com/contest/802">problems</a>, <a href="http://hc2.ch/scoreboard.html">onsite results</a>, <a href="http://codeforces.com/contest/802/standings">online results</a>, online top 5 on the left, <a href="http://dj3500.webfactional.com/helvetic-coding-contest-2017-editorial.pdf">analysis</a>). Congratulations to the sweet team on the victory (and their penalty time is better than ours from the onsite contest, too)!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-_pyowDkB7AU/WSy4mA1E4HI/AAAAAAAB0ys/oFdkFcqCJg4CDTZKNyXGbxMwoqLbpKoAQCLcB/s1600/IMG_20170525_163724.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1200" data-original-width="1600" height="480" src="https://2.bp.blogspot.com/-_pyowDkB7AU/WSy4mA1E4HI/AAAAAAAB0ys/oFdkFcqCJg4CDTZKNyXGbxMwoqLbpKoAQCLcB/s640/IMG_20170525_163724.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2017/05/an-almost-rapid-week.html">my previous summary</a>, I have mentioned a TopCoder problem: you are given the distances from two vertices to all others in an unknown undirected graph with 50 vertices. You need to construct any graph with such distances from the first two vertices.<br /><br />Consider an arbitrary pair of vertices. If their distances to vertex 1 differ by at least 2, then we can't have an edge between them. The same is true for their distances to vertex 2. This is relatively easy to spot, but here comes the hard part: if neither of the above is true, in other words if both pairs of distances differ by at most 1, then we can assume to <i>always</i> have this edge in our graph. Because if we don't have it, we can add it and distances to vertices 1 and 2 will not be affected for the vertices we just connected, and thus for all other vertices as well.<br /><br />Now, since for each edge we can determine whether we have it in our graph or not, all that remains is to construct the graph, and check if the distances to vertices 1 and 2 come out as expected.<br /><br />Thanks for reading, and check back next week!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/Z31C9xhXaF4" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/05/a-7-time-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-87713683492244790462017-05-24T00:21:00.000+03:002017-05-24T00:21:12.851+03:00ACM ICPC 2017 World Finals stream<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/-k-c1fjJUIIQ/WSSmEO_oeLI/AAAAAAAB0QU/HUkOeQs5GhcXcypqZtpsX4ZUgd-XLQlvgCLcB/s1600/team.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/-k-c1fjJUIIQ/WSSmEO_oeLI/AAAAAAAB0QU/HUkOeQs5GhcXcypqZtpsX4ZUgd-XLQlvgCLcB/s640/team.jpg" width="640" /></a></div>ACM ICPC 2017 World Finals start tomorrow at <a href="https://www.timeanddate.com/worldclock/fixedtime.html?msg=ACM+ICPC+2017+World+Finals&iso=20170524T09&p1=1920&ah=5">9:00 local time</a>. There will be quite a few ways to follow the event, the most prominent being <a href="http://icpclive.com/">ICPC Live</a>. Together with tourist and Endagorion, we have decided to provide another perspective on this competition: we'll try to solve the problems as soon as we get the statements (the rumor has it, we'll be able to submit on Kattis as well), and will stream our screen and our discussions on <a href="https://youtu.be/BZo23gj9ksk">Youtube</a>! Tune in tomorrow around the time World Finals starts, although we might start a bit later.<div><br /></div><div>We're not sure how this will work out, and would appreciate any advice in comments! One thing that we're not yet sure about is whether we should talk in English or in Russian. The latter should be more productive and thus more realistic, but will naturally be harder to follow for most of the audience. On the other side, the sound quality might be so bad that it won't even matter :)</div></div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/PRqp5rDScSg" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/05/acm-icpc-2017-world-finals-stream.htmltag:blogger.com,1999:blog-1953325079793449971.post-88109286641997647042017-05-22T15:30:00.000+03:002017-05-22T15:30:36.498+03:00An almost Rapid 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/-wOQxAVJDblE/WSHhHM2ohLI/AAAAAAAB0Oo/GU_p8AxKu_INZKPp8ZF_hGbCr0xOa5eFACLcB/s1600/tco17r2atop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="96" src="https://2.bp.blogspot.com/-wOQxAVJDblE/WSHhHM2ohLI/AAAAAAAB0Oo/GU_p8AxKu_INZKPp8ZF_hGbCr0xOa5eFACLcB/s640/tco17r2atop5.png" width="640" /></a></div>Last week was relatively calm, with just two competitions that I want to mention, both on Saturday. First, TopCoder Open 2017 Round 2A has significantly raised the stakes compared to Round 1, with just 40 top finishers qualifying (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=16929">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=16929&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://youtu.be/FDAsPNvkYOU">my screencast</a>). I have enjoyed the medium problem of this round the most, as it is quite rewarding to come up with an easy-to-code beautiful solution after wasting some time coding a very tricky one that comes to one's mind first. Especially rewarding step is removing all code written for the tricky solution (<a href="https://youtu.be/FDAsPNvkYOU?t=22m49s">screencast position</a>) :)<br /><br />Here's what <a href="https://community.topcoder.com/stat?c=problem_statement&pm=14596&rd=16929">the problem</a> was about: you are given the distances from two vertices to all others in an unknown undirected graph with 50 vertices. You need to construct any graph with such distances from the first two vertices.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-_5zwD4BcIx0/WSHitDtNp_I/AAAAAAAB0O0/BMi3DvbU7iEra7ot1yFZs9ctM0sEk9AmgCLcB/s1600/cf415top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="156" src="https://3.bp.blogspot.com/-_5zwD4BcIx0/WSHitDtNp_I/AAAAAAAB0O0/BMi3DvbU7iEra7ot1yFZs9ctM0sEk9AmgCLcB/s640/cf415top5.png" width="640" /></a></div>With just a few minutes break, Codeforces hosted its Round 415 (<a href="http://codeforces.com/contest/809">problems</a>, <a href="http://codeforces.com/contest/809/standings">results</a>, top 5 on the left). With the only successful solution to problem E coming from a contestant with no other solved problems, it was the speed that decided the winner, and Radewoosh was almost half an hour faster than the rest. Congratulations!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-GEMyOsGaMvs/WSHnMh0TofI/AAAAAAAB0PA/4odAz_YUWVYdOs7-9NZcIyMpyd2Hfe2GwCKgB/s1600/IMG_20170520_152624.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/-GEMyOsGaMvs/WSHnMh0TofI/AAAAAAAB0PA/4odAz_YUWVYdOs7-9NZcIyMpyd2Hfe2GwCKgB/s640/IMG_20170520_152624.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2017/05/another-speaking-week.html">my previous summary</a>, I have mentioned a Codeforces problem: you are given a connected undirected graph with at most 300000 edges. You suspect that this graph was constructed in the following manner: we started with a graph with no edges and assigned each vertex an integer label, then connected all pairs of vertices for which labels differed by at most one. Your goal is to return a set of labels that could have been used to construct the given graph, or report that there isn't any.<br /><br />First of all, shifting all labels by a constant does not change the answer, so let's pick a vertex A and say that its label is 0. Now, the labels for all other vertices are almost uniquely determined: it's not hard to see that for all vertices labeled <i>not</i> 0, the absolute value of the label is equal to the shortest distance from A. So, we just need to determine which sign will each label have, and which vertices (out of those at distance 1) will have label 0.<br /><br />Here we can see that vertices at distance 1 from A are the most tricky part, so let's concentrate on them. We can assign three labels to them: let's say those with label 1 are set X, with label 0 are set Y, and with label -1 are set Z. By the problem statement, all those sets must be cliques, and additionally we must have all edges between X and Y, and between Y and Z, but no edges between X and Z.<br /><br />Let's assume we have a representative B from X, and a representative C from Z. Then the label of each vertex can be determined trivially: if it's connected only to B, it's 1, only to C, then -1, to both, then 0.<br /><br />It doesn't matter which representatives we pick - in fact, it's not hard to see that we need to pick <i>any</i> two vertices B and C that are connected to A but not between themselves. If we remember that A can also be picked freely, our goal now is to find a chain of two edges such that its endpoints are not connected.<br /><br />And this, in turn, can be done like this: first, let's find <i>any</i> missing edge. The graph is connected, so there's a path between its ends. If this path is of length 2, we're found what we need. If it's longer, consider its next-to-last vertex. If it's connected to its first vertex, we've found what we need. If not, then we can remove the last vertex and obtain a shorter path such that its ends are not connected. By repeating the process, we will eventually find the required path of length 2.<br /><br />Now we have solved the problem for vertices with labels -1, 0 and 1, but how do we determine the sign of the label for the remaining vertices? Well, for vertices with label 2/-2, we can use connectivity to any vertex with label 1 as the differentiating factor, and so on.<br /><br />Finally, having determined all labels, we need to check if our graph does in fact correspond to those labels. The simplest way to do that seems to be: let's check that for all edges in our graph the difference between the labels of the ends is at most one, and also check that the total number of edges in our graph matches the total number of pairs of vertices with labels differing by at most 1. After the first check, the only way we can have an incorrect graph would be having not all required edges, and the second check takes care of that.<br /><br />Thanks for reading, and check back here and in <a href="https://twitter.com/PetrMitrichev">my Twitter</a> for news from ACM ICPC World Finals this week!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/zZio4Yr-OFw" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/05/an-almost-rapid-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-58221634601509628072017-05-22T15:23:00.000+03:002017-05-22T15:23:20.609+03:00Another speaking 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/-a2bOdFPPIwE/WSHSAAJwilI/AAAAAAAB0NY/3F1thmifvI03csibzJ669e1GCGGehz36gCLcB/s1600/cf413top5.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/-a2bOdFPPIwE/WSHSAAJwilI/AAAAAAAB0NY/3F1thmifvI03csibzJ669e1GCGGehz36gCLcB/s640/cf413top5.png" width="640" /></a></div>Just like the previous week, the fun of May 8 - May 14 week started on Thursday with a Codeforces round, this time with Playrix Codescapes Cup (<a href="http://codeforces.com/contest/799">problems</a>, <a href="http://codeforces.com/contest/799/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/51947">analysis</a>). Even an incorrect submission for E could not stop tourist, as he still won thanks to solving problem G and having much more points than everybody else on F. Well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-IKH8zPha1uY/WSHTOi9XkyI/AAAAAAAB0Nk/nt7aZBbx8Aw539RVD29KlLpgvHZDf4LiACLcB/s1600/cf414top5.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/-IKH8zPha1uY/WSHTOi9XkyI/AAAAAAAB0Nk/nt7aZBbx8Aw539RVD29KlLpgvHZDf4LiACLcB/s640/cf414top5.png" width="640" /></a></div>The next round of the week was also a named Codeforces round - this time Tinkoff Challenge Final Round (<a href="http://codeforces.com/contest/794">problems</a>, <a href="http://codeforces.com/contest/794/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/51962">analysis</a>, <a href="https://youtu.be/ko282ZAZe5w">my screencast with commentary</a>). This time explaining everything aloud did not lead to a disastrous performance for me (finally!). Maybe the quality of explanations suffered :) V--o_o--V was still significantly faster, so congratulations on the victory!<br /><br /><a href="http://codeforces.com/contest/794/problem/D">Problem D</a> was a nice exercise in discovering a reliable way to detect a relatively simple pattern. You are given a connected undirected graph with at most 300000 edges. You suspect that this graph was constructed in the following manner: we started with a graph with no edges and assigned each vertex an integer label, then connected all pairs of vertices for which labels differed by at most one. Your goal is to return a set of labels that could have been used to construct the given graph, or report that there isn't any.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-JbNrX5R1APM/WSHcXKqhpPI/AAAAAAAB0OU/J-k47C0pTZ4kcC_o8J5we1i1cW9oxffJwCLcB/s1600/gcj2017r2top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="148" src="https://4.bp.blogspot.com/-JbNrX5R1APM/WSHcXKqhpPI/AAAAAAAB0OU/J-k47C0pTZ4kcC_o8J5we1i1cW9oxffJwCLcB/s640/gcj2017r2top5.png" width="640" /></a></div><div class="separator" style="clear: both; text-align: center;"></div>Later on Saturday, Google Code Jam Round 2 has narrowed the field to just 500 competitors (<a href="https://code.google.com/codejam/contest/5314486/dashboard">problems</a>, <a href="https://code.google.com/codejam/contest/5314486/scoreboard">results</a>, top 5 on the left, <a href="https://code.google.com/codejam/contest/5314486/dashboard#s=a">analysis</a>). Congratulations to jsannemo on the victory - quite impressive form for the KTH team before the upcoming World Finals, with this win and simonlindholm's win a week earlier.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-HA0VZgeusM8/WSHYDzQAZ7I/AAAAAAAB0N4/NwG8FTjeJFwPpxYD6gQSsslilFlzfJVuQCLcB/s1600/ya2017r1top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="204" src="https://3.bp.blogspot.com/-HA0VZgeusM8/WSHYDzQAZ7I/AAAAAAAB0N4/NwG8FTjeJFwPpxYD6gQSsslilFlzfJVuQCLcB/s640/ya2017r1top5.png" width="640" /></a></div>Yandex.Algorithm 2017 Round 1 took place early on Sunday (<a href="https://contest.yandex.com/algorithm2017/contest/4541/problems/">problems</a>, <a href="https://contest.yandex.com/algorithm2017/contest/4541/standings/">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/51990">analysis</a>, <a href="https://youtu.be/_ZUyzpOMMXw">my screencast</a>). Um_nik was flawless on the five easier problems and correctly noticed the fact that problem E was also, in fact, not very hard. Well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-kwRfKjXHi0A/WSHZ_V_VAvI/AAAAAAAB0OE/9VBDFjsuFNYAROGE5VwSrZCW6UPYt_SKACLcB/s1600/rcc2017elimtop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="286" src="https://3.bp.blogspot.com/-kwRfKjXHi0A/WSHZ_V_VAvI/AAAAAAAB0OE/9VBDFjsuFNYAROGE5VwSrZCW6UPYt_SKACLcB/s640/rcc2017elimtop5.png" width="640" /></a></div>Just 80 minutes later, Russian Code Cup 2017 Elimination Round has revealed the 55 finalists (<a href="http://www.russiancodecup.ru/en/championship/round/59/">problems</a>, <a href="http://www.russiancodecup.ru/en/championship/result/59/">results</a>, top 5 on the left, <a href="http://www.russiancodecup.ru/en/press/razbor-zadach-otborochnogo-raunda-2017/">analysis</a>, <a href="https://youtu.be/aY2HiHOO5ng">my screencast</a>). LHiC did not make any mistakes, and that turned out to be the key to getting the first place. Congratulations!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-CA2QVdXQt4I/WSHcD3brrxI/AAAAAAAB0OQ/zExUSYKAIoQ6h3p69Hpz9NNkln8Qga7FACLcB/s1600/dcj2017r1top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="138" src="https://4.bp.blogspot.com/-CA2QVdXQt4I/WSHcD3brrxI/AAAAAAAB0OQ/zExUSYKAIoQ6h3p69Hpz9NNkln8Qga7FACLcB/s640/dcj2017r1top5.png" width="640" /></a></div>And finally, Distributed Google Code Jam Round 1 wrapped up the week (<a href="https://code.google.com/codejam/contest/8314486/dashboard#s=p1">problems</a>, <a href="https://code.google.com/codejam/contest/8314486/scoreboard">results</a>, top 5 on the left, <a href="https://code.google.com/codejam/contest/8314486/dashboard#s=a">analysis</a>). mk.al13n was ten minutes faster than the rest of the pack in this still quite unusual format with parallel computations. Great job on the victory!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-Wodpaapca0I/WSHgQ9lMckI/AAAAAAAB0Og/d5UBqcM0wS0XZr2RUYRZSr1Cs723nXuGACKgB/s1600/IMG_20170429_183705.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/-Wodpaapca0I/WSHgQ9lMckI/AAAAAAAB0Og/d5UBqcM0wS0XZr2RUYRZSr1Cs723nXuGACKgB/s640/IMG_20170429_183705.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2017/05/a-plus-minus-week.html">my previous summary</a>, I have mentioned an AtCoder problem: you are given two trees on the same set of vertices, one blue and one red. You want to convert the blue tree into the red one, step-by-step. At each step, you must take any path consisting of blue edges, add a red edge connecting its endpoints, but remove one of the edges of the path. After <i>n</i>-1 steps all blue edges will be removed, and <i>n</i>-1 red edges will be added, and you want those edges to form the required red tree.<br /><br />The key idea in this problem is: let's look at the process from the end. Before the last step, we have just one blue edge connecting vertices, say, A and B, so our only option is to remove that edge and add a red edge connecting A and B. Now in the next-to-last step, we must either do the same, or make use of the last blue edge: for example, we can remove blue edge A-C, and add red edge B-C. After some staring at the paper, one can figure out what does this mean: first, we need to find an edge that is both blue and red for the last step, and then we need to <i>contract</i> it - unit its ends together into one vertex. Then, we need to find an edge that is both blue and red in the resulting graph (it might either be blue and red in the beginning, or be a result of a merge of different blue and red edges during the contraction), and contract it again, and so on until the graph is just one vertex.<br /><br />Now it becomes clear that it doesn't really matter in which order we do the contractions, as they never make things worse. So we should just repeatedly perform any available contraction. There's some technical mastery involved in making the process run in O(<i>n</i>*polylog(<i>n</i>)) time, but that part is relatively standard and I don't want to focus on it too much. You can check <a href="https://atcoder.jp/img/agc014/editorial.pdf">the analysis</a> for more details.<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/1adVUhsMF2w" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/05/another-speaking-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-73652167705104084832017-05-21T20:34:00.001+03:002017-05-21T20:37:38.569+03:00A plus-minus 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/-dQgnRa9ig3Q/WSG69HxHlfI/AAAAAAAB0MQ/3rV05udlLQII4AcmNivgi5jMKpYG6fWzACLcB/s1600/cf411top5.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/-dQgnRa9ig3Q/WSG69HxHlfI/AAAAAAAB0MQ/3rV05udlLQII4AcmNivgi5jMKpYG6fWzACLcB/s640/cf411top5.png" width="640" /></a></div>The first contest in May was the Codeforces Round 411 (<a href="http://codeforces.com/contest/804">problems</a>, <a href="http://codeforces.com/contest/804/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/51846">analysis</a>). This was one of those rare rounds where finding bugs in the solutions of others turned out to be a better strategy than solving more problems - but just barely. Congratulations to AlexDmitriev for finding 18 challenges and finishing less than one challenge above the second place!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-67kCTtBXdqg/WSG70FV75cI/AAAAAAAB0MY/xl57K1Wm3eUP4w6Hxn7anUlA9kbC-n6nwCLcB/s1600/agc014top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="314" src="https://4.bp.blogspot.com/-67kCTtBXdqg/WSG70FV75cI/AAAAAAAB0MY/xl57K1Wm3eUP4w6Hxn7anUlA9kbC-n6nwCLcB/s640/agc014top5.png" width="640" /></a></div>And then, the weekend. First off, AtCoder Grand Contest 014 (<a href="http://agc014.contest.atcoder.jp/assignments">problems</a>, <a href="http://agc014.contest.atcoder.jp/standings#page_1">results</a>, top 5 on the left, <a href="https://atcoder.jp/img/agc014/editorial.pdf">analysis</a>, <a href="https://youtu.be/pTSHMT12PSQ">my screencast</a>). The round seemed to have been decided in the first 45 minutes thanks to the amazing performance by w4yneb0t, but with just 20 seconds left simonlindholm overcame all tricks in the last problem and claimed the victory. Huge congratulations!<br /><br /><a href="http://agc014.contest.atcoder.jp/tasks/agc014_e">Problem E</a> looked tedious at first, but coming up with the right idea helped make the implementation really easy. You are given two trees on the same set of vertices, one blue and one red. You want to convert the blue tree into the red one, step-by-step. At each step, you must take any path consisting of blue edges, add a red edge connecting its endpoints, but remove one of the edges of the path. After <i>n</i>-1 steps all blue edges will be removed, and <i>n</i>-1 red edges will be added, and you want those edges to form the required red tree.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-jQK0ripmCTA/WSG-yKO0gNI/AAAAAAAB0Mk/vh4jDBZX3lokni-IcCpDMZ35JQrl0gFxQCLcB/s1600/tco17r1ctop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="80" src="https://3.bp.blogspot.com/-jQK0ripmCTA/WSG-yKO0gNI/AAAAAAAB0Mk/vh4jDBZX3lokni-IcCpDMZ35JQrl0gFxQCLcB/s640/tco17r1ctop5.png" width="640" /></a></div>In a few ours after the end of AGC 014, TopCoder Open 2017 Round 1C provided the last chance to qualify into Round 2 (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=16915">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=16915&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left). The results were not very surprising, with all contestants with a "red" rating who took part advancing to the next round. Nevertheless, the fight for the first place was extremely heated with several changes of the leader. In the end Baz93 has emerged on top thanks to 9 successful challenges, including one made 7 seconds before the end of the challenge phase. Congratulations!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-Pm8-qmvl2B0/WSHAtP2gOVI/AAAAAAAB0Mw/r4og0xqigeUersGuIbeMwIC-4Ja_SFeRACLcB/s1600/tco17russiatop5.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/-Pm8-qmvl2B0/WSHAtP2gOVI/AAAAAAAB0Mw/r4og0xqigeUersGuIbeMwIC-4Ja_SFeRACLcB/s640/tco17russiatop5.png" width="640" /></a></div>On Sunday, TopCoder hosted a TopCoder Open 2017 Regional event in St Petersburg (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=16916">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=16916&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=16883&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">SRM 714 results</a> with 2 same problems out of 3, <a href="https://youtu.be/8KlsIRjtGF8">my screencast</a>). <a href="https://community.topcoder.com/stat?c=problem_statement&pm=14595&rd=16916">The medium problem</a> (easy in SRM) was another example of extremely easy implementation after coming up with the right idea. You are given a string of at most 2500 parentheses which is a valid parentheses sequence. You repeatedly do the following: remove the first character of the string (which is always an opening parenthesis), and remove any closing parenthesis from the string. The remaining string must also be a valid parentheses sequence. You repeat this step until everything has been removed. How many ways are there to complete the entire process, modulo 10<sup>9</sup>+7?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-INW16ZZWHng/WSHCtjuFkuI/AAAAAAAB0M8/QhnRQfzOwQcchczqNAlPpfBU3_ssXR3BQCLcB/s1600/vk2017r3top5.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/-INW16ZZWHng/WSHCtjuFkuI/AAAAAAAB0M8/QhnRQfzOwQcchczqNAlPpfBU3_ssXR3BQCLcB/s640/vk2017r3top5.png" width="640" /></a></div>Finally, Codeforces hosted VK Cup 2017 Round 3 (<a href="http://codeforces.com/contest/773">problems</a>, <a href="http://codeforces.com/contest/773/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/contest/806/standings">parallel round results</a>, <a href="http://codeforces.com/blog/entry/51883">analysis</a>, <a href="https://youtu.be/KoWxEC4sIXM">my screencast</a>). This time it was another team of Moscow students who dominated the proceedings, with over 500 points margin. Congratulations to the sinful team!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-xUKp_yGFvDs/WSHPac-P_tI/AAAAAAAB0NM/YD11NLR2C0sFZXDpmvMbqGG0tIdhDlm1wCKgB/s1600/IMG_20170428_120537.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="240" src="https://4.bp.blogspot.com/-xUKp_yGFvDs/WSHPac-P_tI/AAAAAAAB0NM/YD11NLR2C0sFZXDpmvMbqGG0tIdhDlm1wCKgB/s320/IMG_20170428_120537.jpg" width="320" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2017/05/a-week-modulo-3.html">my previous summary</a>, I have mentioned an interactive Open Cup problem. You are given six six-sided dice, each having some digits and mathematical symbols written on it, as follows:<br /><br />Die 1: <span style="font-family: "courier new" , "courier" , monospace;">= < > != <= >=</span><br />Die 2: <span style="font-family: "courier new" , "courier" , monospace;">4 + - ( ( )</span><br />Die 3: <span style="font-family: "courier new" , "courier" , monospace;">0 / / / 8 +</span><br />Die 4: <span style="font-family: "courier new" , "courier" , monospace;">2 3 4 5 - )</span><br />Die 5: <span style="font-family: "courier new" , "courier" , monospace;">+ - * / 1 9</span><br />Die 6: <span style="font-family: "courier new" , "courier" , monospace;">6 7 + - ( )</span><br /><br />You need to pick a die, then roll it (by interacting with the judge program), and record the symbol that appears. Then you can do it again, using either the same or a different die, and so on, doing at most 1000 rolls. At some point you need to stop rolling, and form a correct mathematical expression (equality or inequality) by concatenating <i>all</i> recorded symbols in some order. No need to optimize anything - just build any correct expression after at most 1000 rolls.<br /><br />There must be a ton of different approaches in this problem, as any valid expression suffices. The first idea lies on the surface: since the first die always gives us a comparison, and there must be exactly one comparison in each expression, we can start by rolling the first die once. This will give us the type of comparison we're building. In the remainder of the explanation I will assume we get "=", as that is the most tricky case - the rest can be handled in the same manner.<br /><br />But then, things get not so easy. First, we should get enough symbols to form any syntactically valid expression: we should get the same amount of opening and closing parentheses, and the amount of operations we get should be two less (one for each side) than the amount of numbers we have (after the contest I've noticed that the numbers can be joined together to form multiple-digit numbers, but I did not notice this in the heat of the moment). Then, of course, we need to form not just syntactically valid expression but a correct equality.<br /><br />The next idea is: the "correct" part is actually much easier than "syntactically valid" part. Assuming we have only digits and +/- signs, then we just need to split the digits into two groups with the same sum, and with enough different digits this is always possible.<br /><br />Now, we need to find a way to get the right left-right parenthesis balance, and the right operation-digit balance. The two key dice that help accomplish that are, for example, die 3 and die 2. Let's assume we already rolled some dice, and we have more closing parentheses than opening parentheses. Then we can repeatedly roll die 2 until we get the right parentheses balance. After that, let's assume we have more digits than operations. Then we can repeatedly roll die 3 until we get the right balance (and this won't affect the parentheses).<br /><br />So now we only need to prepare the ground for rolling dies 2 and 3 - we need to roll some dice in such a way that we have more closing than opening parentheses, and much more digits than operations (so that even rolling die 2 a few times does not cancel that), and enough different digits and +/- operations to build our equality in the end. Die 3 also gives us "/" operations, but to avoid complications we'll just divide 0 by some numbers to get rid of those.<br /><br />It's easy to see now that die 4 is exactly what we need. Let's roll it a few (say, 100) times. We will have a few (~16) closing parentheses, and a lot more digits than operations, and those digits will be from a wide variety, so we're guaranteed to get two equal sums. Now we also need a 0 to handle the divisions, so let's roll die 3 until we get it. After this we can switch to "die 2, then die 3" strategy described above to get the right balances, and finally form our equation.<br /><br />How did your team solve this problem? Maybe there's a simpler approach?</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/tvdo169XqUQ" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/05/a-plus-minus-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-18684664937521578982017-05-13T21:08:00.001+03:002017-05-13T21:08:14.460+03:00A week modulo 3<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/-FZij_eIoF6g/WRc--WdMTNI/AAAAAAAB0DY/x5dpS-br1KE0e4QPPnONYRXGuwmXuRqrQCLcB/s1600/srm713top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="80" src="https://2.bp.blogspot.com/-FZij_eIoF6g/WRc--WdMTNI/AAAAAAAB0DY/x5dpS-br1KE0e4QPPnONYRXGuwmXuRqrQCLcB/s640/srm713top5.png" width="640" /></a></div>TopCoder SRM 713 opened the last week of April (<a href="https://community.topcoder.com/stat?c=round_overview&rd=16882">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=16882&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left). Once again, nobody has managed to solve the hard problem. Endagorion was the fastest on the first two, and defended his lead during the challenge phase with a +50. Well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-7EjDEOj-pl4/WRc_s8J25uI/AAAAAAAB0Dg/zHudrII4kvISIQP1-XF7vOr2gj9507ASwCLcB/s1600/ya2017qualtop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="202" src="https://3.bp.blogspot.com/-7EjDEOj-pl4/WRc_s8J25uI/AAAAAAAB0Dg/zHudrII4kvISIQP1-XF7vOr2gj9507ASwCLcB/s640/ya2017qualtop5.png" width="640" /></a></div>Yandex.Algorithm 2017 Qualification Round was available as a virtual contest for the whole Saturday (<a href="https://contest.yandex.com/algorithm2017/contest/4502/problems/">problems</a>, <a href="https://contest.yandex.com/algorithm2017/contest/4502/standings/">results</a>, top 5 on the left, <a href="https://contest.yandex.com/algorithm2017/qual_a/">analysis</a>). Egor has dominated the round thanks to very fast problem solving, and the most appropriate strategy: get one problem accepted in the open to ensure qualification, and then submit the rest blindly to minimize the penalty time. Very well executed!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-kXKw9m2O7Zs/WRdA1HNJytI/AAAAAAAB0Ds/aqrOzO0VoOYAdv2W6BBuCQ9fVinKfF3zgCLcB/s1600/rcc2017q3top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="292" src="https://3.bp.blogspot.com/-kXKw9m2O7Zs/WRdA1HNJytI/AAAAAAAB0Ds/aqrOzO0VoOYAdv2W6BBuCQ9fVinKfF3zgCLcB/s640/rcc2017q3top5.png" width="640" /></a></div>Russian Code Cup 2017 Qualification Round 3 also took place on Saturday (<a href="http://www.russiancodecup.ru/en/championship/round/62/">problems</a>, <a href="http://www.russiancodecup.ru/en/championship/result/62/">results</a>, top 5 on the left, <a href="http://www.russiancodecup.ru/en/press/rcc-2017-razbor-zadach-3-go-kvalifikacionnogo-raunda/">analysis</a>). -XraY- fought back after missing the top 200 in the first qualification round and solved all problems cleanly and so fast that his penalty time is more than 2x smaller than that of the second place - amazing!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-cp2ZIbhr5x0/WRdDVRUs3LI/AAAAAAAB0D4/5f3Il2fJSYEFCzDnvq5ercIoValVoOh5ACLcB/s1600/oc1617uraltop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="152" src="https://3.bp.blogspot.com/-cp2ZIbhr5x0/WRdDVRUs3LI/AAAAAAAB0D4/5f3Il2fJSYEFCzDnvq5ercIoValVoOh5ACLcB/s640/oc1617uraltop5.png" width="640" /></a></div>The final Open Cup round of the 2016-17 season took place on Sunday, the Grand Prix of Ural (<a href="http://opentrains.snarknews.info/~ejudge/res/res10378">results</a>, top 5 on the left, <a href="http://opencup.ru/index.cgi?data=macros/results&menu=index&head=index&ncup=och&class=och&region=main">overall Open Cup results</a>, top 5 on the left). Team Past Glory did not really leave much doubt as to who would win this round, solving 12 problems 1.5 hours before the end of the contest, and having all the time in the world to solve the tricky geometric problem F. Congratulations on the victory!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-gfsvhQ2VCZU/WRdEs2MhsaI/AAAAAAAB0EI/VgeOzB5XRDIQwbFtnDLVxQhL3-Iqt1J_wCEw/s1600/oc1617overalltop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="72" src="https://2.bp.blogspot.com/-gfsvhQ2VCZU/WRdEs2MhsaI/AAAAAAAB0EI/VgeOzB5XRDIQwbFtnDLVxQhL3-Iqt1J_wCEw/s640/oc1617overalltop5.png" width="640" /></a></div>Problem E was a great example of a non-obvious problem that still requires almost pure creativity to solve, instead of mathematical theorems, algorithms or data structure knowledge. It is an interactive problem. You are given six six-sided dice, each having some digits and mathematical symbols written on it, as follows:<br /><br />Die 1: <span style="font-family: "courier new" , "courier" , monospace;">= < > != <= >=</span><br />Die 2: <span style="font-family: "courier new" , "courier" , monospace;">4 + - ( ( )</span><br />Die 3: <span style="font-family: "courier new" , "courier" , monospace;">0 / / / 8 +</span><br />Die 4: <span style="font-family: "courier new" , "courier" , monospace;">2 3 4 5 - )</span><br />Die 5: <span style="font-family: "courier new" , "courier" , monospace;">+ - * / 1 9</span><br />Die 6: <span style="font-family: "courier new" , "courier" , monospace;">6 7 + - ( )</span><br /><br />You need to pick a die, then roll it (by interacting with the judge program), and record the symbol that appears. Then you can do it again, using either the same or a different die, and so on, doing at most 1000 rolls. At some point you need to stop rolling, and form a correct mathematical expression (equality or inequality) by concatenating <i>all</i> recorded symbols in some order. No need to optimize anything - just build any correct expression after at most 1000 rolls.<br /><br />How would you approach this problem?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-dllcRExAIyo/WRdHmH1eTwI/AAAAAAAB0EQ/rxNkNh1uh5sN4x3QHcrf00Zz2CEoK4LtACLcB/s1600/gcj2017r1ctop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="162" src="https://3.bp.blogspot.com/-dllcRExAIyo/WRdHmH1eTwI/AAAAAAAB0EQ/rxNkNh1uh5sN4x3QHcrf00Zz2CEoK4LtACLcB/s640/gcj2017r1ctop5.png" width="640" /></a></div>In keeping with the new trend of having multiple competitions at the same time, Google Code Jam 2017 Round 1C took place in the middle of the Open Cup (<a href="https://code.google.com/codejam/contest/3274486/dashboard">problems</a>, <a href="https://code.google.com/codejam/contest/3274486/scoreboard#vt=1">results</a>, top 5 on the left, <a href="https://code.google.com/codejam/contest/3274486/dashboard#s=a&a=3">analysis</a>). It was EgorKulikov who followed Eryx's strategy from Round 1A this time, submitting the super tricky hardest problem much earlier than everybody else. Congratulations on the victory!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-TkHk8Vesu_M/WRdK9n5v-FI/AAAAAAAB0Ek/8nH6IYrNGSUu27uOaSDoXZ7Q-lM5jPnlACLcB/s1600/IMG_20170417_132444.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/-TkHk8Vesu_M/WRdK9n5v-FI/AAAAAAAB0Ek/8nH6IYrNGSUu27uOaSDoXZ7Q-lM5jPnlACLcB/s640/IMG_20170417_132444.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2017/05/an-oeis-week.html">my previous summary,</a> I have mentioned another Open Cup problem: construct a <a href="https://en.wikipedia.org/wiki/Completely_multiplicative_function">completely multiplicative function</a> f(x) such that f(x)=1 or -1, f(<i>a</i>*<i>b</i>)=f(<i>a</i>)*f(<i>b</i>), and that for each n between 1 and 1000000 the prefix sum f(1)+f(2)+...+f(n) does not exceed 20 by absolute value.<br /><br />When trying to solve it, I was approaching it in the way that many recent "constructive" problems were meant to be solved: try a few things on the computer, maybe do some local optimizations, and it should work. However, I did not manage to find success on this path.<br /><br />It turns out that there is a solution that can be easily done on paper without using any computer time. Let's define f(3k+1)=1, f(3k+2)=-1, f(3k)=f(k). The multiplicativity follows from the fact that powers of 3 do not impact the value of the function, and numbers 1 and 2 modulo 3 are the same as 1 and -1 modulo 3. Finally, almost all numbers in the prefix sum cancel out: if we look at positions not divisible by 3, 1 and -1 alternate, so the prefix sum of those positions is always 1 or 0. For positions divisible by 3, but not by 9, the same argument applies, and so on; thus each prefix sum will never exceed log<sub>3</sub>1000000 (one for each power of 3), which is less than 20.<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/wkd4JoN3kMA" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/05/a-week-modulo-3.htmltag:blogger.com,1999:blog-1953325079793449971.post-3042995837827994702017-05-13T11:22:00.000+03:002017-05-13T11:22:16.756+03:00An OEIS 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/-BmUXsoXskco/WRa0NsVB0xI/AAAAAAAB0Bo/uzgi7Ew0n4IzgvqLZkYYtgM9FtvrzzM5wCLcB/s1600/srm712top5.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/-BmUXsoXskco/WRa0NsVB0xI/AAAAAAAB0Bo/uzgi7Ew0n4IzgvqLZkYYtgM9FtvrzzM5wCLcB/s640/srm712top5.png" width="640" /></a></div>TopCoder SRM 712 took place on Tuesday, April 18 (<a href="https://community.topcoder.com/stat?c=round_overview&rd=16881">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=16881&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left). The results remind me of <a href="https://community.topcoder.com/stat?c=round_overview&rd=10007">the second SRM</a> that I prepared myself - two accepted solutions on the medium, and none on the hard :)<br /><br />The reason for such crushing difficulty of <a href="https://community.topcoder.com/stat?c=problem_statement&pm=14570&rd=16881">the medium problem</a> was the fact that the most obvious solution did not work because of <a href="https://en.wikipedia.org/wiki/Loss_of_significance">catastrophic cancellation</a> in floating-point computations. I do not want to go into the details of this particular problem here, so I will refer you to <a href="http://codeforces.com/blog/entry/50574?#comment-355204">the post-match discussion</a> for the details of how my solution overcame this obstacle.<br /><br />More generally, I think understanding how floating-point numbers work is not that hard, and it pays off not just in such black-and-white cases like this problem, but also in more subtle situations, for example when thinking about whether an eps is required or not in comparisons in a geometry problem, and how big it should be if it's required. I think at some point <a href="https://www.topcoder.com/community/data-science/data-science-tutorials/representation-of-integers-and-reals-section-2/">this misof's tutorial</a> was the eye-opener for me with regard to floating-point computations, so I heartily recommend it. At the same time, it's quite likely that even more useful tutorials on floating-point numbers have been published since then, so please point those out in comments!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-D0q-Ds_YGHo/WRa4E1ApXiI/AAAAAAAB0B0/H4vf66hk_DYk4nI5Jn5pflRPna2xlw22gCLcB/s1600/ya2017warmuptop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="206" src="https://2.bp.blogspot.com/-D0q-Ds_YGHo/WRa4E1ApXiI/AAAAAAAB0B0/H4vf66hk_DYk4nI5Jn5pflRPna2xlw22gCLcB/s640/ya2017warmuptop5.png" width="640" /></a></div>Yandex.Algorithm 2017 started with its Warm-up round on Saturday (<a href="https://contest.yandex.com/algorithm2017/contest/4449/problems/">problems</a>, <a href="https://contest.yandex.com/algorithm2017/contest/4449/standings/">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/51668">analysis</a>). It was enough to solve any problem to advance, and thus the first place did not hold much tournament value; nevertheless, it was still the first place. Congratulations to kusas2018 on the victory!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-BHRpqULIifg/WRa4ZkS0gXI/AAAAAAAB0B4/h9gqPuWBx641bPbT9uPIv1vvzyF43sEEwCLcB/s1600/gcj2017r1btop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="170" src="https://2.bp.blogspot.com/-BHRpqULIifg/WRa4ZkS0gXI/AAAAAAAB0B4/h9gqPuWBx641bPbT9uPIv1vvzyF43sEEwCLcB/s640/gcj2017r1btop5.png" width="640" /></a></div>Google Code Jam 2017 Round 1B followed in a little over an hour (<a href="https://code.google.com/codejam/contest/8294486/dashboard">problems</a>, <a href="https://code.google.com/codejam/contest/8294486/scoreboard#vt=1">results</a>, top 5 on the left, <a href="https://code.google.com/codejam/contest/8294486/dashboard#s=a">analysis</a>). The problems were not as tricky as in Round 1A, and JAPLJ had to be really fast to beat the second place by less than a minute!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-EyOlLWf1AkA/WRa69_T5H7I/AAAAAAAB0CI/85TFhyRXVFswEY9qTlDAUAo43Y8uM3I3gCLcB/s1600/oc1617moscowworkshoptop5.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/-EyOlLWf1AkA/WRa69_T5H7I/AAAAAAAB0CI/85TFhyRXVFswEY9qTlDAUAo43Y8uM3I3gCLcB/s640/oc1617moscowworkshoptop5.png" width="640" /></a></div>No April weekend is complete without an Open Cup round, this time the penultimate Grand Prix of Moscow Workshop (<a href="http://opencup.ru/index.cgi?data=macros/stage&head=index&menu=index&stg=17&region=main&ncup=och&class=och">results</a>, top 5 on the left, <a href="https://www.dropbox.com/s/wyibgkdycf8ubxe/20170417.pdf?dl=1">analysis</a>). The SPb ITMO 1 team has clinched the first place in the overall standings with a win in this round - the first season in a while where Gennady's team could not win the Open Cup. Big congratulations to Ivan, Ilya and Vladimir!<br /><br />Problem B was a nice mathematical puzzle that did not crack for our team: one needed to construct a <a href="https://en.wikipedia.org/wiki/Completely_multiplicative_function">completely multiplicative function</a> f(x) such that f(x)=1 or -1, f(<i>a</i>*<i>b</i>)=f(<i>a</i>)*f(<i>b</i>), and that for each n between 1 and 1000000 the prefix sum f(1)+f(2)+...+f(n) does not exceed 20 by absolute value. Do you see a way?<br /><div><br /></div><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-tkY1r7M-UsI/WRa9AoaPGXI/AAAAAAAB0CU/9XArfBjF9NoCuQl-lC7JPUKzce6LkkYUACLcB/s1600/tinkoffelim2017top5.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/-tkY1r7M-UsI/WRa9AoaPGXI/AAAAAAAB0CU/9XArfBjF9NoCuQl-lC7JPUKzce6LkkYUACLcB/s640/tinkoffelim2017top5.png" width="640" /></a></div>And finally, Codeforces held the Elimination Round for another company-sponsored tournament: the Tinkoff Challenge (<a href="http://codeforces.com/contest/793">problems</a>, <a href="http://codeforces.com/contest/793/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/51685">analysis</a>). LHiC held the first place despite failing one of the problems during the system test, thanks to being the only one to solve both problems E and F. Well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-8iPNnOc_eDk/WRa-iX7sxSI/AAAAAAAB0Cs/bM9MlUvkCPUavNtVaBlwW283yBO4srzHwCLcB/s1600/IMG_20170415_123708.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="336" src="https://2.bp.blogspot.com/-8iPNnOc_eDk/WRa-iX7sxSI/AAAAAAAB0Cs/bM9MlUvkCPUavNtVaBlwW283yBO4srzHwCLcB/s640/IMG_20170415_123708.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2017/05/a-zero-pigeon-week.html">my previous summary</a>, I have mentioned several problems, and <a href="http://agc013.contest.atcoder.jp/tasks/agc013_e">this AtCoder problem</a> allows me to share an interesting experience, so I will explain it. We are given a long (10<sup>9</sup>) segment. Some (at most 10<sup>5</sup>) integer points on the segment are special. We consider all ways to take some set of <i>non</i>-special integer points on the segment. Each such set splits the segment into smaller segments. Let's find the <i>product</i> p of their lengths, and then compute the sum of the squares <i>p</i><sup>2</sup> of those products over all ways. What number are we going to get, modulo 10<sup>9</sup>+7?<br /><br />For quite some time, I had no clue how to approach it. I've started to think about an easier version: what if there are no special points? Even for that problem, I could not come up with a solution that's fast enough for 10<sup>9</sup>. However, I could come up with a somewhat straightforward O(<i>n</i><sup>2</sup>) dynamic programming approach: to find the answer for a given length, we will simply iterate over all possibilities for the last segment and use the answers for smaller lengths that were computed previously.<br /><br />I've implemented this solution quickly, obtained the answers for small values of <i>n</i>, and entered them into <a href="https://oeis.org/">the OEIS search</a> which yielded me <a href="https://oeis.org/A033453">this sequence</a>. For a moment it seemed that the OEIS entry is not very helpful, but then I noticed the generating function (<i>x</i>+1)/(1-4<i>x</i>+2<i>x</i><sup>2</sup>-<i>x</i><sup>3</sup>), which is in a form of polynomial fraction, which means that the elements of the sequence correspond to a linear recurrence <i>a</i><sub>n</sub>=4<i>a</i><sub>n-1</sub>-2<i>a</i><sub>n-2</sub>+<i>a</i><sub>n-3</sub>. In order to see that, we can rewrite the equation for the generating function like this:<br /><br />(<i>a</i><sub>0</sub><i>x</i><sup>0</sup>+<i>a</i><sub>1</sub><i>x</i><sup>1</sup>+...)*(1-4<i>x</i>+2<i>x</i><sup>2</sup>-<i>x</i><sup>3</sup>)=(<i>x</i>+1)<br /><br />Since the right part is a finite polynomial, so is the left part, and it means that the coefficient near <i>x<sup>n</sup></i> in that product is 0 for almost all values of <i>n</i>, and expanding the product allows us to find that the coefficient near <i>x<sup>n </sup></i>is <i>a</i><sub>n</sub>-4<i>a</i><sub>n-1</sub>+2<i>a</i><sub>n-2</sub>-<i>a</i><sub>n-3</sub>, which directly yields the recurrence.<br /><br />Finding the 10<sup>9</sup>-th element of a linear recurrence is a standard task that can be solved using fast matrix exponentiation, so we have now solved the version of the problem without the special points. The answer is given by (some element of) the product M<i><sup>n</sup>v</i> where <i>M</i> is some matrix and <i>v</i> is some vector.<br /><br />Now suppose we have exactly one special point <i>y</i>. We need to subtract the decompositions that use this special point, and that means that if f(<i>n</i>) is the answer without special points, then the answer with one special point is equal to g(<i>n</i>)=f(<i>n</i>)-f(<i>y</i>)*f(<i>n</i>-<i>y</i>). We can now rewrite it using the formula for f(<i>n</i>) that we have: g(n)=M<i><sup>n</sup>v</i>-f(y)*M<i><sup>n-y</sup>v=</i>M<i><sup>n</sup>v</i>-f(y)*M<i><sup>n</sup></i>M<i><sup>-y</sup></i><i>v</i>=M<i><sup>n</sup></i>(<i>v</i>-f(y)*M<i><sup>-y</sup></i><i>v</i>). In other words, g(<i>n</i>) has the same form: the <i>n</i>-th power of the matrix <i>M</i> times some vector!<br /><br />It's not hard to generalize this to any amount of special points. I.e., with the second special point placed at <i>z</i> we will have h(<i>n</i>)=g(<i>n</i>)-g(<i>z</i>)*f(<i>n</i>-<i>z</i>) which transforms in exactly the same way, and so on. Each special point is handled in logarithmic time (to compute f(<i>y</i>) and M<i><sup>-y</sup></i>), so the overall running time is O(<i>m</i>log<i>n</i>), where <i>m</i> is the number of special points.<br /><br />This story is quite the opposite to the approach I have shown in two previous posts: here we do not build any meaningful intuition about the problem, and instead try to almost mechanically build something that works using random facts found on the Internet.<br /><br />Of course, this problem has a more sensible solution, which you can find in <a href="https://atcoder.jp/img/agc013/editorial.pdf">the official analysis</a>. Thanks for reading, and check back soon!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/YAPYe3pyLr4" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/05/an-oeis-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-78150359761083650722017-05-10T10:44:00.001+03:002017-05-10T10:44:35.672+03:00A zero pigeon 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/-rmiyOC8-Llg/WRLBOdboL9I/AAAAAAABz-o/8ZcP__HmXs0mj8nrRzfAqLhq9rtBIqAxQCLcB/s1600/gcj2017r1atop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="164" src="https://2.bp.blogspot.com/-rmiyOC8-Llg/WRLBOdboL9I/AAAAAAABz-o/8ZcP__HmXs0mj8nrRzfAqLhq9rtBIqAxQCLcB/s640/gcj2017r1atop5.png" width="640" /></a></div>The April 15-16 Easter weekend was even more packed with contests. First off, Google Code Jam Round 1A took place very early on Saturday (<a href="https://code.google.com/codejam/contest/5304486/dashboard">problems</a>, <a href="https://code.google.com/codejam/contest/5304486/scoreboard#vt=1">results</a>, top 5 on the left, <a href="https://code.google.com/codejam/contest/5304486/dashboard#s=a">analysis</a>). Eryx has solved all problems 40 minutes faster than anybody else, but he might've been taking a big gamble, as the last problem was exceptionally tricky (8 correct out of 124 attempts). In any case, congratulations on the victory!<br /><br />I think <a href="https://code.google.com/codejam/contest/5304486/dashboard#s=p0">problem A</a> was a great example of a beautiful easy problem. You are given a grid where some cell contain letters, and some are empty, such that each letter appears at most once. Your goal is to write letters to all empty cells in such a way that the cells with each letter form a grid-aligned rectangle. You're only allowed to use letters that are already present in the grid. Any valid solution suffices.<br /><br />For example,<br /><span style="font-family: "courier new" , "courier" , monospace;">G??</span><br /><span style="font-family: "courier new" , "courier" , monospace;">?C?</span><br /><span style="font-family: "courier new" , "courier" , monospace;">??J</span><br />can be solved as<br /><span style="font-family: "courier new" , "courier" , monospace;">GGJ</span><br /><span style="font-family: "courier new" , "courier" , monospace;">CCJ</span><br /><span style="font-family: "courier new" , "courier" , monospace;">CCJ</span><br /><div><br /></div><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-KCb18nyUKSA/WRLBgbrU98I/AAAAAAABz-s/hYpbAMYaGVM1Tjwi8tAHo6OqYeRJMOUAACLcB/s1600/agc013top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="230" src="https://1.bp.blogspot.com/-KCb18nyUKSA/WRLBgbrU98I/AAAAAAABz-s/hYpbAMYaGVM1Tjwi8tAHo6OqYeRJMOUAACLcB/s640/agc013top5.png" width="640" /></a></div>A few hours later AtCoder held its Grand Contest 013 (<a href="http://agc013.contest.atcoder.jp/assignments">problems</a>, <a href="http://agc013.contest.atcoder.jp/standings#page_1">results</a>, top 5 on the left, <a href="https://atcoder.jp/img/agc013/editorial.pdf">analysis</a>). Nobody has managed to get all problems right, and yosupo was the fastest to solve all but one. Well done!<br /><br />I've had the most fun with <a href="http://agc013.contest.atcoder.jp/tasks/agc013_e">problem E</a>. We are given a long (10<sup>9</sup>) segment. Some (at most 10<sup>5</sup>) integer points on the segment are special. We consider all ways to take some set of <i>non</i>-special integer points on the segment. Each such set splits the segment into smaller segments. Let's find the <i>product</i> p of their lengths, and then compute the sum of the squares <i>p</i><sup>2</sup> of those products over all ways. What number are we going to get, modulo 10<sup>9</sup>+7?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-12UJrd8G8z4/WRLBpBL0UGI/AAAAAAABz-w/rBcjxiiVLH4EsfkJF9K8ljYCGeww1MDFgCLcB/s1600/oc1617americatop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="188" src="https://1.bp.blogspot.com/-12UJrd8G8z4/WRLBpBL0UGI/AAAAAAABz-w/rBcjxiiVLH4EsfkJF9K8ljYCGeww1MDFgCLcB/s640/oc1617americatop5.png" width="640" /></a></div>Open Cup 2016-17 Grand Prix of America took place on Sunday (<a href="http://opencup.ru/index.cgi?data=macros/stage&head=index&menu=index&stg=16&region=main&ncup=och&class=och">results</a>, top 5 on the left, <a href="https://naipc17.kattis.com/standings">other results on same problems</a>). Huge congratulations to team Deep Dark Fantasy on solving the hardest problem I and winning the round!<br /><br />We didn't solve the very nice problem K during the round. We are given a number <i>k</i>, a parentheses sequence of length 10<sup>5</sup>, and also for each position you're given the cost of changing the parenthesis in this position to the opposite one. Our goal is to produce a parentheses sequence that is <i>k</i>-unbalanced: it requires changing at least <i>k</i>+1 parentheses to arrive at a balanced parentheses sequence. What is the smallest total cost to achieve that?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/--6IkrJdqtkI/WRLBvDunAaI/AAAAAAABz-0/HymG7x5auIYVNaqx3TeBS_ZflHYP5P-dQCLcB/s1600/rcc2017q2top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="282" src="https://2.bp.blogspot.com/--6IkrJdqtkI/WRLBvDunAaI/AAAAAAABz-0/HymG7x5auIYVNaqx3TeBS_ZflHYP5P-dQCLcB/s640/rcc2017q2top5.png" width="640" /></a></div>Right in the middle of the Open Cup round, Russian Code Cup 2017 held its second Qualification Round (<a href="http://www.russiancodecup.ru/en/championship/round/60/">problems</a>, <a href="http://www.russiancodecup.ru/en/championship/result/60/">results</a>, top 5 on the left, <a href="http://www.russiancodecup.ru/en/press/razbor-zadach-2-go-kvalifikacionnogo-raunda-rcc-2017/">analysis</a>). Congratulations to AndreiNet on beating the others to the first place by just two minutes of penalty time!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-2p2XiVFR0t4/WRLCGn_68yI/AAAAAAABz-4/PNh-ccSW-PgpMJxnLqlriS61e15xloPVQCLcB/s1600/vk2017r2top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="164" src="https://2.bp.blogspot.com/-2p2XiVFR0t4/WRLCGn_68yI/AAAAAAABz-4/PNh-ccSW-PgpMJxnLqlriS61e15xloPVQCLcB/s640/vk2017r2top5.png" width="640" /></a></div>And to wrap up the Sunday, Codeforces hosted VK Cup 2017 Round 2 (<a href="http://codeforces.com/contest/772">problems</a>, <a href="http://codeforces.com/contest/772/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/contest/800/standings">parallel round results</a>, <a href="http://codeforces.com/blog/entry/51598">analysis</a>). The goose team stood out by being the only one to solve all five problems - congratulations! <br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-A7s4EBaE-5Y/WRLDJn0_36I/AAAAAAABz_g/EICUyT7HE9k9ZYBhbY-QdpPdxHejAAwoQCLcB/s1600/IMG_20170415_111857.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/-A7s4EBaE-5Y/WRLDJn0_36I/AAAAAAABz_g/EICUyT7HE9k9ZYBhbY-QdpPdxHejAAwoQCLcB/s640/IMG_20170415_111857.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2017/05/a-double-dirichlet-week.html">my previous summary</a>, I have mentioned an interactive Open Cup problem: two players are playing a game using a grid with <i>n</i>+1 rows and <i>n</i> columns. Each cell of the grid will contain a 0 or a 1, but the contents of the cells are initially undetermined. The first player, let's call him Dirichlet, can ask questions of form "what is the sum modulo 2 in this subset of cells", for any subset of cells. The second player, let's call him Pigeon, answers the questions - each answer is either 0 or 1. Pigeon can answer questions in any way - for example, he does <i>not</i> have to imagine a concrete grid and use it to compute the answers.<br /><br />Dirichlet's goal is to get one of the three outcomes:<br />1) Find a contradiction in Pigeon's answers. More precisely, find a set of questions such that each cell of the grid appears an even number of times in this set, and thus the sum of all answers must be 0 modulo 2, but the sum of Pigeon's answers is 1 modulo 2. One simple case of a contradiction is when he asked about the same set twice and got different answers, but there are much more complicated situations possible.<br />2) Find two different cells in the same column that he can prove to contain 1. In order to prove that a certain cell contains 1, he can use a set of his questions such that the interesting cell appears an odd number of times in them, and all other cells appear an even number of times in them, and the sum of Pigeon's answers for those questions is 1 modulo 2. One simple way to prove is to ask about the set containing just the interesting cell and receive answer 1, but there are also other ways.<br />3) Find a row such that he can prove that <i>all</i> its cells contain 0. Proof for each cell must be done similarly to the previous case.<br /><br />Dirichlet knows that sooner or later one of those three things will happen, since the grid has more rows than columns, and thus it either has a row of 0s or two 1s in the same column. One way to certainly arrive at one of the outcomes is to ask about each cell of the grid separately, using <i>n</i>*(<i>n</i>+1) questions. But Dirichlet wants to win faster: using at most 5*(<i>n</i>+1) questions. Pigeon's goal is to prevent Dirichlet from arriving at one of the three outcomes so fast. You need to implement a program that plays for Dirichlet. <i>n</i> is at most 70.<br /><div><br /></div><div><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-evoQduKcBGI/WRLEbvAbdOI/AAAAAAABz_8/ZgV0pTnrNMQ38Vjw4WZs58PU_rnNGulNwCKgB/s1600/IMG_20170510_094004.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="308" src="https://4.bp.blogspot.com/-evoQduKcBGI/WRLEbvAbdOI/AAAAAAABz_8/ZgV0pTnrNMQ38Vjw4WZs58PU_rnNGulNwCKgB/s320/IMG_20170510_094004.jpg" width="320" /></a></div>Let's ask about the sum modulo 2 in each column. First, consider the case where all answers are 0 (it's not a special case in the solution, but it helps understand the general case). Then we can do the following: let's pick any row, and ask about its cells one by one. In case all of those come back as 0 as well, we have found a row of zeroes so we're done. In case one of those comes back as 1, we know there's another 1 in its column, since the sum of each column is 0 modulo 2, so we can just ask about other cells in that column one by one to find the second 1, and we're done.<br /><br />Now, let's solve the general case: when some columns have an odd number of ones. Let's split all rows into two almost equal halves A and B arbitrarily, and let's ask about sum mod 2 in rows from A in each column with total sum 1 (we also learn the sum in each such column in rows from B, by subtraction). Since the total sum in each "interesting" column is 1, exactly one of its sums in A and in B will be 0, and exactly one will be 1. Now we want to pick either A or B, and continue recursively with this set of rows and only with columns that have sum 1 in it, until at some point we have no columns with sum 1 anymore. Which one to pick between A and B? Well, in order for the recursive calls to converge, we need to maintain the invariant: the number of rows in our set is strictly greater than the number of interesting columns. Initially it's true (<i>n</i>+1><i>n</i>), and since we split the rows into two parts and columns into two parts, it's not hard to see that it will still be true either for A, or for B — and that's what we should pick.<br /><br />What do we have after the dust settles? We have used at most <i>n</i> (initial column queries) + <i>n</i> (column queries on first split) + <i>n</i>/2 (column queries on second split, since we split the rows in two and the number of interesting columns keeps being less than the number of remaining rows) +<i>n</i>/4+... <= 3<i>n</i> queries. And we have the following artifact: we have a row such that for each column there's a segment of cells in that column that has sum 0 modulo 2 and contains the given row (whenever a column becomes "not interesting", we find such a segment for this column).<br /><br />Now we can just do the same thing we did for the case where all columns had sum 0: we iterate over our row, find any 1, and then find the second 1 in its column (it exists, since we have a segment with sum 0 there), spending at most 2<i>n</i> more queries, so overall we fit exactly in 5<i>n</i> as needed.<br /><br />How to come up with this solution? Once again, I think it was about slowly building up enough intuition about the problem. I've kept asking myself questions, and there were two that combined to make a breakthrough. One was: when does any knowledge about a sum of a set of many (more than 1) cells lead to an improvement versus a naive approach of just asking about all cells in some order? And the other was: how can we defeat Pigeon's strategy that always answers 0 until the last moment when that would lead to Dirichlet finding a row of zeros?<br /><br />At this point I realized that knowing that the sum of a column is 0 is actually very valuable, since then it suffices to find just one 1 in this column instead of two. That led to the solution for the case where the answer for all columns is 0, and then the "parallel binary search" for the general case was a somewhat standard follow-up approach.<br /><br />Thanks for reading, and check back soon for the next week's summary!</div></div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/mBkQH3q2AhE" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/05/a-zero-pigeon-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-49145523462507582582017-05-08T19:07:00.001+03:002017-05-08T19:07:23.520+03:00A double Dirichlet 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/-nurusEIGTSI/WRBJloR5VfI/AAAAAAABz9M/BWgaJNEJFosFxBh3zn0MzpsH-tMvabuigCLcB/s1600/gcj2017qualtop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="116" src="https://4.bp.blogspot.com/-nurusEIGTSI/WRBJloR5VfI/AAAAAAABz9M/BWgaJNEJFosFxBh3zn0MzpsH-tMvabuigCLcB/s640/gcj2017qualtop5.png" width="640" /></a></div>Google Code Jam 2017 Qualification Round spanned 27 hours over the April 8-9 weekend (<a href="https://code.google.com/codejam/contest/3264486/dashboard">problems</a>, <a href="https://code.google.com/codejam/contest/3264486/scoreboard#vt=1">results</a>, top 5 on the left, <a href="https://code.google.com/codejam/contest/3264486/dashboard#s=a">analysis</a>). Excited to see so many participants, and hope you enjoyed the problems!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-5QDVYk8QGcc/WPCJZUviOyI/AAAAAAABy5E/eC3ifbCmfqwem5TIVVWD8WfWzg-y3SjPgCLcB/s1600/tco17r1btop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" src="https://2.bp.blogspot.com/-5QDVYk8QGcc/WPCJZUviOyI/AAAAAAABy5E/eC3ifbCmfqwem5TIVVWD8WfWzg-y3SjPgCLcB/s1600/tco17r1btop5.png" /></a></div>TopCoder Open 2017 Round 1B took place later on Saturday (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=16901">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=16901&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left). While the problem were a bit on the easy side, xudyh was still very impressive in solving all three in a little over 9 minutes, and adding 200 challenge points to boot. This result has earned him a spot in <a href="https://community.topcoder.com/stat?&c=highest_totals&dn=1">the official record book</a>, and could've placed him second in <a href="http://web.archive.org/web/20140605103459/https://www.otinn.com/topcoder/al/fastest3.php?type=2">this unofficial one</a> had it still been up. Well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-8NS6kc3Nkp4/WPCJCdRWN_I/AAAAAAABy5A/FDEhLgilygolrZORmqIl3-JhjU-EXQJLwCLcB/s1600/oc1617twocapstop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="126" src="https://1.bp.blogspot.com/-8NS6kc3Nkp4/WPCJCdRWN_I/AAAAAAABy5A/FDEhLgilygolrZORmqIl3-JhjU-EXQJLwCLcB/s640/oc1617twocapstop5.png" width="640" /></a></div>Open Cup 2016-17 Grand Prix of Two Capitals continued the weekly rush of spring Open Cup rounds (<a href="http://opentrains.snarknews.info/~ejudge/res/res10375">results</a>, top 5 on the left). The interactive problem G "Pigeonhole Principle" was very beautiful, so please try to bear with the long statement :)<br /><br />Two players are playing a game using a grid with <i>n</i>+1 rows and <i>n</i> columns. Each cell of the grid will contain a 0 or a 1, but the contents of the cells are initially undetermined. The first player, let's call him Dirichlet, can ask questions of form "what is the sum modulo 2 in this subset of cells", for any subset of cells. The second player, let's call him Pigeon, answers the questions - each answer is either 0 or 1. Pigeon can answer questions in any way - for example, he does <i>not</i> have to imagine a concrete grid and use it to compute the answers.<br /><br />Dirichlet's goal is to get one of the three outcomes:<br />1) Find a contradiction in Pigeon's answers. More precisely, find a set of questions such that each cell of the grid appears an even number of times in this set, and thus the sum of all answers must be 0 modulo 2, but the sum of Pigeon's answers is 1 modulo 2. One simple case of a contradiction is when he asked about the same set twice and got different answers, but there are much more complicated situations possible.<br />2) Find two different cells in the same column that he can prove to contain 1. In order to prove that a certain cell contains 1, he can use a set of his questions such that the interesting cell appears an odd number of times in them, and all other cells appear an even number of times in them, and the sum of Pigeon's answers for those questions is 1 modulo 2. One simple way to prove is to ask about the set containing just the interesting cell and receive answer 1, but there are also other ways.<br />3) Find a row such that he can prove that <i>all</i> its cells contain 0. Proof for each cell must be done similarly to the previous case.<br /><br />Dirichlet knows that sooner or later one of those three things will happen, since the grid has more rows than columns, and thus it either has a row of 0s or two 1s in the same column. One way to certainly arrive at one of the outcomes is to ask about each cell of the grid separately, using <i>n</i>*(<i>n</i>+1) questions. But Dirichlet wants to win faster: using at most 5*(<i>n</i>+1) questions. Pigeon's goal is to prevent Dirichlet from arriving at one of the three outcomes so fast. You need to implement a program that plays for Dirichlet. <i>n</i> is at most 70.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-VRUXehmBCA0/WRCWXp_fzaI/AAAAAAABz-A/gGC25WI1Xokwb8PRhpWkEa5g3ZvLWkh6ACLcB/s1600/IMG_20170413_151801.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/-VRUXehmBCA0/WRCWXp_fzaI/AAAAAAABz-A/gGC25WI1Xokwb8PRhpWkEa5g3ZvLWkh6ACLcB/s640/IMG_20170413_151801.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2017/04/a-dominator-week.html">the previous summary</a>, I have mentioned a cute Open Cup problem: 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 1<=<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 />First of all, consider a sequence of <i>n</i> equal numbers shows that we mush include all <i>k</i> (<i>a</i>,<i>a</i>) pairs in our answer. Moreover, when <i>n</i>><i>k</i>, we don't need any other pairs thanks to our old friend Dirichlet. But what to do when <i>n</i><=<i>k</i>? Here one needs to build some intuition first in order to see the right approach.<br /><br />Let's consider the case <i>n</i>=<i>k</i>. After taking the (<i>a</i>,<i>a</i>) pairs we need to additionally cover all permutations of <i>k</i> numbers. Let's consider one of them: 1,2,...,<i>k</i>. Without loss of generality, we can assume that the pair (1,2) is one of its subsequences present in the answer, so we have at <i>k</i>+1 pairs in our answer now. Is that enough? No, since there exist permutations that do not contain (1,2) as a subsequence. Moreover, there exists a permutation that does not have <i>any</i> common subsequence with our first permutation: <i>k</i>,<i>k</i>-1,...,1. This shows that we need at least <i>k</i>+2 pairs. Which pair should we cover the decreasing permutation with? A natural choice is to use the (2,1) pair. In fact, it's not hard to see that any permutation of <i>k</i> numbers contains either the (1,2) pair or the (2,1) pair as a subsequence, so our <i>k</i>+2 pairs cover all sequences.<br /><br />Now let's turn to the <i>n</i>=<i>k</i>-1 case. Here the reasoning becomes less formal and more intuitive. Our solution for <i>n</i>=<i>k</i> does not cover sequences that do not contain 1 or 2, for example 2,3,...,<i>k</i>. Let's say this sequence will be covered by (3,4) pair (a pair that contains 2, like (2,3) is less useful since we can replace 2 with 1 and get another uncovered sequence). Again, its reverse will need to be covered, so let's take (4,3) pair as well. Now we have <i>k</i>+4 pairs: (1,1), (2,2), ..., (<i>k</i>,<i>k</i>), (1,2), (2,1), (3,4), (4,3). Dirichlet can easily notice that these <i>k</i>+4 pairs are enough to cover all sequences of length <i>k</i>-1, since any such sequence either contains a repeat, or is missing just one number, and thus either contains both 1 and 2, or contains both 3 and 4.<br /><br />The cases above have hopefully helped build some intuitive understanding of the problem that allows to generalize the construction to any <i>n</i>: we will split all <i>k</i> numbers into <i>n</i>-1 groups of equal or almost equal size, and will include all pairs of elements from one group into our answer. By the pigeonhole principle, each sequence of length <i>n</i> will contain two elements from the same group, and thus will be covered. As an example, when <i>n</i>=3 and <i>k</i>=5, we will output pairs (1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3), (4,5), and (5,4).<br /><br />A formal proof that this answer is optimal is a bit tedious, so I will just refer you to <a href="https://en.wikipedia.org/wiki/Tur%C3%A1n%27s_theorem">the Wikipedia article</a>. During the actual contest, the intuition built on simple cases helped this solution to "click" in my head, and thus I submitted it without having a formal proof.<br /><br />Thanks for reading, and check back soon!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/B9xaH0sO_b8" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/05/a-double-dirichlet-week.htmltag: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.html