tag:blogger.com,1999:blog-19533250797934499712018-01-19T15:46:33.778+03:00Algorithms Weekly by Petr MitrichevPetr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.comBlogger343125PetrMitrichevhttps://feedburner.google.comtag:blogger.com,1999:blog-1953325079793449971.post-60810786266368224952018-01-15T00:32:00.000+03:002018-01-15T00:32:05.366+03:00An Um_nik 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/-CvofOhRiXd8/WlvF7X7Wo8I/AAAAAAAB80Y/j425zUJ8W2oRheJwgD6bGWslRZSMGraOACLcBGAs/s1600/hello2018top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="274" data-original-width="1106" height="158" src="https://1.bp.blogspot.com/-CvofOhRiXd8/WlvF7X7Wo8I/AAAAAAAB80Y/j425zUJ8W2oRheJwgD6bGWslRZSMGraOACLcBGAs/s640/hello2018top5.png" width="640" /></a></div>This week's contests shared one of the problemsetters — and the winner. On Monday, Codeforces hosted its Hello 2018 round (<a href="http://codeforces.com/contest/913">problems</a>, <a href="http://codeforces.com/contest/913/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/56992">analysis</a>). With the hardest problem having too much piecewise polynomial integration, the competition focused on the remaining seven. Only Um_nik could get them all, and even with 24 minutes to spare — congratulations!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-ztxD2wBTnxc/WlvFLlqvKgI/AAAAAAAB80Q/s6fv3UfXUzoxblK_WsUlnJT4xwXzAtjiwCLcBGAs/s1600/agc020top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="446" data-original-width="905" height="314" src="https://2.bp.blogspot.com/-ztxD2wBTnxc/WlvFLlqvKgI/AAAAAAAB80Q/s6fv3UfXUzoxblK_WsUlnJT4xwXzAtjiwCLcBGAs/s640/agc020top5.png" width="640" /></a></div>On Sunday, AtCoder Grand Contest 020 started <a href="https://atcoder.jp/post/171">the race to Japan</a> (<a href="https://agc020.contest.atcoder.jp/assignments">problems</a>, <a href="https://agc020.contest.atcoder.jp/standings#page_1">results</a>, top 5 on the left, <a href="https://youtu.be/6rFmqWl_RwA">my screencast</a>, <a href="https://img.atcoder.jp/agc020/editorial.pdf">analysis</a>). Once again the hardest problem by tourist was a tiny bit too hard (and I even solved it after the contest by integrating polynomials, probably inspired by the analysis of the previous contest), and once again Um_nik was way faster than everybody else on the remaining problems — big congratulations again!<br /><br />I found <a href="https://agc020.contest.atcoder.jp/tasks/agc020_c">problem C</a> quite cute. You are given <i>n</i><=2000 positive integers, each up to 2000. Consider all 2<sup>n</sup>-1 nonempty subsets, and compute the sum of the numbers in each subset. Now sort those sums, and find the median sum — the 2<sup>n-1</sup>-th in the sorted order. You need to output this median sum. Time limit is 2 seconds.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-u4HjmJRYhmY/WlvME4BS8jI/AAAAAAAB804/pfJxX291iLgQjEjHpAVce5B1bESvjhipgCLcBGAs/s1600/IMG_20180106_134848.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1165" data-original-width="1600" height="466" src="https://1.bp.blogspot.com/-u4HjmJRYhmY/WlvME4BS8jI/AAAAAAAB804/pfJxX291iLgQjEjHpAVce5B1bESvjhipgCLcBGAs/s640/IMG_20180106_134848.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2018/01/an-otherland-week.html">my last post</a> I've discussed what was arguably <a href="http://codeforces.com/gym/101611/problem/E">the hardest contest problem</a> of 2017: you are given an undirected graph with at most 200000 vertices and edges. Your goal is to split its vertices into four disjoint groups A, B, C, D in such a way that:<br /><ul style="text-align: left;"><li>The subgraph formed by groups A+B is connected and has at least 2 vertices.</li><li>The subgraph formed by groups C+D is connected and has at least 2 vertices.</li><li>Each vertex in A has an edge to each vertex in C.</li><li>There are no other edges between subgraphs A+B and C+D.</li></ul>If there are many possible solutions, you need to output any one of them.<br /><br />Thanks to great ideas and pointers by Swistakk, mnbvmar and lewin, we were able to put together a O(<i>n*</i>log<i>n</i>) solution — you can check it out in <a href="http://codeforces.com/blog/entry/56977?#comment-406180">this comment thread</a>.<br /><br />Thanks for reading, and check back next week!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/qeYbQW_151s" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2018/01/an-umnik-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-1039776478056843932018-01-08T01:37:00.001+03:002018-01-08T01:37:52.851+03:00An Otherland 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/-i7OFSaWC9b0/WlKgbzS90mI/AAAAAAAB8qI/wKk5N-WuvvIE3cAT6G3cOuu2OmdRkLQYQCKgBGAs/s1600/IMG_20180107_233307.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1104" data-original-width="1600" height="275" src="https://1.bp.blogspot.com/-i7OFSaWC9b0/WlKgbzS90mI/AAAAAAAB8qI/wKk5N-WuvvIE3cAT6G3cOuu2OmdRkLQYQCKgBGAs/s400/IMG_20180107_233307.jpg" width="400" /></a></div>The first week of 2018 was quite calm, with the most devoted taking stabs at the still-ongoing <a href="https://contest.yandex.com/newyear2018/contest/7006/standings/">Prime New Year contest</a> by snarknews. Only one problem remains unsolved there, and it looks like it might take some team effort to crack it. I think it's within the spirit of the contest to discuss its problems publicly (after all, many even have analysis posted online), so I propose to do just that. Please skip the following paragraphs if you don't want spoilers!<br /><br /><a href="https://contest.yandex.com/newyear2018/contest/7006/problems/19/">The problem</a> goes like this: you are given an undirected graph with at most 200000 vertices and edges. Your goal is to split its vertices into four disjoint groups A, B, C, D in such a way that:<br /><ul style="text-align: left;"><li>The subgraph formed by groups A+B is connected and has at least 2 vertices.</li><li>The subgraph formed by groups C+D is connected and has at least 2 vertices.</li><li>Each vertex in A has an edge to each vertex in C.</li><li>There are no other edges between subgraphs A+B and C+D.</li></ul>If there are many possible solutions, you need to output any one of them.<br /><br />I have been thinking about the problem for some time, but only have the following not very helpful observations:<br /><ul style="text-align: left;"><li>If the graph has an articulation point, then we can take this point as set A, any of the components it separates as set B, and the rest as C+D. So we can assume the graph is vertex-biconnected.</li><li>The answer is not always "Yes" - the smallest counterexample is the graph with 4 vertices and 5 edges. This example also shows that if a biconnected graph has a vertex of degree 2, then this vertex and both adjacent vertices must be in the same half of our splitting, since both ends of a splitting edge must have degree of at least 3 (two splitting edges plus one inside the half).</li><li>There are also counterexamples without vertices of degree 2.</li><li>There might be some hashing trick involved. I.e., for example suppose we assign a random number <i>a<sub>i</sub></i> to each vertex, and compute for each vertex the value sum(<i style="font-style: italic;">a<sub>i</sub></i><i style="font-style: italic;">-a<sub>j</sub></i>), where the summation goes over all adjacent vertices <i>j</i>. Then if we add up those values within one half of the graph (A+B in the above terminology), then almost everything will cancel out, leaving us |C|*<i>a</i><sub>A</sub>-|A|*<i>a</i><sub>C</sub>, where <i>a</i><sub>A</sub> is the sum of <i>a<sub>i </sub></i>in A. But where to go from here?..</li></ul>Please share your ideas!<br /><div><br /><div><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-gA9fL0DOvW0/WlKfGDCJ5bI/AAAAAAAB8p0/RJjBvR772KkgH0Fy5iD8AVK9GOdMEwNSwCLcBGAs/s1600/IMG_20180106_123832.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1200" data-original-width="1600" height="480" src="https://4.bp.blogspot.com/-gA9fL0DOvW0/WlKfGDCJ5bI/AAAAAAAB8p0/RJjBvR772KkgH0Fy5iD8AVK9GOdMEwNSwCLcBGAs/s640/IMG_20180106_123832.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2017/12/best-problems-of-2017.html">my last post</a>, I have held a vote for the best problem of 2017. And the winner is <a href="https://agc018.contest.atcoder.jp/tasks/agc018_f">this AtCoder problem</a> by <a href="https://twitter.com/maroon_kuri">maroonrk</a>: you are given two rooted trees on the same set of 10<sup>5</sup> vertices. You need to assign integer weights to all vertices in such a way that for <i>each</i> subtree of <i>each</i> of the trees the sum of weights is either 1 or -1, or report that it's impossible. The solution is explained in <a href="http://petr-mitrichev.blogspot.com/2017/07/a-week-with-two-trees.html">this post</a>. Congratulations to the problemsetter and to AtCoder, and thanks to all problemsetters of 2017!<br /><br />Thanks for reading, and check back next week.</div></div></div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/T2pX8PrZ63k" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2018/01/an-otherland-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-43662458876712853732017-12-31T20:43:00.000+03:002017-12-31T20:43:21.135+03:00Best problems of 2017<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/-1QN3REiUF74/WkkhYnCWiVI/AAAAAAAB8L0/Ci5aAA70WoQl9Azw6HFUDYFXD29Dx9p1gCLcBGAs/s1600/IMG_20171216_120511.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="300" src="https://2.bp.blogspot.com/-1QN3REiUF74/WkkhYnCWiVI/AAAAAAAB8L0/Ci5aAA70WoQl9Azw6HFUDYFXD29Dx9p1gCLcBGAs/s400/IMG_20171216_120511.jpg" width="400" /></a></div>I have reviewed all problems I've highlighted this year in my blog, and also the problems sent by the readers in response to my question — thanks a lot for your input! I've distilled everything to a shortlist of five problems (in chronological order):<br /><br /><ul style="text-align: left;"><li>The Open Cup problem about interactively proving the pigeonhole principle, by <a href="http://codeforces.com/profile/tunyash">tunyash</a>, with solution in <a href="http://petr-mitrichev.blogspot.com/2017/05/a-zero-pigeon-week.html">this post</a>.</li><li>The AtCoder problem about moving two chips on a subset of a DAG, by <a href="http://codeforces.com/profile/sugim48">sugim48</a>, with solution in <a href="http://petr-mitrichev.blogspot.com/2017/07/a-dynamic-nimber-week.html">this post</a>.</li><li>The IPSC problem about picking optimal sequences of red and black cards to get the first match, by <a href="http://codeforces.com/profile/misof">misof</a>, with solution in <a href="http://petr-mitrichev.blogspot.com/2017/07/a-red-black-week.html">this post</a>.</li><li>The AtCoder problem about assigning numbers to shared vertices of two trees so that all subtrees sum to +-1, by <a href="http://codeforces.com/profile/maroonrk">maroonrk</a>, with solution in <a href="http://petr-mitrichev.blogspot.com/2017/07/a-week-with-two-trees.html">this post</a>.</li><li>The Open Cup problem about interactively exploring a maze on Mars with a communication delay, by <a href="http://codeforces.com/profile/gassa">Gassa</a>, discussed in <a href="http://petr-mitrichev.blogspot.com/2017/12/a-delayed-week.html">this post</a>. </li></ul><br />What is the best problem of 2017?<br /><iframe allowtransparency="true" frameborder="0" height="176px" name="poll-widget-1975279128869797257" src="https://www.google.com/reviews/polls/display/-1975279128869797257/blogger_template/run_app?txtclr=%23666666&lnkclr=%235588aa&chrtclr=%235588aa&font=normal+normal+100%25+Georgia,+Serif&hideq=true&purl=http://petr-mitrichev.blogspot.com/" style="border: none; width: 100%;"></iframe> <br /><div>As usual around New Year, <a href="http://codeforces.com/blog/snarknews">snarknews</a> is hosting the Prime New Year contest, which consists of problems given at top-level team competitions in 2017 but not solved by anybody there. If you like real challenge and don't have much to do during the holidays, here's <a href="https://contest.yandex.com/newyear2018/contest/7006/enter/">your link</a> :)<br /><br />Guten Rutsch!<br /><br /></div></div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/D9800lGJ3P4" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/12/best-problems-of-2017.htmltag:blogger.com,1999:blog-1953325079793449971.post-18946464027473545752017-12-31T00:06:00.000+03:002017-12-31T00:06:16.396+03:00A sparse 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/-CjcpnyxEKt0/WkfyOa_9D_I/AAAAAAAB8Ic/SEbicbD-LZ01WVhfYlcHpQM21bFiMLTCgCLcBGAs/s1600/goodbye2017top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="270" data-original-width="1104" height="156" src="https://4.bp.blogspot.com/-CjcpnyxEKt0/WkfyOa_9D_I/AAAAAAAB8Ic/SEbicbD-LZ01WVhfYlcHpQM21bFiMLTCgCLcBGAs/s640/goodbye2017top5.png" width="640" /></a></div>This week had the now traditional last contest of the year: Good Bye 2017 at Codeforces (<a href="http://codeforces.com/contest/908">problems</a>, <a href="http://codeforces.com/contest/908/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/56713">analysis</a>, <a href="https://youtu.be/I_dvna43rY0">my screencast</a>). The hardest problem H, after removing some layers, ended up being about finding a <a href="https://en.wikipedia.org/wiki/Graph_coloring#Vertex_coloring">proper vertex coloring</a> for a graph with <i>n</i><=23 vertices with the smallest number of colors. My first thought was: surely for such classical problem the best approaches are well-known? However, it turned out that the algorithms I could remember were a O(3<sup><i>n</i></sup>) subset dynamic programming and various heuristics to speed up backtracking, both of which seemed too slow. Thanks to <a href="http://www.wisdom.weizmann.ac.il/~dinuri/courses/11-BoundaryPNP/L01.pdf">this paper</a> I have now learned how to do this in O(<i>n</i>*2<sup><i>n</i></sup>), see point 4.2 "Inclusion-exclusion". Always nice to discover better approaches to classical problems!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-ASx3FWuA0f0/Wkf_dmdJLcI/AAAAAAAB8Jc/53-4Dum1fMwMT6FcOkEiRuDfNYRrgizrQCLcBGAs/s1600/IMG_20171217_191048.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1200" data-original-width="1600" height="480" src="https://4.bp.blogspot.com/-ASx3FWuA0f0/Wkf_dmdJLcI/AAAAAAAB8Jc/53-4Dum1fMwMT6FcOkEiRuDfNYRrgizrQCLcBGAs/s640/IMG_20171217_191048.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2017/12/a-quadratic-week.html">my previous summary</a>, I have mentioned a TopCoder problem: you are given <i>n</i>=2000000 tasks, to be done in <i>m</i>=2000 days, at most one task per day (so most of the tasks will end up not being done). For each task you know three numbers: the segment of days when it can be done (from <i>l<sub>i</sub></i> to <i>r<sub>i</sub></i>), and the profit <i>c<sub>i</sub></i> from doing it. You need to pick the task to be done in each day in such a way that the total profit is maximized.<br /><br />This can be naturally viewed as a weighted maximum matching problem, which thanks to <a href="http://petr-mitrichev.blogspot.com/2017/12/a-transversal-week.html">the transversal matroid</a> can be solved by trying to add tasks to the matching in decreasing order of profit, trying to find the augmenting path each time, and only resetting the "visited" state of each vertex once the matching is increased (this is called "Kuhn's algorithm" in the Russian-speaking community, but I couldn't find an authoritative link for it). Since the matching is only increased <i>m</i> times, we process each edge of the graph at most <i>m</i> times. The problem is that we have O(<i>n</i>*<i>m</i>) edges, so the total running time seems to be O(<i>n</i>*<i>m</i><sup>2</sup>). However, we can notice that for each task that we end up not adding to the matching we process its edges only once (since we will never visit it in subsequent iterations), so the number of actually revisited edges is O(<i>m</i><sup>2</sup>), and the running time is only O(<i>n</i>*<i>m+</i><i>m</i><sup>3</sup>), which is of course still too slow.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-EGDWp0P6jeY/Wkf-PgWSvoI/AAAAAAAB8JM/AwbzfJnAH9Aev6-t_Iz1r_bCiCxwVBAkwCKgBGAs/s1600/IMG_20171230_215810.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" data-original-height="857" data-original-width="1600" height="342" src="https://4.bp.blogspot.com/-EGDWp0P6jeY/Wkf-PgWSvoI/AAAAAAAB8JM/AwbzfJnAH9Aev6-t_Iz1r_bCiCxwVBAkwCKgBGAs/s640/IMG_20171230_215810.jpg" width="640" /></a></div>But now we can use another relatively standard trick: let's reduce the number of "active" edges from O(<i>m</i><sup>2</sup>) to O(<i>m*</i>log<i>m</i>) in the following manner: instead of a matching problem we'll now have a flow problem, and we'll add auxiliary vertices between left and right parts. The vertices will correspond to segments. First, we'll pick the middle point <i>b</i>=<i>m</i>/2, and add vertices corresponding to segments [1,<i>b</i>], [2,<i>b</i>], ..., [<i>b</i>-1,<i>b</i>], [<i>b</i>,<i>b</i>], and infinite capacity edges in this manner: [1,<i>b</i>]->[2,<i>b</i>]->...->[<i>b</i>,<i>b</i>]; [1,<i>b</i>]->1; [2,<i>b</i>]->2; ..., [<i>b</i>,<i>b</i>]-><i>b</i>. The idea is that if we add an edge from some vertex in the left part to a segment [<i>a</i>,<i>b</i>], then the flow can then go to any vertex in the right part between <i>a</i> and <i>b</i> using those infinite edges, and only to those vertices. We handle the other half in a similar way: [<i>b</i>+1,<i>b</i>+1]<-[<i>b</i>+1,<i>b</i>+2]<-...<-[<i>b</i>+1,<i>m-1</i>]<-[<i>b</i>+1,<i>m</i>]. These two sets of segments already allow to handle any task that can be done in days <i>b</i> and <i>b</i>+1 using only two edges: to [<i>l<sub>i</sub></i>,<i>b</i>] and to [<i>b</i>+1,<i>r<sub>i</sub></i>].<br /><br />We can then apply the same procedure recursively to segments [1,<i>b</i>] and [<i>b</i>+1,<i>m</i>]: for example, we'll pick the middle point <i>c</i>=<i>b</i>/2, and build the auxiliary vertices [1,<i>c</i>]->[2,<i>c</i>]->...->[<i>c</i>,<i>c</i>] and [<i>c</i>+1,<i>c</i>+1]<-[<i>c</i>+1,<i>c</i>+2]<-...<-[<i>c</i>+1,<i>b</i>], and so on. Overall we'll have log<i>m</i> sets of <i>m</i> auxiliary vertices each (one per level of recursion), with two outgoing edges for each vertex, and every task can now be handled with at most two edges to auxiliary vertices instead of O(<i>m</i>) edges to the right part. This approach resembles the centroid decomposition of a tree when applied to a chain; we could also have used the sparse table to achieve the same result.<br /><br />Now our graph has O(<i>m</i>log<i>m</i>) active edges, and additional O(<i>n</i>) edges that are visited only once, so the total running time is O(<i>n</i>+<i>m</i><sup>2</sup>*log<i>m</i>), which is fast enough.<br /><br />That's it for the contests of 2017 — thanks for reading, and check back tomorrow (hopefully) for the best problems of 2017!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/wzWFDtvO31E" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/12/a-sparse-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-87234728919840945702017-12-30T23:03:00.002+03:002017-12-31T00:17:29.290+03:00A quadratic 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/-BgQ1L6gYBMI/WkfiKSoPFsI/AAAAAAAB8Hk/KPs0Ny1Djxwf_NeC85Ax7V_5Arz1R_RngCLcBGAs/s1600/cf453top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="273" data-original-width="1103" height="158" src="https://1.bp.blogspot.com/-BgQ1L6gYBMI/WkfiKSoPFsI/AAAAAAAB8Hk/KPs0Ny1Djxwf_NeC85Ax7V_5Arz1R_RngCLcBGAs/s640/cf453top5.png" width="640" /></a></div>Last week had a relatively high density of contests, so much that two of them collided: Codeforces Round 453 and TopCoder SRM 726 took place at the same time on Tuesday. The Codeforces round started 25 minutes earlier, so we'll begin with it (<a href="http://codeforces.com/contest/901">problems</a>, <a href="http://codeforces.com/contest/901/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/56478">analysis</a>). dotorya had chosen a seemingly suboptimal order to solve the first four problems, as A and B required disproportionately much time relative to their value, but he was faster than the competition and thus still ended up in first place — well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-7ED5pgjKFxw/WkfjRHRAlGI/AAAAAAAB8Hw/BXZ5kLBwazcZ9VaAAvu-jw0k3XVPhbFBgCLcBGAs/s1600/srm726top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="94" data-original-width="629" src="https://3.bp.blogspot.com/-7ED5pgjKFxw/WkfjRHRAlGI/AAAAAAAB8Hw/BXZ5kLBwazcZ9VaAAvu-jw0k3XVPhbFBgCLcBGAs/s1600/srm726top5.png" /></a></div>TopCoder SRM 726 at roughly the same time attracted the second half of the community (<a href="https://community.topcoder.com/stat?c=round_overview&rd=17048">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17048&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://youtu.be/BG2tGOJmjO0">my screencast</a>). <a href="https://community.topcoder.com/stat?c=problem_statement&pm=14750&rd=17048&rm=330805&cr=10574855">The hard problem</a> has proved decisive: you are given 2000000 tasks, to be done in 2000 days, at most one task per day (so most of the tasks will end up not being done). For each task you know three numbers: the segment of days when it can be done (from <i>l<sub>i</sub></i> to <i>r<sub>i</sub></i>), and the profit <i>c<sub>i</sub></i> from doing it. You need to pick the task to be done in each day in such a way that the total profit is maximized. This is naturally reduced to a weighted maximum matching problem, but surely it will time out with 2 million vertices in the graph — or will it?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-ZJZ3GwzJPMo/Wkflgqm7RhI/AAAAAAAB8H8/AMDXQa2ghuExhMCLI4xlblsy04TSrlCWACLcBGAs/s1600/cf454top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="273" data-original-width="1114" height="156" src="https://1.bp.blogspot.com/-ZJZ3GwzJPMo/Wkflgqm7RhI/AAAAAAAB8H8/AMDXQa2ghuExhMCLI4xlblsy04TSrlCWACLcBGAs/s640/cf454top5.png" width="640" /></a></div>Codeforces ran another round, Round 454, on Saturday (<a href="http://codeforces.com/contest/906">problems</a>, <a href="http://codeforces.com/contest/906/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/56601">analysis</a>). All problems were tractable this time for moejy0viiiiiv and Radewoosh, and in case of the former with 30 minutes to spare. Congratulations on the victory!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-O6RDnkfTK3Y/Wkfw8Ps4XpI/AAAAAAAB8IQ/CoX1NzlWcGoAueteM_XN-OUz8CLPq3wxACLcBGAs/s1600/IMG_20171216_120459.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/-O6RDnkfTK3Y/Wkfw8Ps4XpI/AAAAAAAB8IQ/CoX1NzlWcGoAueteM_XN-OUz8CLPq3wxACLcBGAs/s640/IMG_20171216_120459.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2017/12/a-newton-week.html">my previous summary</a>, I have mentioned an Open Cup problem: you are given an integer <i>n</i> with at most a million digits. You need to determine if it's a perfect square or not. You don't need to actually find the square root.<br /><br />As is often the case in problems with a Yes/No answer, it suffices to find an algorithm that always finds one of the two answers correctly, and the other with a certain probability that is greater than zero. We can then apply it repeatedly until the probability of not finding the correct answer is exponentiated to become essentially zero.<br /><br />Let's pick a prime number <i>p</i>. If n is a perfect square, then <i>n</i> mod <i>p</i> is always a quadratic residue. If not, then assuming <i>p</i> is picked randomly the probability of <i>n</i> mod <i>p</i> being a quadratic residue is roughly 0.5, since roughly half of all numbers mod <i>p</i> are quadratic residues (this is merely handwaving; can anyone prove this probability estimation formally?).<br /><br />So we can pick, say, 30 random prime numbers, and check if <i>n</i> is a quadratic residue modulo each of them. If at least one says no, then the overall answer is no, otherwise it's yes. Checking if a number is a quadratic residue modulo p is done by checking if <i>n</i><sup>(<i>p</i>-1)/2</sup>=1 (mod <i>p</i>).<br /><br />Thank for reading, and check back for this week's summary!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/zOEzhkZBcqU" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/12/a-quadratic-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-52504790878233327282017-12-30T21:33:00.000+03:002017-12-30T21:33:24.868+03:00A Newton 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/-ntOrf0Qgp64/WkfZYL4kFKI/AAAAAAAB8HU/-3q0rDW5XswSl9Pi3X7okCh4xlrxBnkOwCLcBGAs/s1600/oc1718peterhoftop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="269" data-original-width="849" height="202" src="https://1.bp.blogspot.com/-ntOrf0Qgp64/WkfZYL4kFKI/AAAAAAAB8HU/-3q0rDW5XswSl9Pi3X7okCh4xlrxBnkOwCLcBGAs/s640/oc1718peterhoftop5.png" width="640" /></a></div>The Dec 11 - Dec 17 week contained the last Open Cup round of the year: the Grand Prix of Peterhof (<a href="http://opencup.ru/files/oci/gp9/problems1-e.pdf">problems</a>, <a href="http://opencup.ru/index.cgi?data=macros/stage&head=index&menu=index&stg=9&region=main&ncup=oci&class=oci">results</a>, top 5 on the left). The deciding problem H required the ability to find the exponent a formal series fast, and the teams that were able to do so claimed the first two places — congratulations to the Moscow IPT team and to SPb Havka-papstvo!<br /><br />I found the relatively easy problem J very nice. You are given an integer with at most a million digits. You need to determine if it's a perfect square or not. You don't need to actually find the square root. Can you see how to get this problem accepted on the 8th minute of the contest?<br /><br />Thanks for reading, and check back soon!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/zHAamKHEpS8" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/12/a-newton-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-85839071069456912642017-12-30T20:45:00.000+03:002017-12-30T20:45:01.492+03:00A correlation 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/-440xu7Mlzr4/WkfQaZfThGI/AAAAAAAB8HE/tsojKOjOXJstuaTnAyuxEbzjnhVmmqgkACLcBGAs/s1600/IMG_20171211_151032.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1200" data-original-width="1600" height="480" src="https://1.bp.blogspot.com/-440xu7Mlzr4/WkfQaZfThGI/AAAAAAAB8HE/tsojKOjOXJstuaTnAyuxEbzjnhVmmqgkACLcBGAs/s640/IMG_20171211_151032.jpg" width="640" /></a></div>The Dec 4 - Dec 10 week was another of the calm ones, so let's use this post to discuss the interactive NEERC problem I mentioned in <a href="http://petr-mitrichev.blogspot.com/2017/12/a-timing-week.html">the previous one</a>: you work with a device that takes an <i>a</i> as input and computes <i>a</i><sup><i>d</i></sup> mod <i>n</i> using the following pseudocode:<br /><br /><span style="font-family: "courier new" , "courier" , monospace;">1 modPow(a, d, n) {</span><br /><span style="font-family: "courier new" , "courier" , monospace;">2 r = 1;</span><br /><span style="font-family: "courier new" , "courier" , monospace;">3 for (i = 0; i < 60; ++i) {</span><br /><span style="font-family: "courier new" , "courier" , monospace;">4 if ((d & (1 << i)) != 0) {</span><br /><span style="font-family: "courier new" , "courier" , monospace;">5 r = r * a % n;</span><br /><span style="font-family: "courier new" , "courier" , monospace;">6 }</span><br /><span style="font-family: "courier new" , "courier" , monospace;">7 a = a * a % n;</span><br /><span style="font-family: "courier new" , "courier" , monospace;">8 }</span><br /><span style="font-family: "courier new" , "courier" , monospace;">9 }</span><br /><div><br /></div><div>However, instead of receiving the result of the computation, you only receive the <i>time</i> it took the device to execute it, which is computed in the following way: only the multiplications on lines 5 and 7 take nonzero time, and multiplying <i>x</i> by <i>y</i> modulo <i>n</i> takes (bits(<i>x</i>)+1)*(bits(<i>y</i>)+1), where bits(<i>x</i>) is the length of the binary representation of <i>x</i> without leading zeroes.</div><div><br /></div><div>You know the number <i>n</i> but not the number <i>d</i>, and your goal is to find <i>d</i> after sending at most 30000 requests to the device. You know that <i>n</i> and <i>d</i> were chosen in the following way: first, two prime numbers <i>p</i> and <i>q </i>with bits(<i>p</i>)=bits(<i>q</i>)=30 were picked independently and uniformly at random. Then <i>n</i> was computed as <i>p</i>*<i>q</i>. Then the number <i>m</i>=(<i>p</i>-1)*(<i>q</i>-1) was computed. Then <i>d</i> was picked uniformly at random between 1 and <i>m</i>-1 inclusive, such that it is coprime with <i>m</i>.<br /><br /><a href="http://neerc.ifmo.ru/archive/2017/neerc-2017-analysis.pdf">The official analysis</a> has a pretty detailed description of the intended solution starting from page 8, so let me just recap it here briefly;<br /><ul style="text-align: left;"><li>We're going to just send 30000 random queries.</li><li>Lowest bit of d is always 1, let's determine the second lowest.</li><li>If it's also 1, then we multiply <i>a</i> by <i>a</i><sup>2</sup>, otherwise we don't.</li><li>For queries where <i>a</i> and/or <i>a</i><sup>2 </sup>have less bits than usual, the overall modPow time will also be less than usual, but only on average, so we can't just tell from one <i>a</i>.</li><li>However, the correlation between the time to multiply <i>a</i> by <i>a</i><sup>2</sup> and the overall modPow time over all 30000 queries can tell us this bit with extremely high certainty.</li><li>We can then determine the next bit in the same manner, and so on.</li><li><a href="https://en.wikipedia.org/wiki/Timing_attack#Examples">This Wikipedia page</a> also describes the same idea.</li></ul>This solution is very easy to code and generalizes well to bigger constraints, but it might be hard to intuitively feel if 30000 queries gives enough certainty. Egor has suggested another approach which is a bit harder to code but easier to believe that it works (but we have not actually tried to implement it): instead of sending random queries, we will send queries such that one repeated square of them is very small modulo <i>n</i>, say, at most 10 bits. Such a query will give much more signal on whether this repeated square is used in the multiplications, since multiplying 10 by 60 bits, compared to multiplying 60 by 60 bits, is about 3000 nanoseconds faster, and standard deviation of modPow computation time if we just feed it random inputs is on the order of 1700, so the middle point is roughly one standard deviation away from each expectation. If we try, say, 49 such numbers for every bit, then we'll have seven standard deviations and will always guess correctly, so we need only 60*49 which is about 3000 queries to find all bits.<br /><br />Of course, finding a number that has few bits in a certain power modulo <i>n</i> is a hard task in itself, but here <i>n</i> is small enough that we can factorize it using <a href="https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm">Pollard's rho</a> algorithm, and after that we just need to invert the said power modulo phi(<i>n</i>) to be able to find the root of this power of any number, including ones with few bits.<br /><br />Thanks for reading, and check back for more!</div></div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/UksLI8hNvcs" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/12/a-correlation-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-88068206679876038102017-12-30T14:35:00.001+03:002017-12-30T14:35:45.078+03:00A timing 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/-dUhoGkV-_Rw/Wkdrlj0FVrI/AAAAAAAB8GY/dIaEBVjXB1QFmas9dCvrdF-Y1NjWx631wCLcBGAs/s1600/srm724top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="97" data-original-width="629" src="https://3.bp.blogspot.com/-dUhoGkV-_Rw/Wkdrlj0FVrI/AAAAAAAB8GY/dIaEBVjXB1QFmas9dCvrdF-Y1NjWx631wCLcBGAs/s1600/srm724top5.png" /></a></div>The Nov 27 - Dec 3 week started with TopCoder SRM 724 (<a href="https://community.topcoder.com/stat?c=round_overview&rd=17033">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17033&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left). snuke, sugim48 and Swistakk had more coding phase points but this round was ultimately decided during the challenge phase, as <a href="https://community.topcoder.com/stat?c=problem_statement&pm=14744&rd=17033">the easy problem</a> allowed for a lot of incorrect approaches.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-6DpliuaCFZs/WkdvQSLQ99I/AAAAAAAB8Gk/Nl2TM6u8vMgxORcmTU7OCY_pa_JvozsCQCLcBGAs/s1600/cf449top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="269" data-original-width="1106" height="154" src="https://1.bp.blogspot.com/-6DpliuaCFZs/WkdvQSLQ99I/AAAAAAAB8Gk/Nl2TM6u8vMgxORcmTU7OCY_pa_JvozsCQCLcBGAs/s640/cf449top5.png" width="640" /></a></div>On Saturday, Codeforces Round 449 gave ACM ICPC 2017-18 NEERC contestants the last chance to practice, although I'm not sure if many of them did (<a href="http://codeforces.com/contest/896">problems</a>, <a href="http://codeforces.com/contest/896/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/56135">analysis</a>). In a somewhat unusual outcome, MrDindows has won the round with less problems than the second place, thanks to an extremely fast solution to the hardest problem — congratulations on the victory!<br /><br />He's managed to pull this off thanks to being able to squeeze a "naive" quadratic solution under the time limit in <a href="http://codeforces.com/contest/896/problem/E">a problem</a> with <i>n</i>=100000. This is no small feat, as demonstrated by the fact that just one other contestant was able to do it at all, even within the full two hours. Thankfully he <a href="http://codeforces.com/blog/entry/56101?#comment-398797">has explained</a> how he was able to achieve this, so that we all can learn the tricks and/or deepen our understanding of compilers!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-EehJGiSQ-5Q/Wkd2adQIOLI/AAAAAAAB8G0/o86jfgiFkFk4j_2YAWSQRilj24Xm7P6dwCLcBGAs/s1600/neerc2017top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="268" data-original-width="1184" height="144" src="https://4.bp.blogspot.com/-EehJGiSQ-5Q/Wkd2adQIOLI/AAAAAAAB8G0/o86jfgiFkFk4j_2YAWSQRilj24Xm7P6dwCLcBGAs/s640/neerc2017top5.png" width="640" /></a></div>On Sunday, the said ACM ICPC 2017-18 NEERC took place in St Petersburg (<a href="https://neerc.ifmo.ru/archive/2017/neerc-2017-statement.pdf">problems</a>, <a href="https://neerc.ifmo.ru/archive/2017/standings.html">results</a>, top 5 on the left, <a href="https://neerc.ifmo.ru/archive/2017/neerc-2017-analysis.pdf">analysis</a>, <a href="https://youtu.be/X9OLK-2Zwg8">broadcast in Russian</a>). The competition was very tight, and Moscow IPT 1 team has earned the first place with 10 minutes to go, in no small part thanks to solving the tricky problem K with just two attempts, whereas the only two other teams to get it accepted required 10 and 14 attempts. Congratulations!<br /><br />I have set problem H for this round, which was unfortunately the only one left unsolved. This is an interactive problem where you work with a device that takes an <i>a</i> as input and computes <i>a</i><sup><i>d</i></sup> mod <i>n</i> using the following pseudocode:<br /><br /><span style="font-family: Courier New, Courier, monospace;">1 modPow(a, d, n) {</span><br /><span style="font-family: Courier New, Courier, monospace;">2 r = 1;</span><br /><span style="font-family: Courier New, Courier, monospace;">3 for (i = 0; i < 60; ++i) {</span><br /><span style="font-family: Courier New, Courier, monospace;">4 if ((d & (1 << i)) != 0) {</span><br /><span style="font-family: Courier New, Courier, monospace;">5 r = r * a % n;</span><br /><span style="font-family: Courier New, Courier, monospace;">6 }</span><br /><span style="font-family: Courier New, Courier, monospace;">7 a = a * a % n;</span><br /><span style="font-family: Courier New, Courier, monospace;">8 }</span><br /><span style="font-family: Courier New, Courier, monospace;">9 }</span><br /><div><br /></div><div>However, instead of receiving the result of the computation, you only receive the <i>time</i> it took the device to execute it, which is computed in the following way: only the multiplications on lines 5 and 7 take nonzero time, and multiplying <i>x</i> by <i>y</i> modulo <i>n</i> takes (bits(<i>x</i>)+1)*(bits(<i>y</i>)+1), where bits(<i>x</i>) is the length of the binary representation of <i>x</i> without leading zeroes.</div><div><br /></div><div>You know the number <i>n</i> but not the number <i>d</i>, and your goal is to find <i>d</i> after sending at most 30000 requests to the device. You know that <i>n</i> and <i>d</i> were chosen in the following way: first, two prime numbers <i>p</i> and <i>q </i>with bits(<i>p</i>)=bits(<i>q</i>)=30 were picked independently and uniformly at random. Then <i>n</i> was computed as <i>p</i>*<i>q</i>. Then the number <i>m</i>=(<i>p</i>-1)*(<i>q</i>-1) was computed. Then <i>d</i> was picked uniformly at random between 1 and <i>m</i>-1 inclusive, such that it is coprime with <i>m</i>.</div><div><br /></div><div>Surprisingly, just knowing the time the computation takes for a few requests is enough to extract the value of <i>d</i>. Can you see how to do it?</div><div><br /></div><div>Thanks for reading, and check back later today!</div><div><br /></div></div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/c3EUKspB0sc" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/12/a-timing-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-58782618145675052552017-12-28T02:16:00.000+03:002017-12-28T02:16:10.344+03:00A directly opposite 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/-Jg4Gi9_Hddo/WkQeQgjTlrI/AAAAAAAB8Do/Vifg8cl6AyYcunZ6gK2xynX7J2A4ZYN9ACLcBGAs/s1600/codefestival2017finaltop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="446" data-original-width="1175" height="242" src="https://4.bp.blogspot.com/-Jg4Gi9_Hddo/WkQeQgjTlrI/AAAAAAAB8Do/Vifg8cl6AyYcunZ6gK2xynX7J2A4ZYN9ACLcBGAs/s640/codefestival2017finaltop5.png" width="640" /></a></div>Code Festival 2017 onsite for university students and recent graduates ran by AtCoder was the biggest event of the Nov 20 - Nov 26 week. It consisted of multiple rounds, but the main and rated one was the Final (<a href="https://cf17-final.contest.atcoder.jp/assignments">problems</a>, <a href="https://cf17-final.contest.atcoder.jp/standings">results</a>, top 5 on the left, <a href="https://cf17-final-open.contest.atcoder.jp/standings">parallel round results</a>, <a href="https://img.atcoder.jp/cf17-final/editorial.pdf">analysis</a>). The problemset has provided a lot of variety, and the people at the top had quite different sets of problems solved. tourist was quite a bit faster than others — big congratulations on the victory!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-7AavdkkTqyo/WkQkErixhdI/AAAAAAAB8EI/hln8ebIHmjIixYAyXrldv7qgx0g-oJSCgCLcBGAs/s1600/oc1718europetop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="269" data-original-width="907" height="188" src="https://2.bp.blogspot.com/-7AavdkkTqyo/WkQkErixhdI/AAAAAAAB8EI/hln8ebIHmjIixYAyXrldv7qgx0g-oJSCgCLcBGAs/s640/oc1718europetop5.png" width="640" /></a></div>The Open Cup continued its weekly cadence with the Grand Prix of Europe on Sunday (<a href="http://opencup.ru/files/oci/gp8/problems1-e.pdf">problems</a>, <a href="http://opencup.ru/index.cgi?data=macros/stage&head=index&menu=index&stg=8&region=main&ncup=oci&class=oci">results</a>, top 5 on the left, <a href="http://cerc.hsin.hr/index.php?page=results">CERC results on the same problems</a>). Team japan02 had 10 problems solved even before the last hour, but could not make further progress and allowed ITMO 1 to steal the victory with two minutes to go — congratulations to both teams solving 10 problems, and to the Warsaw team who got 10 at the onsite round, also with a last-minute accepted submission!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-KbSic0d8ugU/WkQpeYMyANI/AAAAAAAB8Eg/L36wDdH5yjUfYn2nbfp0pVcyu-nN0Ph3gCLcBGAs/s1600/IMG_20171211_155643.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1127" data-original-width="1600" height="450" src="https://3.bp.blogspot.com/-KbSic0d8ugU/WkQpeYMyANI/AAAAAAAB8Eg/L36wDdH5yjUfYn2nbfp0pVcyu-nN0Ph3gCLcBGAs/s640/IMG_20171211_155643.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2017/12/a-test-driven-week.html">my previous summary</a>, I have mentioned an interactive Open Cup problem happening on the faces of a cube with each face divided into <i>n</i> times <i>n</i> cells (<i>n</i><=300). You are located on some cell on some face of the cube, facing one of the four cardinal directions, and your goal is located on some cell on some face of the cube, but you don't know where you are located and where the goal is located. All you can do is to issue commands left, right or forward, with the first two causing you to rotate in place by 90 degrees, and the last one causing you to move one cell in the direction you're facing, with moving through the sides of the cube handled in the natural way. For each move forward, the system tells you whether your new cell is closer, farther or at the same distance from the goal as the old one. The distance is defined as the Euclidean distance between the centers of the cells. You need to stop moving at the goal cell after using at most 100<i>n</i> commands.<br /><br />The solution that we got accepted looked like this: first, we try to move closer to the goal whenever we can, until we reach a cell from which all four moves don't give us a "closer" reply. This can be coded with a simple loop without the need to remember the coordinates or to even represent the sides of the cube, and will always converge in O(<i>n</i>) steps.<br /><br />Then, we're either in the goal cell or in the cell directly opposite it on the opposite face. We don't know the size of the cube, but even without it in order to transition from one to the other we can walk forward while we're not seeing a "closer" answer, and then keep moving forward while we're seeing "closer" answer. If we were in the opposite cell, we will reach the goal. If we were in the goal, then we'll either be in the opposite cell, or in the goal again after making a full loop. To distinguish the cases, we can compare the number of moves in the "not closer" state to the number of moves in the "closer" state. In case the former is bigger than the latter, we started our forward walk in the goal, and we will undo all those moves to go back to the goal. In case the latter is bigger, we're done.<br /><br />It takes some case studying and convincing oneself that this approach works in various corner cases as well, but after that the actual implementation is just a few lines.<br /><br />Thanks for reading, and check back for more!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/6y-uwELIgeI" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/12/a-directly-opposite-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-71422608987398029542017-12-27T02:09:00.002+03:002017-12-27T02:09:48.780+03:00A test-driven 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/-DWYH8gR_feU/WkLJMXBdlEI/AAAAAAAB744/tpnculTqIbENFRzkBIRVLC7GPnhMoI6ZACLcBGAs/s1600/cf446top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="273" data-original-width="1102" height="158" src="https://2.bp.blogspot.com/-DWYH8gR_feU/WkLJMXBdlEI/AAAAAAAB744/tpnculTqIbENFRzkBIRVLC7GPnhMoI6ZACLcBGAs/s640/cf446top5.png" width="640" /></a></div>The Nov 13 - Nov 19 week had one each of the usual suspects. First off, Codeforces Round 446 took place on Friday (<a href="http://codeforces.com/contest/891">problems</a>, <a href="http://codeforces.com/contest/891/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/55841">analysis</a>). moejy0viiiiiv has earned his first place at the very last minute of the contest by solving D — very well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-n8xe5lZWnpA/WkLKARHwOrI/AAAAAAAB75A/iug9aUSHJsYDex_LDC_udLjEB8rM78T6gCLcBGAs/s1600/srm723top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="149" data-original-width="775" height="122" src="https://3.bp.blogspot.com/-n8xe5lZWnpA/WkLKARHwOrI/AAAAAAAB75A/iug9aUSHJsYDex_LDC_udLjEB8rM78T6gCLcBGAs/s640/srm723top5.png" width="640" /></a></div>Then, TopCoder SRM 723 happened on Saturday (<a href="https://community.topcoder.com/stat?c=round_overview&rd=17027">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17027&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://www.topcoder.com/blog/single-round-match-723-editorials/">analysis</a>, <a href="https://youtu.be/PDtOOwQcgco">my screencast</a>). Only ksun48 was able to solve the hard problem, but it took him so long that his score was on par with scores people got for their medium problem, and the first place was decided during the challenge phase.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-5WNuqsAA0TY/WkLKbCwS60I/AAAAAAAB75E/-wlX0x3qBagFiFELFQNytPfkhGP_mtk5wCLcBGAs/s1600/oc1718siberiatop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="271" data-original-width="959" height="180" src="https://2.bp.blogspot.com/-5WNuqsAA0TY/WkLKbCwS60I/AAAAAAAB75E/-wlX0x3qBagFiFELFQNytPfkhGP_mtk5wCLcBGAs/s640/oc1718siberiatop5.png" width="640" /></a></div>And finally, the Open Cup Grand Prix of Siberia wrapped up the week on Sunday (<a href="http://opencup.ru/files/oci/gp7/problems1-e.pdf">problems</a>, <a href="http://opencup.ru/index.cgi?data=macros/stage&head=index&menu=index&stg=7&region=main&ncup=oci&class=oci">results</a>, top 5 on the left). Team Past Glory has continued their streak which is now up to 4 consecutive victories, this one by a mere 29 penalty minutes. Well done!<br /><br />Problem 2 in this round is a good example of a problem that is not so hard to solve in some way, but is harder to solve in a way that is really easy to code without bugs. This is an interactive problem happening on the faces of a cube with each face divided into <i>n</i> times <i>n</i> cells (<i>n</i><=300). You are located on some cell on some face of the cube, facing one of the four cardinal directions, and your goal is located on some cell on some face of the cube, but you don't know where you are located and where the goal is located. All you can do is to issue commands left, right or forward, with the first two causing you to rotate in place by 90 degrees, and the last one causing you to move one cell in the direction you're facing, with moving through the sides of the cube handled in the natural way. For each move forward, the system tells you whether your new cell is closer, farther or at the same distance from the goal as the old one. The distance is defined as the Euclidean distance between the centers of the cells. You need to stop moving at the goal cell after using at most 100<i>n</i> commands. Which approach is the easiest to implement here?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-ZqzdkFV94lI/WkLWfWinC9I/AAAAAAAB75U/dBZx7mjRjcsDkjSdflZ_68NGT8K6N3L3QCLcBGAs/s1600/IMG_20171125_160311.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/-ZqzdkFV94lI/WkLWfWinC9I/AAAAAAAB75U/dBZx7mjRjcsDkjSdflZ_68NGT8K6N3L3QCLcBGAs/s640/IMG_20171125_160311.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2017/12/a-f5-week.html">my previous summary</a>, I have mentioned <a href="http://codeforces.com/contest/889/problem/C">a Codeforces problem</a>: how many permutations of size <i>n</i> have the following property: if you go from left to right, and keep track of the maximum seen so far, there will be no time where it will not change for <i>k</i> consecutive steps, except if it's already equal to <i>n</i>. <i>n</i> and <i>k</i> are up to a million, and the answer needs to be returned modulo 10<sup>9</sup>+7.<br /><br />First, let's come up with a standard but slow solution. We'll do dynamic programming that finds the number of such permutations of size <i>m</i><=<i>n</i> that the last element is the maximum and there's always an update to the maximum in each <i>k</i> consecutive steps when we go from left to right. In order to find this number, we iterate over the step <i>p</i> where the previous maximum appeared: it has to be between <i>m</i>-<i>k</i> and <i>m</i>-1. Then we need to multiply the answer for <i>p</i> by the number of ways to choose which <i>m</i>-<i>p-1</i> numbers out of <i>m-2</i> form the numbers on positions between <i>p</i>+1 and <i>m</i>-1, and in which order, which turns out to be simply (<i>m</i>-2)!/(<i>p</i>-1)!, so our final formula becomes:<br /><br />dp[<i>m</i>] = sum(dp[<i>p</i>]*(<i>m</i>-2)!/(<i>p</i>-1)!, <i>m</i>-<i>k</i><=<i>p</i><=<i>m</i>-1)<br /><br />This looks to be O(<i>n</i><sup>2</sup>), but we can now notice that (<i>m</i>-2)! can be moved outside the sum, and the remaining sum can be computed in O(1) if we store prefix sums of dp[<i>p</i>]/(<i>p</i>-1)!, bringing the overall running time to O(<i>n</i>).<br /><br />You can watch <a href="https://youtu.be/H9QhxYHcT8M?t=2h15m21s">as I code the solution in the screencast</a> to see my proposed way of implementing such solutions: start by implementing the quadratic approach, get it to pass the sample cases, then start implementing the optimizations one by one while keeping it passing the sample cases. One step that I did not make but should have is to also add a few random cases that are still small enough for the quadratic solution to handle to the samples, and make sure the outputs don't change on them while optimizing, too.<br /><br />Thanks for reading, and check back for more!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/ClTO_ycYe00" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/12/a-test-driven-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-20101208013169742862017-12-27T01:06:00.001+03:002017-12-27T01:06:44.084+03:00A F5 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/-onvEh4n_GfM/WkLCip-ogAI/AAAAAAAB74c/ZPeXzG7aqno72LexBDjWBZICykJwQKGWQCLcBGAs/s1600/oc1718ukrainetop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="269" data-original-width="901" height="190" src="https://2.bp.blogspot.com/-onvEh4n_GfM/WkLCip-ogAI/AAAAAAAB74c/ZPeXzG7aqno72LexBDjWBZICykJwQKGWQCLcBGAs/s640/oc1718ukrainetop5.png" width="640" /></a></div>The Nov 6 - Nov 12 week had two contests on Sunday. First off, it was time for the Open Cup Grand Prix of Ukraine (<a href="http://opencup.ru/files/oci/gp6/problems1-e.pdf">problems</a>, <a href="http://opencup.ru/index.cgi?data=macros/stage&head=index&menu=index&stg=6&region=main&ncup=oci&class=oci">results</a>, top 5 on the left). Team Past Glory has won their third Grand Prix in a row — what an amazing achievement! Both Moscow IPT Cryptozoology and japan02 teams were quite close and had real chances for the first place as well — congratulations, too!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-l3nmMyCaWR8/WkLEI8MefvI/AAAAAAAB74o/Jk-maSXAlwsKpwfFOXz9HNJvlNfZCMl0wCLcBGAs/s1600/cf445top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="269" data-original-width="1104" height="154" src="https://4.bp.blogspot.com/-l3nmMyCaWR8/WkLEI8MefvI/AAAAAAAB74o/Jk-maSXAlwsKpwfFOXz9HNJvlNfZCMl0wCLcBGAs/s640/cf445top5.png" width="640" /></a></div>A bit later, Codeforces hosted its Round 445 (<a href="http://codeforces.com/contest/889">problems</a>, <a href="http://codeforces.com/contest/889/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/55734">analysis</a>, <a href="https://youtu.be/H9QhxYHcT8M">my screencast</a>). V--o_o--V was way too fast and thus got an easy first place — great job!<br /><br />Somewhat surprisingly, <a href="http://codeforces.com/contest/889/problem/C">problem C</a> was the most difficult to solve (as opposed to implement) for me this round — you can probably find around 20 minutes of staring at its statement in the screencast during the moments I was trying to solve it on paper. It asked: how many permutations of size <i>n</i> have the following property: if you go from left to right, and keep track of the maximum seen so far, there will be no time where it will not change for <i>k</i> consecutive steps, except if it's already equal to <i>n</i>. <i>n</i> and <i>k</i> are up to a million, and the answer needs to be returned modulo 10<sup>9</sup>+7. Is it easy for you?<br /><br />Thanks for reading, and check back soon for the solution!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/vKLsQuCeu-I" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/12/a-f5-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-53728523736962384062017-12-27T00:34:00.001+03:002017-12-27T00:41:24.261+03:00An empty 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/-kYkz1BvkzoQ/WkLAGahAL8I/AAAAAAAB74Q/pD3gO3PwV-cObyVQEieSZUauItoTtM8KQCLcBGAs/s1600/IMG_20171122_134934.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1060" data-original-width="1600" height="422" src="https://2.bp.blogspot.com/-kYkz1BvkzoQ/WkLAGahAL8I/AAAAAAAB74Q/pD3gO3PwV-cObyVQEieSZUauItoTtM8KQCLcBGAs/s640/IMG_20171122_134934.jpg" width="640" /></a></div>There were no contests I'd like to mention during the Oct 30 - Nov 5 week, so let me use this summary for an audience question.<br /><br />I'm planning to finish all summaries for 2017 during this week, and then put together a shortlist of best problems of 2017 to my taste, chosen from the ones I've highlighted in my blog, just like <a href="http://petr-mitrichev.blogspot.com/2017/01/a-week-of-five.html">I did last year</a>. However, the "to my taste" criterion is more important to me than "highlighted in my blog", so if you think you know a 2017 problem that I'd like a lot, but which did not get mentioned in the blog, most likely because I solved less contests and thus saw less problems, please mention it in comments!<br /><br />I should also note that the New Year tradition of picking the best of the past year in competitive programming was pioneered and is still being pursued by Snarknews, so consider taking part in his (unfortunately, Russian-only, but maybe automatic translation is good enough these days?..) <a href="http://codeforces.com/blog/entry/56637">poll</a> as well!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/1xtLKze2yJw" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/12/an-empty-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-13059712095980294972017-12-23T22:30:00.000+03:002017-12-23T22:30:12.962+03:00A transversal 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/-Mdz2PL86Uyg/Wj6hMElWxbI/AAAAAAAB70M/cX9lWov9y2I_BDsGu1JpvXtEaW1ynvkYQCLcBGAs/s1600/tco17semi2top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="169" data-original-width="760" height="142" src="https://2.bp.blogspot.com/-Mdz2PL86Uyg/Wj6hMElWxbI/AAAAAAAB70M/cX9lWov9y2I_BDsGu1JpvXtEaW1ynvkYQCLcBGAs/s640/tco17semi2top5.png" width="640" /></a></div>The TopCoder Open onsite continued during the Oct 23 - Oct 29 week with Semifinal 2 on Monday (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=17017">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17017&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a> on the left, <a href="https://youtu.be/AqpjM86iZlc">our commentary</a>). Two contestants got the medium problem this time, tourist and ikatanic, and bcip was the third advancer thanks to fast time on the easy. Congratulations to all advancers!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-vfiPInkX7sg/Wj6i16w8ioI/AAAAAAAB70Y/gtbH4u33-iEnT-gMVfeTo_dCMBgl890dwCLcBGAs/s1600/tco17finaltop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="174" data-original-width="762" height="146" src="https://2.bp.blogspot.com/-vfiPInkX7sg/Wj6i16w8ioI/AAAAAAAB70Y/gtbH4u33-iEnT-gMVfeTo_dCMBgl890dwCLcBGAs/s640/tco17finaltop5.png" width="640" /></a></div>The final round of the TopCoder Open took place just 24 hours later (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=17018">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17018&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a> on the left, <a href="https://youtu.be/qrlDoP3JQkI">our commentary</a>). One again just two contestants have managed to solve two problems, and xudyh was quite a lot faster than rng_58. Congratulations on the TopCoder Open victory!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-GSz_iPr8iL0/Wj6kvJUXWPI/AAAAAAAB70k/CR_TTU5Z54snsAkVH2L9QwXkDhxQ122AACLcBGAs/s1600/cf443top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="273" data-original-width="1104" height="158" src="https://4.bp.blogspot.com/-GSz_iPr8iL0/Wj6kvJUXWPI/AAAAAAAB70k/CR_TTU5Z54snsAkVH2L9QwXkDhxQ122AACLcBGAs/s640/cf443top5.png" width="640" /></a></div>Codeforces Round 443 took place on Thursday (<a href="http://codeforces.com/contest/878">problems</a>, <a href="http://codeforces.com/contest/878/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/55435">analysis</a>). dotorya has dominated the proceedings, solving all problems in the end, but having enough points for a clear first place with just four of them. Amazing performance!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-wX4h9ZIMrls/Wj6lAB4-WrI/AAAAAAAB70o/wO2fC7BtwEMyuoSzuIzwwcaW9Q_rNTGQQCLcBGAs/s1600/oc1719easterntop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="270" data-original-width="918" height="188" src="https://1.bp.blogspot.com/-wX4h9ZIMrls/Wj6lAB4-WrI/AAAAAAAB70o/wO2fC7BtwEMyuoSzuIzwwcaW9Q_rNTGQQCLcBGAs/s640/oc1719easterntop5.png" width="640" /></a></div>On the weekend, the Open Cup Eastern Grand Prix took place (<a href="http://opencup.ru/files/oci/gp5/problems1-e.pdf">problems</a>, <a href="http://opencup.ru/index.cgi?data=macros/stage&head=index&menu=index&stg=5&region=main&ncup=oci&class=oci">results</a>, top 5 on the left). Five teams have solved all problems, and team Past Glory did it faster than everybody else. Well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-aU-42lmhaDM/Wj6ulrEZQMI/AAAAAAAB71M/QAz2OxnmZWUjfG_g76lozfaugzIjrC63wCLcBGAs/s1600/IMG_20171118_133041.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="989" data-original-width="1600" height="394" src="https://4.bp.blogspot.com/-aU-42lmhaDM/Wj6ulrEZQMI/AAAAAAAB71M/QAz2OxnmZWUjfG_g76lozfaugzIjrC63wCLcBGAs/s640/IMG_20171118_133041.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2017/12/an-extremely-formal-week.html">my previous summary</a>, I have mentioned <a href="http://codeforces.com/contest/875/problem/F">a Codeforces problem</a>: you are given a bipartite graph with at most 200000 vertices each each part. Each vertex in the left part has exactly two edges to different vertices in the right part. Each vertex in the left part also has a weight. You need to find the weight of the maximum weight matching in this graph (but you don't need to output the matching itself).<br /><br />First of all, we can find the maximum weight matching greedily, by trying to add the vertices in the left part in decreasing order of weight, since the set of left parts of matchings forms <a href="https://mathoverflow.net/a/96676">the transversal matroid</a>. How do we check if a vertex in the left part can be added to the matching without building the traditional augmenting path, which would be too slow in this problem? Since we don't need to build the matching itself, we will rely on <a href="https://en.wikipedia.org/wiki/Hall%27s_marriage_theorem#Graph_theoretic_formulation">the Hall's theorem</a>. Suppose we're adding a vertex <i>a</i> in the left part that is connected to vertices <i>b</i> and <i>c </i>in the right part. Consider the connected components of the graph formed by the right part plus the vertices in the left part which have been matched (whenever we can't match a vertex in the left part, we disregard it together with the adjacent edges). Each of those components has at least as many vertices in the right part as in the left part, since all vertices of the left part are matched. Moreover, if it has <i>k</i> vertices in the left part, then it has 2<i>k</i> edges, and since it also has at least <i>k</i> vertices in the right part, its total number of vertices is at least 2<i>k</i>. A connected graph with at least 2<i>k</i> vertices and 2<i>k</i> edges does not have that many possibilities: it either has exactly 2<i>k</i> vertices and has one cycle, or it has 2<i>k</i>+1 vertices and is a tree.<br /><br />We claim that we can add the vertex <i>a</i> to the matching if and only if one of the components corresponding to <i>b</i> and <i>c</i> is such a tree, so all we need to maintain in our solution is a set of connected components using a disjoint set union data structure, and the number of vertices in each part for each connected component.<br /><br />If both components corresponding to <i>b</i> and <i>c</i> are not trees, they have the same number of vertices in left and right parts, and the union of those components and vertex <i>a</i> has more vertices in the left part than in the right part, so the Hall's theorem tells us it's impossible to add <i>a</i> to the matching. If the component corresponding to say, <i>b</i>, is a tree, then let's prove it's possible to rearrange the matching inside this component in such a way that we can add <i>a</i> to the matching. Suppose it's impossible, then the Hall's theorem tells us that there exists a subset <i>U</i> of vertices of the left part of the component such that if <i>V</i> is the set of the right part vertices adjacent to <i>U</i>, then the size of <i>V</i> is equal to the size of <i>U</i>. If <i>U</i> has <i>k</i> vertices, then the graph formed by <i>U</i> and <i>V</i> has 2<i>k</i> vertices and 2<i>k</i> edges, which means that it has a cycle, which is a contradiction.<br /><br />Thanks for reading, and check back for more!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/96lJ3j5VUx8" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/12/a-transversal-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-79380877233585502442017-12-23T20:47:00.002+03:002017-12-23T20:47:43.722+03:00An extremely formal 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/-ACHgGKPJCAU/Wj6TNGMV-yI/AAAAAAAB7zg/Ghfxa-06HcovJvkA9w7xFdeknCNQLprMgCLcBGAs/s1600/cf441top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="274" data-original-width="1119" height="156" src="https://1.bp.blogspot.com/-ACHgGKPJCAU/Wj6TNGMV-yI/AAAAAAAB7zg/Ghfxa-06HcovJvkA9w7xFdeknCNQLprMgCLcBGAs/s640/cf441top5.png" width="640" /></a></div>The Oct 16 - Oct 22 week started with Codeforces Round 441 on Monday (<a href="http://codeforces.com/contest/875">problems</a>, <a href="http://codeforces.com/contest/875/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/55233">analysis</a>). fateice demonstrated impressive speed in solving 6 problems in 50 minutes only, good 20 minutes earlier than everybody else. Congratulations on the victory!<br /><br /><a href="http://codeforces.com/contest/875/problem/F">The problem F</a> in this round was quite nice: you are given a bipartite graph with at most 200000 vertices each each part. Each vertex in the left part has exactly two edges to different vertices in the right part. Each vertex in the left part also has a weight. You need to find the weight of the maximum weight matching in this graph (but you don't need to output the matching itself). Of course, the standard maximum matching algorithms would be quadratic or at least O(<i>n</i>*sqrt(<i>n</i>)) and thus too slow for this problem. How to solve it faster?<br /><div><br /></div><div><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-1Pl2_RhxEqU/Wj6UT8FOauI/AAAAAAAB7zo/4J_vXbjV1v4QrjFHp4zHeskieVTVVNr2wCLcBGAs/s1600/tco17semi1top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="174" data-original-width="777" height="142" src="https://2.bp.blogspot.com/-1Pl2_RhxEqU/Wj6UT8FOauI/AAAAAAAB7zo/4J_vXbjV1v4QrjFHp4zHeskieVTVVNr2wCLcBGAs/s640/tco17semi1top5.png" width="640" /></a></div>On Sunday, the onsite portion of TopCoder Open 2017 started with its Semifinal 1 (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=17016">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17016&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a> on the left). xudyh solved the medium problem in 25 minutes, while everybody else could not solve it at all — what a commanding performance! scott_wu and rng_58 also advanced to the finals thanks to fast times on the easy problem.<br /><div><br /></div><div></div><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-ZjgvvzgAGrg/Wj6Wm9EZyII/AAAAAAAB7z8/G4uYose41PAC3HpqDH4-X-2WwDvXBeeHACLcBGAs/s1600/IMG_20171114_145105.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1200" data-original-width="1600" height="480" src="https://3.bp.blogspot.com/-ZjgvvzgAGrg/Wj6Wm9EZyII/AAAAAAAB7z8/G4uYose41PAC3HpqDH4-X-2WwDvXBeeHACLcBGAs/s640/IMG_20171114_145105.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2017/12/a-delayed-week.html">my previous summary</a>, I have mentioned an Open Cup problem about formal proofs (<a href="http://opencup.ru/files/oci/gp4/problems-e.pdf">problem H here</a>): you are given an undirected connected graph with at most 73 vertices and 492 edges, and a desired parity for each vertex (either odd, denoted by 1, or even, denoted by 0). The sum of all parities is 1 modulo 2. You need to <i>prove</i> that there doesn't exist a subset of edges of the graph with the desired parity of the number of edges adjacent to each vertex. It would be easy to prove, as it is well known that the number of vertices of odd degree in any graph is always even. However, you're only interested in proofs stated in a specific form.<br /><br />Such proof is a sequence of <i>clauses</i>. Each clause is an "or" of zero or more <i>variables</i> and/or their negations. Each variable corresponds to an edge in the graph, and is true if we take this edge, and false otherwise. Each clause must be built in one of the three ways:<br /><ol style="text-align: left;"><li>In can be an <i>axiom</i>, which in our case means that it must contain the variables corresponding to all edges adjacent to some vertex of the graph, with the number of negated variables having the parity that is opposite to the desired parity for this vertex. For example, consider a vertex of degree 5 and desired parity 0, with adjacent edges <i>a</i>, <i>b</i>, <i>c</i>, <i>d</i>, <i>e</i>. A valid axiom for this vertex would be for example !<i>a</i>|!<i>b</i>|<i>c</i>|<i>d</i>|!<i>e</i>, which would be false only if variables <i>a</i>,<i>b</i>,<i>e</i> are true, and variables <i>c</i>,<i>d</i> are false, but that would mean that the vertex has 3 adjacent edges which doesn't satisfy its parity requirement, so this axiom is always true.</li><li>It can be a <i>conclusion</i>, in which we take two previous clauses of form <i>A</i>|<i>x</i> and <i>B</i>|!<i>x</i>, and make a new clause <i>A</i>|<i>B</i>. Since both original clauses are true the conclusion is true as well.</li><li>It can be a <i>transformation</i> of a previous clause. We take a previous clause and a permutation of the set of all variables and their negations, and apply the permutation to the elements of the clause to get the new clause. The permutation can not be arbitrary: it must be an automorphism of the set of axioms (map every axiom to an axiom). Note that transformations are not a strictly necessary operation, as we could have constructed the resulting clause by applying the automorphism to the axioms used to build the original clause, and then repeating how it was built, but it allows to dramatically reduce the number of clauses in a proof.</li></ol><div>Your goal to derive an empty clause in at most 1000 steps, which would mean a contradiction, and prove that the parities goal is impossible to achieve.<br /><br />First, let's solve our problem for the case where our graph is a tree. We will apply a recursive procedure that takes a subtree, and builds a clause with just one variable corresponding to the edge going into that subtree, either negated or not. For a leaf, such clause is just an axiom. For an internal vertex, we can recursively build such clauses for edges going to its children, and then build an axiom from negations of those clauses, and choosing whether to negate the edge to the parent to obtain the required parity for the axiom. We can then eliminate all variables but one from this axiom using the conclusion, as we have negated single variables for all edges going to the children.<br /><br />When we reach the root of the tree, we apply the same procedure, only there's no extra variable for the edge to the parent. The condition on the sum of all parities will guarantee that the above approach is still applicable, i.e. the axiom we need to cancel out all variables will be a valid axiom for the root (a formal proof of that fact would probably inductively find that the edge going from a subtree gives us a negated or non-negated clause based on the sum of parities in that subtree). And we will obtain an empty clause after eliminating all variables in the root, thus completing the required formal proof in less than 2<i>n</i> steps, where <i>n</i> is the number of vertices.<br /><br />Now how to adapt this approach for the case where the graph is not a tree? Let's pick an arbitrary spanning tree in it, and apply the same idea. Whenever we need to create a new axiom for a vertex, let's keep all variables corresponding to the edges that are <i>not</i> in the spanning tree non-negated. This does not affect the validity of axioms since it depends only on the number of negated variables. In the end, instead of an empty clause we will get a clause that is an or of all edges that are not in the spanning tree, and does not have variables corresponding to the edges of the spanning tree.<br /><br />This is where the third operation type, the transformation, comes into play. For each edge not in the spanning tree consider its <i>fundamental cycle</i> formed by this edge and the path between its ends in the spanning tree. Let's apply a transformation that negates all variables corresponding to this cycle. This is a valid transformation since for each vertex it negates 0 or 2 variables, which does not affect the parity, and thus maps axioms to axioms. In our clause it will negate exactly one variable, since we don't have variables corresponding to the edges of the spanning tree, and we can then use conclusion to remove that variable from our clause. We can then repeat this process for all edges not in the spanning tree and obtain the empty clause in 2(<i>m</i>-<i>n</i>+1) additional operations, or less than 2(<i>m</i>+1<i>)</i> overall, where <i>m</i> is the number of edges, which is good enough.<br /><br />Thanks for reading, and check back soon!</div></div></div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/acR4SNKkM2E" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/12/an-extremely-formal-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-10341294432337633032017-12-23T20:19:00.001+03:002017-12-23T20:19:41.269+03:00A delayed 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/-SqBPZNrgXK4/WjbTJ0TJG8I/AAAAAAAB7sg/gOHFnjvHO3MWvUH2p1APHOVlf6f9qpazgCLcBGAs/s1600/srm722top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="148" data-original-width="783" height="120" src="https://2.bp.blogspot.com/-SqBPZNrgXK4/WjbTJ0TJG8I/AAAAAAAB7sg/gOHFnjvHO3MWvUH2p1APHOVlf6f9qpazgCLcBGAs/s640/srm722top5.png" width="640" /></a></div>TopCoder SRM 722 on Thursday was the first contest of the Oct 9 - Oct 15 week (<a href="https://community.topcoder.com/stat?c=round_overview&rd=17010">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17010&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://www.topcoder.com/blog/single-round-match-722-editorials/">analysis</a>). TopCoder has put together an easier problemset with a very tricky medium problem this time, which put a great emphasis on the challenge phase. tourist, uwi and gainullin.ildar have found enough challenges to overtake the others into the top three. Congratulations!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-HsgjkHTnlV0/WjbUEPd9fxI/AAAAAAAB7so/B9ZnMPJRvOgBCLgfBn5jjo7dcErcU3e-ACLcBGAs/s1600/cf440top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="272" data-original-width="1105" height="156" src="https://2.bp.blogspot.com/-HsgjkHTnlV0/WjbUEPd9fxI/AAAAAAAB7so/B9ZnMPJRvOgBCLgfBn5jjo7dcErcU3e-ACLcBGAs/s640/cf440top5.png" width="640" /></a></div>Codeforces Round 440 took place early on Sunday (<a href="http://codeforces.com/contest/871">problems</a>, <a href="http://codeforces.com/contest/871/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/55200">analysis</a>). All top scorers solved 4 problems, albeit different ones, and mere minutes separated them. khadaev was 1 minute faster than Errichto, and thus earned the first place. Well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-5ahEBCgHP1Y/WjbUw9ggPLI/AAAAAAAB7sw/gKsyBiWf-vAd3dLNsXS2PAIpvHdIhaGsQCLcBGAs/s1600/oc1718spbtop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="286" data-original-width="866" height="210" src="https://2.bp.blogspot.com/-5ahEBCgHP1Y/WjbUw9ggPLI/AAAAAAAB7sw/gKsyBiWf-vAd3dLNsXS2PAIpvHdIhaGsQCLcBGAs/s640/oc1718spbtop5.png" width="640" /></a></div>Overlapping with that round, the Open Cup Grand Prix of SPb took place just an hour later (<a href="http://opencup.ru/files/oci/gp4/problems-e.pdf">problems</a>, <a href="http://opencup.ru/index.cgi?data=macros/stage&head=index&menu=index&stg=4&region=main&ncup=oci&class=oci">results</a>, top 5 on the left). Uncharacteristically for our team we had reasonable penalty time and just needed to solve the last problem in an hour to win — but missed a small detail in the problem statement and could not get it accepted, which allowed team Past Glory to score another victory — congratulations!<br /><br />In continuing the great traditions of St. Petersburg State University championships, this contest featured many interesting problems, of which I'd like to highlight the two hardest ones. Problem F was an interactive problem about exploring a random maze with a communication delay. You are given a maze in a 20x20 grid with walls between cells. The maze is randomly generated to form a tree using the Kruskal-like approach. You control a robot that starts in the bottom-left corner. You can command the robot to move in one of the four cardinal directions, and you would receive a reply telling you that the robot has moved in that direction (if there was no wall there), or that it stayed in its current cell (if there was a wall). You need to get the robot in the bottom-right corner in 10000 moves. The catch is that you don't receive the replies right away: the reply to the <i>i</i>-th command only arrives after you send the (<i>i</i>+100)-th command. We can't afford 100 moves per cell, so we have to somehow continue exploring without knowing where exactly we are. Can you see an effective approach?<br /><br />I have explained and analyzed our approach in <a href="http://codeforces.com/blog/entry/55204?#comment-390856">this comment thread</a>.<br /><br />Problem H discussed formal proofs in the spirit of <a href="http://petr-mitrichev.blogspot.com/2017/05/a-zero-pigeon-week.html">the Dirichlet problem</a> from another St. Petersburg State University Championship this spring. You are given an undirected connected graph with at most 73 vertices and 492 edges, and a desired parity for each vertex (either odd, denoted by 1, or even, denoted by 0). The sum of all parities is 1 modulo 2. You need to <i>prove</i> that there doesn't exist a subset of edges of the graph with the desired parity of the number of edges adjacent to each vertex. It would be easy to prove, as it is well known that the number of vertices of odd degree in any graph is always even. However, you're only interested in proofs stated in a specific form.<br /><br />Such proof is a sequence of <i>clauses</i>. Each clause is an "or" of zero or more <i>variables</i> and/or their negations. Each variable corresponds to an edge in the graph, and is true if we take this edge, and false otherwise. Each clause must be built in one of the three ways:<br /><ol style="text-align: left;"><li>In can be an <i>axiom</i>, which in our case means that it must contain the variables corresponding to all edges adjacent to some vertex of the graph, with the number of negated variables having the parity that is opposite to the desired parity for this vertex. For example, consider a vertex of degree 5 and desired parity 0, with adjacent edges <i>a</i>, <i>b</i>, <i>c</i>, <i>d</i>, <i>e</i>. A valid axiom for this vertex would be for example !<i>a</i>|!<i>b</i>|<i>c</i>|<i>d</i>|!<i>e</i>, which would be false only if variables <i>a</i>,<i>b</i>,<i>e</i> are true, and variables <i>c</i>,<i>d</i> are false, but that would mean that the vertex has 3 adjacent edges which doesn't satisfy its parity requirement, so this axiom is always true.</li><li>It can be a <i>conclusion</i>, in which we take two previous clauses of form <i>A</i>|<i>x</i> and <i>B</i>|!<i>x</i>, and make a new clause <i>A</i>|<i>B</i>. Since both original clauses are true the conclusion is true as well.</li><li>It can be a <i>transformation</i> of a previous clause. We take a previous clause and a permutation of the set of all variables and their negations, and apply the permutation to the elements of the clause to get the new clause. The permutation can not be arbitrary: it must be an automorphism of the set of axioms (map every axiom to an axiom). Note that transformations are not a strictly necessary operation, as we could have constructed the resulting clause by applying the automorphism to the axioms used to build the original clause, and then repeating how it was built, but it allows to dramatically reduce the number of clauses in a proof.</li></ol><div>Your goal to derive an empty clause in at most 1000 steps, which would mean a contradiction, and prove that the parities goal is impossible to achieve. Can you do that?</div><div><br /></div><div><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-kj4oYAbI4z4/Wj6P7KIolLI/AAAAAAAB7zE/miP6LKpvXo4vW4pOhwenQApmexoJZbLSgCLcBGAs/s1600/IMG_20171025_153244.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1065" data-original-width="1600" height="426" src="https://3.bp.blogspot.com/-kj4oYAbI4z4/Wj6P7KIolLI/AAAAAAAB7zE/miP6LKpvXo4vW4pOhwenQApmexoJZbLSgCLcBGAs/s640/IMG_20171025_153244.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2017/12/a-future-week.html">my previous summary</a>, I have mentioned <a href="http://codeforces.com/contest/868/problem/E">a Codeforces problem</a>: two players are playing a real-time game on a tree. The first player has one token, and in one second can move it to an adjacent vertex of the tree. The second player has several tokens, and can move them with infinite speed whenever they want. However, as soon as a token of the second player meets the token of the first player, this second player's token is removed from the game. The goal of the first player is to remove all tokens of the second player as fast as possible. How long would it take in worst case? You are given the tree and the starting locations of all tokens. There are at most 50 vertices in the tree, and at most 50 tokens.<br /><br />We can notice that whenever we (the first player) are walking along an edge, only two numbers matter: how many tokens are there on each side of this edge in the tree. When we approach a vertex, the second player has to decide how to distribute the tokens on the side we're approaching between different subtrees of that vertex. We must then proceed into one of those subtrees, as going back along the edge we just arrived on just wastes two seconds. We must proceed into a subtree that has at least one token. Eventually, we will reach a leaf and remove all tokens which are there (at least one).<br /><br />This makes our game acyclic, and we can solve it using dynamic programming where the state is the directed edge of the tree we're traversing, and two numbers: the number of second player tokens on each side of it. When we reach a vertex, in order to find how the second player will divide their tokens, we use an inner dynamic programming which computes the highest minimum time to finish the game if we placed <i>a</i> tokens into the first <i>b</i> subtrees of this vertex. This means we process one state in O(<i>n</i><sup>3</sup>), and we have O(<i>n</i><sup>2</sup>) states, for the total running time of O(<i>n</i><sup>5</sup>). However, we can notice that the inner dynamic programming actually computes the answers not just for one state, but for all states with the same total number of tokens of the second player left, and thus the running time becomes O(<i>n</i><sup>4</sup>) which is fast enough.<br /><br />Thanks for reading, and check back soon for the next week's summary!<br /><br /></div></div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/pbohgAWNTSE" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/12/a-delayed-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-25328163564479646322017-12-17T23:12:00.002+03:002017-12-23T20:11:41.845+03:00A future 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/-dIxd5AqrGVw/WjbIIgvCQkI/AAAAAAAB7ro/UskKjcMv7dw4sTZnwcjnFc-Ct1pFqc7sgCLcBGAs/s1600/cf438top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="271" data-original-width="1104" height="156" src="https://3.bp.blogspot.com/-dIxd5AqrGVw/WjbIIgvCQkI/AAAAAAAB7ro/UskKjcMv7dw4sTZnwcjnFc-Ct1pFqc7sgCLcBGAs/s640/cf438top5.png" width="640" /></a></div>The Oct 2 - Oct 8 week contained Codeforces Round 438 (<a href="http://codeforces.com/contest/868">problems</a>, <a href="http://codeforces.com/contest/868/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/55046">analysis</a>). With problem G out of reach, the competition turned to the first six problems + challenges, and cubelover has excelled at both — congratulations on the win!<br /><br /><a href="http://codeforces.com/contest/868/problem/E">Problem E</a> continued the streak of problems with nice and simple statements. Two players are playing a real-time game on a tree. The first player has one token, and in one second can move it to an adjacent vertex of the tree. The second player has several tokens, and can move them with infinite speed whenever they want. However, as soon as a token of the second player meets the token of the first player, this second player's token is removed from the game. The goal of the first player is to remove all tokens of the second player as fast as possible. How long would it take in worst case? You are given the tree and the starting locations of all tokens. There are at most 50 vertices in the tree, and at most 50 tokens.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-Kdj8MLd2lYE/WjbPhSW0ZgI/AAAAAAAB7sA/ZZZGFuRB2JQQkdaa8sIifwyDYSjTA6umgCLcBGAs/s1600/IMG_20171021_143759.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1200" data-original-width="1600" height="480" src="https://3.bp.blogspot.com/-Kdj8MLd2lYE/WjbPhSW0ZgI/AAAAAAAB7sA/ZZZGFuRB2JQQkdaa8sIifwyDYSjTA6umgCLcBGAs/s640/IMG_20171021_143759.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2017/12/a-stock-week.html">my previous summary</a>, I have mentioned a similarly simple sounding problem: you are given the price of a stock for each of <i>n</i> days. You start with 0 stocks, want to finish with 0 stocks, and do one of three things each day: buy 1 stock, sell 1 stock, or do nothing. How much money you can earn? <i>n</i> is up to 300000.<br /><br />The solution proceeds as follows. A new day starts, with stock price <i>a</i>. We will then create two <i>futures</i> for this stock: we will remember that we can buy two units of stock at price <i>a</i> (the reason for creating two futures instead of one will become clear soon). Then we will sell one unit of stock at price <i>a</i>. Which one? Of course, we will take the remaining future with the lowest price, act on it (i.e. buy a unit a stock at that price), and then sell it at price <i>a</i>, realizing the profit. Note that this might be the future that we just created, in case all previous ones were more expensive, in which case the buy and sell cancel out.<br /><br />Note that for each stock, we create one sale and at most two buys via the futures. We can treat the first buy as cancelling the sale, and the second buy as the actual buy — this is the reason we need two futures.<br /><br />As an example, suppose the stock prices are 4, 3, 6, 5. Then our algorithm proceeds as follows:<br /><br /><ul style="text-align: left;"><li>Add two 4s to the futures priority queue, now it has [4, 4].</li><li>Remove the lowest future and pair it with a sale at 4, for a profit of 4-4=0. Our queue is now [4].</li><li>Add two 3s: [3, 3, 4].</li><li>Remove the lowest and pair it with 3: profit is 3-3=0, queue is [3, 4].</li><li>Add two 6s: [3, 4, 6, 6].</li><li>Remove the lowest and pair it with 6: profit is 6-3=3, queue is [4, 6, 6].</li><li>Add two 5s: [4, 5, 5, 6, 6].</li><li>Remove the lowest and pair it with 5: profit is 5-4=1, queue is [5, 5, 6, 6].</li></ul>The total profit is 0+0+3+1=4, and what happened is that we bought at 4 and 3 and sold at 6 and 5. After careful consideration one can see that all valid sequences of stock sales can be expressed in our framework, and that greedily choosing the cheapest future every time leads to an optimal solution thanks to an exchange argument. Still, I find the fact that this greedy approach works very beautiful!<br /><br />Thanks for reading, and check back later!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/0SQ1cHXCAfs" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/12/a-future-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-39811669026214212212017-12-17T22:32:00.001+03:002017-12-17T22:32:23.633+03:00A stock 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/-aDi_7g0MrUI/Wja-5guG79I/AAAAAAAB7rA/5cnuqCthaJUzuq03JAzHPrzogQ8mOXsOACLcBGAs/s1600/srm721top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="149" data-original-width="785" height="120" src="https://2.bp.blogspot.com/-aDi_7g0MrUI/Wja-5guG79I/AAAAAAAB7rA/5cnuqCthaJUzuq03JAzHPrzogQ8mOXsOACLcBGAs/s640/srm721top5.png" width="640" /></a></div>The last September week featured the relatively rare guest: a TopCoder SRM, number 721 (<a href="https://community.topcoder.com/stat?c=round_overview&rd=16983">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=16983&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://www.topcoder.com/blog/single-round-match-721-editorials/">analysis</a>). eddy1021 scored the most points from the problems, but K.A.D.R has overtaken him thanks to his 100 challenge points. Congratulations on the win!<div><br /></div><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-I_exQQsK7TY/WjbA1POOHII/AAAAAAAB7rM/MAc5FcD5kCwahlkyh1x2NsNOkAnEwcNZACLcBGAs/s1600/memsql2017r2top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="271" data-original-width="1104" height="156" src="https://3.bp.blogspot.com/-I_exQQsK7TY/WjbA1POOHII/AAAAAAAB7rM/MAc5FcD5kCwahlkyh1x2NsNOkAnEwcNZACLcBGAs/s640/memsql2017r2top5.png" width="640" /></a></div><div>MemSQL Start[c]UP round 2 took place on Saturday (<a href="http://codeforces.com/contest/866">problems</a>, <a href="http://codeforces.com/contest/866/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/contest/865/standings">onsite results</a>, <a href="http://codeforces.com/blog/entry/54888">analysis</a>). There was a wide variety of problems to solve, and tourist has made the right choice and claimed the first place with A+B+C+D+F. Well done!</div><div><br /></div><div>Problem D had deceptively simple statement which led to a lot of frustration as I was unable to come up with its solution for two hours :) You are given the price of a stock for each of <i>n</i> days. You start with 0 stocks, want to finish with 0 stocks, and do one of three things each day: buy 1 stock, sell 1 stock, or do nothing. How much money you can earn? <i>n</i> is up to 300000.</div><div><br /></div><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-Fh6e0Glv1UU/WjbFtssNggI/AAAAAAAB7rc/qniDPN4m-UcYF1ODHW6BEqLcBMrMHkohQCLcBGAs/s1600/oc1718eurasiatop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="268" data-original-width="951" height="180" src="https://1.bp.blogspot.com/-Fh6e0Glv1UU/WjbFtssNggI/AAAAAAAB7rc/qniDPN4m-UcYF1ODHW6BEqLcBMrMHkohQCLcBGAs/s640/oc1718eurasiatop5.png" width="640" /></a></div><div>Finally, the third Open Cup stage, the Grand Prix of Eurasia, took place on Sunday (<a href="http://opencup.ru/files/oci/gp3/problems-e.pdf">problems</a>, <a href="http://opencup.ru/index.cgi?data=macros/stage&head=index&menu=index&stg=3&region=main&ncup=oci&class=oci">results</a>, top 5 on the left). This time the active Russian ICPC teams stepped forward, with Moscow SU and ITMO leading everybody else by a problem. Well done!</div><div><br /></div><div>Thanks for reading, and check back later as we dive into October!</div></div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/4EiRcS0MoTo" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/12/a-stock-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-39928829441238147982017-12-11T21:54:00.000+03:002017-12-11T21:54:05.894+03:00A global shift 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/-3kX6WqD9xqA/Wi66H90WcWI/AAAAAAAB7co/rkWETvHgJUg3S5gMCyF9sGmkSoJJnKVSgCLcBGAs/s1600/oc1718uraltop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="267" data-original-width="876" height="194" src="https://4.bp.blogspot.com/-3kX6WqD9xqA/Wi66H90WcWI/AAAAAAAB7co/rkWETvHgJUg3S5gMCyF9sGmkSoJJnKVSgCLcBGAs/s640/oc1718uraltop5.png" width="640" /></a></div>The Sep 18 - Sep 24 week featured the second Open Cup stage: the Grand Prix of Ural (<a href="http://opencup.ru/files/oci/gp2/problems1-e.pdf">problems</a>, <a href="http://opencup.ru/index.cgi?data=macros/stage&head=index&menu=index&stg=2&region=main&ncup=oci&class=oci">results</a>, top 5 on the left). The Seoul National U 2 team continued to amaze, this time claiming the victory by 1 problem to Past Glory and by 2 problems to everybody else. Very well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-f4LY-UdtufU/Wi63zo3hOCI/AAAAAAAB7cc/Sq8BHJXwmwAUWvxLaMTE2tZ2B9OZgu1CACLcBGAs/s1600/manthan17top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="271" data-original-width="1102" height="156" src="https://4.bp.blogspot.com/-f4LY-UdtufU/Wi63zo3hOCI/AAAAAAAB7cc/Sq8BHJXwmwAUWvxLaMTE2tZ2B9OZgu1CACLcBGAs/s640/manthan17top5.png" width="640" /></a></div>Later on Sunday, Codeforces hosted a contest titled "Manthan, Codefest 17" (<a href="http://codeforces.com/contest/855">problems</a>, <a href="http://codeforces.com/contest/855/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/54750">analysis</a>). anta has stumbled on the tricky problem D (less than a third of contestants who submitted got it accepted), but has still came out clearly on top thanks to being the only contestant to submit all problems. Congratulations on the victory!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-ASA8cwiP7pA/Wi7SriWVh-I/AAAAAAAB7dc/1wQzVkvNkQQ4Y8lxAewck9HGAzIloao7gCLcBGAs/s1600/IMG_20171007_195629.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1200" data-original-width="1600" height="480" src="https://4.bp.blogspot.com/-ASA8cwiP7pA/Wi7SriWVh-I/AAAAAAAB7dc/1wQzVkvNkQQ4Y8lxAewck9HGAzIloao7gCLcBGAs/s640/IMG_20171007_195629.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2017/12/a-chain-cut-week.html">my previous summary</a>, I have mentioned a couple of problems. One was with a recursive background: there are many contestants taking part in a competition, and top <i>c</i> will be awarded with t-shirts. There are <i>n</i> available t-shirt sizes (<i>n</i><=200000). Each contestant has indicated one of two things: either they need a t-shirt with some concrete size, or they need a t-shirt with one of the two concrete adjacent sizes. More precisely, for each size <i>i</i> we know the number <i>a<sub>i</sub></i> of contestants (up to 10<sup>8</sup>) that need a t-shirt of size <i>i</i>, and the number <i>b<sub>i</sub></i> of contestants (also up to 10<sup>8</sup>) that need either a t-shirt of size <i>i</i> or a t-shirt of size <i>i</i>+1. What is the minimal number of t-shirts we need to buy in order to be able to give t-shirts to top <i>c</i> contestants, no matter which ones end up in top <i>c</i>?<br /><br />First, we can notice that we need to buy such set of t-shirts that in the resulting (huge) graph there's a full matching for any set of <i>c</i> nodes in the left part. <a href="https://en.wikipedia.org/wiki/Hall%27s_marriage_theorem">Hall's theorem</a> gives us an equivalent formulation: we need to make sure that for any set of sizes for which we buy <i>x</i> t-shirts in total, and <i>x</i> is less than <i>c</i>, the number of people who can only wear a t-shirt from this set must not exceed <i>x</i>.<br /><br />Then, we can notice that we can only consider segments of sizes, and not arbitrary sets, in the above condition, as when we have multiple disjoint segments that violate the constraint together, one of them will also provide a constraint violation.<br /><br />Then, just like in many other problems with constraints on segments, we can buy the t-shirts greedily: going in increasing order of sizes, for each size, we will buy just enough t-shirts to make sure the constraint is not violated for all segments that ends with this size. It doesn't make sense to buy more of this size as we can replace those extra t-shirts with ones of size one higher without making things worse.<br /><br />Formally speaking, <i>s<sub>i</sub></i>=max(min(<i>c</i>,<i>a<sub>i</sub></i>), min(<i>c</i>,<i>a<sub>i</sub></i>+<i>b</i><sub><i>i</i>-1</sub>+<i>a</i><sub><i>i</i>-1</sub>)-<i>s</i><sub><i>i</i>-1</sub>, min(<i>c</i>,<i>a<sub>i</sub></i>+<i>b</i><sub><i>i</i>-1</sub>+<i>a</i><sub><i>i</i>-1</sub>+<i>b</i><sub><i>i</i>-2</sub>+<i>a</i><sub><i>i</i>-2</sub>)-<i>s</i><sub><i>i</i>-2</sub>-<i>s</i><sub><i>i</i>-1</sub>, ...). As we move from <i>i</i> to <i>i</i>+1, the arguments to max() change in the following way: the subtracted part increases by <i>s<sub>i</sub></i> for all terms, the <i>a</i>+<i>b</i> part increases by <i>a<sub>i+1</sub></i>+<i>b</i><sub><i>i</i></sub>, and we get a new term. The latter causes some terms to jump over <i>c</i>, in which case the corresponding min() will forever stay equal to <i>c</i>, and these terms will be zero or negative in all subsequent steps, so we can forget about them.<br /><br />This leads to the following approach: let's keep a set of terms for which the min() is still less than <i>c</i>, then we only need to be able to add a constant to the positive part of all terms, add a constant to the negative part of all terms, to find all terms where the positive part exceeds <i>c</i>, and to find the term with the largest difference between positive and negative parts. Such set of operations can be most straightforwardly implemented by keeping two priority queues of those terms: ordered by positive part and ordered by difference, and to implement adding a constant by keeping an extra "global shift" variable.<br /><br />This yields a O(<i>nlogn</i>) solution which is fast enough, but it can also be made O(<i>n</i>) as described in <a href="http://codeforces.com/blog/entry/54572">the official analysis</a>.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-YgXGP0-pR_U/Wi7TH3Y54eI/AAAAAAAB7dk/vl6xYUbE2JcrgYTLTlZJT4zcAk_SwKeCgCLcBGAs/s1600/IMG_20171008_181838.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" data-original-height="1200" data-original-width="1600" height="480" src="https://2.bp.blogspot.com/-YgXGP0-pR_U/Wi7TH3Y54eI/AAAAAAAB7dk/vl6xYUbE2JcrgYTLTlZJT4zcAk_SwKeCgCLcBGAs/s640/IMG_20171008_181838.jpg" width="640" /></a></div>Another problem I mentioned was: two players have a sequence of 50000 integers, and alternately take numbers from either end of the sequence. When all numbers have been taken, each player computes the bitwise xor of their numbers, and the one with a higher bitwise xor wins. Who will win?<br /><br />I have described our solution in <a href="http://codeforces.com/blog/entry/54587?#comment-386036">this comment</a>, but I still feel a bit uneasy about it. It can probably be proven by induction, but it would seem that in such simple setting there should be a simple argument that proves it. I'm really curious to see such argument, please share if you know one!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-efZ5h0mW940/Wi7T8pW27xI/AAAAAAAB7eI/72hGuf42YtAfbW7bN4nAmlLru_rAZUTCACLcBGAs/s1600/IMG_20171017_151704.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="941" data-original-width="1600" height="376" src="https://2.bp.blogspot.com/-efZ5h0mW940/Wi7T8pW27xI/AAAAAAAB7eI/72hGuf42YtAfbW7bN4nAmlLru_rAZUTCACLcBGAs/s640/IMG_20171017_151704.jpg" width="640" /></a></div>Finally, I've just remembered an interesting bit about the TopCoder problem which I explained in <a href="http://petr-mitrichev.blogspot.com/2017/12/a-chain-cut-week.html">the previous summary</a>, about the attractions, mornings, evenings and constraints. During the contest, I was unable to come up with a max flow solution even though I felt like one is possible, and out of desperation started to implement backtracking that greedily does things that are obviously good to do, branches when we don't have an obvious next step, and cuts branches that are definitely worse than the current best answer. To my surprise, I've received a wrong answer instead of time limit exceeded on the system test. The reason for that was that I assumed that I've taken a transitive closure of the set of constraints when implementing the solution, and forgot to actually take the closure. After making this fix, the backtracking passed the system test in the practice room in 42ms :)<br /><br />Thanks for reading, and check back later for more September stories!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/R5WpHziv2UI" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/12/a-global-shift-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-80587062104169735822017-12-11T16:58:00.002+03:002017-12-11T16:58:20.804+03:00A chain cut 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/-jPfRDDTEPqE/Wi5fSV_Zk0I/AAAAAAAB7PY/uHugsZ2tvpst_UQP2X33g7yk4sfyfJvNACLcBGAs/s1600/memsql2017r1top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="273" data-original-width="1103" height="158" src="https://4.bp.blogspot.com/-jPfRDDTEPqE/Wi5fSV_Zk0I/AAAAAAAB7PY/uHugsZ2tvpst_UQP2X33g7yk4sfyfJvNACLcBGAs/s640/memsql2017r1top5.png" width="640" /></a></div>The Sep 11 - Sep 17 week had its contests on the weekend. On Saturday MemSQL Start[c]UP has returned to Codeforces after a three-year absence with Round 1 of its third edition (<a href="http://codeforces.com/contest/859">problems</a>, <a href="http://codeforces.com/contest/859/standings">results</a>, top 5 on the left, <a href="https://youtu.be/XdF5C7clLzs">my screencast</a>, <a href="http://codeforces.com/blog/entry/54572">analysis</a>). moejy0viiiiiv was 25 minutes faster than everybody else to solve all problems, and made sure to protect his lead with a few challenges. Congratulations on the win!<br /><br />The round had a few nice problems, but let me highlight <a href="http://codeforces.com/contest/859/problem/F">problem F</a>: there are many contestants taking part in a competition, and top <i>c</i> will be awarded with t-shirts. There are <i>n</i> available t-shirt sizes (<i>n</i><=200000). Each contestant has indicated one of two things: either they need a t-shirt with some concrete size, or they need a t-shirt with one of the two concrete adjacent sizes. More precisely, for each size <i>i</i> we know the number <i>a<sub>i</sub></i> of contestants (up to 10<sup>8</sup>) that need a t-shirt of size <i>i</i>, and the number <i>b<sub>i</sub></i> of contestants (also up to 10<sup>8</sup>) that need either a t-shirt of size <i>i</i> or a t-shirt of size <i>i</i>+1. What is the minimal number of t-shirts we need to buy in order to be able to give t-shirts to top <i>c</i> contestants, no matter which ones end up in top <i>c</i>?<br /><br />Apart from being an interesting problem in general, it's a great example for <a href="http://codeforces.com/blog/entry/55596">this recent discussion</a> about stories in problem statements. I think that here the t-shirt and contestant story actually makes the problem statement really easy to understand and think about, while a completely formal mathematical statement would be hard to parse.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-YoK26-h0eDQ/Wi5f_K-bWuI/AAAAAAAB7Pg/2hAYr-U_wEg7hbQDyrZxvbS1Jnbkjtz8QCLcBGAs/s1600/oc1718romaniatop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="273" data-original-width="915" height="190" src="https://1.bp.blogspot.com/-YoK26-h0eDQ/Wi5f_K-bWuI/AAAAAAAB7Pg/2hAYr-U_wEg7hbQDyrZxvbS1Jnbkjtz8QCLcBGAs/s640/oc1718romaniatop5.png" width="640" /></a></div>On Sunday the new season of the Open Cup started with the Grand Prix of Romania (<a href="http://opencup.ru/files/oci/gp1/problems1-e.pdf">problems</a>, <a href="http://opencup.ru/index.cgi?data=macros/stage&head=index&menu=index&stg=1&region=main&ncup=oci&class=oci">results</a>, top 5 on the left). Team Past Glory did not show any signs of slowing down and won convincingly by a problem — well done! The great performance and second place of the Seoul National U 2 team was a great surprise, and even more so given that this is a different team from the one that <a href="https://icpc.baylor.edu/worldfinals/results">earned gold medals</a> at the last ICPC World Finals for Seoul.<br /><br />Problem L of this contest showed that we can still find new games with non-trivial solutions in a very simple setup: two players have a sequence of 50000 integers, and alternately take numbers from either end of the sequence. When all numbers have been taken, each player computes the bitwise xor of their numbers, and the one with a higher bitwise xor wins. Who will win?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-_al19xnZGrY/Wi5gq14KpBI/AAAAAAAB7Ps/pm2uSiLJ-rMFKBD7iGE3HHBGf0ppoIQRACLcBGAs/s1600/cf434top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="273" data-original-width="1101" height="158" src="https://2.bp.blogspot.com/-_al19xnZGrY/Wi5gq14KpBI/AAAAAAAB7Ps/pm2uSiLJ-rMFKBD7iGE3HHBGf0ppoIQRACLcBGAs/s640/cf434top5.png" width="640" /></a></div>And right after the end of the Grand Prix, Codeforces held its Round 434 (<a href="http://codeforces.com/contest/860">problems</a>, <a href="http://codeforces.com/contest/860/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/54604">analysis</a>). The battle for the first place was quite tight. Congratulations to kmjp who came out on top by a mere 25 points!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-UgZnsMg1M_I/Wi6NMRDJFTI/AAAAAAAB7QM/txj0LoWUjswaBtKFs2FajkNy0UQsXJq0gCLcBGAs/s1600/IMG_20171007_194607.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1200" data-original-width="1600" height="480" src="https://3.bp.blogspot.com/-UgZnsMg1M_I/Wi6NMRDJFTI/AAAAAAAB7QM/txj0LoWUjswaBtKFs2FajkNy0UQsXJq0gCLcBGAs/s640/IMG_20171007_194607.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2017/12/an-almost-there-week.html">my previous summary</a>, I have mentioned <a href="https://community.topcoder.com/stat?c=problem_statement&pm=14687&rd=16991&rm=330540&cr=10574855">a hard TopCoder problem</a>: you are given 50 attractions in a city. You will visit exactly one attraction per day. Each attraction can be visited either in the morning, costing <i>a<sub>i</sub></i>, or in the evening, costing <i>b<sub>i</sub></i>. Every time you visit an attraction in the morning after visiting another attraction the previous evening, you pay an extra cost <i>c</i>. Every time you switch from evening to morning, you pay an extra cost <i>d</i>. Additionally, you are given a directed graph of restrictions — a set pairs of attractions that constrain the order of visits: in each pair, the first attraction must be visited before the second one. What is the minimal cost to perform all visits?<br /><br />First of all, let's split our visits into groups: a group of morning visits, then a group of evening visits, then a group of morning visits, and so on (we need to consider two cases based on whether the very first visit is in the morning or in the evening). Since we only pay extra costs when we switch groups, the total cost depends on the number of groups and on the assignment of visits to groups, but not on the order of visits within each group.<br /><br />Now let's try to build a network in which a cost of a cut would correspond to the total cost of the visits, so that we can solve our problem with the minimum cut algorithm. For each attraction, let us build a chain of vertices, with all chains having the source and sink as start and end respectively. A chain for one attraction looks like: <i>s</i>-><i>v</i><sub>1</sub>-><i>v</i><sub>2</sub>->..-><i>v<sub>n</sub></i>-><i>t</i>. Let's add infinite capacity edges going backwards in the chain, to guarantee that any finite cut separates some prefix of this chain from the rest. The size of this prefix will correspond to the number of the group that this attraction belongs to, and thus the capacity of the edges should be alternating <i>a<sub>i</sub></i> and <i>b<sub>i</sub></i>: if the vertex belongs to an even-numbered group, the corresponding edge will contribute <i>a<sub>i</sub></i> to the total capacity of the cut, and otherwise <i>b<sub>i</sub></i>, just as we need.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-u5evZ_mvzd0/Wi6OiULXmGI/AAAAAAAB7Rk/zAeMXjQGtOgH2KvO9drRwEu7ORRXzt4zgCKgBGAs/s1600/IMG_20171211_145422.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" data-original-height="1193" data-original-width="1600" height="297" src="https://1.bp.blogspot.com/-u5evZ_mvzd0/Wi6OiULXmGI/AAAAAAAB7Rk/zAeMXjQGtOgH2KvO9drRwEu7ORRXzt4zgCKgBGAs/s400/IMG_20171211_145422.jpg" width="400" /></a></div>In order incorporate a restriction "<i>p</i> must be visited before <i>q</i>" into our network, we will add infinite capacity edges from the vertices of the chain for <i>p</i> to the corresponding vertices of the chain for <i>q</i>. This guarantees that with any finite cut, the position we cut the chain for <i>p</i> will be the same or earlier than the position we cut the chain for <i>q</i>.<br /><br />Finally, in order to incorporate the morning/evening switching costs, let us add an extra attraction that must be visited after all others, and set up the capacities on its chain not as alternating <i>a<sub>i</sub></i> and <i>b<sub>i</sub></i>, but rather as 0, <i>c</i>, <i>c</i>+<i>d</i>, 2<i>c</i>+<i>d</i>, 2<i>c</i>+2<i>d</i>, ...<br /><br />The finite cuts in the resulting network correspond to valid ways of visiting the attractions, and the capacity of the cut is equal to the total visit cost, so now we just need to find the minimum cut. Also note that we have built our network using two relatively standard building blocks: infinite edges can give us constraints on the cut, and a chain of vertices with infinite backwards edges implements a choice from several alternatives with specific costs.<br /><br />Thanks for reading, and check back soon!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/ttsNodl3s9E" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/12/a-chain-cut-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-59197597818434274902017-12-10T20:00:00.001+03:002017-12-10T20:00:14.966+03:00An almost there 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/-gWODG0OFKag/Wi1YouJgv6I/AAAAAAAB7Mo/PB10LCgPwTcTRO0VFlK52gXuMfncge70QCLcBGAs/s1600/cf432top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="272" data-original-width="1125" height="154" src="https://4.bp.blogspot.com/-gWODG0OFKag/Wi1YouJgv6I/AAAAAAAB7Mo/PB10LCgPwTcTRO0VFlK52gXuMfncge70QCLcBGAs/s640/cf432top5.png" width="640" /></a></div>The Sep 4 - Sep 10 week started with two Codeforces rounds. On Monday, Codeforces Round 432 took place (<a href="http://codeforces.com/contest/850">problems</a>, <a href="http://codeforces.com/contest/850/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/54317">analysis</a>). AngryBacon has started with the hardest problem F and solved it very fast, which gave them a clear path to victory. Congratulations!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-uBWv0XitHOE/Wi1ZHKlh1UI/AAAAAAAB7Ms/RWjO_hervFQ3ujH6WNML-31AnFyC90-DQCLcBGAs/s1600/cf433top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="272" data-original-width="1105" height="157" src="https://3.bp.blogspot.com/-uBWv0XitHOE/Wi1ZHKlh1UI/AAAAAAAB7Ms/RWjO_hervFQ3ujH6WNML-31AnFyC90-DQCLcBGAs/s640/cf433top5.png" width="640" /></a></div>On Wednesday, Codeforces hosted the next Round 433 (<a href="http://codeforces.com/contest/853">problems</a>, <a href="http://codeforces.com/contest/853/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/54368">analysis</a>). In a round with 4 problems solvable within an hour and the fifth one too hard to crack, Um_nik has combined excellent speed with 3 successful challenges for a clear first place. Well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-QGL_mq06Hk0/Wi1a0xOj8gI/AAAAAAAB7M4/FLDa1WlHeScBEx9IOkHqUh6dqB0366v-ACLcBGAs/s1600/tco17r3btop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="150" data-original-width="771" height="124" src="https://2.bp.blogspot.com/-QGL_mq06Hk0/Wi1a0xOj8gI/AAAAAAAB7M4/FLDa1WlHeScBEx9IOkHqUh6dqB0366v-ACLcBGAs/s640/tco17r3btop5.png" width="640" /></a></div>On the weekend TopCoder hosted not one but two rounds that finalized the list of finalists for its flagship tournament TopCoder Open 2017. Round 3B took place on Saturday (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=16988">problems</a> — unavailable now, but hopefully the TopCoder website will be fixed soon, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=16988&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left). In order to advance one simply needed to solve either the first two (like qwerty787788, Um_nik and ikatanic did), or the third problem (like rng_58 and RRx did). Congratulations to all advancers!<br /><br />With 1.5 minutes to go in the challenge phase, I had 344.14 points which would be enough to advance with just the easy problem solved, only to <a href="http://codeforces.com/blog/entry/54433?#comment-384840">make an incorrect challenge</a> that brought me down to 319.14 which was not enough. Of course I didn't know that 344.14 would be enough during the round itself, but seeing the final scoreboard made me quite annoyed at myself for that -25 :)<br /><br />Here is <a href="https://community.topcoder.com/stat?c=problem_statement&pm=14685&rd=16988&rm=330537&cr=10574855">the easy problem</a> that brought the challenge phase excitement about: you are given two strings of the same length, which is at most 50. You are allowed to swap corresponding characters in the strings (<i>i</i>-th character of the first string with the <i>i</i>-th character of the second string) as many times as you want. Your goal is to obtain two strings with as large as possible longest common substring. Can you see the right approach?<br /><br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-HK2R3KVJiNA/Wi1cywgDh7I/AAAAAAAB7NI/-Ejbq1wJruAWvJ5-83PN36i4mk105qSmACLcBGAs/s1600/rcc2017finaltop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="480" data-original-width="1086" height="282" src="https://4.bp.blogspot.com/-HK2R3KVJiNA/Wi1cywgDh7I/AAAAAAAB7NI/-Ejbq1wJruAWvJ5-83PN36i4mk105qSmACLcBGAs/s640/rcc2017finaltop5.png" width="640" /></a></div>In between the TopCoder rounds, Russian Code Cup 2017 Final Round saw the top contestants compete for glory and prizes (<a href="http://www.russiancodecup.ru/en/championship/">problems</a>, <a href="http://www.russiancodecup.ru/en/championship/result/58/">results</a>, top 5 on the left, <a href="https://youtu.be/6mglruO5eDU">my screencast</a>, <a href="http://www.russiancodecup.ru/en/press/razbor-zadach-finalnogo-raunda-rcc-2017/">analysis</a>). xudyh was about half an hour faster than everybody else on the first 5 problems. I have tried to leapfrog him by trying to squeeze in a suboptimal solution for the last problem that is fast to code, but it did not pass and xudyh has maintained his first place — congratulations on the win!<br /><br />I have found the easiest problem of this round to be the cutest. You are given a set 100 distinct integers <i>a<sub>i</sub></i> each up to a million, and need to find any set of 100 integers <i>b<sub>j</sub></i> also each up to a million, such that all 100<sup>2</sup> pairwise sums <i>a<sub>i</sub></i>+<i>b<sub>j</sub></i> are distinct. What is the nicest way to achieve that?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-XhqHY8lTQy8/Wi1ciDQ-GkI/AAAAAAAB7NE/xYFkYcT-5sIzW_9grdNouuKezsTO5OYMACLcBGAs/s1600/tco17wildtop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="146" data-original-width="778" height="120" src="https://3.bp.blogspot.com/-XhqHY8lTQy8/Wi1ciDQ-GkI/AAAAAAAB7NE/xYFkYcT-5sIzW_9grdNouuKezsTO5OYMACLcBGAs/s640/tco17wildtop5.png" width="640" /></a></div>And finally, the Wildcard Round of TCO 2017 determined the last two finalists on Sunday (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=16991">problems</a> — unavailable now, but hopefully the TopCoder website will be fixed soon, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=16991&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://youtu.be/XNphi0sE_T4">my screencast</a>). Only kuniavski and xudyh have solved the hard problem, so it is only fitting that they qualified for the TCO onsite — great job!<br /><br />I have once again tried to compensate the poor coding phase performance with lots of successful challenges, but was unable to find enough and got eliminated from the TCO. <a href="https://community.topcoder.com/stat?c=problem_statement&pm=14687&rd=16991&rm=330540&cr=10574855">The hard problem</a> that I couldn't crack stated: you are given 50 attractions in a city. You will visit exactly one attraction per day. Each attraction can be visited either in the morning, costing <i>a<sub>i</sub></i>, or in the evening, costing <i>b<sub>i</sub></i>. Every time you visit an attraction in the morning after visiting another attraction the previous evening, you pay an extra cost <i>c</i>. Every time you switch from evening to morning, you pay an extra cost <i>d</i>. Additionally, you are given a directed graph of restrictions — a set pairs of attractions that constrain the order of visits: in each pair, the first attraction must be visited before the second one. Can you see the way to use max flow to find the minimal cost to perform all visits?<br /><br />Thanks for reading, and check back tomorrow for more backfills!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/USMwu19eCw8" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/12/an-almost-there-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-36522556946303234752017-12-10T18:45:00.000+03:002017-12-10T18:45:26.846+03:00A Chihuahua 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/-HvP62OM60ns/Wi1T_rD3ZGI/AAAAAAAB7MA/P0atyG4hn1ATEYT4PqZHytK-Q53MvwtcgCLcBGAs/s1600/cf431top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="277" data-original-width="1104" height="160" src="https://3.bp.blogspot.com/-HvP62OM60ns/Wi1T_rD3ZGI/AAAAAAAB7MA/P0atyG4hn1ATEYT4PqZHytK-Q53MvwtcgCLcBGAs/s640/cf431top5.png" width="640" /></a></div>Codeforces hosted its Round 431 during the Aug 28 - Sep 3 week (<a href="http://codeforces.com/contest/848">problems</a>, <a href="http://codeforces.com/contest/848/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/54233">analysis</a>). dotorya has managed to solve all four solvable problems in just over one hour, more than 20 minutes faster than the second-placed Reyna and more than 50 minutes faster than everybody else. Well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-Bgf5VLIXOUs/Wi1VmkmyVhI/AAAAAAAB7Mc/PCXZFOp_W1Ir1W0upXMLKJd6N10J48XFgCLcBGAs/s1600/pzsummer2017top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="231" data-original-width="1247" height="118" src="https://4.bp.blogspot.com/-Bgf5VLIXOUs/Wi1VmkmyVhI/AAAAAAAB7Mc/PCXZFOp_W1Ir1W0upXMLKJd6N10J48XFgCLcBGAs/s640/pzsummer2017top5.png" width="640" /></a></div>Also during this week, the biannual Petrozavodsk Training Camp for teams taking part in ICPC has completed (<a href="http://karelia.snarknews.info/index.cgi?data=macros/results&menu=index&head=index&round=09&class=2017s&sbname=2017s">results</a>, top 5 on the left). With 9 5-hour contests packed into just 11 days, and many world class teams participating, this is the first detailed comparison of top student teams this season. Congratulations to the Moscow SU team Chihuahua for topping the overall standings with quite a margin!<br /><br />Thanks for reading, and check back for more.</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/opx-vbp95yE" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/12/a-chihuahua-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-61782324491158550762017-12-10T18:08:00.000+03:002017-12-10T19:07:38.814+03:00A yosupo week<div dir="ltr" style="text-align: left;" trbidi="on">Miss me?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-niuk1NOHd54/Wi0vutU3J-I/AAAAAAAB7JE/qrMRpQ7bg8M9VN2LNZ_ley4N7Q_Ngoa2wCLcBGAs/s1600/srm720top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="150" data-original-width="762" height="125" src="https://2.bp.blogspot.com/-niuk1NOHd54/Wi0vutU3J-I/AAAAAAAB7JE/qrMRpQ7bg8M9VN2LNZ_ley4N7Q_Ngoa2wCLcBGAs/s640/srm720top5.png" width="640" /></a></div>The Aug 21 - Aug 27 week started of with TopCoder SRM 720 on Thursday (<a href="https://community.topcoder.com/stat?c=round_overview&rd=16957">problems</a> — unavailable now, but hopefully the TopCoder website will be fixed soon, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=16957&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left). There was a tense challenge phase battle at the top, but yosupo has made sure it was only for the second place by solving the 1000-pointer — congratulations on the victory!<br /><br />The said 1000-pointer was concerned with somewhat theoretical <i>isotonic regression in L<sub>1</sub> metric</i>. On the outside, it looked like this: you are given an undirected weighted graph with at most 50 vertices and at most 1000 edges, and two spanning trees in it. You have to modify the weights of the edges in such a way that the first given spanning tree is minimal, and the second given spanning tree is maximal, while minimizing the total change of weights.<br /><br />A few solutions for this problem are described and linked in <a href="http://codeforces.com/blog/entry/54020?#comment-380689">this comment thread</a>.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-iADnMV71Mmg/Wi0ugLCZjRI/AAAAAAAB7Iw/2sn9S9XoIeoDLz5X9pwn9Ehipu7tvabIQCLcBGAs/s1600/aimround4top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="274" data-original-width="1107" height="158" src="https://4.bp.blogspot.com/-iADnMV71Mmg/Wi0ugLCZjRI/AAAAAAAB7Iw/2sn9S9XoIeoDLz5X9pwn9Ehipu7tvabIQCLcBGAs/s640/aimround4top5.png" width="640" /></a></div>Later on the same day we had AIM Tech Round 4 on Codeforces (<a href="http://codeforces.com/contest/843">problems</a>, <a href="http://codeforces.com/contest/843/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/54029">analysis</a>). yosupo has continued his great day, this time winning without an extra problem but thanks to solving everything fast enough. Well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-KwIhrKBVfr4/Wi0vAcOs5EI/AAAAAAAB7I4/wwZ9U4x0tr4pCLTPkdPGeSswVFvmFCn4ACLcBGAs/s1600/agc019top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="440" data-original-width="901" height="312" src="https://3.bp.blogspot.com/-KwIhrKBVfr4/Wi0vAcOs5EI/AAAAAAAB7I4/wwZ9U4x0tr4pCLTPkdPGeSswVFvmFCn4ACLcBGAs/s640/agc019top5.png" width="640" /></a></div>Finally, Saturday presented us with AtCoder Grand Contest 019 (<a href="https://agc019.contest.atcoder.jp/assignments">problems</a>, <a href="https://agc019.contest.atcoder.jp/standings">results</a>, top 5 on the left, <a href="https://youtu.be/Kf4k758bjfM">my screencast</a>, <a href="https://atcoder.jp/img/agc019/editorial.pdf">analysis</a>). This time yosupo was only 6th, and the victory instead went to Um_nik who has dominated the round by finishing all problems with half an hour to spare. Congratulations!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-PvrO-UnpPEg/Wi1NeZZpbXI/AAAAAAAB7Jg/f8uiWNuKUAkd5FJtv7eEQOu_h26T08E1wCLcBGAs/s1600/IMG_20170923_174030.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1200" data-original-width="1600" height="480" src="https://4.bp.blogspot.com/-PvrO-UnpPEg/Wi1NeZZpbXI/AAAAAAAB7Jg/f8uiWNuKUAkd5FJtv7eEQOu_h26T08E1wCLcBGAs/s640/IMG_20170923_174030.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2017/10/a-randomized-week.html">my previous summary</a>, I have mentioned <a href="http://codeforces.com/contest/840/problem/D">a Codeforces problem</a>: you are given an array of 300000 numbers, and 300000 queries of the following form: a segment [<i>l</i>;<i>r</i>] and a number <i>k</i>, for which you need to find the smallest number that appears on at least 1/<i>k</i> of all positions in the given segment of the array. Note that <i>k</i> is at most 5, so the number must be quite frequent within the segment.<br /><br />The first idea is to use <a href="http://codeforces.com/blog/entry/7383">Mo's algorithm</a> to handle the segments; we'll keep count of how many of each number are there in the current segment in a simple array, and thus can handle the counting for all segments in O(<i>n</i>*sqrt(<i>n</i>)). In order to find the answer for each segment, we'll need to find the counts that are above 1/5 of their sum. One way to do that would be to maintain a priority queue, but that adds an extra log factor <i>both</i> for queries and for the Mo's part, and some coding complexity.<br /><br />A nicer way to find the high counts is to use randomization: let's just pick 120 random numbers within our segment, and hope that all numbers that occupy at least 1/5 of the segment will be found. Indeed, the probability of that not occurring for a number is less than (1-1/5)<sup>120 </sup>, or about 2.3e-12. We have at most 5 interesting numbers, 300000 queries, and around 100 testcases, so the overall probability of an incorrect answer does not exceed 5*100*300000*2.3e-12=3.45e-4, which is good enough.<br /><br />Thanks for reading, and check back soon as I crawl towards the present :)</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/nx5zlczoYeU" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/12/a-yosupo-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-65776597325212026472017-10-24T17:50:00.002+03:002017-10-24T17:50:21.377+03:00Commentary stream for TopCoder Open 2017 Finals<div dir="ltr" style="text-align: left;" trbidi="on">TopCoder Open 2017 final round is today at <a href="https://www.timeanddate.com/worldclock/fixedtime.html?msg=TopCoder+Open+2017+finals&iso=20171024T1330&p1=422&ah=2">19:30 CEST</a>. Tune in at <a href="https://youtu.be/qrlDoP3JQkI">https://youtu.be/qrlDoP3JQkI</a> to hear me, pashka and Endagorion discuss! This time we should have problem statements at the beginning of the round :)</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/xGr0bXvyPu0" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/10/commentary-stream-for-topcoder-open_24.htmltag:blogger.com,1999:blog-1953325079793449971.post-22810927601672104492017-10-23T17:08:00.000+03:002017-10-23T18:32:23.582+03:00Commentary stream for TopCoder Open 2017 Semifinal 2 with Egor<div dir="ltr" style="text-align: left;" trbidi="on">We'll try to do live commentary of TopCoder Open 2017 Semifinal 2 with Egor on <a href="https://youtu.be/AqpjM86iZlc">https://youtu.be/AqpjM86iZlc</a> - tune in at <a href="https://www.timeanddate.com/worldclock/fixedtime.html?msg=TopCoder+Open+2017+Semifinal+2&iso=20171023T1330&p1=422&ah=2">19:30 CEST</a>!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/Rjcu_fkmBtw" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/10/commentary-stream-for-topcoder-open.htmltag:blogger.com,1999:blog-1953325079793449971.post-355566935453625702017-10-08T17:18:00.002+03:002017-10-08T17:34:58.607+03:00A randomized week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-tZCoq7UisDQ/WdoVjoTbgbI/AAAAAAAB4wE/lFOZQ8XD0wEkv3Hidob25PCw0sRI7yO6ACLcBGAs/s1600/srm719top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="150" data-original-width="778" height="123" src="https://2.bp.blogspot.com/-tZCoq7UisDQ/WdoVjoTbgbI/AAAAAAAB4wE/lFOZQ8XD0wEkv3Hidob25PCw0sRI7yO6ACLcBGAs/s640/srm719top5.png" width="640" /></a></div>The Aug 14 - Aug 20 week contained the usual suspects: a TopCoder SRM and a Codeforces round. First off, TopCoder SRM 719 took place in the early Tuesday hours (<a href="https://community.topcoder.com/stat?c=round_overview&rd=16956">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=16956&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://www.topcoder.com/blog/single-round-match-719-editorials/">analysis</a>). yanQval was a lot faster than everybody else and won the round - well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-n7YetRQKC-4/WdoW6SWzudI/AAAAAAAB4wQ/BIVWgnenpfIh03hw9mZI5g9l8kA963B6gCLcBGAs/s1600/cf429top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="273" data-original-width="1106" height="156" src="https://1.bp.blogspot.com/-n7YetRQKC-4/WdoW6SWzudI/AAAAAAAB4wQ/BIVWgnenpfIh03hw9mZI5g9l8kA963B6gCLcBGAs/s640/cf429top5.png" width="640" /></a></div>Codeforces Round 429 followed on Friday (<a href="http://codeforces.com/contest/840">problems</a>, <a href="http://codeforces.com/contest/840/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/53943">analysis</a>). anta and LHiC have both solved their final fifth problem with only a few minutes to spare and thus obtained quite a margin at the top of the scoreboard - way to go!<br /><br /><a href="http://codeforces.com/contest/840/problem/D">Problem D</a> in this round allowed for a cute randomized solution that in my view is a bit easier than the one from the official analysis. The problem was: you are given an array of 300000 numbers, and 300000 queries of the following form: a segment [<i>l</i>;<i>r</i>] and a number <i>k</i>, for which you need to find the smallest number that appears on at least 1/<i>k</i> of all positions in the given segment of the array. Note that <i>k</i> is at most 5, so the number must be quite frequent within the segment. Can you see how to use that fact to implement a simple randomized solution?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-dAzBaTW6ctE/WdoauXCD0VI/AAAAAAAB4wc/cjKIFtLZF4Mnfg9sFwkvN-KwGL1Ls8U4wCLcBGAs/s1600/codechefaug17top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="407" data-original-width="1012" height="256" src="https://1.bp.blogspot.com/-dAzBaTW6ctE/WdoauXCD0VI/AAAAAAAB4wc/cjKIFtLZF4Mnfg9sFwkvN-KwGL1Ls8U4wCLcBGAs/s640/codechefaug17top5.png" width="640" /></a></div>And finally, I've checked out CodeChef August 2017 Cook-Off on Sunday (<a href="https://www.codechef.com/COOK85">problems</a>, <a href="https://www.codechef.com/rankings/COOK85">results</a>, top 5 on the left, <a href="https://youtu.be/uDyzufcNu58">my screencast</a>). EgorK was at the top of the standings with 4 problems for quite some time, but gennady.korotkevich has then submitted his fourth and fifth problems in rapid succession and won the competition. Congratulations!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-JwB3-58ZVcg/WdozgRGexQI/AAAAAAAB4w0/N2WYnVs8ab8JZTKiHyoccknj9zOkV1lJACLcBGAs/s1600/IMG_20170910_172204.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1200" data-original-width="1600" height="480" src="https://4.bp.blogspot.com/-JwB3-58ZVcg/WdozgRGexQI/AAAAAAAB4w0/N2WYnVs8ab8JZTKiHyoccknj9zOkV1lJACLcBGAs/s640/IMG_20170910_172204.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2017/09/a-week-of-22.html">my previous summary</a>, I have mentioned a problem that I have set for Google Code Jam 2017 finals: you are given a number <i>k</i> between 3 and 10000. Output any simple undirected graph with at most 22 vertices that has exactly <i>k</i> spanning trees.<br /><br />The approach that works the most frequently in such problems is to learn several transitions that help cover all required numbers. For example, if we could come up with a way to transition from a graph with <i>k</i> spanning trees to graphs with 2<i>k</i> and 2<i>k</i>+1 spanning trees by adding one vertex, the problem would be solved. Alas, this does not seem possible, as it's not clear how to achieve that extra "+1" spanning tree.<br /><br />As explicit construction turns out to be hard to impossible, we have to turn to more experimental approaches. One thing that stands out is that there's an enormous amount of graphs on 22 vertices, and while they have at most 22<sup>20</sup> spanning trees, many have under 10000 spanning trees, and thus we can hope that for each <i>k</i> in the given range there are many possible answers. So the next idea is to try generating random graphs and checking how many spanning trees those graphs have using <a href="https://en.wikipedia.org/wiki/Kirchhoff%27s_theorem">the matrix tree theorem</a>, hoping to find all numbers between 3 and 10000 at least once.<br /><br />It turns out that some amounts of trees are more difficult to achieve than others, so this approach by itself is not sufficient to generate all answers within reasonable time. However, there are numerous different ideas that help it find all required numbers faster, and thus help get the problem accepted. I won't be surprised if everybody who got this problem accepted at the Code Jam has used a different approach :) My experimentation led me down the following path:<br /><br /><ul style="text-align: left;"><li>Since some numbers are hard to get, we try to steer the random graphs towards those numbers. Suppose we have a "goal" number we're trying to achieve. The easiest way to do that is to avoid recreating the graph from scratch, but instead take the graph from the previous attempt, and check if it has less trees than the goal, or more. In the former case, we add a random edge to it, and otherwise remove one. As a result, we're more likely to hit the goal, and as soon as we do it, we pick another goal from the yet unseen numbers and repeat the process.</li><li>This process has an unfortunate bad state: when we remove an edge, we can make the graph disconnected, thus having 0 spanning trees. At this point we start adding random edges, but if the graph stays disconnected, it keeps having 0 spanning trees. Finally, we add an edge that connects the graph back, but since we have added so many other edges in the meantime, suddenly the graph has a lot of spanning trees, way more than we need. So we need to remove a lot of edges to get back to reasonable numbers, and may well jump back to 0 in the process. Having noticed this happening, I've modified the process to never remove an edge that would make the graph disconnected.</li><li>Finally, we get almost all numbers we need! After a minute or so, my solution has generated all numbers between 3 and 10000 except 13 and 22 (if I remember correctly). The final idea is that small numbers can still be generated by an explicit construction: a cycle with <i>k</i> vertices has <i>k</i> spanning trees. Since we're allowed at most 22 vertices, 13 and 22 can be done using a cycle.</li></ul><div>That's all for my solution, but I have one more question for you: why is 22 so hard to get? In particular, does there exist a simple undirected graph with at most 21 vertices that has 22 spanning trees? I strongly suspect that the answer is no, but don't know for sure.</div><div><br /></div><div>Thanks for reading, and check back later!</div></div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/saZD2yA-i1k" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/10/a-randomized-week.html