tag:blogger.com,1999:blog-19533250797934499712017-06-22T05:24:36.454+03:00Algorithms Weekly by Petr MitrichevPetr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.comBlogger306125PetrMitrichevhttps://feedburner.google.comtag: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.htmltag:blogger.com,1999:blog-1953325079793449971.post-22030669504971962192017-04-01T09:10:00.000+03:002017-04-01T09:10:09.268+03:00A week with two rows<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-y5NcQKyQAEY/WN88aATzkxI/AAAAAAAByiU/yva3DSA061I3mrASufpCB3ajuJCfO-KugCLcB/s1600/vk2017r1top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="166" src="https://2.bp.blogspot.com/-y5NcQKyQAEY/WN88aATzkxI/AAAAAAAByiU/yva3DSA061I3mrASufpCB3ajuJCfO-KugCLcB/s640/vk2017r1top5.png" width="640" /></a></div>On the Mar 13 - Mar 19 week, VK Cup 2017 started with its Round 1 (<a href="http://codeforces.com/contest/771">problems</a>, <a href="http://codeforces.com/contest/771/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/contest/790/standings">parallel Codeforces round results</a>, <a href="https://youtu.be/9dTLvhv5U44">my screencast of the Codeforces round with commentary</a>, <a href="http://codeforces.com/blog/entry/51068">analysis</a>). Congratulations to Zlobober and zemen on the win!<br /><br />I've made a second attempt at explaining myself to the camera during the competition, and this time it it went even worse. I've managed to implement an incorrect solution for C before realizing it and rewriting from scratch, and if that wasn't bad enough followed up with doing the same - implementing an incorrect solution that needs to be dropped on the floor - <i>twice</i> for problem D. Maybe talking <i>is</i> indeed incompatible with critical thinking?..<br /><br />Here is <a href="http://codeforces.com/contest/790/problem/D">problem D</a> that has stopped me in my tracks. You are given a grid with two rows and <i>n</i> columns, each cell containing a (not necessarily positive) integer. Your goal is to find as many non-intersecting rectangles on this grid as possible, such that each rectangle has a sum of 0. <i>n</i> is up to 300000.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-0uQmmpGeEA4/WN9CwgHYx9I/AAAAAAAByig/x2S9b5HQgcEfCMr92k4unty8_yWRYhaywCLcB/s1600/IMG_20170226_175414.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="480" src="https://2.bp.blogspot.com/-0uQmmpGeEA4/WN9CwgHYx9I/AAAAAAAByig/x2S9b5HQgcEfCMr92k4unty8_yWRYhaywCLcB/s640/IMG_20170226_175414.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2017/03/a-speaking-week.html">my previous summary</a>, I have mentioned a cute AtCoder problem. You are given a huge number n with at most 500000 (decimal) digits, and need to find the smallest number <i>k</i> such that <i>n</i> can be represented as a sum of <i>k</i> numbers with non-decreasing decimal representation (for example, 1157888).<br /><div><br /></div><div>The approach I talk about in my screencast is a bit vague, and I like the approach from the editorial more. First, we notice that numbers with non-decreasing decimal representation are exactly those numbers that can be represented as a sum of 9 numbers which consist only of ones (like 1 or 1111; we will also count 0 as such a number with zero ones) - the main Young diagram trick strikes back :) So our goal is to represent <i>n</i> as a sum of 9<i>k</i> such numbers.</div><div><br /></div><div>Each such number is equal to (10<sup><i>m</i></sup>-1)/9 for some <i>m</i>, so we actually need to represent 9<i>n</i>+9<i>k</i> as a sum of exactly 9<i>k</i> numbers of form 10<sup><i>m</i></sup>. The smallest amount of such numbers needed to achieve 9<i>n</i>+9<i>k</i> is naturally given by the sum of digits in the decimal representation of 9<i>n</i>+9<i>k</i>, and is divisible by 9. We can then repeatedly replace a power of 10 with ten smaller powers to get any bigger amount divisible by 9, up to 9<i>n</i>+9<i>k</i> (when the sum is all ones). We need to achieve 9<i>k</i> which is also divisible by 9, so we just need to check if the sum of digits in the decimal representation of 9<i>n</i>+9<i>k</i> is less than or equal to 9<i>k</i>.<br /><br />Now that we know how to check any given <i>k</i>, we can use binary search to find the minimum possible value of <i>k</i>. VoilÃ !<br /><br />Thanks for reading, and check back soon for the last week's summary.</div></div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/ZC_FDB_CqzI" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/04/a-week-with-two-rows.htmltag:blogger.com,1999:blog-1953325079793449971.post-87954269586861801052017-03-27T21:47:00.000+03:002017-03-28T16:33:17.687+03:00A speaking week<div dir="ltr" style="text-align: left;" trbidi="on">Before I switch to the Mar 6 - Mar 12 week, let me correct a mistake in my previous summary: there was in fact a Codeforces round on Sunday, March 5 - but it somehow disappeared from <a href="http://clist.by/">clist.by</a>, and my memory turned out to be too short :)<br /><div><br /></div><div><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-TKUJjZbEPt0/WNlb77LQAUI/AAAAAAAByfA/THu2nJ-aZ_Md-3_i61aiJNuaNTffossFQCLcB/s1600/cf403top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="156" src="https://4.bp.blogspot.com/-TKUJjZbEPt0/WNlb77LQAUI/AAAAAAAByfA/THu2nJ-aZ_Md-3_i61aiJNuaNTffossFQCLcB/s640/cf403top5.png" width="640" /></a></div>Codeforces Round 403 was the forgotten round (<a href="http://codeforces.com/contest/781">problems</a>, <a href="http://codeforces.com/contest/781/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/50854">analysis</a>). Right after the round, I was sure that I needed a lot more debugging to get the last problem accepted - but it turned out that I was super close: the only issue was the often forgotten case of <i>a</i>=0 when solving a quadratic inequality <i>ax</i><sup>2</sup>+<i>bx</i>+<i>c</i><=0. In absence of people solving the last problem during the round it was the speed on the first five that mattered, and V--o_o--V was the quickest - congratulations!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-CXv8E58c42E/WNlcF0XUXMI/AAAAAAAByfE/0nMjYRvyueUFS3IKEM35bY9FhBb5f9T-gCLcB/s1600/srm710top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="82" src="https://2.bp.blogspot.com/-CXv8E58c42E/WNlcF0XUXMI/AAAAAAAByfE/0nMjYRvyueUFS3IKEM35bY9FhBb5f9T-gCLcB/s640/srm710top5.png" width="640" /></a></div>Now we can go back to the subject week. Early on Friday, TopCoder SRM 710 took place (<a href="https://community.topcoder.com/stat?c=round_overview&rd=16879">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=16879&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/50572?#comment-348227">analysis</a>). Just like the previous round, the hardest problem did not budge, and the round was decided on the first two. Congratulations to al13n on the victory!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-IICuwk6P6GM/WNlcs3YBrbI/AAAAAAAByfM/ZO5Whsg08Ek5yU5usjajMvqtMg7l_N1AwCLcB/s1600/agc011top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="242" src="https://2.bp.blogspot.com/-IICuwk6P6GM/WNlcs3YBrbI/AAAAAAAByfM/ZO5Whsg08Ek5yU5usjajMvqtMg7l_N1AwCLcB/s640/agc011top5.png" width="640" /></a></div>And finally, AtCoder held its Grand Contest 011 on Sunday (<a href="http://agc011.contest.atcoder.jp/assignments">problems</a>, <a href="http://agc011.contest.atcoder.jp/standings#page_1">results</a>, top 5 on the left, <a href="https://youtu.be/rsm4XDlcbRE">my screencast with commentary</a>, <a href="https://atcoder.jp/img/agc011/editorial.pdf">analysis</a>). Egor has won the contest thanks to a superior strategy, as he went for the hardest problem in the last minutes of the contest instead of the second hardest. Well done!<br /><br />I have attempted something new for this round: in addition to the screen content, I've included a camera feed in the screencast, and tried to explain aloud what I'm thinking and doing. I had two big hopes when I decided to do that: that I would actually be able to come up with more polished solutions that take less time to code if I explain them aloud first, and that my mumbling will be interesting to the viewers. The results of the round show that the first hope was likely unfounded, so now I'm really curious about the second one :)<br /><br />As far as problems go, let me highlight <a href="http://agc011.contest.atcoder.jp/tasks/agc011_e">problem E</a>. You are given a huge number <i>n</i> with at most 500000 (decimal) digits, and need to find the smallest number <i>k</i> such that <i>n</i> can be represented as a sum of <i>k</i> numbers with non-decreasing decimal representation (for example, 1157888).<br /><br />Thanks for reading, and check back soon for the next week's contests!</div></div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/Q08biq7Lr04" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/03/a-speaking-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-1374546190210552672017-03-27T15:35:00.001+03:002017-03-27T15:35:32.733+03:00An all-black week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-DSAt1aQAv0c/WNkGbWMF0wI/AAAAAAAByeI/5QVVkJeVLbkq7-IFwgcRhTKNg_GuXNtBACKgB/s1600/IMG_20170218_152755.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="480" src="https://1.bp.blogspot.com/-DSAt1aQAv0c/WNkGbWMF0wI/AAAAAAAByeI/5QVVkJeVLbkq7-IFwgcRhTKNg_GuXNtBACKgB/s640/IMG_20170218_152755.jpg" width="640" /></a></div>In stark contrast to the previous week, the Feb 27 - Mar 5 week had no contests that I'd like to mention. However, we can of course still discuss the problems I mentioned in <a href="http://petr-mitrichev.blogspot.com/2017/02/a-7x-week.html">my previous summary</a>.<br /><br /><a href="http://mujin-pc-2017.contest.atcoder.jp/tasks/mujin_pc_2017_b">The AtCoder one</a> was concerned with a square <i>n</i> times <i>n</i> matrix with each cell either black or white. In one step, you could take an arbitrary row of the matrix, and replace an arbitrary column of the matrix with the values from the chosen row. Your goal is to make all cells black. What is the minimum number of steps required to achieve that?<br /><br />First, we can notice that if a certain column of the matrix is already all black, there's never a need to replace it, since it satisfies the final condition, and it's also the most optimal for other operations as the corresponding cell in all rows will be black.<br /><br />Second, any other column can become all black only if we have a row that is all black. Moreover, as soon as we have a row that is all black, we should immediately start replicating it to all non-all-black columns (note that the number of non-all-black columns stays constant up to this point). So the problem has been reduced to: what is the minimum number of steps required to make one row all-black?<br /><br />Now, each operation changes only one cell in each row. So if a row has <i>k</i> white cells, we will require at least <i>k</i> operations to make it all-black. Moreover, if each column has at least one black cell, then we require <i>exactly</i> <i>k</i> operations to make it all-black (since for each cell in this row we can replicate the row that has a black cell in the corresponding column). We can iterate over all rows and pick the one where this number is minimized. So the only unsolved case is when there's one or more all-white columns.<br /><br />For each all-white column, we need at least one operation to put at least one black cell in it. If the column corresponding to the row we're making all-black has at least one black cell, then we have a row which serves two purposes: when replicating it to an all-white column, we both make it not-all-white, and also put a black cell in the row we're making all-black, so in that case no extra move is needed and we can still make the row all-black in exactly <i>k</i> operations.<br /><br />Now, the very specific remaining case is: we want to make a certain row all-black, and the corresponding column is initially all-white. Then if we look at the first move that replaces this column, it's clear that the cell on the intersection of the all-black-to-be row and this column will stay white, meaning that we waste 1 move and require at least <i>k</i>+1 operation to make the row all-black. But it's easy to waste exactly one move: we just replicate any non-all-white row to the problematic column as the first move. Of course, if the board is initially all-white then there's no solution.<br /><br />That completes the solution for this problem. As you can see, each particular step is relatively straightforward and not very hard to come up with. However, one has to stitch together quite a few of those, and that's where the difficulty - and beauty - of this problem lies.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-QdYpnQTOnAo/WNkGrbTE1aI/AAAAAAAByeM/ULVEs-0cr7Q-Ajbt3o4CDZvJsOr_iH5PACKgB/s1600/IMG_20170225_104622.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" height="480" src="https://2.bp.blogspot.com/-QdYpnQTOnAo/WNkGrbTE1aI/AAAAAAAByeM/ULVEs-0cr7Q-Ajbt3o4CDZvJsOr_iH5PACKgB/s640/IMG_20170225_104622.jpg" width="640" /></a></div>The Open Cup problem was concerned with a permutation of size <i>n</i>. For each number, we can compute its radius: the largest number <i>r</i> such that <i>r</i> numbers to the left of our number, and <i>r</i> numbers to the right of our number, are all smaller than that number. For example, for the permutation "1 3 2 6 4 5" the radii are "0 1 0 2 0 0". Given the sequence of radii, how many different permutations correspond to it?<br /><br />The solution depends on one main insight: let's look for <i>n</i> (the largest number) in the permutation. Since it is the largest number, it "stops" all other radii, and thus the problem decomposes into two independent problems to the left and to the right of this number. Just this idea leads to a O(<i>n</i><sup>3</sup>) dynamic programming solution which solves the problem for each segment and tries all positions of the largest number.<br /><br />Since this was a tiny bit too slow, one needed to optimize this approach. Since the radius of the largest number always reaches either to the left or to the right boundary, and no other radius should cover the largest number, in each segment there are at most two candidates for the largest number: the rightmost position with radius reaching the left boundary, and the leftmost position with radius reaching the right boundary. Since now we have just 2 candidates to check for each segment instead of <i>n</i>, the solution works in O(<i>n</i><sup>2</sup>) which is fast enough.<br /><br />Thanks for reading, and check back soon for the next week's summary!<br /><br /></div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/N8lRRLKLIAc" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/03/an-all-black-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-44171573093718956662017-02-26T23:37:00.001+03:002017-02-26T23:37:45.999+03:00A 7x week<div dir="ltr" style="text-align: left;" trbidi="on">This week was extremely packed with competitions - I think this might be the new record for the number of scoreboards in one summary. Consequently, there were a couple nice problems, so if you haven't solved all of this week's competitions (:P), read on!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-t_dI4ic1zaQ/WLMqAZui_qI/AAAAAAABwgM/B9PN6KCdjfULMQzWZTU7FQHBu6ULC8uNQCLcB/s1600/cf399top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="156" src="https://4.bp.blogspot.com/-t_dI4ic1zaQ/WLMqAZui_qI/AAAAAAABwgM/B9PN6KCdjfULMQzWZTU7FQHBu6ULC8uNQCLcB/s640/cf399top5.png" width="640" /></a></div>First off, Codeforces held its Round 399 on Monday (<a href="http://codeforces.com/contest/768">problems</a>, <a href="http://codeforces.com/contest/768/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/50550">analysis</a>). y0105w49 and W4yneb0t had a fiery challenge competition and have managed to overtake the only contestant who solved all problems, V--o_o--V. Congratulations to all three!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-OsjomGxa7PE/WLMpCG49p0I/AAAAAAABwgI/sTYl5yXwKA4L1afS9zOsWj7r7-Dy53OEwCLcB/s1600/srm709top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" src="https://2.bp.blogspot.com/-OsjomGxa7PE/WLMpCG49p0I/AAAAAAABwgI/sTYl5yXwKA4L1afS9zOsWj7r7-Dy53OEwCLcB/s1600/srm709top5.png" /></a></div>TopCoder SRM 709 on Tuesday offered the deceptively little 800 points for the hard problem (<a href="https://community.topcoder.com/stat?c=round_overview&rd=16853">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=16853&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://youtu.be/eHGm-UL1ctQ">my screencast</a>). Just 3 competitors have managed to grab (some part of) those points, and thus -XraY-'s dominating victory is even more impressive!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-iJlXGiYI8lc/WLMqbn-ze7I/AAAAAAABwgQ/-3_zou4d7uc8nOKkqRoi6SCc_jpZXPj7ACLcB/s1600/cf400top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="158" src="https://3.bp.blogspot.com/-iJlXGiYI8lc/WLMqbn-ze7I/AAAAAAABwgQ/-3_zou4d7uc8nOKkqRoi6SCc_jpZXPj7ACLcB/s640/cf400top5.png" width="640" /></a></div>Codeforces Round 400 on Thursday continued the non-stop week (<a href="http://codeforces.com/contest/776">problems</a>, <a href="http://codeforces.com/contest/776/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/50622">analysis</a>). The challenges were not in abundance this time, and thus the coding speed and accuracy came to the forefront. ainta was a tiny bit faster this time, and made fewer submissions that didn't pass pretests - congratulations on the win!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-aYhRFqXz4Yo/WLMr5rEOSsI/AAAAAAABwgY/wAwi7f8wqmEATvdmIMh3rVPgQmkirU4qgCLcB/s1600/mujin2017top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="308" src="https://1.bp.blogspot.com/-aYhRFqXz4Yo/WLMr5rEOSsI/AAAAAAABwgY/wAwi7f8wqmEATvdmIMh3rVPgQmkirU4qgCLcB/s640/mujin2017top5.png" width="640" /></a></div>On Saturday, Mujin Programming Challenge 2017 on AtCoder offered monetary prizes for the top performers (<a href="http://mujin-pc-2017.contest.atcoder.jp/assignments">problems</a>, <a href="http://mujin-pc-2017.contest.atcoder.jp/standings#page_1">results</a>, top 5 on the left, <a href="https://atcoder.jp/img/mujin-pc-2017/editorial.pdf">analysis</a>, <a href="https://youtu.be/zUwfNf0cQFw">my screencast</a>). Tourist has claimed the first prize by being way ahead of everybody on the hardest problem - well done!<br /><br />I think <a href="http://mujin-pc-2017.contest.atcoder.jp/tasks/mujin_pc_2017_b">problem B</a> in this round provided a nice way to practice one's skill for dissecting a problem step by step until it becomes trivial. You were given a square <i>n</i> times <i>n</i> matrix with each cell either black or white. In one step, you could take an arbitrary row of the matrix, and replace an arbitrary column of the matrix with the values from the chosen row. Your goal is to make all cells black. What is the minimum number of steps required to achieve that?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-RiM2e14ejS4/WLMtsSY0StI/AAAAAAABwgo/yL7Sr_jglQgqfbnD8UWdZut2weGeKvZTACLcB/s1600/codechefltime45top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="176" src="https://4.bp.blogspot.com/-RiM2e14ejS4/WLMtsSY0StI/AAAAAAABwgo/yL7Sr_jglQgqfbnD8UWdZut2weGeKvZTACLcB/s640/codechefltime45top5.png" width="640" /></a></div>Right after the AtCoder round ended, Codechef held its February Lunchtime 2017 competition (<a href="https://www.codechef.com/LTIME45">problems</a>, <a href="https://www.codechef.com/rankings/LTIME45">results</a>, top 5 on the left, <a href="https://youtu.be/XWAxqcs7_5U">my screencast</a>). The problems were a bit easier than in other competitions mentioned in this summary, but still provided a nice challenge!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-nVM5uNyG1nc/WLMs-snV2YI/AAAAAAABwgg/hsayGEo9fng3DsE7pYVpxpEBsmmueIncwCLcB/s1600/cf402top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="184" src="https://2.bp.blogspot.com/-nVM5uNyG1nc/WLMs-snV2YI/AAAAAAABwgg/hsayGEo9fng3DsE7pYVpxpEBsmmueIncwCLcB/s640/cf402top5.png" width="640" /></a></div>Codeforces Round 402 started at the same time with the Open Cup round (<a href="http://codeforces.com/contest/778">problems</a>, <a href="http://codeforces.com/contest/778/standings">results</a>, top 6 on the left). As a result, many active ACM ICPC participants have skipped the Codeforces Round, but the competition remained fierce. Congratulations to bmerry on finding a unique set of problems to solve and winning thanks to that strategy!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-Bh3dQkS1x5I/WLMta7h3qdI/AAAAAAABwgk/8abMc5wFDpgpwspuSWfNQP8lwVkzIyWhQCLcB/s1600/oc2017wroclawtop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="170" src="https://4.bp.blogspot.com/-Bh3dQkS1x5I/WLMta7h3qdI/AAAAAAABwgk/8abMc5wFDpgpwspuSWfNQP8lwVkzIyWhQCLcB/s640/oc2017wroclawtop5.png" width="640" /></a></div>Finally, the aforementioned Open Cup 2016-17 Grand Prix of Wroclaw also took place today (<a href="http://opentrains.snarknews.info/~ejudge/res/res10372">results</a>, top 5 on the left). Problem F was right in the middle by difficulty level, and required a nice observation to come up with a O(<i>n</i><sup>2</sup>) solution.<br /><br />Consider a permutation of size <i>n</i>. For each number, we can compute its <i>radius</i>: the largest number <i>r</i> such that <i>r</i> numbers to the left of our number, and <i>r</i> numbers to the right of our number, are all smaller than that number. For example, for the permutation "1 3 2 6 4 5" the radii are "0 1 0 2 0 0". Given the sequence of radii, how many different permutations correspond to it?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-JQq1-dBsbkU/WLMx5aNRoVI/AAAAAAABwg4/OWrY-7Q-fXERRIJUkLT4MDzisb_EpSC_wCLcB/s1600/IMG_20170218_124053.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="480" src="https://2.bp.blogspot.com/-JQq1-dBsbkU/WLMx5aNRoVI/AAAAAAABwg4/OWrY-7Q-fXERRIJUkLT4MDzisb_EpSC_wCLcB/s640/IMG_20170218_124053.jpg" width="640" /></a></div>Thanks for reading, and check back next week! (which promises to be much calmer)</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/VS3J0uP6-Qg" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/02/a-7x-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-61208127337315431702017-02-20T00:58:00.001+03:002017-02-20T00:58:24.190+03:00A casino week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-kaFrcwIlcmg/WKoOLPkEVtI/AAAAAAABwL0/qaydHhvX4-AvPxxuRYNfgAh4ws-8S9IgwCLcB/s1600/cf397top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="156" src="https://1.bp.blogspot.com/-kaFrcwIlcmg/WKoOLPkEVtI/AAAAAAABwL0/qaydHhvX4-AvPxxuRYNfgAh4ws-8S9IgwCLcB/s640/cf397top5.png" width="640" /></a></div>Codeforces Round 397 was the highlight of this week (<a href="http://codeforces.com/contest/765">problems</a>, <a href="http://codeforces.com/contest/765/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/50456">analysis</a>). Merkurev has created a comfortable margin for himself thanks to fast solutions of the first five problems and two successful challenges - congratulations on the victory!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-CxkSLdRtk5o/WKoUIwmoTrI/AAAAAAABwME/x_jFDtH5Nv0BA2I8kDkO1DhgKYInNRc4ACLcB/s1600/IMG_20170129_125629.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="480" src="https://2.bp.blogspot.com/-CxkSLdRtk5o/WKoUIwmoTrI/AAAAAAABwME/x_jFDtH5Nv0BA2I8kDkO1DhgKYInNRc4ACLcB/s640/IMG_20170129_125629.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2017/02/a-spanning-week.html">my previous summary</a>, I have mentioned two interesting problems. The first was a TopCoder problem about distinguishing optimal strategy and random play: you are playing a betting game in a casino. You start with <i>a</i> dollars, and your goal is to reach <i>b</i> dollars. You can play at most <i>k</i> rounds. In each round, you bet some integer (possibly zero) amount of dollars not exceeding the amount you have now, then with probability 50% you lose that amount, and with probability 50% you gain that amount. As soon as you reach your goal (have at least <i>b</i> dollars), you leave the casino.<br /><br />There are of course many strategies to place your bets. In this problem we're concerned with two of them: one is an <i>optimal</i> strategy, where you place each bet to maximize the probability that you will reach your goal by the end of the <i>k</i>-th round or earlier. Note that there might still be several choices for each bet in an optimal strategy that all lead to the same probability of achieving the goal. One of the optimal strategies can be somewhat easily googled. The other strategy we're concerned with is the <i>fully random</i> one: for each bet, we choose the number of dollars between 0 and our amount of money uniformly at random.<br /><br />Now, you've chosen to use the fully random strategy, and played it to completion (end of <i>k</i>-th round, or getting at least <i>b</i> dollars). An outside observer (who knows the values of <i>a</i>, <i>b</i> and <i>k</i>), however, was assuming that you're actually following an optimal strategy - and did not find evidence otherwise observing your fully random play (in other words, each time you randomly chose a bet that leads to the maximum probability of achieving the goal). What is the probability of such situation?<br /><br /><i>a</i> and <i>b</i> are up to 100000, and <i>k</i> is at most 5.<br /><br />A quadratic dynamic programming solution is straightforward: given the amount of money we have and the number of rounds remaining, we will compute what's the probability of winning, and what's the probability that a random play will look optimal. In order to compute those probabilities, we will iterate over all possible bets and see what state to we get into if we win and if we lose.<br /><br />The key insight required to speed it up is: the probability of winning is always a rational number with denominator 2<sup><i>k</i> </sup>(because our play consists of <i>k</i> events each with 50-50 chances). Because of this, it has at most 2<sup><i>k</i></sup><complete id="goog_1567086616">+1 </complete>possible values. On the other hand, it's not hard to see that this probability will not decrease if we increase the amount of money we have. That means that for a fixed <i>k</i>, the probabilities of winning for each <i>a</i> form a set of at most 2<sup><i>k</i></sup><complete id="goog_1567086616">+1 </complete>segments, each with the same value. And that, in turn, allows to speed up the dynamic programming: instead of considering possible bets one by one, we will consider them in groups: a group is determined by which segments on level <i>k</i>-1 we land on if we win, and if we lose. There will be at most 2*(2<sup><i>k-1</i></sup><complete id="goog_1567086616">+1) such groups, and thus the total running time will be O(<i>b</i>*<i>k</i>*</complete>2<sup><i>k</i></sup>) which is fast enough.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-k7-kf3igAtY/WKoUkCURmPI/AAAAAAABwMI/falGrYBrDu0KIpAJjiQhHvddgJShyIkvQCLcB/s1600/IMG_20170129_142440.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="480" src="https://4.bp.blogspot.com/-k7-kf3igAtY/WKoUkCURmPI/AAAAAAABwMI/falGrYBrDu0KIpAJjiQhHvddgJShyIkvQCLcB/s640/IMG_20170129_142440.jpg" width="640" /></a></div>The second problem from the previous summary was a purely mathematical puzzle: you are given an undirected graph with at most 200000 vertices and at most 200000 edges. Consider its <i>spanning</i> subsets of edges: such subsets of its edges that connect all its vertices. Is the number of such subsets odd or even?<br /><br />The solution here is completely magical. It turns out that the number of spanning subsets of edges is odd <i>if and only if</i> the graph is bipartite. A couple of different proofs can be found in <a href="http://codeforces.com/blog/entry/50380?#comment-342897">this Codeforces thread</a>, but I think they don't fully answer the natural question: what is the intuition behind this fact? How to come up with it without knowing it in advance? I would be grateful if the readers could shed some light here.<br /><br />Thanks for reading, and check back next week!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/yvj-BwPkPdk" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/02/a-casino-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-48029002382658077942017-02-19T22:41:00.002+03:002017-02-19T22:41:27.721+03:00A spanning week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-TKqnPnEqr9w/WKnmBfhsdFI/AAAAAAABwKY/Ju791c5chDAXWjuTfWbApFB9fk_mxH04wCLcB/s1600/srm708top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" src="https://4.bp.blogspot.com/-TKqnPnEqr9w/WKnmBfhsdFI/AAAAAAABwKY/Ju791c5chDAXWjuTfWbApFB9fk_mxH04wCLcB/s1600/srm708top5.png" /></a></div>TopCoder SRM 708 took place in the middle of last week (<a href="https://community.topcoder.com/stat?c=round_overview&rd=16852">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=16852&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://youtu.be/pQv2rYX2dsk">my screencast</a>, <a href="http://codeforces.com/blog/entry/49910?#comment-342631">analysis</a>). rng_58 returned to winning ways in his second SRM after the November TCO victory - congratulations!<br /><br />The victory is mostly thanks to the high score on <a href="https://community.topcoder.com/stat?c=problem_statement&pm=14525&rd=16852">the hard problem</a> (moreover, as you can see from the top 5 this problem decided all five places, not just the winner). It went like this: you are playing a betting game in a casino. You start with <i>a</i> dollars, and your goal is to reach <i>b</i> dollars. You can play at most <i>k</i> rounds. In each round, you bet some integer (possibly zero) amount of dollars not exceeding the amount you have now, then with probability 50% you lose that amount, and with probability 50% you gain that amount. As soon as you reach your goal (have at least <i>b</i> dollars), you leave the casino.<br /><br />There are of course many strategies to place your bets. In this problem we're concerned with two of them: one is an <i>optimal</i> strategy, where you place each bet to maximize the probability that you will reach your goal by the end of the <i>k</i>-th round or earlier. Note that there might still be several choices for each bet in an optimal strategy that all lead to the same probability of achieving the goal. One of the optimal strategies can be somewhat easily googled. The other strategy we're concerned with is the <i>fully random</i> one: for each bet, we choose the number of dollars between 0 and our amount of money uniformly at random.<br /><br />Now, you've chosen to use the fully random strategy, and played it to completion (end of <i>k</i>-th round, or getting at least <i>b</i> dollars). An outside observer (who knows the values of <i>a</i>, <i>b</i> and <i>k</i>), however, was assuming that you're actually following an optimal strategy - and did not find evidence otherwise observing your fully random play (in other words, each time you randomly chose a bet that leads to the maximum probability of achieving the goal). What is the probability of such situation?<br /><br /><i>a</i> and <i>b</i> are up to 100000, and <i>k</i> is at most 5. Can you solve it as fast as Makoto?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-NZMrM96LqwY/WKnm4IUtsCI/AAAAAAABwKg/wbn92jcjt1USQee3gJoStch92f11efTxQCLcB/s1600/oc2017chinatop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="175" src="https://3.bp.blogspot.com/-NZMrM96LqwY/WKnm4IUtsCI/AAAAAAABwKg/wbn92jcjt1USQee3gJoStch92f11efTxQCLcB/s640/oc2017chinatop5.png" width="640" /></a></div>Open Cup 2016-17 Grand Prix of China on the weekend provided another set of tough problems (<a href="http://opentrains.snarknews.info/~ejudge/res/res10371">results</a>, top 5 on the left). The reigning ICPC world champions from SPb SU continued their winning streak - well done!<br /><br />Problem B in this round was a cute purely mathematical puzzle. You are given an undirected graph with at most 200000 vertices and at most 200000 edges. Consider its <i>spanning</i> subsets of edges: such subsets of its edges that connect all its vertices. Is the number of such subsets odd or even?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-pFdpFjXJCbQ/WKn0tEnzdbI/AAAAAAABwLQ/0OTm_HdcvLgXSqKjNed7cwUu7zcwkvVhQCLcB/s1600/IMG_20170122_154110.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="480" src="https://3.bp.blogspot.com/-pFdpFjXJCbQ/WKn0tEnzdbI/AAAAAAABwLQ/0OTm_HdcvLgXSqKjNed7cwUu7zcwkvVhQCLcB/s640/IMG_20170122_154110.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2017/02/a-gomel-week.html">my last summary</a>, I have mentioned two nice problems. The first one came from AtCoder: two players are playing a game on a tree where each node has some amount of stones. There's also a chip in one of the vertices of the tree. They make moves in turn, and each move consists of removing one stone from the vertex where the chip is, and then moving the chip to an adjacent vertex. When there's no more stones in the vertex where the chip is, the player that needs to make the next move is unable to do so, and thus loses the game. How to determine who will win with optimal play?<br /><br />The key idea needed to solve this problem is: if the vertex <i>a</i> the chip is currently on has less or the same amount of stones as its adjacent vertex <i>b</i>, then the second player can force the game to never go beyond <i>b</i> in the tree. If the first player moves the chip to <i>b</i>, the second player can return it to <i>a</i>, and after repeating this a few times <i>a</i> will run out of stones earlier than <i>b</i>, so if the first player doesn't want to lose, he will have to pick a vertex other than <i>b</i> to move to.<br /><br />Because of this, we can see that the outcome of the game does not change if we only ever allow to move from a vertex to a vertex with strictly fewer stones. The latter game is acyclic, and thus it's very easy to determine the winner in just a few lines of code.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-RkY8IOuMILE/WKn0Cez4yII/AAAAAAABwLE/J8fAkgKT_44K-u8hpWRJ0LYgBkvZmAmpQCKgB/s1600/IMG_20170219_203626.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="310" src="https://2.bp.blogspot.com/-RkY8IOuMILE/WKn0Cez4yII/AAAAAAABwLE/J8fAkgKT_44K-u8hpWRJ0LYgBkvZmAmpQCKgB/s640/IMG_20170219_203626.jpg" width="640" /></a></div>Another problem I mentioned was from Gennady's contest: <i>n</i><=400 people have participated in a programming contest, and will receive <i>x</i><=10<sup>9</sup> roubles of prize money in total. You do not know what is the prize for each place, you only know that each prize is an integer amount of roubles, that they add up to <i>x</i>, and that the prize amounts are in non-increasing order as we go through the ranking list. Given a subset of places in the ranking list (for example the 1st place, the 5th place and the 8th place), what is the smallest possible total prize for those places?<br /><br />The main idea here is to realize that the prizes essentially form <a href="https://en.wikipedia.org/wiki/Young_tableau">a Young diagram</a>, and as it is often the case, reading the diagram column-by-column after writing it row-by-row proves super useful. Without abstract mathematical terms, one could just say that we can view the distribution of the prize money as the following process: we repeatedly pick a number <i>m<sub>i</sub></i><=<i>n</i>, and give 1 dollar to the top <i>m<sub>i</sub></i> finishers. All <i>m<sub>i</sub></i> must add up to <i>x</i>.<br /><br />Now, giving 1 dollar to the top <i>m<sub>i</sub></i> finishers gives some concrete amount <i>f</i>(<i>m<sub>i</sub></i>) dollars to the finishers in our chosen subset of places. Now we can see that we have a classical knapsack problem instance where the weight of each item is relatively small (<i>m<sub>i</sub></i><=400), each item has a cost <i>f</i>(<i>m<sub>i</sub></i>), and we want to pick a multiset of items with the given total weight <i>x</i> and the smallest possible cost. This problem is solved by noticing that we must use the item with the smallest cost-to-weight ratio for most of the total weight - more precisely, we can keep using that item until the remaining total weight is below 400<sup>2</sup>=160000. And for such small total weight we can then solve the knapsack problem using the standard dynamic programming.<br /><br />The proof of the fact that we only need to run the dynamic programming up to 400<sup>2</sup> is based on the following lemma: in a set of <i>n</i> numbers, there's always a non-empty subset with sum divisible by <i>n</i>.<br /><br />Thanks for reading, and check back soon for this week's summary!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/XRJj2qnCh2Y" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/02/a-spanning-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-45608365876381202772017-02-11T20:21:00.001+03:002017-02-11T20:21:07.120+03:00A Gomel week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-7Zdi7dmqfqc/WJ7bbgWCL6I/AAAAAAABu70/lpXjIEV5ccII8c2oZIxWQLT2MSKaLsaUACLcB/s1600/srm707top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="84" src="https://1.bp.blogspot.com/-7Zdi7dmqfqc/WJ7bbgWCL6I/AAAAAAABu70/lpXjIEV5ccII8c2oZIxWQLT2MSKaLsaUACLcB/s640/srm707top5.png" width="640" /></a></div>Last week started with the early morning TopCoder SRM 707 on Tuesday (<a href="https://community.topcoder.com/stat?c=round_overview&rd=16851">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=16851&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left). Nobody has managed to solve all three problems correctly - but not just because the hard problem was on the difficult side: <a href="https://community.topcoder.com/stat?c=problem_statement&pm=14527&rd=16851">the medium problem</a> had an unusually low 19% success rate, with a deceptively simple statement but quite a few corner cases.<br /><br />The winner Kriii also couldn't get the medium right, but has managed to get some compensation by successfully challenging two other medium solutions. Congratulations on the win!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-tCZAC8ne3e8/WJ7avS6QmhI/AAAAAAABu7s/uZoxKVHu2zwYJVg5rDQTBkUXkV4oEQkzwCLcB/s1600/cf395top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="158" src="https://1.bp.blogspot.com/-tCZAC8ne3e8/WJ7avS6QmhI/AAAAAAABu7s/uZoxKVHu2zwYJVg5rDQTBkUXkV4oEQkzwCLcB/s640/cf395top5.png" width="640" /></a></div>Codeforces Round 395 took place on Thursday (<a href="http://codeforces.com/contest/763">problems</a>, <a href="http://codeforces.com/contest/763/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/50205">analysis</a>). moejy0viiiiiv has solved everything with 24 minutes to spare, while nobody else was able to get all five. That's a very convincing victory!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-E-KT-K4ZW3o/WJ7aSRuh26I/AAAAAAABu7o/zbLn3PhTIqgX30xlKB1fbV0q9QnsSxvvACLcB/s1600/agc010top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="312" src="https://4.bp.blogspot.com/-E-KT-K4ZW3o/WJ7aSRuh26I/AAAAAAABu7o/zbLn3PhTIqgX30xlKB1fbV0q9QnsSxvvACLcB/s640/agc010top5.png" width="640" /></a></div>AtCoder Grand Contest 010 on Saturday has gathered the top three rated contestants among others, and it was exactly those three contestants who occupied the top of the scoreboard (<a href="http://agc010.contest.atcoder.jp/assignments">problems</a>, <a href="http://agc010.contest.atcoder.jp/standings#page_1">results</a>, top 5 on the left, <a href="https://atcoder.jp/img/agc010/editorial.pdf">analysis</a>). Congratulations to Um_nik on being 8 minutes faster than everybody else!<br /><br /><a href="http://agc010.contest.atcoder.jp/tasks/agc010_f">The last problem</a> turned out a bit easier than the organizers have expected. Two players are playing a game on a tree where each node has some amount of stones. There's also a chip in one of the vertices of the tree. They make moves in turn, and each move consists of removing one stone from the vertex where the chip is, and then moving the chip to an adjacent vertex. When there's no more stones in the vertex where the chip is, the player that needs to make the next move is unable to do so, and thus loses the game. How to determine who will win with optimal play?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-w_UvN9kK1Us/WJ7ZNE3pHNI/AAAAAAABu7c/AnTDJrk6D4oxgYCYHlx4pNIQzxjUKa5lwCLcB/s1600/oc2017gomeltop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="175" src="https://3.bp.blogspot.com/-w_UvN9kK1Us/WJ7ZNE3pHNI/AAAAAAABu7c/AnTDJrk6D4oxgYCYHlx4pNIQzxjUKa5lwCLcB/s640/oc2017gomeltop5.png" width="640" /></a></div>And finally, OpenCup 2016-17 Grand Prix of Gomel resumed the Open Cup season on Sunday, featuring Gennady as the problemsetter (<a href="http://opentrains.snarknews.info/~ejudge/res/res10370">results</a>, top 5 on the left). The reigning ACM ICPC world champions SPb SU Base were significantly faster than other teams, and thus found time to solve the hardest problem C in the last hour - great job!<br /><br />Problem D has disguised a relatively standard idea behind an unusual but very natural background. <i>n</i><=400 people have participated in a programming contest, and will receive <i>x</i><=10<sup>9</sup> roubles of prize money in total. You do not know what is the prize for each place, you only know that each prize is an integer amount of roubles, that they add up to <i>x</i>, and that the prize amounts are in non-increasing order as we go through the ranking list. Given a subset of places in the ranking list (for example the 1st place, the 5th place and the 8th place), what is the smallest possible total prize for those places?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-ZCbhmm5NkGQ/WJ9En2ZBr3I/AAAAAAABvC0/QWmqhSc7240usjmmw7BTZi1EKRUlDIIzQCLcB/s1600/IMG_20170122_105631.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="480" src="https://2.bp.blogspot.com/-ZCbhmm5NkGQ/WJ9En2ZBr3I/AAAAAAABvC0/QWmqhSc7240usjmmw7BTZi1EKRUlDIIzQCLcB/s640/IMG_20170122_105631.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2017/02/a-k-ary-week.html">my previous summary</a>, I have mentioned a Hacker Cup problem: you are given a sequence of <i>n</i> positive integers <i>h<sub>i</sub></i>, and a number <i>k</i>. You're allowed to do the following <i>k</i> times: take an integer, and decrease it by 1 (but it must remain positive). After you do this, we compute the maximum value of <i>h<sub>i</sub></i>+<i>h<sub>j</sub></i>+abs(<i>i</i>-<i>j</i>). How small can this maximum value be?<br /><br />The first idea is to start with a binary search. Given a value <i>m</i>, can we achieve <i>h<sub>i</sub></i>+<i>h<sub>j</sub></i>+abs(<i>i</i>-<i>j</i>)<=<i>m</i> for all <i>i</i> not equal to <i>j</i>? Since abs(<i>i</i>-<i>j</i>)=max(<i>i</i>-<i>j</i>,<i>j</i>-<i>i</i>), this is equivalent to <i>h<sub>i</sub></i>+<i>h<sub>j</sub></i>+<i>i</i>-<i>j</i><=<i>m</i> and <i>h<sub>i</sub></i>+<i>h<sub>j</sub></i>+<i>j</i>-<i>i</i><=<i>m</i>. The second inequality is obtained from the first by swapping <i>i</i> and <i>j</i>, so they're equivalent and we can keep just one: <i>h<sub>i</sub></i>+<i>h<sub>j</sub></i>+<i>i</i>-<i>j</i><=<i>m</i>. We can now rewrite it as (<i>h<sub>i</sub></i>+<i>i</i>)+(<i>h<sub>j</sub></i>-<i>j</i>)<=<i>m</i>.<br /><br />Now, if we didn't have the constraint that <i>i</i> is not equal to <i>j</i>, we could define <i>a</i>=max(<i>h<sub>i</sub></i>+<i>i</i>), <i>b</i>=(<i>h<sub>j</sub></i>-<i>j</i>), and simply check if we can make <i>a</i>+<i>b</i><=<i>m</i>. If we fix the value of <i>a</i>, then we know the (maximum value of) <i>b</i>, and thus know how much each height needs to be decreased, and thus can check if <i>k</i> decreases are enough. Of course we can't check all possible values of <i>a</i> this way, but we can notice that if we go through values of <i>a</i> in increasing order, the contribution of each <i>h<sub>i</sub></i> to the total required decrease will be piecewise-linear with at most 5 pieces, and thus we can add all those piecewise-linear curves together in O(<i>n</i>log<i>n</i>) time.<br /><br />Now, what to do with the additional constraint that <i>i</i> is not equal to <i>j</i>? It turns out that it doesn't matter in most cases. More specifically, for this constraint to matter both max(<i>h<sub>i</sub></i>+<i>i</i>) and max(<i>h<sub>j</sub></i>-<i>j</i>) must be achieved in the same point, and only in that point. In that case we have one <i>h<sub>i</sub></i> that is significantly bigger than all others, and thus decreasing this <i>h<sub>i</sub></i> will result in the answer decreasing as well. Because of this, we can always "transfer" one more decrease from any other number to that <i>h<sub>i</sub></i> without making the answer worse, unless all <i>k</i> decreases have been applied to it. And that means that in addition to the piecewise-linear sum mentioned above, it suffices to check just one more case: when all <i>k</i> decreases are applied to the maximum <i>h<sub>i</sub></i>.<br /><br />Thanks for reading, and check back next week!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/AKiunjO4I44" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/02/a-gomel-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-20517672334342688542017-02-03T17:14:00.002+03:002017-02-03T18:07:00.273+03:00A k-ary week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-T1DLx5rD9-k/WJSOdz7ywxI/AAAAAAABu2Q/fCyXbN_QiW0NvwgeTf7FFO259h20cQTbQCLcB/s1600/fbhc2017r3top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="275" src="https://2.bp.blogspot.com/-T1DLx5rD9-k/WJSOdz7ywxI/AAAAAAABu2Q/fCyXbN_QiW0NvwgeTf7FFO259h20cQTbQCLcB/s640/fbhc2017r3top5.png" width="640" /></a></div>Last week, the 200 participants of Facebook Hacker Cup Round 3 were fighting for the 25 spots in the Seattle onsite (<a href="https://www.facebook.com/hackercup/problem/1834377036809994/">problems</a>, <a href="https://www.facebook.com/hackercup/scoreboard/1198810003536974/?filter=everyone">results</a>, top 5 on the left, <a href="https://www.facebook.com/notes/facebook-hacker-cup/hacker-cup-2017-round-3-solutions/1617058738310021">analysis</a>). This time double- and triple-checking was not the best approach, as one needed to solve the first three problems quite quickly to get through. Congratulations to Egor on the victory!<br /><br /><a href="https://www.facebook.com/hackercup/problem/637797413079757/">The hardest problem</a> required both a careful implementation and several key insights. You are given a sequence of <i>n</i> positive integers <i>h<sub>i</sub></i>, and a number <i>k</i>. You're allowed to do the following <i>k</i> times: take an integer, and decrease it by 1 (but it must remain positive). After you do this, we compute the maximum value of <i>h<sub>i</sub></i>+<i>h<sub>j</sub></i>+abs(<i>i</i>-<i>j</i>). How small can this maximum value be?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-AposeOXvCW4/WJSPFfpVVQI/AAAAAAABu2c/VHakTpzkAPoOQyTpMsykT_S8pdd0l9PkACLcB/s1600/IMG_20170108_111040.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="480" src="https://1.bp.blogspot.com/-AposeOXvCW4/WJSPFfpVVQI/AAAAAAABu2c/VHakTpzkAPoOQyTpMsykT_S8pdd0l9PkACLcB/s640/IMG_20170108_111040.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2017/02/a-limak-week.html">my previous summary</a>, I have mentioned two interesting problems. The first one, coming from TopCoder, asked to find any sequence of 500 positive integers up to 10<sup>18</sup>, such that any two adjacent numbers in this sequence are coprime, and any two non-adjacent numbers in this sequence are not coprime.<br /><br />As usual with such "constructive" problems, a lot of different approaches are possible. I think the most beautiful approach is the randomized one, as described in <a href="http://codeforces.com/blog/entry/49002?#comment-338806">the analysis</a>. Let's take the first <i>n</i> primes, and each of the 500 numbers will be a product of some <i>k</i> of them. To build the sequence, we will pick each number at random from all possible products of some <i>k</i> of those primes that do not include the <i>k</i> primes used to build the previous number. This will guarantee that adjacent numbers will be coprime. After generating each number, we will also verify if it's coprime with any other number except the one directly preceding it. If yes, we'll regenerate it again at random, and so on until this number fits, then move on to the next number.<br /><br />Why does this work, and how to pick <i>n</i> and <i>k</i>? I can only offer some advice partly based on intuition here. Obviously <i>k</i> must be chosen in such a way that the product of the largest <i>k</i> of the first <i>n</i> primes does not exceed 10<sup>18</sup>. Also, <i>k</i> must be close to <i>n</i>/2, but not too close :) Basically, the higher is <i>k</i>, the more likely it is for two random numbers with <i>k</i> bits out of <i>n</i> to share a common bit. However, when <i>k</i> approaches <i>n</i>/2 a different mechanic comes into play: the bits (primes used) in the sequence start to alternate, and thus the numbers at an odd distance are more likely to be coprime. Practically speaking, <i>n</i>=23 and <i>k</i>=10 seems to work with a comfortable margin. Still, it's not entirely clear to me how to expect this solution to work before trying it out - I think it requires the right kind of statistical intuition.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-aIGatlRyzUE/WJSQGqTldxI/AAAAAAABu24/FcEWbcoySwElH0ICZXJA9_NHQG1uGrxPgCKgB/s1600/IMG_20170203_171209.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="300" src="https://1.bp.blogspot.com/-aIGatlRyzUE/WJSQGqTldxI/AAAAAAABu24/FcEWbcoySwElH0ICZXJA9_NHQG1uGrxPgCKgB/s400/IMG_20170203_171209.jpg" width="400" /></a></div>The other problem I mentioned was from AtCoder: you start with <i>n</i> zeros and <i>m</i> ones on a blackboard, and you're also given a number <i>k</i> such that <i>k</i>-1 divides <i>n</i>+<i>m</i>-1. You repeatedly pick any <i>k</i> numbers on the blackboard, erase them, and instead write their arithmetic mean (which is not necessarily an integer). Since <i>k</i>-1 divides <i>n</i>+<i>m</i>-1, you will eventually end up with just one number. How many different values can this last number have? <i>n</i> and <i>m</i> are up to 2000.<br /><br />The right approach to this problem is to build a rigorous mental model of what's going on. We can view the computation as a rooted tree: the root of the tree corresponds to the final value, each non-leaf node has exactly <i>k</i> children corresponding to the values used to obtain the value of this node, and there are <i>n</i>+<i>m</i> leaf nodes corresponding to the original numbers, each containing either 0 or 1, with exactly <i>m</i> 1s. There will be <i>d</i>=(<i>n</i>+<i>m</i>-1)/(<i>k</i>-1) inner nodes in the tree.<br /><br />We can then notice that the final value is uniquely determined by the depths of each 1 leaf node. More precisely, a 1 at distance <i>p</i> from root contributes 1/<i>k</i><sup><i>p</i></sup> to the final value. Now it's clear that the final value must be representable as <i>x</i>/<i>k</i><sup><i>q</i></sup>, where <i>q</i><=<i>d.</i> For a given value, let's pick the minimum such <i>q</i>. How do we determine if it's representable given <i>x</i> and <i>q</i>?<br /><br />Representing <i>x</i>/<i>k</i><sup><i>q</i></sup> as a sum of <i>m</i> terms of form 1/<i>k</i><sup><i>p</i></sup> is equivalent to representing <i>x</i> as a sum of <i>m</i> terms of form <i>k</i><sup><i>q-p</i></sup>. In other words, we need to represent <i>x</i> in <i>k</i>-ary system with sum of digits equal to <i>m</i>, but where each digit can be arbitrarily big. It's not hard to see that the minimum sum of digits is achieved if we use the standard representation of <i>x</i> in <i>k</i>-ary system, and all other representations are obtained by replacing one of the 1s with <i>k</i> smaller 1s. We can make at most <i>d</i>-<i>q</i> such replacements (since <i>q</i> out of <i>d</i> tree nodes are already used for the initial representation).<br /><br />To summarize, for each <i>q</i><=<i>d</i> we just need to count the amount of numbers <i>x </i>with <i>q</i> digits in <i>k</i>-ary system with sum of digits equal to <i>m</i>-(<i>k</i>-1)*<i>y</i>, where 0<=<i>y</i><=<i>d</i>-<i>q</i>, and with nonzero last digit. This is now a standard dynamic programming task, and note that we didn't need to have any insights or magical ideas to arrive at it - just gradually expanding our understanding of the problem domain.<br /><br />Thanks for reading, and check back next week!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/AxMeU0C8eZE" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/02/a-k-ary-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-30083728722050917392017-02-03T16:36:00.000+03:002017-02-03T16:36:22.792+03:00A Limak week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-wm4KYnQ3AN8/WI5xasI1sjI/AAAAAAABuwQ/dW8Yw98b89kJOhR-y6opqOzeh3N8eNGeACLcB/s1600/srm706top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" src="https://4.bp.blogspot.com/-wm4KYnQ3AN8/WI5xasI1sjI/AAAAAAABuwQ/dW8Yw98b89kJOhR-y6opqOzeh3N8eNGeACLcB/s1600/srm706top5.png" /></a></div>TopCoder SRM 706 kicked off the activity-packed weekend of the Jan 16 - Jan 22 week (<a href="https://community.topcoder.com/stat?c=round_overview&rd=16850">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=16850&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/49002?#comment-338806">analysis</a>, <a href="https://youtu.be/k65MkV38RSk">my screencast</a>). Our old friend, bear Limak, promised the reliably high quality of Errichto's problems, and the contest did not disappoint. I had other reasons to be disappointed, though, not being able to maintain the first place through the challenge phase. Kudos to ainta for the decisive +50!<br /><br /><a href="https://community.topcoder.com/stat?c=problem_statement&pm=14495&rd=16850">The hardest problem</a> had a deceptively easy statement: you need to find any sequence of 500 positive integers up to 10<sup>18</sup>, such that any two adjacent numbers in this sequence are coprime, and any two non-adjacent numbers in this sequence are not coprime. Can you see the way?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-iCxrO2rxFIU/WI5yiWIvzuI/AAAAAAABuwc/c9LjAGuOxIAU9ovqxJNlki4D7GAx87CHwCLcB/s1600/fbhc2017r2top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="292" src="https://4.bp.blogspot.com/-iCxrO2rxFIU/WI5yiWIvzuI/AAAAAAABuwc/c9LjAGuOxIAU9ovqxJNlki4D7GAx87CHwCLcB/s640/fbhc2017r2top5.png" width="640" /></a></div>Right after the end of the SRM, Facebook Hacker Cup 2017 Round 2 narrowed the list of contenders for the cup to just 200 algorithmists (<a href="https://www.facebook.com/hackercup/problem/371325719893664/">problems</a>, <a href="https://www.facebook.com/hackercup/scoreboard/742957399195355/?filter=everyone">results</a>, top 5 on the left, <a href="https://www.facebook.com/notes/facebook-hacker-cup/hacker-cup-2017-round-2-solutions/1607098535972708">analysis</a>, <a href="https://youtu.be/0cIPGx7IWSg">my screencast</a>). Given the extremely harsh judging system and the fact that the 1st and the 200th place were similarly useful, one had to find the right balance between double- and triple-checking the solutions, and moving on to the next problem. Congratulations to all 200 algorithmists who got this right, and to Marek for being the fastest!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-B-_6ks4CPwA/WI5zFWeK9BI/AAAAAAABuwg/EJa4vC3BHrEouzxyxJPw_RBK0s2dF36BwCLcB/s1600/agc009top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="312" src="https://2.bp.blogspot.com/-B-_6ks4CPwA/WI5zFWeK9BI/AAAAAAABuwg/EJa4vC3BHrEouzxyxJPw_RBK0s2dF36BwCLcB/s640/agc009top5.png" width="640" /></a></div>On Sunday, AtCoder Grand Contest 009 has gathered roughly the same crowd again (<a href="http://agc009.contest.atcoder.jp/assignments">problems</a>, <a href="http://agc009.contest.atcoder.jp/standings">results</a>, top 5 on the left, <a href="https://atcoder.jp/img/agc009/editorial.pdf">analysis</a>). w4yneb0t has continued his string of excellent results, winning this round and cementing his second place in <a href="https://atcoder.jp/ranking">the overall AtCoder rating list</a> - well done!<br /><br /><a href="http://agc009.contest.atcoder.jp/tasks/agc009_e">The last problem</a> was a great example of the type where after developing a good understanding of the mechanics described in the problem statement, coming up with the actual solution is very straightforward. You start with <i>n</i> zeros and <i>m</i> ones on a blackboard, and you're also given a number <i>k</i> such that <i>k</i>-1 divides <i>n</i>+<i>m</i>-1. You repeatedly pick any <i>k</i> numbers on the blackboard, erase them, and instead write their arithmetic mean (which is not necessarily an integer). Since <i>k</i>-1 divides <i>n</i>+<i>m</i>-1, you will eventually end up with just one number. How many different values can this last number have? <i>n</i> and <i>m</i> are up to 2000.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-qiVp9dF7PyU/WI5zxJ8ZcEI/AAAAAAABuwo/QJUlkfh4QiMenvxWZagVi4fcKARx8qhYgCLcB/s1600/8vc2017finaltop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="156" src="https://1.bp.blogspot.com/-qiVp9dF7PyU/WI5zxJ8ZcEI/AAAAAAABuwo/QJUlkfh4QiMenvxWZagVi4fcKARx8qhYgCLcB/s640/8vc2017finaltop5.png" width="640" /></a></div>And finally, Codeforces 8VC Venture Cup 2017 Final Round gave the contestants a shot at monetary prizes (<a href="http://codeforces.com/contest/756">problems</a>, <a href="http://codeforces.com/contest/756/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/contest/759/standings">parallel round results</a>, <a href="http://codeforces.com/blog/entry/49946">analysis</a>). V--o_o--V, previously known as overtroll, was super fast through the first four problems, and has managed to solve the extremely tedious problem E, to win the first prize with a comfortable margin. Congratulations!<br /><br />Thanks for reading, and check back soon for the last week's summary!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/0KlQOPpo0uo" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/02/a-limak-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-62525292078591296362017-01-16T18:57:00.000+03:002017-01-16T19:59:08.183+03:000.636 of a year<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-XP-_U9UgQ9o/WHzo3uZQinI/AAAAAAAA--E/d97lc39z__UxkUTw8SHERpT2nAstoqm6QCLcB/s1600/srm705top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" src="https://1.bp.blogspot.com/-XP-_U9UgQ9o/WHzo3uZQinI/AAAAAAAA--E/d97lc39z__UxkUTw8SHERpT2nAstoqm6QCLcB/s1600/srm705top5.png" /></a></div>Very early on Wednesday, TopCoder SRM 705 set the pace for the competitions in 2017 (<a href="https://community.topcoder.com/stat?c=round_overview&rd=16856">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=16856&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left). Tourist would have been in the 7th place even if all his solutions failed the system test, thanks to an impressive challenge phase performance. And as usual, none of the solutions did fail, so he achieved an extremely commanding victory. Congratulations!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-j6D5pz9juek/WHzo8NNXnGI/AAAAAAAA--I/J4wwrGIigeACDX3kfTyQFUogyuXJv-19ACLcB/s1600/cf391top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="154" src="https://3.bp.blogspot.com/-j6D5pz9juek/WHzo8NNXnGI/AAAAAAAA--I/J4wwrGIigeACDX3kfTyQFUogyuXJv-19ACLcB/s640/cf391top5.png" width="640" /></a></div>Later that day, Codeforces held its own opening contest of 2017 - Codeforces Round 391 (<a href="http://codeforces.com/contest/757">problems</a>, <a href="http://codeforces.com/contest/757/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/49743">analysis</a>). Once again tourist has combined excellent solving with excellent challenging to claim a win, but the competition was much closer this time. Well done to tourist and to his competitors!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-gSOK5kY6Kbg/WHzpNA5lJoI/AAAAAAAA--M/HxOFzFoVyIU8Ocm1bfOp6EFQIS9SOEqvQCLcB/s1600/eightvcelim2016top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="156" src="https://2.bp.blogspot.com/-gSOK5kY6Kbg/WHzpNA5lJoI/AAAAAAAA--M/HxOFzFoVyIU8Ocm1bfOp6EFQIS9SOEqvQCLcB/s640/eightvcelim2016top5.png" width="640" /></a></div>On Sunday, Codeforces held one more round: 8VC Venture Cup 2017 Elimination Round (<a href="http://codeforces.com/contest/755">problems</a>, <a href="http://codeforces.com/contest/755/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/49793">analysis</a>). In case you have not noticed the pattern of the new year, it was tourist at the top once again. Impressive consistency!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-oDGD-TvKP_Y/WHzs0LRKpII/AAAAAAAA--g/3r3Pgerv0L8PtbyfLNEdN16kQchOGCyIgCLcB/s1600/IMG_20170107_122451-PANO.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="268" src="https://4.bp.blogspot.com/-oDGD-TvKP_Y/WHzs0LRKpII/AAAAAAAA--g/3r3Pgerv0L8PtbyfLNEdN16kQchOGCyIgCLcB/s640/IMG_20170107_122451-PANO.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2017/01/a-week-of-five.html">my last summary</a>, I have organized a vote between top 5 problems of 2016 (of course, only according to my taste). Here are its results:<br /><br />5. The problem about recovering the seed used for shuffling a permutation twice - <a href="http://petr-mitrichev.blogspot.com/2016/11/an-unshuffle-week.html">post with solution</a>. 13 votes, author: Ivan Kazmenko.<br />4. The problem about turning one string into another using two operations: replace one letter, or replace all occurrences of the same letter - <a href="http://petr-mitrichev.blogspot.com/2016/05/a-polish-week.html">post with solution</a>. 17 votes, author: Adam Karczmarz.<br />3. The problem about exploring a cave with identical rooms interactively - <a href="http://petr-mitrichev.blogspot.com/2016/12/a-dfs-week.html">post with solution</a>. 21 vote, author: Georgiy Korneev.<br />2. The problem about implementing binary search that's takes at most log(n+1)+0.1 on average, not ceil(log(n)) - <a href="http://petr-mitrichev.blogspot.com/2016/04/a-binary-week.html">post with solution</a>. 29 votes, author: Vasiliy Mokin (not sure, please tell if it's not correct).<br />1. The problem about turning a matching in the plane into a non-intersecting one that's at least 0.636x as long - <a href="http://petr-mitrichev.blogspot.com/2016/05/a-26x26-week.html">post with solution</a>. 37 votes, author: Gaoyuan Chen.<br /><br />Big thanks to the authors of these and all other 2016 problems!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/tJFtuF0YdMA" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/01/0636-of-year.htmltag:blogger.com,1999:blog-1953325079793449971.post-7316115506978585132017-01-08T23:12:00.002+03:002017-01-08T23:12:58.806+03:00A week of five<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-4KjOJq74vlU/WHKcmD2mn0I/AAAAAAAA-qo/-2rdTZR6eZ4SYNWL0BKuPmwF5ZS5PJFrwCLcB/s1600/IMG_20161229_171807.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="480" src="https://2.bp.blogspot.com/-4KjOJq74vlU/WHKcmD2mn0I/AAAAAAAA-qo/-2rdTZR6eZ4SYNWL0BKuPmwF5ZS5PJFrwCLcB/s640/IMG_20161229_171807.jpg" width="640" /></a></div>In my <a href="http://petr-mitrichev.blogspot.com/2017/01/a-random-walk-week.html">last week's summary</a>, I have mentioned an educational Codeforces problem: you were given a string of digits <i>s</i> of length 200000, and at most 200000 queries, each query being a certain substring <i>q<sub>i</sub></i> of this string. For each query, you need to remove the smallest number of characters from this substring <i>q<sub>i</sub></i> in such a way that the resulting string contains 2017 <i>as a subsequence</i>, but does not contain 2016 as a subsequence.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-k_2d7rZBh8Q/WHKCsfaUqtI/AAAAAAAA-qI/P7CyE6u5pp4XGxlfZscmucVyV3ccklo7ACKgB/s1600/IMG_20170108_191813.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" height="138" src="https://4.bp.blogspot.com/-k_2d7rZBh8Q/WHKCsfaUqtI/AAAAAAAA-qI/P7CyE6u5pp4XGxlfZscmucVyV3ccklo7ACKgB/s400/IMG_20170108_191813.jpg" width="400" /></a></div>First, suppose there were no queries and no removed characters, just one string and the need to check if it contains 2017 and 2016 as a subsequence. That would be an extremely easy problem which allows many solutions. There's one solution, however, that lends itself well to the complications of the full problem: we will build a <a href="https://en.wikipedia.org/wiki/Deterministic_finite_automaton">deterministic finite automaton</a> that accepts only strings that contain 2017 but not 2016 as a subsequence. You can find this automaton pictured on the right, all transitions not explicitly mentioned in the picture lead from a vertex to itself. It has 6 states, A is the starting state, and E is the final state.<br /><br />In order to solve the full problem, we will create a segment tree (not the one from Wikipedia, but <a href="https://www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor/#Segment_Trees">this one</a>). For each segment of the given string, and for each pair of states of the automaton <i>s</i> and <i>t</i>, we will remember: what is the smallest number of characters that needs to be removed from this segment in order for the automaton to reach state <i>t</i>, if it starts in state <i>s</i>? In other words, each node of the segment tree will store a 6x6 matrix, and in order to combine the matrices for two child nodes, a process similar to matrix multiplication is needed.<br /><br />Note that this approach would work for any deterministic finite automaton, not just for the one pictured above.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-sz-Z-s5SR44/WHKcvKQnZwI/AAAAAAAA-qs/wJWqJwd8Gp8BWg5jrMRpjha80zP_1fwpACLcB/s1600/IMG_20170101_161650.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="480" src="https://3.bp.blogspot.com/-sz-Z-s5SR44/WHKcvKQnZwI/AAAAAAAA-qs/wJWqJwd8Gp8BWg5jrMRpjha80zP_1fwpACLcB/s640/IMG_20170101_161650.jpg" width="640" /></a></div>This post wraps up the solutions for problems posted in 2016. As such, it is a good time to take a look back and find the best problem of last year! I've taken a look at the 38 problems for which I've explained the solutions in my blog, and picked 5 that appeal the most to my taste. In chronological order:<br /><br />The problem about implementing binary search that's takes at most log(<i>n</i>+1)+0.1 on average, not ceil(log(<i>n</i>)) - <a href="http://petr-mitrichev.blogspot.com/2016/04/a-binary-week.html">post with solution</a>.<br />The problem about turning a matching in the plane into a non-intersecting one that's at least 0.636x as long - <a href="http://petr-mitrichev.blogspot.com/2016/05/a-26x26-week.html">post with solution</a>.<br />The problem about turning one string into another using two operations: replace one letter, or replace all occurrences of the same letter - <a href="http://petr-mitrichev.blogspot.com/2016/05/a-polish-week.html">post with solution</a>.<br />The problem about recovering the seed used for shuffling a permutation twice - <a href="http://petr-mitrichev.blogspot.com/2016/11/an-unshuffle-week.html">post with solution</a>.<br />The problem about exploring a cave with identical rooms interactively - <a href="http://petr-mitrichev.blogspot.com/2016/12/a-dfs-week.html">post with solution</a>.<br /><br />Could you help me pick one? <br /><br /><iframe allowtransparency="true" frameborder="0" height="211px" name="poll-widget-4248165688735669481" src="https://www.google.com/reviews/polls/display/-4248165688735669481/blogger_template/run_app?txtclr=%23666666&lnkclr=%235588aa&chrtclr=%235588aa&font=normal+normal+100%25+Georgia,+Serif&hideq=true&purl=http://petr-mitrichev.blogspot.com/" style="border: none; width: 100%;"></iframe> Thanks for reading, and check back next week!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/ovYYMZZ1jl8" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/01/a-week-of-five.htmltag:blogger.com,1999:blog-1953325079793449971.post-43319757277940559872017-01-02T01:49:00.000+03:002017-01-09T22:41:23.224+03:00A random walk week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-6Rtyamm3D-c/WGl2L84zG9I/AAAAAAAA-Ls/uBH8M6kywHU6CQJMe_Fw9to69kYyXaMugCEw/s1600/srm704top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" src="https://3.bp.blogspot.com/-6Rtyamm3D-c/WGl2L84zG9I/AAAAAAAA-Ls/uBH8M6kywHU6CQJMe_Fw9to69kYyXaMugCEw/s1600/srm704top5.png" /></a></div>The New Year week featured contests from the two usual platforms. First off, TopCoder held its SRM 704 on Thursday (<a href="https://community.topcoder.com/stat?c=round_overview&rd=16849">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=16849&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://youtu.be/EYN-_3pltOE">my screencast</a>). I have almost shot myself in the foot by blindly challenging sky58's medium with a big testcase at the start of the challenge phase on the ground that he has been compiling and testing this problem right up to the end of the coding phase, suggesting he found a testcase where his solution fails but could not fix it in time. I got -25, but luckily Swistakk has returned the favor a couple of minutes later with a -25 of his own, and I was again within one challenge of the top which I was able to find in the remaining minutes.<br /><br />To be completely honest, I have made another unsuccessful attempt at shooting myself in the foot during this match. <a href="https://community.topcoder.com/stat?c=problem_statement&pm=14470&rd=16849">The hard problem</a> was about constructing a directed graph with at most 20 vertices with the given amount <i>k</i> (up to 100000) of Hamiltonian paths from the first vertex to the last one. I was having a hard time trying to come up with a working approach, so I've decided to fall back to one of the standard approaches that often work in this kind of constructive problems: a random walk. We start with some graph, then repeatedly add random edges while it has too little Hamiltonian paths, or remove random edges while it has too many, until we happen to get the exact amount.<br /><br />However, just finding the number of Hamiltonian paths in an arbitrary graph with 20 vertices would require exponential time, which practically meant that I could make only a few random steps in the allotted two seconds, which was clearly not enough. So I've tried to find a family of graphs where, on one hand, I could find the number of Hamiltonian paths quickly, and on the other hand, the family should be rich enough that it can have any number of Hamiltonian paths up to 100000, and preferably have any number of paths achievable in very many different ways, in order for the random walk to be able to stumble upon one.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-PLYrfPPC7Qk/WGmBcvlrXiI/AAAAAAAA-MM/YWBcXAS-2ssGlwpdw3KpM7TAkUcHYtIFACKgB/s1600/IMG_20170101_232142.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="116" src="https://1.bp.blogspot.com/-PLYrfPPC7Qk/WGmBcvlrXiI/AAAAAAAA-MM/YWBcXAS-2ssGlwpdw3KpM7TAkUcHYtIFACKgB/s640/IMG_20170101_232142.jpg" width="640" /></a></div>I was able to find such family relatively quickly: it would be almost acyclic graphs, where we have arcs from each vertex <i>i </i>to vertex <i>i</i>-1, and all other arcs go "to the right" - from each vertex i to vertices with numbers <i>j</i>><i>i</i>. Counting the number of Hamiltonian paths in such graph is a relatively straightforward dynamic programming task, because whenever we make a "jump" vertex <i>j</i> when previously the largest visited vertex was <i>i</i><<i>j-</i>1, we have to immediately go to the left through vertices <i>j</i>-1, <i>j</i>-2, ..., <i>i</i>+1 in this order, as we have no way of reaching them later. And the family seems reasonably expressive - for example, if we take all possible edges to the right, the number of paths would be 2<sup><i>n</i>-3</sup> (we choose the subset of vertices we "jump" to), and if we take only edges from each <i>i</i> to <i>i</i>+1, there's just one path, with other configurations falling somewhere in between and hopefully covering each number many times.<br /><br />I was so happy to find this family that I rushed to code this solution immediately, and submitted it as soon as I realized that it seems to work fast enough (always less than a second) at least on random inputs. However, I was by no means certain that it works in all cases - it might well be that some specific number of paths is harder to achieve, and since I only had a 2x-4x margin, a moderately higher number of random steps required would cause my solution to time out.<br /><br />The shooting oneself in the foot aspect is that it's really easy to come up with a deterministic solution for the problem within this family of graphs. In fact, the fact that the maximum graph has the number of paths equal to a power of two strongly points toward that deterministic solution. And indeed, all other accepted solutions for this problem do exactly that. Somehow it didn't even occur to me to think in this direction during the round :) Can you see this final step?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-rM1_oltd3bw/WGl2RswwuvI/AAAAAAAA-Lw/dWqHzS8zl2E6qlTKEWO_w2dm3pc01b4FACLcB/s1600/goodbye2016top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="156" src="https://4.bp.blogspot.com/-rM1_oltd3bw/WGl2RswwuvI/AAAAAAAA-Lw/dWqHzS8zl2E6qlTKEWO_w2dm3pc01b4FACLcB/s640/goodbye2016top5.png" width="640" /></a></div>One day later, Codeforces held its traditional Good Bye 2016 round (<a href="http://codeforces.com/contest/750">problems</a>, <a href="http://codeforces.com/contest/750/standings">results</a>, top 5 on the left, <a href="https://youtu.be/WqafwPqZG2M">my screencast</a>). It was Gennady's turn to shoot himself in the foot this time, as he was not careful enough when challenging and earned -50 points for an unsuccessful attempt that proved decisive.<br /><br />This round had a few interesting problems, but I think <a href="http://codeforces.com/contest/750/problem/E">problem E</a> was the most educational - it did not require much beyond putting together several standard approaches, but required a good understanding of those approaches to do so. You were given a string of digits <i>s</i> of length 200000, and at most 200000 queries, each query being a certain substring <i>q<sub>i</sub></i> of this string. For each query, you need to remove the smallest number of characters from this substring <i>q<sub>i</sub></i> in such a way that the resulting string contains 2017 <i>as a subsequence</i>, but does not contain 2016 as a subsequence.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-0s9DNHBBWlY/WGmG_peAfFI/AAAAAAAA-M0/oYta_vwe2GEjKwn-xglmqbiR_bI4hF9LgCLcB/s1600/IMAG1766-EFFECTS.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="362" src="https://1.bp.blogspot.com/-0s9DNHBBWlY/WGmG_peAfFI/AAAAAAAA-M0/oYta_vwe2GEjKwn-xglmqbiR_bI4hF9LgCLcB/s640/IMAG1766-EFFECTS.jpg" width="640" /></a></div>Finally, let me turn your attention to another traditional contest that is still running: <a href="https://contest.yandex.com/newyear2017/contest/3641/enter/">the Prime New Year Contest</a> at SnarkNews. <a href="http://petr-mitrichev.blogspot.com/2013/01/prime-contest-on-snarknews.html">As usual</a>, it includes only problems that were given in a team contest in 2016 but were not solved by any team there. You have plenty of time to try your hand at the hardest problems of 2016, as the contest runs until January 10. The solutions for three problems were described in this blog, so you can get a head start :)<br /><br />Thanks for reading, and check back next week!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/IbCR6b2aqWs" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/01/a-random-walk-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-1238403657902718492016-12-28T18:44:00.000+03:002016-12-28T18:44:11.949+03:00A black radius week<div dir="ltr" style="text-align: left;" trbidi="on">Last week was very calm, as most algorithmic competition websites have called it a year or are busy preparing special New Year-themed competitions.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-zN361fbldhc/WGPTIsd-pmI/AAAAAAAA91Q/XeSpalLRHocxqKE5THpu5gSBZAvvEKVlgCLcB/s1600/agc008top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="318" src="https://2.bp.blogspot.com/-zN361fbldhc/WGPTIsd-pmI/AAAAAAAA91Q/XeSpalLRHocxqKE5THpu5gSBZAvvEKVlgCLcB/s640/agc008top5.png" width="640" /></a></div>Nevertheless, AtCoder held its Grand Contest 008 right on Christmas Day (<a href="http://agc008.contest.atcoder.jp/assignments">problems</a>, <a href="http://agc008.contest.atcoder.jp/standings#page_1">results</a>, top 5 on the left, <a href="https://atcoder.jp/img/agc008/editorial.pdf">analysis</a>). In breaking with AGC tradition, the problems were quite technical and tedious this time. Big congratulations to apiad who has managed to get all of them accepted and won!<br /><br />I have spent all 110 minutes on the attractive-looking <a href="http://agc008.contest.atcoder.jp/tasks/agc008_f">problem F</a>, severely underestimating the amount of things that can go wrong in its solution (I got it accepted after about 5 more minutes of debugging after the end of the contest). The problem simply asks: given a tree with some subset of its vertices colored black, consider all subsets of its vertices defined as "all vertices at distance at most <i>d</i> from some black vertex <i>a</i>" (for all combinations of <i>d</i> and <i>a</i>), and return the number of different such subsets. When the same subset is defined through several combinations of <i>d</i> and <i>a</i>, it must still be counted only once.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-8_n1nVyLb3Q/WGPYKX-XUDI/AAAAAAAA91k/OUpvy5KyFc8kGq9vLC1Z4aLgI9LcQ4B4ACKgB/s1600/IMAG1861.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="362" src="https://1.bp.blogspot.com/-8_n1nVyLb3Q/WGPYKX-XUDI/AAAAAAAA91k/OUpvy5KyFc8kGq9vLC1Z4aLgI9LcQ4B4ACKgB/s640/IMAG1861.jpg" width="640" /></a></div>(Moscow Christmas on the left - compare to <a href="http://petr-mitrichev.blogspot.com/2015/12/a-christmas-week.html">last year</a> :)) In <a href="http://petr-mitrichev.blogspot.com/2016/12/an-amazon-week.html">my previous summary</a>, I have mentioned an interactive Open Cup problem: you needed to give a checkmate to a lone king on a 8x8 chessboard using just one piece - <a href="https://en.wikipedia.org/wiki/Amazon_(chess)">the amazon</a>, that can move both as a queen and as a knight. To makes things harder, you are playing blindfolded and do not know the king's position or moves. More precisely, you are given the initial position of the amazon, and need to output such sequence of at most 50 moves that the king that starts in any position that is not checked by the amazon and makes any legal moves will eventually be checkmated at some point in this sequence, and will not be stalemated before that.<br /><br />There are multiple approaches described in <a href="http://codeforces.com/blog/entry/49169">the post-match discussion</a>, highlighting the fact that the problem allowed one's creativity to shine. However, the solution described by Endagorion also allows to answer the extra question I posted last week: how short can such sequence of moves be if the amazon starts at <i>a1</i>?<br /><br />It turns out this shortest sequence is "a1 a2 b3 b4 c5 c6 c5 d4 d3 d4 e5 e6 e5 f4 f3 e5 f6" (16 moves). And to prove this, Endagorion simply runs a breadth-first search over all reachable states of the game. The state of the game, in this case, is the position of the amazon plus the set of positions where the opposite king <i>can</i> be. At first glance it seems like we might get 64*2<sup>64</sup> states, but in practice the number of reachable states is much, much lower - most likely because the set of reachable squares for the king fills any unattacked area reasonably quickly, and thus we get much fewer possibilities (just 312400 states are reachable, and only 54520 of those are traversed before we find a way to checkmate definitely).<br /><br />Thanks for reading, and check back in 2017! Happy New Year!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/_FOxX8PyM9w" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2016/12/a-black-radius-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-44594143469005838102016-12-19T01:22:00.000+03:002016-12-19T01:22:05.514+03:00An amazon week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-f2N-FjdX4tM/WFcCeBOgZpI/AAAAAAAA9pg/bvHAHNpJu5AuyqL8EWbGJMN651Rr1WLQACEw/s1600/srm703top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" src="https://4.bp.blogspot.com/-f2N-FjdX4tM/WFcCeBOgZpI/AAAAAAAA9pg/bvHAHNpJu5AuyqL8EWbGJMN651Rr1WLQACEw/s1600/srm703top5.png" /></a></div>On Wednesday, TopCoder SRM 703 - the first TopCoder round after the TCO - took place (<a href="https://community.topcoder.com/stat?c=round_overview&rd=16848">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=16848&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left). Endagorion has claimed the victory thanks for an amazingly fast solution for the 1000 - he submitted it in just over 7 minutes! It turns out that a similar problem <a href="http://codeforces.com/blog/entry/48849?#comment-330337">has appeared before</a>, and he could reuse most of the code. Nevertheless, congratulations on the flawless execution!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-MH1T2RzISaQ/WFcEmsrnIEI/AAAAAAAA9po/rKcwLcKWNPQtMRqEzlKWV-M3yNik_ULHQCLcB/s1600/cf385top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="166" src="https://1.bp.blogspot.com/-MH1T2RzISaQ/WFcEmsrnIEI/AAAAAAAA9po/rKcwLcKWNPQtMRqEzlKWV-M3yNik_ULHQCLcB/s640/cf385top5.png" width="640" /></a></div>Codeforces Round 385 on Saturday has gathered 8 nutella-rated participants, including the top 3 (<a href="http://codeforces.com/contest/744">problems</a>, <a href="http://codeforces.com/contest/744/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/49126">analysis</a>). Tourist has guaranteed himself the first place in just over an hour, but couldn't solve everything because of extremely tricky geometric problem D. Congratulations on the win!<br /><br />Here's <a href="http://codeforces.com/contest/744/problem/E">problem E</a> which has propelled him to the top, in a slightly simplified form: you are given <i>n</i> words with total length up to <i>m</i>, and need to check whether there exists a <i>cyclic string</i> that has at least two different decompositions into those words, in O(<i>nm</i>) time. For example, for a set {"aa", "aba", "ba", "bab"} the cyclic string "ababa"="babaa" has two decompositions: "aba" + "ba", and "bab" + "aa".<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-wqRlb8rQ4CY/WFcIYG1Y4gI/AAAAAAAA9p4/rgogvfTqfVY5ZVOlO1dqGk_-Fi0nMfwOACLcB/s1600/oc1617r9top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="170" src="https://1.bp.blogspot.com/-wqRlb8rQ4CY/WFcIYG1Y4gI/AAAAAAAA9p4/rgogvfTqfVY5ZVOlO1dqGk_-Fi0nMfwOACLcB/s640/oc1617r9top5.png" width="640" /></a></div>Finally, Open Cup 2016-17 Grand Prix of Peterhof has (probably?) wrapped up 2016 for many ACM ICPC teams (<a href="http://opentrains.snarknews.info/~ejudge/res/res10359">results</a>, top 5 on the left). Problem E was the most unusual and thus the most creative: you needed to give a checkmate to a lone king on a 8x8 chessboard using just one piece: <a href="https://en.wikipedia.org/wiki/Amazon_(chess)">the amazon</a>, that can move both as a queen and as a knight. To makes things harder, you are playing blindfolded and do not know the king's position or moves. More precisely, you are given the initial position of the amazon, and need to output such sequence of at most 50 moves that the king that starts in any position that is not checked by the amazon and makes any legal moves will eventually be checkmated at some point in this sequence, and will not be stalemated before that. Can you figure out how to do it? How short can such sequence of moves be if the amazon starts at <i>a1</i>?<br /><br />Thanks for reading, and check back next week!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/LGdOd1s_n6M" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2016/12/an-amazon-week.html