tag:blogger.com,1999:blog-19533250797934499712017-01-16T19:59:08.148+03:00Algorithms Weekly by Petr MitrichevPetr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.comBlogger286125PetrMitrichevhttps://feedburner.google.comtag:blogger.com,1999:blog-1953325079793449971.post-62525292078591296362017-01-16T18:57:00.000+03:002017-01-16T19:59:08.183+03:000.636 of a year<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-XP-_U9UgQ9o/WHzo3uZQinI/AAAAAAAA--E/d97lc39z__UxkUTw8SHERpT2nAstoqm6QCLcB/s1600/srm705top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" src="https://1.bp.blogspot.com/-XP-_U9UgQ9o/WHzo3uZQinI/AAAAAAAA--E/d97lc39z__UxkUTw8SHERpT2nAstoqm6QCLcB/s1600/srm705top5.png" /></a></div>Very early on Wednesday, TopCoder SRM 705 set the pace for the competitions in 2017 (<a href="https://community.topcoder.com/stat?c=round_overview&rd=16856">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=16856&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left). Tourist would have been in the 7th place even if all his solutions failed the system test, thanks to an impressive challenge phase performance. And as usual, none of the solutions did fail, so he achieved an extremely commanding victory. Congratulations!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-j6D5pz9juek/WHzo8NNXnGI/AAAAAAAA--I/J4wwrGIigeACDX3kfTyQFUogyuXJv-19ACLcB/s1600/cf391top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="154" src="https://3.bp.blogspot.com/-j6D5pz9juek/WHzo8NNXnGI/AAAAAAAA--I/J4wwrGIigeACDX3kfTyQFUogyuXJv-19ACLcB/s640/cf391top5.png" width="640" /></a></div>Later that day, Codeforces held its own opening contest of 2017 - Codeforces Round 391 (<a href="http://codeforces.com/contest/757">problems</a>, <a href="http://codeforces.com/contest/757/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/49743">analysis</a>). Once again tourist has combined excellent solving with excellent challenging to claim a win, but the competition was much closer this time. Well done to tourist and to his competitors!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-gSOK5kY6Kbg/WHzpNA5lJoI/AAAAAAAA--M/HxOFzFoVyIU8Ocm1bfOp6EFQIS9SOEqvQCLcB/s1600/eightvcelim2016top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="156" src="https://2.bp.blogspot.com/-gSOK5kY6Kbg/WHzpNA5lJoI/AAAAAAAA--M/HxOFzFoVyIU8Ocm1bfOp6EFQIS9SOEqvQCLcB/s640/eightvcelim2016top5.png" width="640" /></a></div>On Sunday, Codeforces held one more round: 8VC Venture Cup 2017 Elimination Round (<a href="http://codeforces.com/contest/755">problems</a>, <a href="http://codeforces.com/contest/755/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/49793">analysis</a>). In case you have not noticed the pattern of the new year, it was tourist at the top once again. Impressive consistency!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-oDGD-TvKP_Y/WHzs0LRKpII/AAAAAAAA--g/3r3Pgerv0L8PtbyfLNEdN16kQchOGCyIgCLcB/s1600/IMG_20170107_122451-PANO.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="268" src="https://4.bp.blogspot.com/-oDGD-TvKP_Y/WHzs0LRKpII/AAAAAAAA--g/3r3Pgerv0L8PtbyfLNEdN16kQchOGCyIgCLcB/s640/IMG_20170107_122451-PANO.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2017/01/a-week-of-five.html">my last summary</a>, I have organized a vote between top 5 problems of 2016 (of course, only according to my taste). Here are its results:<br /><br />5. The problem about recovering the seed used for shuffling a permutation twice - <a href="http://petr-mitrichev.blogspot.com/2016/11/an-unshuffle-week.html">post with solution</a>. 13 votes, author: Ivan Kazmenko.<br />4. The problem about turning one string into another using two operations: replace one letter, or replace all occurrences of the same letter - <a href="http://petr-mitrichev.blogspot.com/2016/05/a-polish-week.html">post with solution</a>. 17 votes, author: Adam Karczmarz.<br />3. The problem about exploring a cave with identical rooms interactively - <a href="http://petr-mitrichev.blogspot.com/2016/12/a-dfs-week.html">post with solution</a>. 21 vote, author: Georgiy Korneev.<br />2. The problem about implementing binary search that's takes at most log(n+1)+0.1 on average, not ceil(log(n)) - <a href="http://petr-mitrichev.blogspot.com/2016/04/a-binary-week.html">post with solution</a>. 29 votes, author: Vasiliy Mokin (not sure, please tell if it's not correct).<br />1. The problem about turning a matching in the plane into a non-intersecting one that's at least 0.636x as long - <a href="http://petr-mitrichev.blogspot.com/2016/05/a-26x26-week.html">post with solution</a>. 37 votes, author: Gaoyuan Chen.<br /><br />Big thanks to the authors of these and all other 2016 problems!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/tJFtuF0YdMA" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/01/0636-of-year.htmltag:blogger.com,1999:blog-1953325079793449971.post-7316115506978585132017-01-08T23:12:00.002+03:002017-01-08T23:12:58.806+03:00A week of five<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-4KjOJq74vlU/WHKcmD2mn0I/AAAAAAAA-qo/-2rdTZR6eZ4SYNWL0BKuPmwF5ZS5PJFrwCLcB/s1600/IMG_20161229_171807.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="480" src="https://2.bp.blogspot.com/-4KjOJq74vlU/WHKcmD2mn0I/AAAAAAAA-qo/-2rdTZR6eZ4SYNWL0BKuPmwF5ZS5PJFrwCLcB/s640/IMG_20161229_171807.jpg" width="640" /></a></div>In my <a href="http://petr-mitrichev.blogspot.com/2017/01/a-random-walk-week.html">last week's summary</a>, I have mentioned an educational Codeforces problem: you were given a string of digits <i>s</i> of length 200000, and at most 200000 queries, each query being a certain substring <i>q<sub>i</sub></i> of this string. For each query, you need to remove the smallest number of characters from this substring <i>q<sub>i</sub></i> in such a way that the resulting string contains 2017 <i>as a subsequence</i>, but does not contain 2016 as a subsequence.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-k_2d7rZBh8Q/WHKCsfaUqtI/AAAAAAAA-qI/P7CyE6u5pp4XGxlfZscmucVyV3ccklo7ACKgB/s1600/IMG_20170108_191813.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" height="138" src="https://4.bp.blogspot.com/-k_2d7rZBh8Q/WHKCsfaUqtI/AAAAAAAA-qI/P7CyE6u5pp4XGxlfZscmucVyV3ccklo7ACKgB/s400/IMG_20170108_191813.jpg" width="400" /></a></div>First, suppose there were no queries and no removed characters, just one string and the need to check if it contains 2017 and 2016 as a subsequence. That would be an extremely easy problem which allows many solutions. There's one solution, however, that lends itself well to the complications of the full problem: we will build a <a href="https://en.wikipedia.org/wiki/Deterministic_finite_automaton">deterministic finite automaton</a> that accepts only strings that contain 2017 but not 2016 as a subsequence. You can find this automaton pictured on the right, all transitions not explicitly mentioned in the picture lead from a vertex to itself. It has 6 states, A is the starting state, and E is the final state.<br /><br />In order to solve the full problem, we will create a segment tree (not the one from Wikipedia, but <a href="https://www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor/#Segment_Trees">this one</a>). For each segment of the given string, and for each pair of states of the automaton <i>s</i> and <i>t</i>, we will remember: what is the smallest number of characters that needs to be removed from this segment in order for the automaton to reach state <i>t</i>, if it starts in state <i>s</i>? In other words, each node of the segment tree will store a 6x6 matrix, and in order to combine the matrices for two child nodes, a process similar to matrix multiplication is needed.<br /><br />Note that this approach would work for any deterministic finite automaton, not just for the one pictured above.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-sz-Z-s5SR44/WHKcvKQnZwI/AAAAAAAA-qs/wJWqJwd8Gp8BWg5jrMRpjha80zP_1fwpACLcB/s1600/IMG_20170101_161650.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="480" src="https://3.bp.blogspot.com/-sz-Z-s5SR44/WHKcvKQnZwI/AAAAAAAA-qs/wJWqJwd8Gp8BWg5jrMRpjha80zP_1fwpACLcB/s640/IMG_20170101_161650.jpg" width="640" /></a></div>This post wraps up the solutions for problems posted in 2016. As such, it is a good time to take a look back and find the best problem of last year! I've taken a look at the 38 problems for which I've explained the solutions in my blog, and picked 5 that appeal the most to my taste. In chronological order:<br /><br />The problem about implementing binary search that's takes at most log(<i>n</i>+1)+0.1 on average, not ceil(log(<i>n</i>)) - <a href="http://petr-mitrichev.blogspot.com/2016/04/a-binary-week.html">post with solution</a>.<br />The problem about turning a matching in the plane into a non-intersecting one that's at least 0.636x as long - <a href="http://petr-mitrichev.blogspot.com/2016/05/a-26x26-week.html">post with solution</a>.<br />The problem about turning one string into another using two operations: replace one letter, or replace all occurrences of the same letter - <a href="http://petr-mitrichev.blogspot.com/2016/05/a-polish-week.html">post with solution</a>.<br />The problem about recovering the seed used for shuffling a permutation twice - <a href="http://petr-mitrichev.blogspot.com/2016/11/an-unshuffle-week.html">post with solution</a>.<br />The problem about exploring a cave with identical rooms interactively - <a href="http://petr-mitrichev.blogspot.com/2016/12/a-dfs-week.html">post with solution</a>.<br /><br />Could you help me pick one? <br /><br /><iframe allowtransparency="true" frameborder="0" height="211px" name="poll-widget-4248165688735669481" src="https://www.google.com/reviews/polls/display/-4248165688735669481/blogger_template/run_app?txtclr=%23666666&lnkclr=%235588aa&chrtclr=%235588aa&font=normal+normal+100%25+Georgia,+Serif&hideq=true&purl=http://petr-mitrichev.blogspot.com/" style="border: none; width: 100%;"></iframe> Thanks for reading, and check back next week!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/ovYYMZZ1jl8" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/01/a-week-of-five.htmltag:blogger.com,1999:blog-1953325079793449971.post-43319757277940559872017-01-02T01:49:00.000+03:002017-01-09T22:41:23.224+03:00A random walk week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-6Rtyamm3D-c/WGl2L84zG9I/AAAAAAAA-Ls/uBH8M6kywHU6CQJMe_Fw9to69kYyXaMugCEw/s1600/srm704top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" src="https://3.bp.blogspot.com/-6Rtyamm3D-c/WGl2L84zG9I/AAAAAAAA-Ls/uBH8M6kywHU6CQJMe_Fw9to69kYyXaMugCEw/s1600/srm704top5.png" /></a></div>The New Year week featured contests from the two usual platforms. First off, TopCoder held its SRM 704 on Thursday (<a href="https://community.topcoder.com/stat?c=round_overview&rd=16849">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=16849&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://youtu.be/EYN-_3pltOE">my screencast</a>). I have almost shot myself in the foot by blindly challenging sky58's medium with a big testcase at the start of the challenge phase on the ground that he has been compiling and testing this problem right up to the end of the coding phase, suggesting he found a testcase where his solution fails but could not fix it in time. I got -25, but luckily Swistakk has returned the favor a couple of minutes later with a -25 of his own, and I was again within one challenge of the top which I was able to find in the remaining minutes.<br /><br />To be completely honest, I have made another unsuccessful attempt at shooting myself in the foot during this match. <a href="https://community.topcoder.com/stat?c=problem_statement&pm=14470&rd=16849">The hard problem</a> was about constructing a directed graph with at most 20 vertices with the given amount <i>k</i> (up to 100000) of Hamiltonian paths from the first vertex to the last one. I was having a hard time trying to come up with a working approach, so I've decided to fall back to one of the standard approaches that often work in this kind of constructive problems: a random walk. We start with some graph, then repeatedly add random edges while it has too little Hamiltonian paths, or remove random edges while it has too many, until we happen to get the exact amount.<br /><br />However, just finding the number of Hamiltonian paths in an arbitrary graph with 20 vertices would require exponential time, which practically meant that I could make only a few random steps in the allotted two seconds, which was clearly not enough. So I've tried to find a family of graphs where, on one hand, I could find the number of Hamiltonian paths quickly, and on the other hand, the family should be rich enough that it can have any number of Hamiltonian paths up to 100000, and preferably have any number of paths achievable in very many different ways, in order for the random walk to be able to stumble upon one.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-PLYrfPPC7Qk/WGmBcvlrXiI/AAAAAAAA-MM/YWBcXAS-2ssGlwpdw3KpM7TAkUcHYtIFACKgB/s1600/IMG_20170101_232142.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="116" src="https://1.bp.blogspot.com/-PLYrfPPC7Qk/WGmBcvlrXiI/AAAAAAAA-MM/YWBcXAS-2ssGlwpdw3KpM7TAkUcHYtIFACKgB/s640/IMG_20170101_232142.jpg" width="640" /></a></div>I was able to find such family relatively quickly: it would be almost acyclic graphs, where we have arcs from each vertex <i>i </i>to vertex <i>i</i>-1, and all other arcs go "to the right" - from each vertex i to vertices with numbers <i>j</i>><i>i</i>. Counting the number of Hamiltonian paths in such graph is a relatively straightforward dynamic programming task, because whenever we make a "jump" vertex <i>j</i> when previously the largest visited vertex was <i>i</i><<i>j-</i>1, we have to immediately go to the left through vertices <i>j</i>-1, <i>j</i>-2, ..., <i>i</i>+1 in this order, as we have no way of reaching them later. And the family seems reasonably expressive - for example, if we take all possible edges to the right, the number of paths would be 2<sup><i>n</i>-3</sup> (we choose the subset of vertices we "jump" to), and if we take only edges from each <i>i</i> to <i>i</i>+1, there's just one path, with other configurations falling somewhere in between and hopefully covering each number many times.<br /><br />I was so happy to find this family that I rushed to code this solution immediately, and submitted it as soon as I realized that it seems to work fast enough (always less than a second) at least on random inputs. However, I was by no means certain that it works in all cases - it might well be that some specific number of paths is harder to achieve, and since I only had a 2x-4x margin, a moderately higher number of random steps required would cause my solution to time out.<br /><br />The shooting oneself in the foot aspect is that it's really easy to come up with a deterministic solution for the problem within this family of graphs. In fact, the fact that the maximum graph has the number of paths equal to a power of two strongly points toward that deterministic solution. And indeed, all other accepted solutions for this problem do exactly that. Somehow it didn't even occur to me to think in this direction during the round :) Can you see this final step?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-rM1_oltd3bw/WGl2RswwuvI/AAAAAAAA-Lw/dWqHzS8zl2E6qlTKEWO_w2dm3pc01b4FACLcB/s1600/goodbye2016top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="156" src="https://4.bp.blogspot.com/-rM1_oltd3bw/WGl2RswwuvI/AAAAAAAA-Lw/dWqHzS8zl2E6qlTKEWO_w2dm3pc01b4FACLcB/s640/goodbye2016top5.png" width="640" /></a></div>One day later, Codeforces held its traditional Good Bye 2016 round (<a href="http://codeforces.com/contest/750">problems</a>, <a href="http://codeforces.com/contest/750/standings">results</a>, top 5 on the left, <a href="https://youtu.be/WqafwPqZG2M">my screencast</a>). It was Gennady's turn to shoot himself in the foot this time, as he was not careful enough when challenging and earned -50 points for an unsuccessful attempt that proved decisive.<br /><br />This round had a few interesting problems, but I think <a href="http://codeforces.com/contest/750/problem/E">problem E</a> was the most educational - it did not require much beyond putting together several standard approaches, but required a good understanding of those approaches to do so. You were given a string of digits <i>s</i> of length 200000, and at most 200000 queries, each query being a certain substring <i>q<sub>i</sub></i> of this string. For each query, you need to remove the smallest number of characters from this substring <i>q<sub>i</sub></i> in such a way that the resulting string contains 2017 <i>as a subsequence</i>, but does not contain 2016 as a subsequence.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-0s9DNHBBWlY/WGmG_peAfFI/AAAAAAAA-M0/oYta_vwe2GEjKwn-xglmqbiR_bI4hF9LgCLcB/s1600/IMAG1766-EFFECTS.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="362" src="https://1.bp.blogspot.com/-0s9DNHBBWlY/WGmG_peAfFI/AAAAAAAA-M0/oYta_vwe2GEjKwn-xglmqbiR_bI4hF9LgCLcB/s640/IMAG1766-EFFECTS.jpg" width="640" /></a></div>Finally, let me turn your attention to another traditional contest that is still running: <a href="https://contest.yandex.com/newyear2017/contest/3641/enter/">the Prime New Year Contest</a> at SnarkNews. <a href="http://petr-mitrichev.blogspot.com/2013/01/prime-contest-on-snarknews.html">As usual</a>, it includes only problems that were given in a team contest in 2016 but were not solved by any team there. You have plenty of time to try your hand at the hardest problems of 2016, as the contest runs until January 10. The solutions for three problems were described in this blog, so you can get a head start :)<br /><br />Thanks for reading, and check back next week!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/IbCR6b2aqWs" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/01/a-random-walk-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-1238403657902718492016-12-28T18:44:00.000+03:002016-12-28T18:44:11.949+03:00A black radius week<div dir="ltr" style="text-align: left;" trbidi="on">Last week was very calm, as most algorithmic competition websites have called it a year or are busy preparing special New Year-themed competitions.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-zN361fbldhc/WGPTIsd-pmI/AAAAAAAA91Q/XeSpalLRHocxqKE5THpu5gSBZAvvEKVlgCLcB/s1600/agc008top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="318" src="https://2.bp.blogspot.com/-zN361fbldhc/WGPTIsd-pmI/AAAAAAAA91Q/XeSpalLRHocxqKE5THpu5gSBZAvvEKVlgCLcB/s640/agc008top5.png" width="640" /></a></div>Nevertheless, AtCoder held its Grand Contest 008 right on Christmas Day (<a href="http://agc008.contest.atcoder.jp/assignments">problems</a>, <a href="http://agc008.contest.atcoder.jp/standings#page_1">results</a>, top 5 on the left, <a href="https://atcoder.jp/img/agc008/editorial.pdf">analysis</a>). In breaking with AGC tradition, the problems were quite technical and tedious this time. Big congratulations to apiad who has managed to get all of them accepted and won!<br /><br />I have spent all 110 minutes on the attractive-looking <a href="http://agc008.contest.atcoder.jp/tasks/agc008_f">problem F</a>, severely underestimating the amount of things that can go wrong in its solution (I got it accepted after about 5 more minutes of debugging after the end of the contest). The problem simply asks: given a tree with some subset of its vertices colored black, consider all subsets of its vertices defined as "all vertices at distance at most <i>d</i> from some black vertex <i>a</i>" (for all combinations of <i>d</i> and <i>a</i>), and return the number of different such subsets. When the same subset is defined through several combinations of <i>d</i> and <i>a</i>, it must still be counted only once.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-8_n1nVyLb3Q/WGPYKX-XUDI/AAAAAAAA91k/OUpvy5KyFc8kGq9vLC1Z4aLgI9LcQ4B4ACKgB/s1600/IMAG1861.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="362" src="https://1.bp.blogspot.com/-8_n1nVyLb3Q/WGPYKX-XUDI/AAAAAAAA91k/OUpvy5KyFc8kGq9vLC1Z4aLgI9LcQ4B4ACKgB/s640/IMAG1861.jpg" width="640" /></a></div>(Moscow Christmas on the left - compare to <a href="http://petr-mitrichev.blogspot.com/2015/12/a-christmas-week.html">last year</a> :)) In <a href="http://petr-mitrichev.blogspot.com/2016/12/an-amazon-week.html">my previous summary</a>, I have mentioned an interactive Open Cup problem: you needed to give a checkmate to a lone king on a 8x8 chessboard using just one piece - <a href="https://en.wikipedia.org/wiki/Amazon_(chess)">the amazon</a>, that can move both as a queen and as a knight. To makes things harder, you are playing blindfolded and do not know the king's position or moves. More precisely, you are given the initial position of the amazon, and need to output such sequence of at most 50 moves that the king that starts in any position that is not checked by the amazon and makes any legal moves will eventually be checkmated at some point in this sequence, and will not be stalemated before that.<br /><br />There are multiple approaches described in <a href="http://codeforces.com/blog/entry/49169">the post-match discussion</a>, highlighting the fact that the problem allowed one's creativity to shine. However, the solution described by Endagorion also allows to answer the extra question I posted last week: how short can such sequence of moves be if the amazon starts at <i>a1</i>?<br /><br />It turns out this shortest sequence is "a1 a2 b3 b4 c5 c6 c5 d4 d3 d4 e5 e6 e5 f4 f3 e5 f6" (16 moves). And to prove this, Endagorion simply runs a breadth-first search over all reachable states of the game. The state of the game, in this case, is the position of the amazon plus the set of positions where the opposite king <i>can</i> be. At first glance it seems like we might get 64*2<sup>64</sup> states, but in practice the number of reachable states is much, much lower - most likely because the set of reachable squares for the king fills any unattacked area reasonably quickly, and thus we get much fewer possibilities (just 312400 states are reachable, and only 54520 of those are traversed before we find a way to checkmate definitely).<br /><br />Thanks for reading, and check back in 2017! Happy New Year!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/_FOxX8PyM9w" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2016/12/a-black-radius-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-44594143469005838102016-12-19T01:22:00.000+03:002016-12-19T01:22:05.514+03:00An amazon week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-f2N-FjdX4tM/WFcCeBOgZpI/AAAAAAAA9pg/bvHAHNpJu5AuyqL8EWbGJMN651Rr1WLQACEw/s1600/srm703top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" src="https://4.bp.blogspot.com/-f2N-FjdX4tM/WFcCeBOgZpI/AAAAAAAA9pg/bvHAHNpJu5AuyqL8EWbGJMN651Rr1WLQACEw/s1600/srm703top5.png" /></a></div>On Wednesday, TopCoder SRM 703 - the first TopCoder round after the TCO - took place (<a href="https://community.topcoder.com/stat?c=round_overview&rd=16848">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=16848&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left). Endagorion has claimed the victory thanks for an amazingly fast solution for the 1000 - he submitted it in just over 7 minutes! It turns out that a similar problem <a href="http://codeforces.com/blog/entry/48849?#comment-330337">has appeared before</a>, and he could reuse most of the code. Nevertheless, congratulations on the flawless execution!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-MH1T2RzISaQ/WFcEmsrnIEI/AAAAAAAA9po/rKcwLcKWNPQtMRqEzlKWV-M3yNik_ULHQCLcB/s1600/cf385top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="166" src="https://1.bp.blogspot.com/-MH1T2RzISaQ/WFcEmsrnIEI/AAAAAAAA9po/rKcwLcKWNPQtMRqEzlKWV-M3yNik_ULHQCLcB/s640/cf385top5.png" width="640" /></a></div>Codeforces Round 385 on Saturday has gathered 8 nutella-rated participants, including the top 3 (<a href="http://codeforces.com/contest/744">problems</a>, <a href="http://codeforces.com/contest/744/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/49126">analysis</a>). Tourist has guaranteed himself the first place in just over an hour, but couldn't solve everything because of extremely tricky geometric problem D. Congratulations on the win!<br /><br />Here's <a href="http://codeforces.com/contest/744/problem/E">problem E</a> which has propelled him to the top, in a slightly simplified form: you are given <i>n</i> words with total length up to <i>m</i>, and need to check whether there exists a <i>cyclic string</i> that has at least two different decompositions into those words, in O(<i>nm</i>) time. For example, for a set {"aa", "aba", "ba", "bab"} the cyclic string "ababa"="babaa" has two decompositions: "aba" + "ba", and "bab" + "aa".<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-wqRlb8rQ4CY/WFcIYG1Y4gI/AAAAAAAA9p4/rgogvfTqfVY5ZVOlO1dqGk_-Fi0nMfwOACLcB/s1600/oc1617r9top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="170" src="https://1.bp.blogspot.com/-wqRlb8rQ4CY/WFcIYG1Y4gI/AAAAAAAA9p4/rgogvfTqfVY5ZVOlO1dqGk_-Fi0nMfwOACLcB/s640/oc1617r9top5.png" width="640" /></a></div>Finally, Open Cup 2016-17 Grand Prix of Peterhof has (probably?) wrapped up 2016 for many ACM ICPC teams (<a href="http://opentrains.snarknews.info/~ejudge/res/res10359">results</a>, top 5 on the left). Problem E was the most unusual and thus the most creative: you needed to give a checkmate to a lone king on a 8x8 chessboard using just one piece: <a href="https://en.wikipedia.org/wiki/Amazon_(chess)">the amazon</a>, that can move both as a queen and as a knight. To makes things harder, you are playing blindfolded and do not know the king's position or moves. More precisely, you are given the initial position of the amazon, and need to output such sequence of at most 50 moves that the king that starts in any position that is not checked by the amazon and makes any legal moves will eventually be checkmated at some point in this sequence, and will not be stalemated before that. Can you figure out how to do it? How short can such sequence of moves be if the amazon starts at <i>a1</i>?<br /><br />Thanks for reading, and check back next week!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/LGdOd1s_n6M" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2016/12/an-amazon-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-16567155685540032702016-12-18T01:13:00.000+03:002016-12-18T01:13:51.087+03:00A dfs week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-xeYEyKX3Se8/WFWviWsocmI/AAAAAAAA9oE/LJUadeKahiMRCfMVKaGJCF-xQ7URfBsNgCLcB/s1600/cf383top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="164" src="https://1.bp.blogspot.com/-xeYEyKX3Se8/WFWviWsocmI/AAAAAAAA9oE/LJUadeKahiMRCfMVKaGJCF-xQ7URfBsNgCLcB/s640/cf383top5.png" width="640" /></a></div>Codeforces Round 383 was the main event of the last week (<a href="http://codeforces.com/contest/741">problems</a>, <a href="http://codeforces.com/contest/741/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/48871">analysis</a>). TooDifficult has regained the second place in the overall rankings thanks to his victory; his 2017 ACM ICPC World Finals rival mnbvmar is now ranked sixth thanks to his second place in this round. Well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-8zQ9otnlh6M/WFW4SfhKlbI/AAAAAAAA9ok/RrabFZtt69Uv3AMlxo7KkCyRNZ2gEOxEwCLcB/s1600/IMAG1788.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="362" src="https://2.bp.blogspot.com/-8zQ9otnlh6M/WFW4SfhKlbI/AAAAAAAA9ok/RrabFZtt69Uv3AMlxo7KkCyRNZ2gEOxEwCLcB/s640/IMAG1788.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2016/12/a-maze-week.html">my previous summary</a>, I have mentioned an unsolved NEERC 2016 problem where your program explores a maze with at most 20 rooms which look exactly the same. Each room of the maze has the same amount <i>m</i> (also at most 20) of outgoing one-way passages which also look exactly like one another, arranged in a circle. The only way not to get completely lost in this maze is to use the fact that each room also has a movable rock. Initially there's a rock is in the center of each room. When you leave a room, you can put the rock next to any outgoing passage, and moreover, you can choose whether to put it to the left or to the right of this passage (that means that there are 2<i>m</i> ways to put it). If you ever arrive in this room again, you will see whether the rock is placed to the left or to the right of a passage - but since all passages look the same, you won't have any other information! So now you will be able express the number of the passage to take, and the number of the passage to move the rock to by the number in clockwise order starting from the one marked with the rock when you arrive. Your goal is to visit all rooms in at most 20000 steps.<br /><br />The solution is explained with pictures in <a href="http://neerc.ifmo.ru/archive/2016/neerc-2016-review.pdf">the published analysis PDF</a> (problem I), but let me repeat the outline here. We will implement a depth-first traversal of our graph. However, depth-first traversal sometimes needs to go back, and we can't do that since the passages are one-way. However, since the graph is strongly connected (it looks like I forgot to mention this property in the problem statement summary), there's always some way to get back. The main idea is: when leaving the vertex for the last time, mark the passage that leads as high up as possible in the depth first search tree. This way when we find ourselves in an already processed vertex, we can just follow the marked passages to get back to the current depth first search path. And inside that path, we will mark the passages that lead down this path, so that when we return to this path, we can then get down to the vertex that's being currently processed by the dfs. We can use left/right positioning of the rock to distinguish the vertices on the path ("grey") and the already processed vertices ("black"). There are some more technical details to the solution, but all ideas are above.<br /><br />I find this problem very appealing for multiple reasons, one of them being that the solution is "tight": the amount of information we can store in the visited rooms turns out to be barely enough to perform the traversal. How can one come up with such tight problems?</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/UWFvwH6Bj44" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2016/12/a-dfs-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-31813824967121935512016-12-05T23:35:00.000+03:002016-12-05T23:35:40.905+03:00A maze week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-9SCdIBOS5Es/WEXNNBFRgzI/AAAAAAAA9bQ/zGDntRQZAWgFLgTGv66otYaIEuh5oxyHgCLcB/s1600/codefestival2016grandfinaltop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="272" src="https://1.bp.blogspot.com/-9SCdIBOS5Es/WEXNNBFRgzI/AAAAAAAA9bQ/zGDntRQZAWgFLgTGv66otYaIEuh5oxyHgCLcB/s640/codefestival2016grandfinaltop5.png" width="640" /></a></div>Last week was quite a bit calmer than its predecessors. On Monday, Code Festival 2016 wrapped up the festivities with its Grand Final (<a href="http://cf16-exhibition-final.contest.atcoder.jp/assignments">problems</a>, <a href="http://cf16-exhibition-final.contest.atcoder.jp/standings">results</a>, top 5 on the left, <a href="http://cf16-exhibition-final-open.contest.atcoder.jp/standings">online mirror results</a>, <a href="https://goo.gl/Ntgoek">analysis</a>). It was W4yneb0t's day, as he managed to deny tourist a somewhat expected victory by solving the same amount of problems, but a more expensive set of them. Big congratulatons!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-yTS09R7RveE/WEXNniQz45I/AAAAAAAA9bU/MOXlydlFtuYBIxcTn_3zE2i8nH7NO4FDwCLcB/s1600/neerc2016top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="136" src="https://3.bp.blogspot.com/-yTS09R7RveE/WEXNniQz45I/AAAAAAAA9bU/MOXlydlFtuYBIxcTn_3zE2i8nH7NO4FDwCLcB/s640/neerc2016top5.png" width="640" /></a></div>I did not cover a lot of ACM ICPC regionals this season, but now is a good time to start :) ACM ICPC 2016-17 NEERC took place on Sunday in St Petersburg, Barnaul, Tbilisi and Almaty (<a href="http://neerc.ifmo.ru/information/problems.pdf">problems</a>, <a href="http://neerc.ifmo.ru/information/standings.html">results</a>, top 5 on the left). One of the main events of the year for most of ex-USSR algorithmic competition community, and the main event of their entire algorithmic competition career for many teams who practice for multiple years for this one chance to advance to the World Finals. One can experience a very wide spectrum of emotions just by watching the NEERC award ceremony where some teams are full of joy and are not at all shy to share that moment with everybody, while others ruminate over the far-reaching consequences of just one bad day. Nevertheless, the community stays very close and friendly, and kudos to everybody for keeping the spirit going! And last but not the least, congratulations to the team SPb SU Base on the victory!<br /><br />Problem I was left unsolved in the onsite competition, and it's a pity since I find it really beautiful. It's an interactive problem where your program explores a maze with at most 20 rooms which look exactly the same. Each room of the maze has the same amount <i>m</i> (also at most 20) of outgoing one-way passages which also look exactly like one another, arranged in a circle. The only way not to get completely lost in this maze is to use the fact that each room also has a movable rock. Initially there's a rock is in the center of each room. When you leave a room, you can put the rock next to any outgoing passage, and moreover, you can choose whether to put it to the left or to the right of this passage (that means that there are 2<i>m</i> ways to put it). If you ever arrive in this room again, you will see whether the rock is placed to the left or to the right of a passage - but since all passages look the same, you won't have any other information! So now you will be able express the number of the passage to take, and the number of the passage to move the rock to by the number in clockwise order starting from the one marked with the rock when you arrive. Your goal is to visit all rooms in at most 20000 steps.<br /><br />The problem statement is quite abstract, so I encourage you to read in full in <a href="http://neerc.ifmo.ru/information/problems.pdf">the PDF</a> (problem I), especially the sample input/output. After you understand what's going on, however, I find it really exciting to solve!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-tPY94Qs03CY/WEXO5n6-KQI/AAAAAAAA9bo/5i_9b7UFiOkKl84VI1ftp7st9e67Zbp4wCLcB/s1600/IMAG1742.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="362" src="https://2.bp.blogspot.com/-tPY94Qs03CY/WEXO5n6-KQI/AAAAAAAA9bo/5i_9b7UFiOkKl84VI1ftp7st9e67Zbp4wCLcB/s640/IMAG1742.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2016/12/a-makoto-week.html">my previous summary</a>, I have mentioned a CERC problem that had to do with bipartite matchings. You were given a bipartite graph with at most 20 vertices in each part (40 together). A set <i>s</i> of its vertices was called <i>nice</i> if there existed a matching that covers it - in other words, such that for every vertex from <i>s</i> there was an adjacent edge that belongs to the matching. Note that it's not necessary for each end of the matching edges to be in <i>s</i>. Each vertex also had an integer weight. Your goal was to count the number of nice sets (out of at most 2<sup>40</sup> total sets) with total weight exceeding the given threshold <i>t</i>.<br /><br />I won't describe its detailed solution, but I will mention the main idea that makes this problem tractable. At first sight, we have 2<sup>40</sup> sets which is way too much to handle one-by-one. However, it turns out that a set <i>s</i> consisting of some set <i>x</i> of vertices of the first part and some set <i>y</i> of vertices of the second part can be covered by a matching <i>if and only if</i> both <i>x</i> can be covered by a matching and <i>y</i> can be covered by a matching (but those don't have to be the same matching)! This idea allows to reduce the number of sets to consider to 2<sup>20</sup>, which is tractable.<br /><br />Thanks for reading, and check back for this week's summary! </div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/d53CzpKWb9g" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2016/12/a-maze-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-85035569166716996142016-12-05T23:22:00.000+03:002016-12-05T23:22:39.472+03:00A Makoto week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-G2GBsJZRTM4/WEVVT7rhDsI/AAAAAAAA9ac/5lOxlJ144-c4VLfX4kX4ahPP4Y3-_kgywCLcB/s1600/tco16finalstop6.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" src="https://1.bp.blogspot.com/-G2GBsJZRTM4/WEVVT7rhDsI/AAAAAAAA9ac/5lOxlJ144-c4VLfX4kX4ahPP4Y3-_kgywCLcB/s1600/tco16finalstop6.png" /></a></div>TopCoder Open 2016 Final fell on the Nov 21 - Nov 27 week (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=16842">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats&rd=16842&dn=1">results</a> on the left, <a href="http://blog.brucemerry.org.za/2016/11/tco-2016-finals.html">analysis by Bruce</a>). The final results have all finalists sorted by rating, with one notable exception: rng_58 has completely dominated the field, already winning on the first two problems but also adding the 1000-pointer to make it clear that others don't stand a chance. Extremely well done! With this result, Makoto is 3 out of 3 for TCO finals.<br /><br />Here's what <a href="https://community.topcoder.com/stat?c=problem_statement&pm=14250&rd=16842">the 1000-pointer</a> was about. You are given an undirected graph with at most 14 vertices. You make at most 50000 copies of this graph, without any edges between them, to obtain a bigger graph (with at most 14*50000 vertices). Then, you replace the resulting graph with its complement: for each pair of vertices connected by an edge, you remove that edge, and for each pair of vertices that don't have a connecting edge, you add one. How many Hamiltonian paths does the complementary graph have, modulo 998244353?<br /><br /><div class="separator" style="clear: both; text-align: center;"></div><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-4giWwqGxf_A/WEXJ7U7RbEI/AAAAAAAA9a0/1EGfYZAl-VAjoiLAaNdAj-duXg8hk_Q4ACLcB/s1600/cf381top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="166" src="https://4.bp.blogspot.com/-4giWwqGxf_A/WEXJ7U7RbEI/AAAAAAAA9a0/1EGfYZAl-VAjoiLAaNdAj-duXg8hk_Q4ACLcB/s640/cf381top5.png" width="640" /></a></div>Codeforces resumed its contests after a month-long break with Round 381 on Wednesday (<a href="http://codeforces.com/contest/739">problems</a>, <a href="http://codeforces.com/contest/739/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/48582">analysis</a>). TooDifficult continued his streak of victories, adding this round to the last two TopCoder SRMs. Amazing consistency!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-U9SFBI-gesU/WEXKArzy3_I/AAAAAAAA9a4/JefYAh2do287ww3J0UuiWCqA8TVTmOADgCLcB/s1600/codefestival2016finaltop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="282" src="https://1.bp.blogspot.com/-U9SFBI-gesU/WEXKArzy3_I/AAAAAAAA9a4/JefYAh2do287ww3J0UuiWCqA8TVTmOADgCLcB/s640/codefestival2016finaltop5.png" width="640" /></a></div>On Saturday, a brand new international onsite competition called Code Festival and ran by AtCoder took off in Tokyo. It has featured a diverse set of competitions, with the Code Festival 2016 Final being the closest to traditional rounds (<a href="http://cf16-final.contest.atcoder.jp/assignments">problems</a>, <a href="http://cf16-final.contest.atcoder.jp/standings">results</a>, top 5 on the left, <a href="http://cf16-final-open.contest.atcoder.jp/standings">online mirror results</a>, <a href="https://goo.gl/kpgYqj">analysis</a>). Only current and recent university students were allowed to join, nevertheless the field was top-notch. Facing very tough competition, tourist rose to the challenge and won in style by being the only one to solve all tasks. Congratulations!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-ps-VgWBxPyc/WEXKHiW80nI/AAAAAAAA9a8/7AfSC42Loz8GyBW8-INtVi8bXYp9aVbawCLcB/s1600/oc1617r8top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="164" src="https://4.bp.blogspot.com/-ps-VgWBxPyc/WEXKHiW80nI/AAAAAAAA9a8/7AfSC42Loz8GyBW8-INtVi8bXYp9aVbawCLcB/s640/oc1617r8top5.png" width="640" /></a></div>Open Cup 2016-17 Grand Prix of Europe on Sunday has completed the run of 5 consecutive Open Cup weekends (<a href="http://opencup.ru/files/och/gp8/problems1-e.pdf">problems</a>, <a href="http://opentrains.snarknews.info/~ejudge/res/res10358">results</a>, top 5 on the left, <a href="http://cerc.hsin.hr/index.php?page=results">CERC results on the same problems</a>, <a href="https://dl.dropboxusercontent.com/u/1909330/CERC%202016-%20Presentation%20of%20solutions.pdf">analysis</a>). This time ITMO 1 was head and shoulders above everybody, winning 11-9 (11-10 if you take CERC into account) - really unbelievable result! My team in particular got stuck after solving 8 problems in 3 hours, and couldn't solve any of the remaining 4 tasks in the last 2 hours. Also notable is Makoto solving 9 problems single-handedly. He was really on a roll that week :)<br /><br />Problem B in this round relied on a sound yet not widely known theoretical fact. You were given a bipartite graph with at most 20 vertices in each part (40 together). A set <i>s</i> of its vertices was called <i>nice</i> if there existed a matching that covers it - in other words, such that for every vertex from <i>s</i> there was an adjacent edge that belongs to the matching. Note that it's not necessary for each end of the matching edges to be in <i>s</i>. Each vertex also had an integer weight. Your goal was to count the number of nice sets (out of at most 2<sup>40</sup> total sets) with total weight exceeding the given threshold <i>t</i>.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-DHWo3Dvt8t8/WEXKl5N6EXI/AAAAAAAA9bA/vhdGR8Ezi40YotRbP8Kma0rcyCU-XvT0wCLcB/s1600/cf382top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="162" src="https://4.bp.blogspot.com/-DHWo3Dvt8t8/WEXKl5N6EXI/AAAAAAAA9bA/vhdGR8Ezi40YotRbP8Kma0rcyCU-XvT0wCLcB/s640/cf382top5.png" width="640" /></a></div>Finally, Codeforces Round 382 wrapped up the week on Sunday night (<a href="http://codeforces.com/contest/736">problems</a>, <a href="http://codeforces.com/contest/736/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/48659">analysis</a>). The coders in places from 3rd to 5th could've grabbed the first place if they could simply finish solving all problems in time, and that seems to have been quite doable, with more than 30 minutes left for Haghani and overtroll, and more than an hour left for MainDullMoeHand for just one problem - but they couldn't, and jcvb submitted his last problem with just 5 minutes to go to claim the victory. Well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-Vs9TwmZeoWM/WEXLwjgJ-dI/AAAAAAAA9bI/RcU1Cz--QxQG9oKqT0Rj0fyvGy8GgHDSgCLcB/s1600/20161122_123057.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="360" src="https://1.bp.blogspot.com/-Vs9TwmZeoWM/WEXLwjgJ-dI/AAAAAAAA9bI/RcU1Cz--QxQG9oKqT0Rj0fyvGy8GgHDSgCLcB/s640/20161122_123057.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2016/12/an-and-clique-week.html">my previous summary</a>, I have mentioned the problem that threw TCO 2016 Semifinal 2 into turmoil. You are given 1000 positive integers up to 10<sup>18</sup>. You need to find any subset of those integers with the following two properties:<br /><br /><ol style="text-align: left;"><li>Bitwise <i>and</i> of all integers in the subset is zero.</li><li>For any two integers in the subset, their bitwise <i>and</i> is not zero.</li></ol><br />The problem statement sounds so simple, and yet the solution is very hard to spot, so let me describe it. Since the bitwise and of all integers in the sought subset is zero, for every bit (position in the binary representation) at least one of the numbers in the subset doesn't have it set. Here comes the key idea: if there exists any such subset, then there exists such subset and a bit such that <i>exactly </i>one of the numbers in the subset doesn't have this bit set. Why? Because when for each bit at least two numbers don't have it, we can remove any number from the subset without violating properties 1 or 2.<br /><br />Now the problem becomes polynomial instead of exponential. Let's iterate over which bit will be present in all numbers except one, and which number will not have it. Which other numbers could we take into the subset? The numbers that have the chosen bit set and also have non-zero bitwise and with the chosen number. Property 2 will then always hold since all of those numbers have the chosen bit and thus non-zero bitwise ands, And for property 1, more numbers is always better, so we can afford to just take <i>all</i> numbers described above! We just need to check if their overall bitwise and (together with the first chosen number) is zero, and if yes, we have found our answer.<br /><br />One reason this solution seems quite hard to spot is that it operates in a counter-intuitive manner. On the first step, we're <i>reducing </i>our subset to achieve the desired property. But on the second step, we're actually <i>expanding</i> it back.<br /><br />Thanks for reading, and check back soon for the last week's summary!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/qVK4BbqjjBI" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2016/12/a-makoto-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-39918712550230075712016-12-04T14:50:00.000+03:002016-12-04T14:50:07.196+03:00An and-clique week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-6p-EzYTuAH4/WEQAKUgrmUI/AAAAAAAA9ZM/BsdyLuYA1tolwIQeFaWl6OKwtbdRkP5WwCLcB/s1600/srm702top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="78" src="https://3.bp.blogspot.com/-6p-EzYTuAH4/WEQAKUgrmUI/AAAAAAAA9ZM/BsdyLuYA1tolwIQeFaWl6OKwtbdRkP5WwCLcB/s640/srm702top5.png" width="640" /></a></div>The Nov 14 - Nov 20 week was busier. TopCoder SRM 702 on Tuesday was the last chance to practice before the TopCoder Open weekend (<a href="https://community.topcoder.com/stat?c=round_overview&rd=16832">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=16832&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://apps.topcoder.com/wiki/display/tc/SRM+702">analysis</a>). xudyh won the second SRM in a row, and was the only one to solve all three problems. Congratulations!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-oALwO5ipFXI/WEQAnwvMJfI/AAAAAAAA9ZQ/KNliecGOpfYF5UUka79V0EoIiOolHaMDQCLcB/s1600/tco16semi1top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="106" src="https://4.bp.blogspot.com/-oALwO5ipFXI/WEQAnwvMJfI/AAAAAAAA9ZQ/KNliecGOpfYF5UUka79V0EoIiOolHaMDQCLcB/s640/tco16semi1top5.png" width="640" /></a></div>The onsite event of TopCoder Open 2016, one of the main tournaments of the year, started with Semifinal 1 on Saturday (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=16839">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats&rd=16839&dn=1">results</a> on the left, <a href="http://blog.brucemerry.org.za/2016/11/topcoder-open-2016-semifinal-1.html">analysis by Bruce</a>). Top 3 advanced to the final round next Monday, and everything was essentially decided by the speed on <a href="https://community.topcoder.com/stat?c=problem_statement&pm=14297&rd=16839">the 500-pointer</a>. The problem statement was extremely simple: one needs to construct any weighted directed graph with at most 20 vertices that has exactly the given amount <i>k</i> of different minimum cuts. <i>k</i> is up to 1000.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/--2DhdohovX4/WEQA6Xs7yII/AAAAAAAA9ZU/aDyNAU6mEXU_sU79hr83ssbQOby6WYaJwCLcB/s1600/oc1617r7top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="174" src="https://3.bp.blogspot.com/--2DhdohovX4/WEQA6Xs7yII/AAAAAAAA9ZU/aDyNAU6mEXU_sU79hr83ssbQOby6WYaJwCLcB/s640/oc1617r7top5.png" width="640" /></a></div>Open Cup 2016-17 Grand Prix of Dolgoprudny took place early on Sunday (<a href="http://opencup.ru/files/och/gp7/problems1-e.pdf">problems</a>, <a href="http://opentrains.snarknews.info/~ejudge/res/res10357">results</a>, top 5 on the left). Team Past Glory retook the ground they lost to ITMO 1 in the overall standings a week ago - well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-6SurXNGmrT0/WEQBPw3ibUI/AAAAAAAA9Zc/6BvJAdxuaO0-Je9db283keq1b5A2aM9VwCLcB/s1600/tco16semi2top4.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="106" src="https://1.bp.blogspot.com/-6SurXNGmrT0/WEQBPw3ibUI/AAAAAAAA9Zc/6BvJAdxuaO0-Je9db283keq1b5A2aM9VwCLcB/s640/tco16semi2top4.png" width="640" /></a></div>Finally, TopCoder Open 2016 Semifinal 2 determined 3 more finalists (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=16841">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats&rd=16841&dn=1">results</a> on the left, <a href="http://blog.brucemerry.org.za/2016/11/tco-2016-semifinal-2-solutions.html">analysis by Bruce</a>). Unlike the first semifinal, which went more or less normal, this round was very unusual. For the first 10-15 minutes none of the participants, and almost none of the observers, could figure out how to solve the easiest 250-pointer problem. Because of that, the advancement in this round hinged on the ability to give up on a problem and clear one's head before the next one. It's worth mentioning that the 500-pointer was also in no way obvious. Congratulations to Enot on successfully navigating the tricky round and coming out on top!<br /><br />Here's <a href="https://community.topcoder.com/stat?c=problem_statement&pm=14448&rd=16841">the problem</a> that puzzled everybody. You are given 1000 positive integers up to 10<sup>18</sup>. You need to find any subset of those integers with the following two properties:<br /><br /><ol style="text-align: left;"><li>Bitwise <i>and</i> of all integers in the subset is zero.</li><li>For any two integers in the subset, their bitwise <i>and</i> is not zero.</li></ol>Can you see the key solution idea?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-k96Qv4WWPfQ/WEQCyR0MlLI/AAAAAAAA9Z4/CFRHNbgq84cKGbM9BsklRvkLAJ38sIWZwCLcB/s1600/IMAG1562.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="362" src="https://4.bp.blogspot.com/-k96Qv4WWPfQ/WEQCyR0MlLI/AAAAAAAA9Z4/CFRHNbgq84cKGbM9BsklRvkLAJ38sIWZwCLcB/s640/IMAG1562.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2016/12/a-cosplay-week.html">my previous summary</a>, I have mentioned an easy problem: you are given an <i>n</i> times <i>n</i> grid of uppercase English characters, where <i>n</i> is at least 3. This grid was built in the following way: first, we fill it with <i>n</i> different characters in such a way that each row and each column has exactly one occurrence of each character. Then, we replace exactly one character in the entire grid with another character. Your goal is to figure out which character has been replaced, and what was there originally.<br /><br />Here's a solution that's very easy to implement. First, we count the number of times each letter appears in the grid, and find letters that appear at least twice. Those are the original letters. Then, for each row and column of the grid we check if they contain at least one appearance of those letters. We will find exactly one row and exactly one column that will be missing one of those letters - and those are precisely the row, column and letter that we need to output.<br /><br />Thanks for reading, and check back later for more!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/29mv0mtCTHw" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2016/12/an-and-clique-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-42166427645533973852016-12-03T15:13:00.000+03:002016-12-03T15:13:30.933+03:00A cosplay week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-3q8leDh4kzg/WEKxxCtZIgI/AAAAAAAA81Y/37DtkgjIv4I7Fo4ZY5cpj8fdRjUmGsJpgCLcB/s1600/agc007top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="244" src="https://1.bp.blogspot.com/-3q8leDh4kzg/WEKxxCtZIgI/AAAAAAAA81Y/37DtkgjIv4I7Fo4ZY5cpj8fdRjUmGsJpgCLcB/s640/agc007top5.png" width="640" /></a></div>The Nov 7 - Nov 13 week woke up late with AtCoder Grand Contest 007 on Saturday (<a href="http://agc007.contest.atcoder.jp/assignments">problems</a>, <a href="http://agc007.contest.atcoder.jp/standings">results</a>, top 5 on the left, <a href="http://agc007.contest.atcoder.jp/data/agc/007/editorial.pdf">analysis</a>). The problemset seems quite well-rounded, offering competitors a choice of different strategies. cospleermusora has figured out the winning strategy this time - start with the three hardest problems since they're worth a lot more points, and then solve whichever easy problems there's time for. Great idea and execution!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-LAZCNIqo6tQ/WEKzMaRbAOI/AAAAAAAA81o/o-07t2il-zENaH8YVhlGsBMlfvr8MtXSACLcB/s1600/oc1617r6top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="186" src="https://4.bp.blogspot.com/-LAZCNIqo6tQ/WEKzMaRbAOI/AAAAAAAA81o/o-07t2il-zENaH8YVhlGsBMlfvr8MtXSACLcB/s640/oc1617r6top5.png" width="640" /></a></div>Open Cup 2016-17 Czech Grand Prix took the usual Sunday spot (<a href="http://opencup.ru/index.cgi?data=macros/stage&head=index&menu=index&stg=6&region=main&ncup=och&class=och">results</a>, top 5 on the left). The ITMO 1 team won again and started to create quite a gap at the top of the overall standings. Amazing performance!<br /><br />Problem J in this round was very easy, and yet it required some thinking to avoid too many special cases in code. You are given an <i>n</i> times <i>n</i> grid of uppercase English characters, where <i>n</i> is at least 3. This grid was built in the following way: first, we fill it with <i>n</i> different characters in such a way that each row and each column has exactly one occurrence of each character. Then, we replace exactly one character in the entire grid with another character. Your goal is to figure out which character has been replaced, and what was there originally.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-Zrbz3PhJbIc/WEKzcMWzN3I/AAAAAAAA81s/Um23oZ5l00wI0qzQunaFlMfuXxegUOuOgCKgB/s1600/IMAG1757.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="200" src="https://3.bp.blogspot.com/-Zrbz3PhJbIc/WEKzcMWzN3I/AAAAAAAA81s/Um23oZ5l00wI0qzQunaFlMfuXxegUOuOgCKgB/s200/IMAG1757.jpg" width="193" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2016/11/yet-another-triangle-week.html">my previous summary</a>, I've mentioned an interactive Open Cup problem: the judging program has a hidden non-degenerate triangle. The coordinates of its vertices are integers not exceeding 1000 by absolute value. You're allowed to make at most 1000 queries, and your goal is to determine the coordinates of the vertices of the triangle. In each query, you choose a line (more precisely, a half-plane), and you're told the areas of the two parts this line splits the triangle into (one of them can be 0 if it doesn't intersect the triangle).<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-HzVcpzI2KQ8/WEKzreiN-zI/AAAAAAAA810/_-lOfVrEBCwfd5IYBfMjHjycTzYkPLK1ACKgB/s1600/IMAG1758.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" height="178" src="https://4.bp.blogspot.com/-HzVcpzI2KQ8/WEKzreiN-zI/AAAAAAAA810/_-lOfVrEBCwfd5IYBfMjHjycTzYkPLK1ACKgB/s200/IMAG1758.jpg" width="200" /></a></div>Here is the solution of our team, which we've created together with Michael Levin: first, we figure out the bounding box of the triangle, using binary search with horizontal and vertical half-planes. At least one of the corners of the bounding box is a vertex of the triangle, which we can find using a 45-degree half-plane which cuts off just one small corner from the bounding box.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-TNTL38Oz6Qs/WEK2mUx2j7I/AAAAAAAA82g/6Jg-y-nJ1dUEjsLacU4WfO4qdJlTA9oDgCKgB/s1600/IMAG1759.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="172" src="https://2.bp.blogspot.com/-TNTL38Oz6Qs/WEK2mUx2j7I/AAAAAAAA82g/6Jg-y-nJ1dUEjsLacU4WfO4qdJlTA9oDgCKgB/s200/IMAG1759.jpg" width="200" /></a></div>When we know a vertex and a 90 degree angle containing the rest, we can use binary search by angle using lines passing through this vertex to find the lines containing the two sides. Finally, we can find the remaining two vertices by binary searching along one of the lines with half-planes parallel to the other line.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-4R-qCaPye-I/WEK2p66TpNI/AAAAAAAA82k/849DiQ8NAeMNKvVnhSMf8TR7V-wz4w2-QCKgB/s1600/IMAG1760.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" height="195" src="https://4.bp.blogspot.com/-4R-qCaPye-I/WEK2p66TpNI/AAAAAAAA82k/849DiQ8NAeMNKvVnhSMf8TR7V-wz4w2-QCKgB/s200/IMAG1760.jpg" width="200" /></a></div>This solution has 4 steps, with the first and last step sharing the same binary search problem (given a direction, find the first half-plane with this direction that has non-zero intersection area), so one needed to implement 3 different functions for the interaction. On the good side, the solution doesn't have any special casing at all.<br /><br />Do you know a simpler approach?</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/pC-qN-LaYMI" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2016/12/a-cosplay-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-13810166974358815082016-11-20T19:16:00.001+03:002016-11-20T19:21:03.949+03:00Yet another triangle week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-f1wzs8vyvmo/WDG8elui-jI/AAAAAAAA8hg/Oxx_LuNjRXwrN_aiGdWSHmOOKN7OpJ-dACLcB/s1600/oc1617r5top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="170" src="https://1.bp.blogspot.com/-f1wzs8vyvmo/WDG8elui-jI/AAAAAAAA8hg/Oxx_LuNjRXwrN_aiGdWSHmOOKN7OpJ-dACLcB/s640/oc1617r5top5.png" width="640" /></a></div>The first November week included the fifth stage of the 2016-17 Open Cup, the Grand Prix of Siberia (<a href="http://opencup.ru/files/och/gp5/problems1-e.pdf">problems</a>, <a href="http://opentrains.snarknews.info/~ejudge/res/res10355">results</a>, top 5 on the left). Team Havka-papstvo dominated the proceedings, and topped the cake with the only passing solution for the very tedious problem 10 - congratulations!<br /><br />I'd like to highlight the interactive problem 3, which turned out to be the second most difficult. The judging program has a hidden non-degenerate triangle. The coordinates of its vertices are integers not exceeding 1000 by absolute value. You're allowed to make at most 1000 queries, and your goal is to determine the coordinates of the vertices of the triangle. In each query, you choose a line (more precisely, a half-plane), and you're told the areas of the two parts this line splits the triangle into (one of them can be 0 if it doesn't intersect the triangle). There are two steps to solving this one: figuring out how to do it, and then figuring out how to do it in such a way that the implementation isn't a nightmare :)<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-nk5G0uQwzzQ/WDHMVYmZdaI/AAAAAAAA8iI/wu-lAvdYYD8TWWaFzc2dni6dYIa4tfSLQCLcB/s1600/IMAG1473.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="362" src="https://3.bp.blogspot.com/-nk5G0uQwzzQ/WDHMVYmZdaI/AAAAAAAA8iI/wu-lAvdYYD8TWWaFzc2dni6dYIa4tfSLQCLcB/s640/IMAG1473.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2016/11/a-triangle-week.html">my previous summary</a>, I've described another triangle problem: you are given 200000 points on the plane which are guaranteed to be randomly placed within a bounding box, and need to find three points which form a triangle with the largest area.<br /><br />The solution is surprisingly straightforward: we find the convex hull of the given points, and then try all triangles with vertices from the convex hull to determine the largest one. It is correct because it's not hard to see that when we fix 2 out of 3 vertices of the triangle, the third one needs to be as far from that line as possible, which means it's a farthest point in some direction, which means it's a vertex of the convex hull. And it is fast enough because it turns out that a set of random points has only O(logn) points on average on its convex hull (see <a href="http://valis.cs.uiuc.edu/~sariel/papers/notes/rand_hull.ps">this paper</a>).<br /><br />Thanks for reading, and check back soon for the next week's summary!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/ekmfuMTw3EA" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2016/11/yet-another-triangle-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-24078153200469649252016-11-20T18:02:00.002+03:002016-11-20T18:57:40.876+03:00A triangle week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-LNLiXkHZ82Y/WDG2y-wsh-I/AAAAAAAA8hI/CSVrS-B-p04JMG7baoN7L4qvAGXu4S__wCLcB/s1600/srm701top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="80" src="https://4.bp.blogspot.com/-LNLiXkHZ82Y/WDG2y-wsh-I/AAAAAAAA8hI/CSVrS-B-p04JMG7baoN7L4qvAGXu4S__wCLcB/s640/srm701top5.png" width="640" /></a></div>The last week of October was relatively busy. First off, TopCoder SRM 701 took place on Wednesday (<a href="https://community.topcoder.com/stat?c=round_overview&rd=16822">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=16822&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://apps.topcoder.com/wiki/display/tc/SRM+701">analysis</a>). The top 3 could be a foreshadowing for the upcoming TCO 2016 Semifinal 2, but unfortunately xudyh could not make it to Washington (does anybody know why?). Nevertheless, congratulations on the SRM victory!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-SRPkiLckMWo/WDG4BhwnRTI/AAAAAAAA8hU/maIoYotoue0hWSaC8_aCQrH1LZE9DbQBgCLcB/s1600/agc006top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="244" src="https://1.bp.blogspot.com/-SRPkiLckMWo/WDG4BhwnRTI/AAAAAAAA8hU/maIoYotoue0hWSaC8_aCQrH1LZE9DbQBgCLcB/s640/agc006top5.png" width="640" /></a></div>Then, AtCoder held its Grand Contest 006 on Saturday (<a href="http://agc006.contest.atcoder.jp/assignments">problems</a>, <a href="http://agc006.contest.atcoder.jp/standings#page_1">results</a>, top 5 on the left, <a href="http://agc006.contest.atcoder.jp/data/agc/006/editorial.pdf">analysis</a>). apiad has dominated the field by being the only one to solve all problems, and he has also demonstrated an unorthodox strategy by starting from the hardest problems - so he would've been first even if he didn't finish the 3 easier ones!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-DjlqngsHiME/WDG5I4AG-SI/AAAAAAAA8hY/TpCLDiQiDg4uEV_ANIMXFrH6J7eMWEJfACLcB/s1600/oc1617r4top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="172" src="https://3.bp.blogspot.com/-DjlqngsHiME/WDG5I4AG-SI/AAAAAAAA8hY/TpCLDiQiDg4uEV_ANIMXFrH6J7eMWEJfACLcB/s640/oc1617r4top5.png" width="640" /></a></div>And finally, Open Cup 2016-17 Eastern Grand Prix took place on Sunday (<a href="http://opencup.ru/files/och/gp4/problems1-e.pdf">problems</a>, <a href="http://opentrains.snarknews.info/~ejudge/res/res10354">results</a>, top 5 on the left). SPb ITMO 1 team has jumped into a big lead in the overall standings after this round - congratulations!<br /><br />Problem B was on the boundary of "oh, beautiful observation" and "oh, nasty trick" :) Which feeling does it leave you with? You are given 200000 points on the plane which are guaranteed to be randomly placed within a bounding box, and need to find three points which form a triangle with the largest area.<br /><br />Thanks for reading, and check back soon for the November news!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/1cp4LORA9DU" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2016/11/a-triangle-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-55957863078728287262016-11-20T17:40:00.002+03:002016-11-20T17:40:33.180+03:00A Canada week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-TKY5JMD9TvA/WDG004PLcxI/AAAAAAAA8g4/tqtd-iH8PVg5MlDuUbV6rcROKzHtj14oACLcB/s1600/canadacup2016top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="166" src="https://3.bp.blogspot.com/-TKY5JMD9TvA/WDG004PLcxI/AAAAAAAA8g4/tqtd-iH8PVg5MlDuUbV6rcROKzHtj14oACLcB/s640/canadacup2016top5.png" width="640" /></a></div>The Oct 17 - Oct 23 week featured just the Canada Cup by Codeforces (<a href="http://codeforces.com/contest/725">problems</a>, <a href="http://codeforces.com/contest/725/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/47974">analysis</a>). If not for challenges, just 5 points would've separated eatmore and tzupengwang - congratulations to both! I could not make this round, so I don't have anything to share about its problems.<div><br /></div><div>Check back soon for the hopefully longer summary of the following week :)</div></div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/CQEvJrkxDTI" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2016/11/a-canada-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-24059742787853678572016-11-20T00:40:00.000+03:002016-11-20T00:40:00.923+03:00An unshuffle week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-zs65FYZYt7A/WDC9BC3QatI/AAAAAAAA8b0/xylCXONdCYUpSNYpNXJ-Fhf-lNH42OXEwCLcB/s1600/srm700top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="78" src="https://1.bp.blogspot.com/-zs65FYZYt7A/WDC9BC3QatI/AAAAAAAA8b0/xylCXONdCYUpSNYpNXJ-Fhf-lNH42OXEwCLcB/s640/srm700top5.png" width="640" /></a></div>During the Oct 10 - Oct 16 week, TopCoder has hit its next milestone: SRM 700 (<a href="https://community.topcoder.com/stat?c=round_overview&rd=16821">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=16821&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://apps.topcoder.com/wiki/display/tc/SRM+700">analysis</a>). Despite the starting time of 4am, the first three spots were occupied by contestants from St Petersburg and Moscow. The first place went to _aid, who has recently joined the ACM ICPC World Champion team SPbSU Base - so all other teams will not have an easy time at 2017 World Finals :) Congratulations!<br /><div><br /></div><div><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-3WQF3AcYunU/WDDGbtbImsI/AAAAAAAA8cQ/ec3FF_YHEG4sT7Lu0kinWDRNqwK0sPJjgCLcB/s1600/IMAG1397.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="362" src="https://2.bp.blogspot.com/-3WQF3AcYunU/WDDGbtbImsI/AAAAAAAA8cQ/ec3FF_YHEG4sT7Lu0kinWDRNqwK0sPJjgCLcB/s640/IMAG1397.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2016/11/a-fourier-combination-week.html">my previous summary</a>, I have mentioned a problem in the trademark style of Ivan Kazmenko: You're given the following random number generator, an implementation of the Fischer-Yates shuffle, and a program using them:</div><div><br /></div><div><span style="font-family: "courier new" , "courier" , monospace;">Function random (range):</span></div><div><span style="font-family: "courier new" , "courier" , monospace;"> state := (state * 1664525 + 1013904223) mod 2<sup>32</sup>;</span></div><div><span style="font-family: "courier new" , "courier" , monospace;"> return (state * range) div 2<sup>32</sup>;</span></div><div><span style="font-family: "courier new" , "courier" , monospace;"><br /></span></div><div><span style="font-family: "courier new" , "courier" , monospace;">Function shuffle (array):</span></div><div><span style="font-family: "courier new" , "courier" , monospace;"> n := length of array;</span></div><div><span style="font-family: "courier new" , "courier" , monospace;"> for i := 0, 1, 2, ..., n - 1:</span></div><div><span style="font-family: "courier new" , "courier" , monospace;"> j := random (i + 1);</span></div><div><span style="font-family: "courier new" , "courier" , monospace;"> swap(array[i], array[j]);</span></div><div><span style="font-family: "courier new" , "courier" , monospace;"> return array;</span></div><div><span style="font-family: "courier new" , "courier" , monospace;"><br /></span></div><div><span style="font-family: "courier new" , "courier" , monospace;">state := seed;</span></div><div><span style="font-family: "courier new" , "courier" , monospace;">n := 10000;</span></div><div><span style="font-family: "courier new" , "courier" , monospace;">array := [1, 2, ..., n];</span></div><div><span style="font-family: "courier new" , "courier" , monospace;">array := shuffle (array);</span></div><div><span style="font-family: "courier new" , "courier" , monospace;">array := shuffle (array);</span></div><div><br /></div><div>In other words, we shuffle the numbers from 1 to n twice. The particular generator used here is well-known, so no particular weaknesses could be expected except of course the fact that it's a linear congruential generator. The task is: given the final state of the array, find what the seed was.</div><div><br /></div><div>There are two main ideas necessary to solve this problem. The first idea is: if we know the numbers that the generator returned on two concrete calls (i.e., on <i>p</i>-th step and on <i>q</i>-th step), there are only so many (on the order of 100) possibilities for the seed that we can try them all, and moreover, we can enumerate all of them efficiently.<br /><br />In order to enumerate them, we can notice that the value of the <i>state</i> variable on <i>p</i>-th step is a linear function of the initial seed. Because of this, having two return values fixed leads to two inequalities that look like <i>l</i> <= <i>seed</i> * <i>a</i> <= <i>r </i>(mod 2<sup>32</sup>)<i>.</i> We can solve this system of inequalities using an algorithm similar to the Euclidean one.<br /><br />The second idea is that it's not actually that hard to find two concrete return values of the generator. During each shuffle, each number participates in at least one swap: when the variable <i>i</i> passes through the cell containing it. It's also not hard to see that on average quite a few numbers will participate in exactly one swap. And because this set of numbers is fairly random for each of the two shuffles, there will be a significant amount of numbers that have participated in exactly two swaps overall. And since we know the starting and ending position for each number, we just need to guess which was its "middle" position after the first swap.<br /><br />So here's the overall solution structure: we iterate over all numbers from <i>n</i> to 1 that have moved to the left after two shuffles. For each of those numbers, we iterate over the "middle" position between the final positions and the starting position. We find all seeds that would make this number do the corresponding jumps, and then check if each of those seeds leads to the overall result we see. We expect to find the seed after trying just a few initial numbers.<br /><br />Thanks for reading, and wish me luck in today's TopCoder Open semifinal (<a href="https://www.timeanddate.com/worldclock/fixedtime.html?msg=TopCoder+Open+2016+Algo+Semifinal+1&iso=20161119T20&p1=263&ah=2">starting time</a>, <a href="https://www.twitch.tv/topcoder_official">broadcast link</a>)!</div></div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/fgCwQjypn2c" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2016/11/an-unshuffle-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-42231042485243417752016-11-07T23:50:00.000+03:002016-11-08T07:55:01.322+03:00A Fourier combination week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-sZ2G9JTRUKU/WB8FDhX77oI/AAAAAAAA8B4/horOnzLsXHM9h3ba58RO1-0RdlmRNe1KgCLcB/s1600/iccfinaltop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="166" src="https://3.bp.blogspot.com/-sZ2G9JTRUKU/WB8FDhX77oI/AAAAAAAA8B4/horOnzLsXHM9h3ba58RO1-0RdlmRNe1KgCLcB/s640/iccfinaltop5.png" width="640" /></a></div>The Oct 3 - Oct 9 week was calmer. Intel Code Challenge Final Round has gathered the top competitors for 3 hours instead of the usual 2 we see on Codeforces (<a href="http://codeforces.com/contest/724">problems</a>, <a href="http://codeforces.com/contest/724/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/47644">analysis</a>). Maybe TooDifficult did not notice this, as he finished all problems within the first 2 hours anyway, and thus won easily :) Congratulations!<br /><div><br /></div><div><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-VUnSH40DXDg/WB8FgUeIKkI/AAAAAAAA8B8/9R67eTU3ANITGQ8xpSGB7vu4BtpzLmKKACLcB/s1600/oc1617r3top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="175" src="https://1.bp.blogspot.com/-VUnSH40DXDg/WB8FgUeIKkI/AAAAAAAA8B8/9R67eTU3ANITGQ8xpSGB7vu4BtpzLmKKACLcB/s640/oc1617r3top5.png" width="640" /></a></div>On Sunday, Open Cup 2016-17 Grand Prix of SPb has completed the 3-week run (<a href="http://opentrains.snarknews.info/~ejudge/res/res10353">results</a>, top 5 on the left). Reminding us how things usually go in Open Cup contests, Past Glory team have won convincingly, and were also the only team to solve problem I - great job!<br /><br />Here's what the problem was about. You're given the following random number generator, an implementation of the Fischer-Yates shuffle, and a program using them:<br /><span style="font-family: "courier new" , "courier" , monospace;"><br /></span><span style="font-family: "courier new" , "courier" , monospace;">Function random (range):</span><br /><span style="font-family: "courier new" , "courier" , monospace;"> state := (state * 1664525 + 1013904223) mod 2<sup>32</sup>;</span><br /><span style="font-family: "courier new" , "courier" , monospace;"> return (state * range) div 2<sup>32</sup>;</span><br /><span style="font-family: "courier new" , "courier" , monospace;"><br /></span><span style="font-family: "courier new" , "courier" , monospace;">Function shuffle (array):</span><br /><span style="font-family: "courier new" , "courier" , monospace;"> n := length of array;</span><br /><span style="font-family: "courier new" , "courier" , monospace;"> for i := 0, 1, 2, ..., n - 1:</span><br /><span style="font-family: "courier new" , "courier" , monospace;"> j := random (i + 1);</span><br /><span style="font-family: "courier new" , "courier" , monospace;"> swap(array[i], array[j]);</span><br /><span style="font-family: "courier new" , "courier" , monospace;"> return array;</span><br /><span style="font-family: "courier new" , "courier" , monospace;"><br /></span><span style="font-family: "courier new" , "courier" , monospace;">state := seed;</span><br /><span style="font-family: "courier new" , "courier" , monospace;">n := 10000;</span><br /><span style="font-family: "courier new" , "courier" , monospace;">array := [1, 2, ..., n];</span><br /><span style="font-family: "courier new" , "courier" , monospace;">array := shuffle (array);</span><br /><span style="font-family: "courier new" , "courier" , monospace;">array := shuffle (array);</span><br /><br />In other words, we shuffle the numbers from 1 to n twice. The particular generator used here is well-known, so no particular weaknesses could be expected except of course the fact that it's a linear congruential generator. The task is: given the final state of the array, find what the seed was.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-htPNgWpr4m8/WCDnxs_timI/AAAAAAAA8SY/xVGHLCfPrsAkPSOLSqTASjq0hdtObeEbgCLcB/s1600/IMAG1329.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="362" src="https://2.bp.blogspot.com/-htPNgWpr4m8/WCDnxs_timI/AAAAAAAA8SY/xVGHLCfPrsAkPSOLSqTASjq0hdtObeEbgCLcB/s1600/IMAG1329.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2016/11/a-week-after-month.html">my previous summary</a>, I've mentioned a tricky AtCoder combinatorics problem: You are given a tree with n<=200000 vertices. Now we consider all C(<i>n</i>,<i>k</i>) ways to pick <i>k</i> vertices of the tree, and for each of them we consider the "convex hull" of the <i>k</i> vertices: the smallest part of the tree that connects all of them together. Your goal is to find the sum of the sizes of those convex hulls over all C(<i>n</i>,<i>k</i>) ways. What's more, you need to find n sums: for each value of <i>k</i> between 1 and <i>n</i>. Each sum must be computed modulo 924844033.</div><div><br /></div><div>Even though the problem statement doesn't mention probabilities and expected values, the solution starts with an observation that is very similar to the linearity of expectation: in order to find the sum of the sizes of the convex hulls, we will find for each vertex the number of convex hulls containing it, and then add up those numbers.</div><div><br /></div><div>In order to find the latter, let's find the number of convex hulls <i>not</i> containing it, and subtract it from C(<i>n</i>,<i>k</i>). In order for the convex hull to not contain a given vertex, all <i>k</i> chosen vertices must lie completely within one of the subtrees formed by removing this vertex from the tree. So if the sizes of all 2(<i>n</i>-1) subtrees of the original tree are <i>a</i><sub>1</sub>, <i>a</i><sub>2</sub>, ..., <i>a</i><sub>2(<i>n</i>-1)</sub>, then we need to find Î£<i><sub>i</sub></i>C(<i>a<sub>i</sub></i>, <i>k</i>). Finding all <i>a<sub>i</sub></i> is a standard task solved by a traversal of the tree, so we can solve our problem for one value of <i>k</i> in O(<i>n</i>). However, since we have <i>n</i> possible values of <i>k</i> to process, the total running time will be O(<i>n</i><sup>2</sup>) which is too slow.<br /><br />The idea to speed up such computation from O(<i>n</i><sup>2</sup>) to O(<i>n</i>log<i>n</i>) using Fast Fourier Transform is not new, but I don't think I've described it in this blog before. Let's reformulate the problem slightly: let <i>b<sub>i</sub></i> be the number of subtrees of size <i>i</i>. We need to find Î£<i><sub>i</sub></i>C(<i>i</i>, <i>k</i>)*<i>b<sub>i</sub></i> for each <i>k</i>. Now let's transform our sum:<br /><br />Î£<i><sub>i</sub></i>C(<i>i</i>, <i>k</i>)*<i>b<sub>i</sub></i> = Î£<i><sub>i</sub></i><i>b<sub>i</sub></i>*<i>i</i>!/<i>k</i>!/(<i>i</i>-<i>k</i>)! = 1/<i>k</i>!*Î£<i><sub>i</sub></i>(<i>b<sub>i</sub></i>*<i>i</i>!)*(1/(<i>i</i>-<i>k</i>)!)<br /><br />Now we can notice that the remaining sum is nothing else but multiplication of polynomials, which can be done fast using FFT. To make it completely clear, let's denote <i>u<sub>i</sub></i>=<i>b<sub>i</sub></i>*<i>i</i>!, and <i>v<sub>j</sub></i>=1/(<i>n</i>-<i>j</i>)!, and multiply two polynomials with those coefficients. The (<i>n</i>+<i>k</i>)-th coefficient of the product will be Î£<i><sub>i</sub></i><i>u<sub>i</sub></i><i>v<sub>n+k-i</sub></i> = Î£<i><sub>i</sub></i>(<i>b<sub>i</sub></i>*<i>i</i>!)*(1/(<i>n</i>-(<i>n</i>+<i>k</i>-<i>i</i>)!) = Î£<i><sub>i</sub></i>(<i>b<sub>i</sub></i>*<i>i</i>!)*(1/(<i>i</i>-<i>k</i>)!), just as we need.<br /><br />To conclude, it also seems that this technique can be applied to a wide variety of sums, not just those involving C(<i>n</i>,<i>k</i>). The only property that we need from the function being summed is that it must decompose as a product of functions of <i>n</i>, <i>k</i>, and <i>n</i>-<i>k</i>. However, C(<i>n</i>,<i>k</i>) seems to be the only practically relevant function with this property. Do you have an example of a different such function in mind, or maybe you can even point me to other problems solved using this trick?<br /><br />Thanks for reading, and check back for more!</div></div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/Qor64CDu4xE" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2016/11/a-fourier-combination-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-85208500399998006342016-11-06T15:30:00.000+03:002016-11-06T15:30:04.323+03:00A week after a month<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/-Y4dgDDwCvd8/WAHcNUpJwpI/AAAAAAAA7gk/5rhxhMqmvVkcgz3xiGjWWCioYu_gefzOQCLcB/s1600/srm699top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" src="https://2.bp.blogspot.com/-Y4dgDDwCvd8/WAHcNUpJwpI/AAAAAAAA7gk/5rhxhMqmvVkcgz3xiGjWWCioYu_gefzOQCLcB/s1600/srm699top5.png" /></a></div>The last week of September was rather busy. The competitions started right on Monday with TopCoder SRM 699 (<a href="https://community.topcoder.com/stat?c=round_overview&rd=16803">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=16803&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://apps.topcoder.com/wiki/display/tc/SRM+699#TwoSquares">analysis</a>, <a href="https://youtu.be/FLHKlMEEtKY">my screencast</a>). At the end of the coding phase, it seemed unusually easy for the recent TopCoder standard, with 8 submissions for the Hard problem. However, the system testing phase showed that even though the general idea of a solution is not hard to see, figuring out all details correctly within the 75-minute round is nearly impossible. matthew99a has thus earned his third SRM victory thanks to super fast solution for the 500, and a solid 100 challenge points to boot. Congratulations!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-mEX3ZJqBhCI/WAHfU6OL9YI/AAAAAAAA7gw/DniCXHqqWaMsWVLZp3PHYJH1fgfm6rWjwCLcB/s1600/agc005top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="244" src="https://1.bp.blogspot.com/-mEX3ZJqBhCI/WAHfU6OL9YI/AAAAAAAA7gw/DniCXHqqWaMsWVLZp3PHYJH1fgfm6rWjwCLcB/s640/agc005top5.png" width="640" /></a></div>AtCoder Grand Contest 005 has followed on Saturday (<a href="http://agc005.contest.atcoder.jp/assignments">problems</a>, <a href="http://agc005.contest.atcoder.jp/standings#page_1">results</a>, top 5 on the left, <a href="http://agc005.contest.atcoder.jp/data/agc/005/editorial.pdf">analysis</a> - scroll down for English). tourist seemed to have started 10 minutes late, so there were some doubts as to who would win initially, but he quashed all of those by finishing all problems within an hour of starting. Amazing job!<br /><br /><a href="http://agc005.contest.atcoder.jp/tasks/agc005_f">The last problem</a> was a great demonstration of the power of combinatorics. You are given a tree with <i>n</i><=200000 vertices. Now we consider all C(<i>n</i>,<i>k</i>) ways to pick <i>k</i> vertices of the tree, and for each of them we consider the "convex hull" of the <i>k</i> vertices: the smallest part of the tree that connects all of them together. Your goal is to find the sum of the sizes of those convex hulls over all C(<i>n</i>,<i>k</i>) ways. What's more, you need to find <i>n</i> sums: for each value of <i>k</i> between 1 and <i>n</i>. Each sum must be computed modulo 924844033.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-aVPk1ykCSKI/WB7_tAaWVgI/AAAAAAAA8Bo/xIBo4ErI42My_zzFwVMfdZPEFGhYiSddACLcB/s1600/iccelimtop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="166" src="https://4.bp.blogspot.com/-aVPk1ykCSKI/WB7_tAaWVgI/AAAAAAAA8Bo/xIBo4ErI42My_zzFwVMfdZPEFGhYiSddACLcB/s640/iccelimtop5.png" width="640" /></a></div>Intel Code Challenge Elimination Round started just 15 minutes after the end of AGC (<a href="http://codeforces.com/contest/722">problems</a>, <a href="http://codeforces.com/contest/722/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/47497">analysis</a>), so it's super impressive that anta shows in the top 5 of the both events. However, he could not come close to FatalEagle, who has earned his first Codeforces victory thanks to solving all problems and finding 9 successful challenges while doing so. Congratulations!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-0O8TdWTR_zk/WB8AVvQLK_I/AAAAAAAA8Bs/MR1Yqv6aLVg3zBLF42aozSyOAd4Yc0UUwCLcB/s1600/oc1617r2top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="180" src="https://1.bp.blogspot.com/-0O8TdWTR_zk/WB8AVvQLK_I/AAAAAAAA8Bs/MR1Yqv6aLVg3zBLF42aozSyOAd4Yc0UUwCLcB/s640/oc1617r2top5.png" width="640" /></a></div>The second stage of Open Cup 2016-17, Grand Prix of Eurasia, has wrapped up the week (<a href="http://opentrains.snarknews.info/~ejudge/res/res10352">results</a>, top 5 on the left). Problem 1 looked very daunting initially, but as one unraveled it the actual solution turned out pretty and short. You are given an array with <i>n</i><=100000 numbers, and want to find the segment of that array with the largest sum. That would be too easy, of course, so there's an added twist: you're allowed to do at most <i>k</i><=10 swaps of two numbers in the array before picking a segment.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-4ZyYtWc6N2E/WB8iIGINNSI/AAAAAAAA8Cw/O1XOoddpsbEumprpDfzh1HJEKMGT_smsQCLcB/s1600/IMAG1278.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="362" src="https://1.bp.blogspot.com/-4ZyYtWc6N2E/WB8iIGINNSI/AAAAAAAA8Cw/O1XOoddpsbEumprpDfzh1HJEKMGT_smsQCLcB/s640/IMAG1278.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2016/10/an-open-week.html">my previous summary</a>, I've mentioned another tricky Open Cup problem: you are given a connected undirected graph with at most 2000 vertices and 2000 edges, where each edge needs to be colored either red or blue. You need to do the coloring using a single alternating walk: you start in some vertex, then keep moving along the edges, coloring the first edge you pass red, the second blue, the third red again, and so on. You are allowed to pass the same vertex and even the same edge twice, and when you pass the same edge multiple times, the last color used stays. Is it possible to obtain the required coloring?<br /><br />It seems hard to approach this problem because it seems that we can do anything: if we color an edge with the wrong color, we can come back later and use the correct color again, so it's not clear how to see if we're making good progress. The main observation is to look at this process from the end. The <i>last</i> edge we traverse must be colored with its intended color. The edge we traverse before it must also be colored with its intended color, unless it's the same edge. More generally, at each point we have some set of edges we've already traversed, which can now be traversed with any color, and the remaining edges which must be first traversed with their intended color, and our goal is to traverse each edge at least once.<br /><br />Also, since can always go back and return to any vertex we've already visited with the same parity, the whole concept of a walk is a bit misleading now. We just have a set of (vertex, parity) pairs we can reach, and a set of edges that we've traversed at least once, and are gradually expanding both sets. If two vertices <i>a</i> and <i>b</i> are connected using an untraversed edge with color c, and we have reached (<i>a</i>, <i>c</i>), then we can traverse the edge, and reach (<i>b</i>, 1-<i>c</i>) pair. If the edge is already traversed, then we can also use it to reach (<i>b</i>, <i>c</i>) from (<i>a</i>, 1-<i>c</i>).<br /><br />To put the solution together, we will maintain a queue of possible moves. When processing a move in the queue, we will add new moves that were made possible by this move to the queue. It's important here to remember that the new moves are of two types: those starting in the new vertex we've reached, and those that use the edge we just traversed with the other color, both in the reverse and in the same direction - many teams have forgotten to account for the latter. And of course we must start from some vertex and some parity - but since the graph is just 2000 in size, we can just iterate over all starting - more precisely, finishing :) - (vertex, parity) pairs.<br /><br />Thanks for reading, and check back soon for the next week's summary! I promise, "soon" does not mean a month this time :)<br /><br /></div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/CyWzYHYqnQk" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2016/11/a-week-after-month.htmltag:blogger.com,1999:blog-1953325079793449971.post-52213874273445399062016-10-11T23:07:00.001+03:002016-10-11T23:07:13.133+03:00An open week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"></div><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-SbEUBCV1fes/V_0-8fh77KI/AAAAAAAA7eg/iXv_h4fjYrwK7AkKYYGiDNwpxdbzBDA2wCEw/s1600/oc1617r1top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" src="https://2.bp.blogspot.com/-SbEUBCV1fes/V_0-8fh77KI/AAAAAAAA7eg/iXv_h4fjYrwK7AkKYYGiDNwpxdbzBDA2wCEw/s1600/oc1617r1top5.png" /></a></div>The September 19 - September 25 week contained the first stage of Open Cup 2016-17: Grand Prix of Japan (<a href="http://opentrains.snarknews.info/~ejudge/res/res10351">results</a>, top 5 on the left). Some teams have competed on this problemset earlier during the Petrozavodsk camp, and two of those teams remained in first two places after everybody else joined - congratulations to Moscow SU Trinity and KTH Omogen Heap!<br /><br />Problem I in this round possessed the right mix of simple statement and interesting solution, while not being very hard: you are given a connected undirected graph with at most 2000 vertices and 2000 edges, where each edge needs to be colored either red or blue. You need to do the coloring using a single alternating walk: you start in some vertex, then keep moving along the edges, coloring the first edge you pass red, the second blue, the third red again, and so on. You are allowed to pass the same vertex and even the same edge twice, and when you pass the same edge multiple times, the last color used stays. Is it possible to obtain the required coloring?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-rBp1srYAEOs/V_1E97dIZII/AAAAAAAA7e8/1-xday7gy7kR-jqoj1ovfdF0E1kj9N_XgCLcB/s1600/IMAG0166.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="362" src="https://1.bp.blogspot.com/-rBp1srYAEOs/V_1E97dIZII/AAAAAAAA7e8/1-xday7gy7kR-jqoj1ovfdF0E1kj9N_XgCLcB/s640/IMAG0166.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2016/09/a-russian-code-week.html">my previous summary</a>, I've mentioned a super hard SRM problem: you're given a 50x50 grid, with each cell either free or blocked. You're also given at most 100 (potentially overlapping) 3x3 subgrids of this grid, and are looking to draw an L-shape or a C-shape in each of those subgrids in such a way that those shapes do not overlap, and use only free cells. An L-shape or a C-shape consists of 5 consecutive border cells of a 3x3 subgrid. There are 4 possible different L-shapes in each 3x3 subgrid, and 4 possible different C-shapes. You need to check if such drawing is possible, and if yes, find for each 3x3 subgrid whether it can have a C-shape as part of a valid drawing, and whether it can have an L-shape as part of a valid drawing.<br /><br />The last part, which asks to see which shape each particular subgrid can have, does not really change the problem a lot - if we can solve the "is it possible" version fast enough, then we can just try placing each shape in each subgrid, and solve the same problem for the rest. So in the rest of this explanation I will concentrate on the "is it possible" part.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-fc46JGLo4uc/V_1FkiI1V5I/AAAAAAAA7fM/RLujc2eKBxQ6Hr70IS5qrgkLpeNzub6nQCKgB/s1600/IMAG1263.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="200" src="https://4.bp.blogspot.com/-fc46JGLo4uc/V_1FkiI1V5I/AAAAAAAA7fM/RLujc2eKBxQ6Hr70IS5qrgkLpeNzub6nQCKgB/s200/IMAG1263.jpg" width="191" /></a></div>The key that opens this problem is: let's replace the 5-cell shape into four dominoes: a C-shape or an L-shape consisting of cells A,B,C,D,E in this order, can be viewed as a union of four dominoes: AB, BC, CD and DE. The eight possible dominoes along the border of a 3x3 subgrid can be split into four pairs of opposite dominoes (see an example on the left). Each 5-cell shape then corresponds to picking one domino in each pair of opposite dominoes.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-B5y7sgWjp2I/V_1FsD1DS-I/AAAAAAAA7fQ/XwPzwKeyaGQXBPRjLtk3NobjaMR2Yr34ACKgB/s1600/IMAG1264.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" height="116" src="https://1.bp.blogspot.com/-B5y7sgWjp2I/V_1FsD1DS-I/AAAAAAAA7fQ/XwPzwKeyaGQXBPRjLtk3NobjaMR2Yr34ACKgB/s400/IMAG1264.jpg" width="400" /></a></div>One might say that this transformation is not accurate: not every way of picking one domino in each pair of opposites yields a valid 5-cell shape. However, it turns out that every way of picking one domino in each pair of opposites yields a set of cells that <i>contains</i> a valid 5-cell shape inside (see an example on the right).<br /><br />Because of this, the following reformulation always has the same answer as the original problem: can we pick four border dominoes in each 3x3 subgrid, one from each pair of opposites, in such a way that dominoes from different subgrids do not overlap?<br /><br />Finally, now it's not that hard that we have an instance of <a href="https://en.wikipedia.org/wiki/2-satisfiability">the 2-SAT problem</a>: we have a few boolean variables (which domino to pick for each pair of opposites), and a few restrictions on pairs of values (stemming from the intersections). We can solve this problem in linear time.<br /><br />Thanks for reading, and check back soon for the next week's summary!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/knqNfBCdpCw" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2016/10/an-open-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-2367563320066233082016-09-19T01:34:00.001+03:002016-09-19T01:34:05.300+03:00A Russian Code 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/-kLeTfoN0FJk/V96qXobu_KI/AAAAAAAA6zA/ArRW8418-vYRPDwe4LWpgUwR0Z9NuYqdgCLcB/s1600/cf371top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="164" src="https://3.bp.blogspot.com/-kLeTfoN0FJk/V96qXobu_KI/AAAAAAAA6zA/ArRW8418-vYRPDwe4LWpgUwR0Z9NuYqdgCLcB/s640/cf371top5.png" width="640" /></a></div>Codeforces held two rounds this week, starting with Round 371 on Tuesday (<a href="http://codeforces.com/contest/713">problems</a>, <a href="http://codeforces.com/contest/713/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/47094">analysis</a>). Despite quite a few attempts at solving the hardest problem E, only LHiC's solution was correct, and since he didn't solve D, the speed of solving the first four was the deciding factor for the top places in the end. Congratulations to geniucos on the victory!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-9iBzFDB5KOk/V96qT8U-m1I/AAAAAAAA6y8/TiMbJGQ5PyMC6aaA3xshq77aCzzoFqP4QCLcB/s1600/cf372top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="166" src="https://1.bp.blogspot.com/-9iBzFDB5KOk/V96qT8U-m1I/AAAAAAAA6y8/TiMbJGQ5PyMC6aaA3xshq77aCzzoFqP4QCLcB/s640/cf372top5.png" width="640" /></a></div>Codeforces Round 372 on Saturday started the competitive weekend (<a href="http://codeforces.com/contest/715">problems</a>, <a href="http://codeforces.com/contest/715/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/47169">analysis</a>). This time TooDifficult left nothing to chance, and claimed the first place by more than a thousand points thanks to being the only contestant to solve four problems. Congratulations!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-CTy-VtvGiqg/V96nzMzv7DI/AAAAAAAA6ys/IPIyu1gTGJckglUpLy8_dQWneg2b7goSwCLcB/s1600/srm698top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" src="https://3.bp.blogspot.com/-CTy-VtvGiqg/V96nzMzv7DI/AAAAAAAA6ys/IPIyu1gTGJckglUpLy8_dQWneg2b7goSwCLcB/s1600/srm698top5.png" /></a></div>After a tiny 15-minute pause, TopCoder SRM 698 picked up the flag (<a href="https://community.topcoder.com/stat?c=round_overview&rd=16802">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=16802&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://youtu.be/HLsv_jcAYbE">my screencast</a>). With almost an hour left to solve the 1000-pointer, I still could not come up with a single idea that would at least transform the problem into something potentially tractable, and not even with randomized backtracking or "subset" dynamic programming that could be close to passing. I was not the only one feeling this way, and so the contest was decided during the challenge phase. I've managed to find +100 that would've earned me the first place, but also picked up -100 on unsuccessful challenges along the way - I'm lucky that the screencast doesn't capture the sound of cursing - and ended up with the coding phase score. So did rng_58, but his coding phase score was significantly higher and thus he kept the victory. Congratulations!<br /><br /><div class="separator" style="clear: both; text-align: center;"></div><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-AMqWAe4Pt8g/V98WJj__0JI/AAAAAAAA60Q/EcVCCeFdYywjA26owg_9xBQmXwJyBUgmACLcB/s1600/srm698hardexamples.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" src="https://3.bp.blogspot.com/-AMqWAe4Pt8g/V98WJj__0JI/AAAAAAAA60Q/EcVCCeFdYywjA26owg_9xBQmXwJyBUgmACLcB/s1600/srm698hardexamples.png" /></a></div>Here's <a href="https://community.topcoder.com/stat?c=problem_statement&pm=14358&rd=16802">the stumbling 1000-pointer</a>: you're given a 50x50 grid, with each cell either free or blocked. You're also given at most 100 (potentially overlapping) 3x3 subgrids of this grid, and are looking to draw an L-shape or a C-shape in each of those subgrids in such a way that those shapes do not overlap, and use only free cells. An L-shape or a C-shape consists of 5 consecutive border cells of a 3x3 subgrid (see the example on the left). There are 4 possible different L-shapes in each 3x3 subgrid, and 4 possible different C-shapes. You need to check if such drawing is possible, and if yes, find for each 3x3 subgrid whether it can have a C-shape as part of a valid drawing, and whether it can have an L-shape as part of a valid drawing.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-NApyc6J2Ul4/V96o1K_ASjI/AAAAAAAA6yw/N_jjz2ITVE0zENF2X4bQB_7VI2rgfmeEgCLcB/s1600/rcc2016finaltop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="295" src="https://3.bp.blogspot.com/-NApyc6J2Ul4/V96o1K_ASjI/AAAAAAAA6yw/N_jjz2ITVE0zENF2X4bQB_7VI2rgfmeEgCLcB/s640/rcc2016finaltop5.png" width="640" /></a></div>Russian Code Cup 2016 Finals on Sunday has wrapped up the sixth installment of this tournament (<a href="http://www.russiancodecup.ru/en/championship/">problems</a>, <a href="http://www.russiancodecup.ru/en/championship/result/56/">results</a>, top 5 on the left, <a href="http://codeforces.com/contest/720/standings">online mirror results</a>, <a href="http://www.russiancodecup.ru/en/press/razbor-zadach-finalnogo-raunda-rcc-2016/">analysis</a>). Extremely technical problems led to a lot of wrong submissions and very slow progress, but tourist still didn't leave any doubt with regard to the winner, solving the required three problems in just over an hour and almost getting the fourth. Congratulations on the second Russian Code Cup victory!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-b3plZvO1J0E/V96rsUXVyoI/AAAAAAAA6zQ/UJUEn8s-g4kNDCtH29jnOs2jI8phNI2JACLcB/s1600/IMAG1095%2B%25281%2529.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="362" src="https://2.bp.blogspot.com/-b3plZvO1J0E/V96rsUXVyoI/AAAAAAAA6zQ/UJUEn8s-g4kNDCtH29jnOs2jI8phNI2JACLcB/s640/IMAG1095%2B%25281%2529.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2016/09/a-discrete-logarithm-week.html">the last week's summary</a>, I have mentioned an algebraic problem from the TCO Wildcard Round: given three integers <i>a</i>, <i>k</i> and <i>p</i>, where <i>p</i> is a prime (more precisely, 10<sup>9</sup>+7), find any integer <i>b</i> such that <i>b<sup>k</sup></i>=<i>a</i> (mod <i>p</i>), or report that there isn't any. You also need to do it relatively fast, as one needs to solve this equation 300 times for different values of <i>a</i> (but <i>k</i> and <i>p</i> stay the same).<br /><br />Ilya Mironov has pointed out <a href="http://petr-mitrichev.blogspot.com/2016/09/a-discrete-logarithm-week.html#comments">in comments</a> that there's a specialized algorithm for solving just this problem. However, I believe that it's more educational to learn to solve this problem using the understanding of the underlying math structure and standard algorithms that come with it. The object we're studying is remainders modulo <i>p</i> with the operation of multiplication. All remainders except 0 form the <i>multiplicative group</i> modulo <i>p</i>, and there's <a href="https://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n#Generators">a well-known theorem</a> that says that this group is always <i>cyclic</i> - in other words, isomorphic to the additive group of remainders modulo <i>p</i>-1. This isomorphism maps taking an element to the power of <i>k</i> to multiplication by <i>k</i> modulo <i>p</i>-1, and we know how to inverse that - it's just division by <i>k</i> modulo <i>p</i>-1.<br /><br />That gives us a full solution to our problem: first, find out to which remainder modulo <i>p</i>-1 does the isomorphism map <i>a</i>. Then divide that remainder by <i>k</i>. Finally, apply the inverse of the isomorphism to get the answer. We also have to handle the case of <i>a</i>=0 separately since 0 doesn't belong to the multiplicative group, but there the solution is easy: <i>b</i>=0.<br /><br />Of course, there are still implementation details to figure out. How does the isomorphism work, and how to evaluate it quickly? It's not hard to see that the isomorphism is completely defined by the multiplicative remainder <i>g</i> that maps to 1 in the additive group, as all other elements then have to be some powers of <i>g</i>, since <i>g<sup>d</sup></i> must map to <i>d</i> for each d from 0 to <i>p</i>-2. Such remainder <i>g</i> is called a <i>generator</i> or a <i>primitive root</i>.<br /><br />Moreover, all powers <i>g<sup>d</sup></i> for <i>d</i> that are relatively prime with <i>p</i>-1 are also generators. Because we need to find any generator, and there are plenty, the most practical strategy for finding one is just trying a few remainders and checking if they are generators. In order to check if a remainder <i>g</i> is a generator, we must see if all its powers from 0 to <i>p</i>-2 are different, but since its order must divide the order of the multiplicative group, it suffices to check that <i>g<sup>d</sup></i> is not equal to 1 for all values of <i>d</i> that are proper divisors of <i>p</i>-1.<br /><br />Finally, having found a generator <i>g</i>, evaluating the isomorphism is called the <i><a href="https://en.wikipedia.org/wiki/Discrete_logarithm#Algorithms">discrete logarithm</a></i> which can be solved using a <i>meet-in-the-middle</i> approach, also known as <i>baby-step-giant-step</i> here. Let's pick a number <i>q</i> around sqrt(<i>p</i>-1), and pre-compute baby steps <i>d</i><sup>0</sup>, <i>d</i><sup>1</sup>, ..., <i>d</i><sup><i>q</i>-1</sup>, and giant steps <i>d</i><sup><i>q</i></sup>, <i>d</i><sup>2<i>q</i></sup>, ... (up to the first giant step with power that exceeds <i>p</i>-1). Now it's not hard to see that if we try multiplying our number <i>a</i> by all giant steps we will at some point get a result equal to some baby step: <i>a</i>*<i>d<sup>uq</sup></i>=<i>d<sup>v</sup></i>, and then <i>a</i>=<i>d</i><sup><i>v</i>-<i>uq</i></sup>, so <i>a</i> maps to <i>v</i>-<i>uq</i> mod <i>p</i>-1 under our isomorphism. The giant and baby steps can be precomputed since <i>p</i> is fixed.<br /><br />The final missing trick is dividing a remainder <i>w</i> by <i>k</i> modulo <i>p</i>-1. This also comes naturally with the understanding of remainders modulo <i>p</i>-1. First, let's represent <i>k</i> as <i>m</i>*<i>n</i> where <i>m</i> is gcd(<i>k</i>, <i>p</i>-1), and <i>n</i> is relatively prime with <i>p</i>-1. If <i>m</i> does not divide <i>w</i>, there's no solution. If <i>m</i> does divide <i>w</i>, then we now need to divide <i>w</i>/<i>m</i> by <i>n</i> modulo (<i>p</i>-1)/<i>m</i>. Since <i>n</i> is relatively prime with (<i>p</i>-1)/<i>m</i>, it has an inverse <i>o </i>such that <i>n</i>*<i>o</i>=1 modulo (<i>p</i>-1)/<i>m</i>, and thus our division result can be found as <i>o</i>*(<i>w</i>/<i>m</i>) modulo (<i>p</i>-1)/<i>m</i>. The numbers <i>o</i> and <i>m</i> can be precomputed since <i>k</i> and <i>p</i> are fixed.<br /><br />Phew! This looks like one hell of a solution, but actually it's much easier to code it than to explain. And since all steps come naturally from understanding of how remainders work, you don't need to memorize any of them - you can construct them on the fly using just a few clues that you remember.<br /><br />Thanks for reading, and see you next week!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/nTnzBvuU_ro" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2016/09/a-russian-code-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-45348168797767586312016-09-11T21:03:00.000+03:002016-09-11T23:27:15.652+03:00A discrete logarithm 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/-kWKVSLyv7EE/V9WYKifyPUI/AAAAAAAA6os/RL-AAbUGbbwDIobO9cZoZDrFU6j6B6ebQCLcB/s1600/tco16wildtop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="96" src="https://3.bp.blogspot.com/-kWKVSLyv7EE/V9WYKifyPUI/AAAAAAAA6os/RL-AAbUGbbwDIobO9cZoZDrFU6j6B6ebQCLcB/s640/tco16wildtop5.png" width="640" /></a></div>For the third week in a row, this week's Saturday was about qualifying for TopCoder Open 2016. This time the final two lucky contestants were chosen via the Wildcard Round (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=16801">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=16801&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=16807&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">parallel round results</a>, <a href="https://youtu.be/SUf1K0nlwDY">my screencast</a>). In the official round, nobody solved 1000, and in both rounds there were only a few solutions to 500. Both were solvable, but together probably just outside the 1 hour and 15 minutes timeframe. xudyh and tourist were the only two official round contestants to get two problems correctly, and thus qualified for the onsite without any close calls. Congratulations!<br /><br />The current set of 10 finalists (including the changes I'm aware of because of inability to travel) is: <span style="color: #cc0000;">Petr</span>, <span style="color: #cc0000;">HellKitsune</span>, <span style="color: #cc0000;">knightL</span>, <span style="color: #cc0000;">eatmore</span>, <span style="color: #cc0000;">rng_58</span>, <span style="color: #cc0000;">Um_nik</span>, <span style="color: #cc0000;">scott_wu</span>, <span style="color: #cc0000;">Enot</span>, <span style="color: #cc0000;">xudyh</span>, <span style="color: #cc0000;">tourist</span>. Please tell if somebody else from this list is not coming!<br /><br />The reason nobody got the 1000 in the official round is probably twofold: first, <a href="https://community.topcoder.com/stat?c=problem_statement&pm=14386&rd=16801">the problem statement </a>is long and a bit convoluted. Then, since none of the top scorers went to the 1000 from the start, there were no successful solutions on the scoreboard, which led people to believe that the problem was harder than it really was.<br /><br />After dissecting the problem statement, it boiled down to this classical algebra task: finding roots modulo a prime. More precisely, given three integers <i>a</i>, <i>k</i> and <i>p</i>, where <i>p</i> is a prime (more precisely, 10<sup>9</sup>+7), find any integer b such that <i>b</i><sup><i>k</i></sup>=<i>a</i> (mod <i>p</i>), or report that there isn't any. You also need to do it relatively fast, as one needs to solve this equation 300 times for different values of <i>a</i> (but <i>k</i> and <i>p</i> stay the same). Do you know how to do it?<br /><br />Thanks for reading, and check back next week for the solution!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/kvZl-64tt-U" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2016/09/a-discrete-logarithm-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-86460685212183341212016-09-11T20:39:00.001+03:002016-09-11T20:39:19.078+03:00A regional 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/-vDgvqny57ps/V9WSjeQzPCI/AAAAAAAA6oI/0XqwxdUqEjgdj1xd3uF7172AnQZKViggQCLcB/s1600/tco16russiatop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" src="https://3.bp.blogspot.com/-vDgvqny57ps/V9WSjeQzPCI/AAAAAAAA6oI/0XqwxdUqEjgdj1xd3uF7172AnQZKViggQCLcB/s1600/tco16russiatop5.png" /></a></div>On Saturday, September 3, TopCoder held its TCO16 Russia event in St Petersburg (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=16800">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=16800&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="http://tco16.topcoder.com/tco16-saint-petersburg-russia-regionals/">official blog</a>, <a href="https://youtu.be/YroxS2yYpBs">my screencast</a>). For the second year in a row, those provide an opportunity for people who don't qualify for the onsite to get together, but this year one could also qualify for a special Wildcard round from the regional event, in order to compete for 2 extra spots in the onsite. That resulted in much more serious competition, but the social element was still there, and I've enjoyed meeting many of my old and new friends in St Petersburg - thanks a lot to TopCoder for organizing the regionals!<div><br /></div><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-Ryu7z_SuZnE/V9WVhbPnj-I/AAAAAAAA6oU/lnd7580kT4oLzgNSBOk3f_C8sx8W-NL2wCLcB/s1600/agc004top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="335" src="https://2.bp.blogspot.com/-Ryu7z_SuZnE/V9WVhbPnj-I/AAAAAAAA6oU/lnd7580kT4oLzgNSBOk3f_C8sx8W-NL2wCLcB/s640/agc004top5.png" width="640" /></a></div><div>On the following Sunday, AtCoder Grand Contest 004 took place (<a href="http://agc004.contest.atcoder.jp/assignments">problems</a>, <a href="http://agc004.contest.atcoder.jp/standings">results</a>, top 5 on the left, <a href="http://agc004.contest.atcoder.jp/data/agc/004/editorial.pdf">analysis</a>). semiexp has won his second Grand Contest, and reclaimed the top spot in <a href="https://atcoder.jp/ranking">the rankings</a> - congratulations!</div><div><br /></div><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-7CUoc4D9Dy8/V9WWnH9sr5I/AAAAAAAA6oc/5wSz9-F7nh0v27VkomQO5-dDAl0bTEFGgCLcB/s1600/IMAG0991.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="362" src="https://2.bp.blogspot.com/-7CUoc4D9Dy8/V9WWnH9sr5I/AAAAAAAA6oc/5wSz9-F7nh0v27VkomQO5-dDAl0bTEFGgCLcB/s640/IMAG0991.jpg" width="640" /></a></div><div>Thanks for reading this super short summary, and check back soon for this week's contests! Please remember that I'm happy to answer your questions in comments to this or any other summary.</div></div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/OF0nfVpaflM" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2016/09/a-regional-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-59180348607877161002016-09-11T20:17:00.000+03:002016-09-23T23:06:18.281+03:00A Reichenbach 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/-mlV1sCFRxI4/V8kh3YY10YI/AAAAAAAA6ak/lC-XyvDK5w0sBxFFydEhe-Te4JpBWhkqgCLcB/s1600/aim3top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="164" src="https://1.bp.blogspot.com/-mlV1sCFRxI4/V8kh3YY10YI/AAAAAAAA6ak/lC-XyvDK5w0sBxFFydEhe-Te4JpBWhkqgCLcB/s640/aim3top5.png" width="640" /></a></div>The fourth August week has marked the start of the Petrozavodsk training camp, and with it came newly traditional AIM Tech Round 3 (<a href="http://codeforces.com/contest/708">problems</a>, <a href="http://codeforces.com/contest/708/standings">results</a>, top 5 on the left). Quite fittingly, the winner was present in Petrozavodsk - congratulations Um_nik!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-wveRPSZsr2I/V8kh9OWNwlI/AAAAAAAA6ao/yztgnkN9WX8jXSzG7sNJd-wQD-LqDU7UgCLcB/s1600/tco16r3btop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" src="https://2.bp.blogspot.com/-wveRPSZsr2I/V8kh9OWNwlI/AAAAAAAA6ao/yztgnkN9WX8jXSzG7sNJd-wQD-LqDU7UgCLcB/s1600/tco16r3btop5.png" /></a></div>On Saturday evening TopCoder Open 2016 Round 3B has selected four more contestants for the onsite round in Washington (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=16798">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=16798&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left). The 1000-pointer did not give this time, and thus the key was in solving the 500-pointer fast. The challenge phase did not affect the top four - congratulations to rng_58, Um_nik, scott_wu and Enot on qualifying!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-hEG3q9D92ac/V9WRSHOR6BI/AAAAAAAA6oA/cgIMtpTSWfAbAwcyvjlLMeuwRMkEdVpPACLcB/s1600/IMAG0850.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="362" src="https://2.bp.blogspot.com/-hEG3q9D92ac/V9WRSHOR6BI/AAAAAAAA6oA/cgIMtpTSWfAbAwcyvjlLMeuwRMkEdVpPACLcB/s640/IMAG0850.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2016/09/a-squeezing-week.html">my previous summary</a>, I've mentioned an interesting AtCoder problem. Initially, one was given a sequence of length <i>n</i>. Then <i>m</i> transformations were applied. After the <i>i</i>-th transformation the new length of the sequence became <i>a<sub>i</sub></i>. If the new length was shorter than the current length, the sequence was simply truncated. If the new length was longer than the current length, then we repeated the current sequence periodically to get to the new length. Given <i>n</i>, <i>m</i>, and the numbers <i>a<sub>i</sub></i>, one needed to find how many times each element of the original sequence appears in the final sequence. <i>n</i> and <i>m</i> are up to 10<sup>5</sup>, <i>a<sub>i</sub></i> are up to 10<sup>18</sup>.<br /><br />The first step in solving this problem is: if a certain value <i>a<sub>i</sub></i> is smaller than or equal to the previous value <i>a</i><sub><i>i</i>-1</sub>, then the previous value can be removed, as we will truncate the result of (<i>i</i>-1)-st operation to <i>a<sub>i </sub></i>numbers anyway. After repeating this several times, we arrive at a strictly increasing sequence <i>a<sub>i</sub></i>, which effectively contains those numbers from the original sequence that are smaller than all following numbers.<br /><br />The next idea is to look at this problem from the end: instead of unfolding the short sequence into a long one, we will fold the long one. We start with one long sequence of length <i>a<sub>m</sub></i>. What does it fold to? Let's divide <i>a<sub>m</sub></i> by <i>a</i><sub><i>m</i>-1</sub>, and get the quotient <i>x</i> and the remainder <i>y</i>. Then we get <i>x</i> copies of the sequence at step <i>m</i>-1, and one more copy of its prefix of length <i>y</i>. What will happen to this prefix of length <i>y</i> later? It will stay unchanged until we reach some <i>a<sub>j</sub></i> that is less than y, after which it will again transform into several copies of <i>a<sub>j </sub></i>plus some smaller remainder. By continuing this process, we will have decomposed our initial long sequence <i>a<sub>m</sub></i> into a few copies of the sequences of length <i>a<sub>j</sub></i> where <i>j</i> is less than <i>m</i>, plus some prefix of the original sequence.<br /><br />Now we can decompose the resulting sequences of length <i>a</i><sub><i>m</i>-1</sub> in the same way, then sequences of length <i>a</i><sub><i>m</i>-2</sub>, remembering how many copies of each length we have, until we've left with just a collection of prefixes (with counts) of the original sequence, which allows us to compute the answer easily.<br /><br />At first sight, it seems that we have a O(<i>m</i><sup>2</sup>) solution since each length decomposes into some set of smaller lengths. However, we can note that the remainder y decreases at least twice in each step, so we have at most log(<i>a</i><sub><i>m</i></sub>) steps, and we can perform each step in O(log(<i>m</i>)) time by doing a binary search for the next suitable <i>a<sub>j</sub></i>. In total, that leads to a running time of O(<i>n</i>+<i>m</i>*log(<i>m</i>)*log(<i>a</i><sub><i>m</i></sub>)), where the O(<i>n</i>) part is for computing and printing the answer.<br /><br />A beautiful fact is that, despite such fancy complexity, the solution itself is very simple and easy to code, as it only uses arrays as data structures, and simple binary search as the most advanced algorithm.<br /><br />Thanks for reading, and check back soon for the next week's summary!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/TPyNtG2oeO0" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2016/09/a-reichenbach-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-36678788558201669692016-09-04T18:01:00.001+03:002016-09-04T18:01:29.073+03:00A squeezing 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/-cFa5kAVD3BY/V8khCO3RXJI/AAAAAAAA6ac/-T-ZWBdG_HAqmdrzM2jyo1YLp0-eydm0QCLcB/s1600/srm697top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="80" src="https://1.bp.blogspot.com/-cFa5kAVD3BY/V8khCO3RXJI/AAAAAAAA6ac/-T-ZWBdG_HAqmdrzM2jyo1YLp0-eydm0QCLcB/s640/srm697top5.png" width="640" /></a></div>The third August week featured TopCoder SRM 697 on Thursday (<a href="https://community.topcoder.com/stat?c=round_overview&rd=16776">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=16776&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://apps.topcoder.com/wiki/display/tc/SRM+697">analysis</a>). I've wasted most of my time trying to solve <a href="https://community.topcoder.com/stat?c=problem_statement&pm=14333&rd=16776">the hard problem</a> and couldn't squeeze my approach into the time limit, but matthew99a turned out to be better at squeezing - congratulations!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-c-jCge0cr9c/V8khUhW4a0I/AAAAAAAA6ag/-u90eI7MpJg-Rw0YXFJRw9JXZn3_Qd0UQCLcB/s1600/agc003top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="250" src="https://2.bp.blogspot.com/-c-jCge0cr9c/V8khUhW4a0I/AAAAAAAA6ag/-u90eI7MpJg-Rw0YXFJRw9JXZn3_Qd0UQCLcB/s640/agc003top5.png" width="640" /></a></div>Later that week, AtCoder Grand Contest 003 has ended with a tiny 16-second margin between the first two places (<a href="http://agc003.contest.atcoder.jp/assignments">problems</a>, <a href="http://agc003.contest.atcoder.jp/standings">results</a>, top 5 on the left, <a href="http://agc003.contest.atcoder.jp/data/agc/003/editorial.pdf">analysis</a>).<br /><br /><a href="http://agc003.contest.atcoder.jp/tasks/agc003_e">Problem E</a> "Sequential operations on Sequence" required a few ideas to get both the right asymptotic complexity, and an easy-to-code implementation. Initially, one was given a sequence of length <i>n</i>. Then <i>m</i> transformations were applied. After the <i>i</i>-th transformation the new length of the sequence became <i>a<sub>i</sub></i>. If the new length was shorter than the current length, the sequence was simply truncated. If the new length was longer than the current length, then we repeated the current sequence periodically to get to the new length. Given <i>n</i>, <i>m</i>, and the numbers <i>a<sub>i</sub></i>, one needed to find how many times each element of the original sequence appears in the final sequence. <i>n</i> and <i>m</i> are up to 10<sup>5</sup>, <i>a<sub>i</sub></i> are up to 10<sup>18</sup>.<br /><br />Thanks for reading, and check back soon for the next week's summary!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/Bst_x1LCE6Q" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2016/09/a-squeezing-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-85728548910029974012016-09-04T17:52:00.000+03:002016-09-04T17:52:02.573+03:00A circular week<div dir="ltr" style="text-align: left;" trbidi="on"><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/-Muj_Lzw3Uj8/V8kggg5laiI/AAAAAAAA6aY/vu5NbWwmzxwbyZYR9-3nv0liwo-5CGaEgCLcB/s1600/srm696top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="78" src="https://3.bp.blogspot.com/-Muj_Lzw3Uj8/V8kggg5laiI/AAAAAAAA6aY/vu5NbWwmzxwbyZYR9-3nv0liwo-5CGaEgCLcB/s640/srm696top5.png" width="640" /></a></div>The second week of August was relatively calm, with just the early morning TopCoder SRM 696 on the agenda (<a href="https://community.topcoder.com/stat?c=round_overview&rd=16775">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=16775&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left). Swistakk was the only contestant to solve the hard problem correctly, but anta has earned his second SRM victory thanks to being the fastest on the medium problem. Great job!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-GnkO0B17uYE/V8wzDH_x99I/AAAAAAAA6hI/2KZ9aJQNq38wMxI1SOGnx-3LOcRXyrqcQCLcB/s1600/grid.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" src="https://4.bp.blogspot.com/-GnkO0B17uYE/V8wzDH_x99I/AAAAAAAA6hI/2KZ9aJQNq38wMxI1SOGnx-3LOcRXyrqcQCLcB/s1600/grid.png" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2016/09/a-jam-week.html">the previous week's summary</a>, I have shared a very nice Code Jam problem: you are given two numbers <i>n</i> and <i>r</i>. There's a <i>n</i>x<i>n</i> grid of pillars, with a pillar of radius <i>r</i> centered in each point of the grid except the bottom-left corner. How many pillars are visible from the bottom-left corner?<br /><br />Which seems to be a geometry problem at the first glance, turns out to be solely about number theory when it comes to the implementation. The first observation that leads us there is the fact that if we can see any point of a column, then we can see its center. To prove that, suppose the column at (<i>x</i>, <i>y</i>) obstructs some part of the view of the column at (<i>a</i>, <i>b</i>) including its center. The column at (<i>a</i>-<i>x</i>, <i>b</i>-<i>y</i>) is in a symmetric location, and thus also obstructs the view of the center of (<i>a</i>, <i>b</i>), but from the other side. As a result, the view of the entire column at (<i>a</i>, <i>b</i>) is obstructed. So instead of having to carefully track which part of a column is visible, we just need to check if its center is visible.<br /><br />Now, when does the column at (<i>x</i>, <i>y</i>) obstruct the center of the column at (<i>a</i>, <i>b</i>)? It happens if <i>x</i><=<i>a</i>, <i>y</i><=<i>b</i>, and the distance <i>d</i> from the point (<i>x</i>, <i>y</i>) to the line connecting the point (0, 0) with the point (<i>a</i>, <i>b</i>) is less than or equal to <i>r</i> - the radius of each column. Now, consider the triangle with vertices (0, 0), (<i>x</i>, <i>y</i>) and (<i>a</i>, <i>b</i>). Its area <i>s</i> can be found by multiplying 0.5 by its base and height, in other words, it is equal to 0.5*sqrt(<i>a</i>*<i>a</i>+<i>b</i>*<i>b</i>)*<i>d</i>, so <i>d</i>=2*<i>s</i>/sqrt(<i>a</i>*<i>a</i>+<i>b</i>*<i>b</i>). On the other hand, its vertices have integer coordinates, and <a href="https://en.wikipedia.org/wiki/Pick%27s_theorem">Pick's formula</a> tells us that <i>s</i> is a half-integer: either 0, or at least 0.5. Because of this, <i>d</i> is either 0 or at least 1/sqrt(<i>a</i>*<i>a</i>+<i>b</i>*<i>b</i>).<br /><br />When can <i>d</i> be equal to 0? It happens if an only if <i>a</i> and <i>b</i> are not relatively prime: in that case there's a column blocking the view directly. In all other cases, <i>d</i> is at least 1/sqrt(<i>a</i>*<i>a</i>+<i>b</i>*<i>b</i>). Moreover, this lower bound is tight: we can always find a point (<i>x</i>, <i>y</i>) that makes <i>d</i> equal to 1/sqrt(<i>a</i>*<i>a</i>+<i>b</i>*<i>b</i>). For example, let's consider the point that's closest to the segment (0, 0) - (<i>a</i>, <i>b</i>) inside its bounding box. It's not hard to see that the resulting triangle does not have any other integer points inside or on its boundary (otherwise those would be closer), and thus its area is 0.5 by Pick's formula, which yields the required value of <i>d</i>.<br /><br />Now we can finally write down a very simple description of the columns we see: we need <i>a</i> and <i>b</i> to be relative prime, and have 1/sqrt(<i>a</i>*<i>a</i>+<i>b</i>*<i>b</i>)><i>r</i>, in other words <i>a</i>*<i>a</i>+<i>b</i>*<i>b</i><1/(<i>r</i>*<i>r</i>). The latter formula simply describes a circle with radius 1/<i>r</i>, so the problem boils down to counting integer points inside an intersection of a square and a quarter-circle, which is a relatively standard number theory problem.<br /><br /></div>The simple circular shape of the set of the visible columns is one of the beautiful sides of this problem, as it enables a different way of solving it: implementing a slow solution, such as the one for the small input, and then visualizing the result to get an insight. For example, plotting a grid corresponding to all visible columns with <i>r</i>=0.01 results in the picture above, which clearly suggests the idea of a circle with radius 1/<i>r</i>.<br /><br />Thanks for reading, and check back soon for the next week's summary!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/OL6l_vzIZl4" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2016/09/a-circular-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-48951693169370075462016-09-03T15:44:00.000+03:002016-09-03T15:44:58.594+03:00A jam 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/-UH9W8FtPzgg/V6j2vo9-qWI/AAAAAAAA5rs/O4Qa2h0vr8EyGnJV_y8goi53gVy8z185gCLcB/s1600/gcj16finalstop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="142" src="https://2.bp.blogspot.com/-UH9W8FtPzgg/V6j2vo9-qWI/AAAAAAAA5rs/O4Qa2h0vr8EyGnJV_y8goi53gVy8z185gCLcB/s640/gcj16finalstop5.png" width="640" /></a></div>Google Code Jam 2016 Finals was the main event of the first August week (<a href="https://code.google.com/codejam/contest/7234486/dashboard#s=p2">problems</a>, <a href="https://code.google.com/codejam/contest/7234486/scoreboard#vt=1">results</a>, top 5 on the left, <a href="https://code.google.com/codejam/contest/7234486/dashboard#s=a">analysis</a>, <a href="https://youtu.be/4diQ6JXY4cI">live stream recording</a>). There was very close competition at the top during the entire contest, but in the end the favorite Gennady.Korotkevich has pulled quite a bit ahead of the field - congratulations!<br /><br />The problems were interesting in different ways this time, and it's hard to pick a single most beautiful one - but I will choose <a href="https://code.google.com/codejam/contest/7234486/dashboard#s=p2&a=4">problem C</a> "Gallery of Pillars". You are given two numbers <i>n</i> and <i>r</i>. There's a <i>n</i>x<i>n</i> grid of pillars, with a pillar of radius <i>r</i> centered in each point of the grid except the bottom-left corner. How many pillars are visible from the bottom-left corner?<br /><br />This could initially seem to be a tedious but standard geometry problem, but the constraints were very high: <i>n</i> is up to 10<sup>9</sup>, and <i>r</i> is between 10<sup>-6</sup> and 0.5. These constraints eliminate any chance of passing for any solution that just tries to enumerate all visible pillars. Can you count them faster?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-xMZ7rG58V8I/V6j20c1FTAI/AAAAAAAA5rw/w1jOwAhRVpMzwDWgtQL943eXkAujxdpXACLcB/s1600/dcj16finalstop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="154" src="https://4.bp.blogspot.com/-xMZ7rG58V8I/V6j20c1FTAI/AAAAAAAA5rw/w1jOwAhRVpMzwDWgtQL943eXkAujxdpXACLcB/s640/dcj16finalstop5.png" width="640" /></a></div>Distributed Google Code Jam 2016 Finals continued the exploration of the new field on Saturday (<a href="https://code.google.com/codejam/contest/5274486/dashboard#s=p4">problems</a>, <a href="https://code.google.com/codejam/contest/5274486/scoreboard#vt=1">results</a>, top 5 on the left, <a href="https://code.google.com/codejam/contest/5274486/dashboard#s=a">analysis</a>). Just like in non-distributed Code Jam, the last year's winner could retain the crown, but the fight was even more fierce this time. Congratulations Bruce!<br /><br />This was also the first time I took a stab at solving distributed problems myself. My result was nothing too impressive (39 points from B-small, E-small and E-large), but now I can appreciate and share with you the nicer problems :)<br /><br />The only problem I solved, <a href="https://code.google.com/codejam/contest/5274486/dashboard#s=p4&a=4">problem E</a> "gold", was very nice. You were looking for gold in a sequence of 10<sup>11</sup> cells. You was also given the number of cells that contain gold, which was up to 10<sup>7</sup>. Your program was executed on 100 machines. Each machine could ask questions about the location of the gold in the following way: given a cell number, the reply was either "this cell contains gold", "the closest cell with gold is to the left", "the closest cell with gold is to the right", or "the closest cells with gold to the left and to the right are at the same distance". One question took 0.2 microseconds, and the time limit was 15 seconds, so each worker could use at most 750000 questions, meaning that even between all 100 workers there was no time to query all 10<sup>11</sup> input cells. The workers could also communicate with each other, each worker sending at most 8MB of data distributed between at most 5000 messages to other workers. How does one find all gold so quickly?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-xLagOWLplKU/V6j26XKUeqI/AAAAAAAA5r0/faez0pEiEbwKiEzUGmkMeuI5bRcmv_gTwCLcB/s1600/cf366top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="164" src="https://4.bp.blogspot.com/-xLagOWLplKU/V6j26XKUeqI/AAAAAAAA5r0/faez0pEiEbwKiEzUGmkMeuI5bRcmv_gTwCLcB/s640/cf366top5.png" width="640" /></a></div>Finally, Codeforces Round 366 wrapped up the week on Sunday (<a href="http://codeforces.com/contest/704">problems</a>, <a href="http://codeforces.com/contest/704/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/46450">analysis</a>). The problems turned out to be very tough, with two problems enough for second place, but it was of course better to solve three and win, just like kcm1700 did - congratulations!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-e2UDFSql-Mo/V8rFXjl02KI/AAAAAAAA6g4/F_YIM4EYP6wZ1-HMu5Vg6lr3VduuroZBACKgB/s1600/IMAG0814.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="640" src="https://3.bp.blogspot.com/-e2UDFSql-Mo/V8rFXjl02KI/AAAAAAAA6g4/F_YIM4EYP6wZ1-HMu5Vg6lr3VduuroZBACKgB/s640/IMAG0814.jpg" width="362" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2016/08/a-young-week.html">my last summary</a> I've mentioned an unsolved Yandex problem: consider sequences of 2<i>n</i> parentheses of <i>n</i> different types such that there's exactly one opening and exactly one closing parenthesis of each type. A sequence is considered good if the parentheses can be colored with two colors in such a way that the subsequences formed by each color are balanced parenthesis sequences. How many good sequences exist for the given <i>n</i>? <i>n</i> is up to 500.<br /><br />The first approach that comes to one's mind might be: let's consider the number of ways to pick two balanced parenthesis sequences of lengths <i>k</i> and <i>n-k</i>, and then multiply that by the number of ways to interleave them, and then by n! to assign the parentheses types.<br /><br />This solution is incorrect because it might count a good sequence more than once, as there might be more than one way to color it with two colors in the way described above. In fact, each good sequence is counted at least twice, as we can swap the two interleaved sequences and get the same result! And in general, each good sequence is counted as many times as the number of valid colorings it has.<br /><br />The next natural question is: how many valid colorings does a given good sequence have? This is relatively easy to determine: we can draw a graph between parentheses types, connecting two types if the corresponding parentheses must have different colors, which happens if the corresponding segments are intersecting but not containing one another. Now valid colorings of the parentheses correspond to colorings of this graph without two vertices of the same color sharing an edge. And that, in turn, is either 0 (in case the graph is not bipartite), or 2 to the power of the number of its connected components otherwise.<br /><br />Even though the last observation doesn't lead to a solution directly, it provides valuable insight into the structure of the problem. We will call the sequences corresponding to a connected bipartite graph <i>simple</i>, and the rest <i>complex</i>. Each simple sequence has exactly two valid colorings. Each complex sequence can be decomposed in the following way: the connected component containing the first parenthesis, and the remaining connected components. That connected component corresponds to a simple sequence of smaller length, and the rest correspond to simple sequences that can be inserted anywhere into it.<br /><br />Now we finally have a clear path towards the solution. We will count the number of <i>colored</i> simple and complex sequences of each length (so each sequence will be counted the number of times equal to its number of valid colorings). In order to count the number of simple sequences, we will subtract the number of complex sequences from the total number of sequences which we've determined above. And in order to count the complex sequences, we will try all possible sizes for the simple sequence containing the first parenthesis, and multiply the number of simple sequences of that size by the number of ways to insert more simple sequences into it.<br /><br />The latter can be counted using two-dimensional dynamic programming: how many ways are there to insert several sequences with a total of <i>n </i>parentheses into a simple sequence with length <i>k </i>(in other words, with 2<i>k</i>+1 different available insertion positions).<br /><br />And finally, after knowing the number of simple sequences, we need to find the total number of sequences, but without counting different colorings of the same sequence multiple times. This is counted by analogous two-dimensional dynamic programming, but without multiplying by 2 each time we add a new sub-sequence.<br /><br />Thanks for reading, and check back later for the next week's summary!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/P8oW1rF4EIg" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2016/09/a-jam-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-35073804998537175652016-08-05T19:32:00.002+03:002016-08-05T19:32:55.846+03:00Google Code Jam 2016 finals live stream<div dir="ltr" style="text-align: left;" trbidi="on"><a href="https://code.google.com/codejam/contest/7234486/scoreboard">The final round of Google Code Jam 2016</a> has just started, and you can follow along <a href="https://youtu.be/4diQ6JXY4cI">the live stream</a>. Enjoy!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/OIqAuyafYDo" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2016/08/google-code-jam-2016-finals-live-stream.html