tag:blogger.com,1999:blog-19533250797934499712019-04-19T12:41:18.342+03:00Algorithms Weekly by Petr MitrichevPetr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.comBlogger411125PetrMitrichevhttps://feedburner.google.comtag:blogger.com,1999:blog-1953325079793449971.post-8790865919243480292019-04-04T00:09:00.001+03:002019-04-08T18:56:17.333+03:00ICPC 2019 World Finals mirror stream<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/-vgnnUdGVxPI/WtQG4sH17qI/AAAAAAACA9Q/bLAMDTiABjcoFWfjp-E8CBeC5nJfDuDKQCLcBGAs/s1600/team.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="540" data-original-width="960" height="360" src="https://2.bp.blogspot.com/-vgnnUdGVxPI/WtQG4sH17qI/AAAAAAACA9Q/bLAMDTiABjcoFWfjp-E8CBeC5nJfDuDKQCLcBGAs/s640/team.jpg" width="640" /></a></div>ICPC 2019 World Finals take place tomorrow on Thursday at approximately 11:30 Porto time (<a href="https://www.timeanddate.com/worldclock/fixedtime.html?msg=ICPC+2019+World+Finals&iso=20190404T1130&p1=320&ah=5">click for other timezones</a>). Just like <a href="https://youtu.be/BZo23gj9ksk">last</a> <a href="https://youtu.be/nF3tSkNWRVQ">two</a> years, we'll try to solve it in parallel with tourist and Endagorion, and stream the process, assuming the problems will be available for submission <a href="https://judge.icpc.global/problems">on Kattis</a>.<br /><br />Tune in <a href="https://youtu.be/X6YdKQspOBk">on Youtube</a>!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/H4MvyvzziAY" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com1http://petr-mitrichev.blogspot.com/2019/04/icpc-2019-world-finals-mirror-stream.htmltag:blogger.com,1999:blog-1953325079793449971.post-29624124802899274752019-03-11T22:02:00.000+03:002019-03-11T22:02:46.153+03:00A painful 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/--hx64s4KH-8/XIajUibYykI/AAAAAAACQho/l7MwQnWrsnU08G9zPSQ1IhHcqIC1xn8CwCLcBGAs/s1600/srm752top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="98" data-original-width="635" src="https://2.bp.blogspot.com/--hx64s4KH-8/XIajUibYykI/AAAAAAACQho/l7MwQnWrsnU08G9zPSQ1IhHcqIC1xn8CwCLcBGAs/s1600/srm752top5.png" /></a></div>TopCoder SRM 752 was the first round of the last week (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=17420">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17420&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://www.topcoder.com/blog/single-round-match-752-editorials/">analysis</a>). rng_58 maintained his advantage in <a href="https://tco19.topcoder.com/home/algorithm/algorithm-leaderboard">the race for the third TCO19 spot</a> and was quite close to increasing his lead even further as he was just 4 points behind the first place before the challenge phase, and pashka was outside the top 10. However, tourist found 100 challenge points and won (congratulations!) and pashka found 50 challenge points and jumped into exactly 10th place, meaning that both rng_58 and pashka got 4 tournament points for this round.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-d_Ak-PgSXXQ/XIakygTJD6I/AAAAAAACQh0/Y2f1zpri-So3aFG0XiI7RAouyoRnu_K-ACLcBGAs/s1600/cf545top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="271" data-original-width="1102" height="156" src="https://1.bp.blogspot.com/-d_Ak-PgSXXQ/XIakygTJD6I/AAAAAAACQh0/Y2f1zpri-So3aFG0XiI7RAouyoRnu_K-ACLcBGAs/s640/cf545top5.png" width="640" /></a></div>Codeforces held its Round 545 early on Friday (<a href="https://codeforces.com/contest/1137">problems</a>, <a href="https://codeforces.com/contest/1137/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/65825">analysis</a>). Only sunset was able to solve very tricky problem F, so even exceeding the memory limit in problem C (thanks to implementing an asymptotically optimal solution but with a huge constant both for time and memory) did not change the outcome. Congratulations on the win!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-t2V7CdVHq8M/XIalcz-z54I/AAAAAAACQh8/OZrnAKNYuhkfXg-m__BC9QAm8ZvsgLAWQCLcBGAs/s1600/oc1819chinatop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="458" data-original-width="1206" height="242" src="https://2.bp.blogspot.com/-t2V7CdVHq8M/XIalcz-z54I/AAAAAAACQh8/OZrnAKNYuhkfXg-m__BC9QAm8ZvsgLAWQCLcBGAs/s640/oc1819chinatop5.png" width="640" /></a></div>Open Cup 2018-19 Grand Prix of China wrapped up the week (<a href="https://official.contest.yandex.ru/opencupXIX/contest/12242/standings/">results</a>, top 5 on the left, <a href="https://drive.google.com/file/d/19mOJBXxJ6O6XXG_7BUy1ZwVxaJ8e6cTd/view">analysis</a>). All problems were solvable in this round, but all of them required quite a bit of thinking and quite a bit of coding, and also, <a href="https://codeforces.com/blog/entry/65836?#comment-498254">as zeliboba quite succinctly formulated</a>, had a few somewhat unnecessary corner cases. Team Past Glory still prevailed in those tricky conditions with the last problem accepted at 4:59. Well done!<br /><br />Problem E in this round reminded me of <a href="https://petr-mitrichev.blogspot.com/2014/05/coming-up-with-tough-dynamic.html">my earlier post</a> where I tried to describe a way to find dynamic programming states semi-automatically. The problem went like this: let's define f(<i>x</i>) as the smallest non-negative number that can be obtained by placing + or - before each digit in the decimal representation of <i>x</i>, and computing the resulting sum. How many numbers <i>x</i> between <i>l</i> and <i>r</i> have f(<i>x</i>) equal to 0, 1, ..., 9? <i>l</i> and <i>r</i> have at most 100 digits, and there are 10000 testcases to solve in 2 seconds.<br /><br />The idea to use dynamic programming is on the surface, but it's completely unclear how to achieve a manageable number of states. Do you see a way to find a small state space algorithmically?<br /><br />Thanks for reading, and check back next week!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/Uj-Ft6XjVeg" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com4http://petr-mitrichev.blogspot.com/2019/03/a-painful-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-51888867217662450332019-03-10T23:32:00.001+03:002019-03-11T22:17:19.926+03:00An oracle 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/-BYZpMGpzXiY/XIU-33br-CI/AAAAAAACQgY/V17dS0tzZPcWHI6dYnz4l4eFNtaJY19swCLcBGAs/s1600/oc1819americatop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="208" data-original-width="801" height="166" src="https://3.bp.blogspot.com/-BYZpMGpzXiY/XIU-33br-CI/AAAAAAACQgY/V17dS0tzZPcWHI6dYnz4l4eFNtaJY19swCLcBGAs/s640/oc1819americatop5.png" width="640" /></a></div>Last week had an Open Cup round for the fourth week in a row. Open Cup 2018-19 Grand Prix of America allowed teams from all over the world to participate in NAIPC 2019 (<a href="https://naipc19.kattis.com/standings">problems</a>, <a href="http://opentrains.snarknews.info/~ejudge/res/res10454">results</a>, top 5 on the left, <a href="https://naipc19.kattis.com/standings">NAIPC results</a>, <a href="https://www.youtube.com/watch?v=lotwdEK6DUU">analysis</a>). Just 3.5 hours were enough for team Past Glory to wrap the problemset up, a good 40 minutes before other teams could do the same. Congratulations on the win!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-nVcILP412Pg/XIVy-7XBs5I/AAAAAAACQgw/X1EV_oBoEvA9bWgdw-PQ9SoxuVxYFY6YwCLcBGAs/s1600/IMG_20190223_175327.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1200" data-original-width="1600" height="480" src="https://4.bp.blogspot.com/-nVcILP412Pg/XIVy-7XBs5I/AAAAAAACQgw/X1EV_oBoEvA9bWgdw-PQ9SoxuVxYFY6YwCLcBGAs/s640/IMG_20190223_175327.jpg" width="640" /></a></div>In <a href="https://petr-mitrichev.blogspot.com/2019/02/a-wtf-week.html">my previous summary</a>, I have mentioned two (in some sense three :)) problems. The first group was from the AtCoder World Tour Finals: consider an infinite 2D grid, where each cell can be either black or white. Initially, exactly one cell was black, and then we repeatedly applied the following operation: take some integers <i>x</i> and <i>y</i>, and invert the color of three cells: (<i>x</i>, <i>y</i>), (<i>x</i>+1, <i>y</i>) and (<i>x</i>, <i>y</i>+1). You are given the set of black cells in the final state of the grid. There are at most 10<sup>5</sup> black cells in C1 and at most 10<sup>4</sup> in C2, and each black cell has coordinates not exceeding 10<sup>17</sup> by absolute value. Your goal is to find the coordinates of the only cell that was black originally. In problem C1 you know that its <i>y</i>-coordinate was 0, and in C2 there are no further constraints.<br /><br />A typical idea in this type of problem is to come up with an invariant that is not changed by the operation and that can be efficiently computed for source and target positions. A typical invariant that plays well with inversions is boolean or bitwise xor. Let's say that a white cell is a 0, a black cell is a 1, let's also pick some set of cells <i>S</i>, then our invariant will be their bitwise xor (in other words, the parity of the number of black cells in <i>S</i>).<br /><br />Not any set <i>S</i> works, though: we must make sure that for each invertible triple (<i>x</i>, <i>y</i>), (<i>x</i>+1, <i>y</i>) and (<i>x</i>, <i>y</i>+1) either 0 or 2 cells belong to <i>S</i>, to make sure the xor does not change when we invert the triple. Suppose that for some row <i>y</i>=<i>y</i><sub>0</sub> the set <i>S</i> contains exactly one cell (<i>x</i><sub>0</sub>,<i>y</i><sub>0</sub>). The triple (<i>x</i><sub>0</sub>,<i>y</i><sub>0</sub>), (<i>x</i><sub>0</sub>+1,<i>y</i><sub>0</sub>), (<i>x</i><sub>0</sub>,<i>y</i><sub>0</sub>+1) must have 0 or 2 cells in <i>S</i>, and since (<i>x</i><sub>0</sub>,<i>y</i><sub>0</sub>) is in <i>S</i> but (<i>x</i><sub>0</sub>+1,<i>y</i><sub>0</sub>) is not, (<i>x</i><sub>0</sub>,<i>y</i><sub>0</sub>+1) must be in <i>S</i>. Applying a similar argument, we find that in the row <i>y</i>=<i>y</i><sub>0</sub> exactly two cells must be in <i>S</i>: (<i>x</i><sub>0</sub>,<i>y</i><sub>0</sub>+1) and (<i>x</i><sub>0</sub>-1,<i>y</i><sub>0</sub>+1). Then we can compute which cells must be in S in the row <i>y</i>=<i>y</i><sub>0</sub>+2, and so on.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-TromSWd2ddo/XIV0HSxuGXI/AAAAAAACQhM/PMuOuAuQoe4IzpU1gBi8xtUUljqLGlX5gCKgBGAs/s1600/IMG_20190310_213004.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" data-original-height="1600" data-original-width="1487" height="400" src="https://4.bp.blogspot.com/-TromSWd2ddo/XIV0HSxuGXI/AAAAAAACQhM/PMuOuAuQoe4IzpU1gBi8xtUUljqLGlX5gCKgBGAs/s400/IMG_20190310_213004.jpg" width="371" /></a></div>We can realize by looking at the resulting pattern, or by understanding what the process really is, that in general a cell (<i>x</i><sub>0</sub>-<i>k</i>,<i>y</i><sub>0</sub>+<i>n</i>) is in <i>S</i> if and only if C(<i>n</i>,<i>k</i>) is odd. And that, in turn, is true if and only if <i>n</i>&<i>k</i>=<i>k</i>, where & denotes bitwise and. There are still multiple ways to extend the set <i>S</i> to rows with <i>y</i><<i>y</i><sub>0</sub>, so to avoid thinking about that we will always pick very small <i>y</i><sub>0</sub> that is below all interesting points.<br /><br />Now it is very easy to compute our invariant for the input set of cells: we need to count the parity of the number of such (<i>x</i>,<i>y</i>) in the set that (<i>y</i>-<i>y</i><sub>0</sub>)&(<i>x</i><sub>0</sub>-<i>x</i>)=<i>x</i><sub>0</sub>-<i>x</i>. But we know that the operations do not change the invariant, and that initially we had only one cell (<i>x</i><sub><i>A</i></sub>,<i>y</i><sub><i>A</i></sub>). This means that we have an oracle that can tell us whether (<i>y</i><sub><i>A</i></sub>-<i>y</i><sub>0</sub>)&(<i>x</i><sub>0</sub>-<i>x</i><sub><i>A</i></sub>)=<i>x</i><sub>0</sub>-<i>x</i><sub><i>A</i></sub> for any two numbers <i>x</i><sub>0</sub> and <i>y</i><sub>0</sub> such that <i>y</i><sub>0</sub><=<i>y</i><sub><i>A</i></sub>.<br /><br />In problem C1, we know that <i>y</i><sub><i>A</i></sub>=0, so we can just pick <i>y</i><sub>0</sub> in such a way that -<i>y</i><sub>0</sub> has all bits set except one, and then the oracle will effectively tell us the corresponding bit of <i>x</i><sub>0</sub>-<i>x</i><sub><i>A</i></sub>, so we can determine <i>x</i><sub><i>A</i></sub> in logarithmic number of queries.<br /><br />In problem C2 the things are not so simple. However, suppose we have found some <i>x</i><sub>0</sub> and <i>y</i><sub>0</sub> such that (<i>y</i><sub><i>A</i></sub>-<i>y</i><sub>0</sub>)&(<i>x</i><sub>0</sub>-<i>x</i><sub><i>A</i></sub>)=<i>x</i><sub>0</sub>-<i>x</i><sub><i>A</i></sub>, in other words we made our oracle return 1. Now we can go from the highest bits to the lowest bit, and by calling our oracle 3 additional times checking what happens if we add 2<sup><i>k</i></sup> to <i>x</i><sub>0</sub> and/or subtract 2<sup><i>k</i></sup> from <i>y</i><sub>0</sub>, we can determine the <i>k</i>-th bit of <i>y</i><sub><i>A</i></sub>-<i>y</i><sub>0</sub> and <i>x</i><sub>0</sub>-<i>x</i><sub><i>A</i></sub>, then setting both to 0 and proceeding to the lower bits, and eventually recovering <i>y</i><sub><i>A </i></sub>and <i>x</i><sub><i>A</i></sub>.<br /><br />The tricky part lies in the initial step of making the oracle return 1 for something: the probability of <i>n</i>&<i>k</i>=<i>k</i> for random <i>n</i> and <i>k</i> is roughly 0.75<sup>number_of_bits</sup>, which is way too low to just stumble upon it. This is how far I got during the contest, so the remaining magic is closely based on the official editorial and my conversations with Makoto.<br /><br />Instead of running the oracle for the set <i>S</i> with just one cell (<i>x</i><sub>0</sub>,<i>y</i><sub>0</sub>) in the row <i>y</i>=<i>y</i><sub>0</sub>, we will run it with the set <i>S</i> which has all cells (<i>x</i><sub>0</sub>,<i>y</i><sub>0</sub>) in the row <i>y</i>=<i>y</i><sub>0 </sub>where <i>x</i><sub>0</sub> mod 3=<i>u</i>, <i>l</i><=<i>x</i><sub>0</sub><=<i>r</i>, where <i>y</i><sub>0</sub>, <i>u</i>, <i>l</i> and <i>r</i> are the parameters of the oracle. This requires counting the number of <i>x</i><sub>0 </sub>satisfying the above criteria and also the constraint (<i>y</i>-<i>y</i><sub>0</sub>)&(<i>x</i><sub>0</sub>-<i>x</i>)=<i>x</i><sub>0</sub>-<i>x</i> for each black cell in the input, which can be done by a relatively standard dynamic programming on the bitwise representation of <i>x</i><sub>0</sub>.<br /><br />As we know, this will give us the parity of the amount of such <i>x</i><sub>0</sub> that <i>x</i><sub>0</sub> mod 3=<i>u</i>, <i>l</i><=<i>x</i><sub>0</sub><=<i>r</i>, and (<i>y</i><sub><i>A</i></sub>-<i>y</i><sub>0</sub>)&(<i>x</i><sub>0</sub>-<i>x</i><sub><i>A</i></sub>)=<i>x</i><sub>0</sub>-<i>x</i><sub><i>A</i></sub>. A crucial observation is: no matter what <i>y</i><sub>0</sub> we pick, if <i>l </i>is very small and <i>r</i> is very large, then for at least one <i>u</i> from the set {0, 1, 2} this oracle will return 1! This can be proven by induction by <i>y</i><sub><i>A</i></sub>: when <i>y</i><sub><i>A</i></sub>=<i>y</i><sub>0</sub>, (<i>y</i><sub><i>A</i></sub>-<i>y</i><sub>0</sub>)&(<i>x</i><sub>0</sub>-<i>x</i><sub><i>A</i></sub>)=<i>x</i><sub>0</sub>-<i>x</i><sub><i>A</i></sub> only when <i>x</i><sub>0</sub>=<i>x</i><sub><i>A</i></sub>, so the oracle will return 1 when u=<i>x</i><sub><i>A</i></sub> mod 3 and zero in the other two cases. When <i>y</i><sub><i>A </i></sub>increases by one, given our C(<i>n</i>,<i>k</i>)-like propagation, every <i>x</i><sub>0 </sub>for which the oracle returns 1 contributes one to itself and <i>x</i><sub>0</sub>+1, which means that we go from parities (<i>a</i>, <i>b</i>, <i>c</i>) for the three remainders modulo 3 to parities (<i>a</i>+<i>b</i>, <i>b</i>+<i>c</i>, <i>a</i>+<i>c</i>), so from (1, 0, 0) to (1, 0, 1), and then to (1, 1, 0), and then to (0, 1, 1), and then to (1, 0, 1) and so on, and never get (0, 0, 0).<br /><br />This means that in at most three attempts we can make this complex oracle return 1. Now (more magic incoming!) we can do a binary search: if for (<i>y</i><sub>0</sub>, <i>u</i>, <i>l</i>, <i>r</i>) the oracle returns 1, then it must return 1 for exactly one of (<i>y</i><sub>0</sub>, <i>u</i>, <i>l</i>, <i>m</i>) and (<i>y</i><sub>0</sub>, <i>u</i>, <i>m</i>+1, <i>r</i>). This way we can find a single cell (<i>x</i><sub>0</sub>,<i>y</i><sub>0</sub>) for which the oracle returns 1 in a logarithmic number of requests to the complex oracle, and then switch to using the simple oracle and proceed with reconstructing the answer as described above, completing the solution of C2.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-P0KVALcJWWY/XIVzEWKHOgI/AAAAAAACQg0/CBBeMjB9WosbvpPcgstGzY4L4EQsmJUowCLcBGAs/s1600/IMG_20190303_135957.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1200" data-original-width="1600" height="480" src="https://1.bp.blogspot.com/-P0KVALcJWWY/XIVzEWKHOgI/AAAAAAACQg0/CBBeMjB9WosbvpPcgstGzY4L4EQsmJUowCLcBGAs/s640/IMG_20190303_135957.jpg" width="640" /></a></div>I have also mentioned an Open Cup problem: you have some amount <i>x</i> of money between 0 and 1. You're playing a betting game where in one turn, you bet some amount <i>y</i>, and with probability <i>p</i> (<i>p</i><0.5) your amount of money becomes <i>x</i>+<i>y</i>, and with probability 1-<i>p</i> it becomes <i>x</i>-<i>y</i>. Your bet must not exceed your current amount of money. Your goal is to reach amount 1. So far this setup is somewhat standard, but here comes the twist: your bets must be non-decreasing, in other words at each turn you must bet at least the amount you bet in the previous turn. In case you don't have enough money for that, you lose. What is the probability of winning if you play optimally? More precisely, what is the supremum of the set of probabilities of winning of all possible strategies? Both <i>x</i> and <i>p</i> are given as fractions with numerator and denominator not exceeding 10<sup>6</sup>, and you need to return the answer using division modulo 998244353.<br /><br />You can find my approach to solving it in <a href="https://codeforces.com/blog/entry/65510?#comment-495131">this Codeforces comment</a>.<br /><br />Thanks for reading, and check back for this week's summary!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/er8RDaFQ5QQ" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com0http://petr-mitrichev.blogspot.com/2019/03/an-oracle-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-67194231488627845602019-02-27T08:51:00.001+03:002019-02-27T08:51:09.373+03:00A WTF 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/-_ig0BKG88cs/XHNpkaDAhXI/AAAAAAACQLo/zbrudwU5BrwbINL6AWosfDK1PTLEQ1DvwCLcBGAs/s1600/acwtf19top8.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="519" data-original-width="826" height="402" src="https://3.bp.blogspot.com/-_ig0BKG88cs/XHNpkaDAhXI/AAAAAAACQLo/zbrudwU5BrwbINL6AWosfDK1PTLEQ1DvwCLcBGAs/s640/acwtf19top8.png" width="640" /></a></div>AtCoder World Tour Finals 2019 in Tokyo headlined the last week (<a href="https://atcoder.jp/contests/wtf19/tasks">problems</a>, <a href="https://atcoder.jp/contests/wtf19/standings">results</a> on the left, <a href="https://atcoder.jp/contests/wtf19-open/standings">open round results</a>, <a href="https://youtu.be/DLRYW7yQNfU">my screencast</a>, <a href="https://img.atcoder.jp/wtf19-open/editorial.pdf">analysis</a>). The last three problems turned out too difficult to solve during the contest, so it all came down to speed on the first three. yutaka1999 was the fastest, but his five incorrect attempts gave the competitors 25 minutes to overtake him, and apiad did just that and won the first ever AtCoder World Tour. Congratulations!<br /><br />I was pretty quick with solving A and C1, but then tried to solve B, C2 and E in parallel, switching often from one to another, instead of focusing on just one of them as it was not clear at that point that solving just one more would be enough for a good result. By the time I managed to come up with a solution for B, it was already too late to catch apiad and yutaka1999.<br /><br />I found the problems <a href="https://atcoder.jp/contests/wtf19/tasks/wtf19_c1">C1</a> and <a href="https://atcoder.jp/contests/wtf19/tasks/wtf19_c2">C2</a> the most exciting. Consider an infinite 2D grid, where each cell can be either black or white. Initially, exactly one cell was black, and then we repeatedly applied the following operation: take some integers <i>x</i> and <i>y</i>, and invert the color of three cells: (<i>x</i>, <i>y</i>), (<i>x</i>+1, <i>y</i>) and (<i>x</i>, <i>y</i>+1). You are given the set of black cells in the final state of the grid. There are at most 10<sup>5</sup> black cells in C1 and at most 10<sup>4</sup> in C2, and each black cell has coordinates not exceeding 10<sup>17</sup> by absolute value. Your goal is to find the coordinates of the only cell that was black originally. In problem C1 you know that its <i>y</i>-coordinate was 0, and in C2 there are no further constraints. Can you see a way to solve at least C1?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-wx27LwInpNE/XHNu9-A8ROI/AAAAAAACQL0/dw6zNxNp4ssoM5yLlJtXEZKnDtVSzr5YQCLcBGAs/s1600/srm751top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="95" data-original-width="628" src="https://4.bp.blogspot.com/-wx27LwInpNE/XHNu9-A8ROI/AAAAAAACQL0/dw6zNxNp4ssoM5yLlJtXEZKnDtVSzr5YQCLcBGAs/s1600/srm751top5.png" /></a></div>TopCoder SRM 751 followed on Friday (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=17400">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17400&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://www.topcoder.com/blog/single-round-match-751-editorials/">analysis</a>). Only rng_58 and pashka submitted all three problems, but the challenge phase did not leave them unscathed, and IH19980412 emerged in the first place thanks to three successful challenges, including one on rng_58 himself. Well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-HA-RuryY3kY/XHNwNEKcSTI/AAAAAAACQMA/vkgagupRaWU48mchCpyJwh7VlnR8R78YQCLcBGAs/s1600/oc1819bytedancetop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="211" data-original-width="787" height="170" src="https://4.bp.blogspot.com/-HA-RuryY3kY/XHNwNEKcSTI/AAAAAAACQMA/vkgagupRaWU48mchCpyJwh7VlnR8R78YQCLcBGAs/s640/oc1819bytedancetop5.png" width="640" /></a></div>Open Cup 2018-19 Grand Prix of Bytedance presented problems from the team Moscow SU: Red Panda on Sunday (<a href="http://opentrains.snarknews.info/~ejudge/res/res10453">results</a>, top 5 on the left, <a href="https://drive.google.com/file/d/1aV_UGxlTh00PsiqUnKN_mOGoL26KrhuO/view?usp=sharing">analysis</a>). There were several nice problems in this contest, and problem C was the one I've enjoyed solving the most.<br /><br />You have some amount <i>x</i> of money between 0 and 1. You're playing a betting game where in one turn, you bet some amount <i>y</i>, and with probability <i>p</i> (<i>p</i><0.5) your amount of money becomes <i>x</i>+<i>y</i>, and with probability 1-<i>p</i> it becomes <i>x</i>-<i>y</i>. Your bet must not exceed your current amount of money. Your goal is to reach amount 1. So far this setup is somewhat standard, but here comes the twist: your bets must be non-decreasing, in other words at each turn you must bet at least the amount you bet in the previous turn. In case you don't have enough money for that, you lose. What is the probability of winning if you play optimally? More precisely, what is the supremum of the set of probabilities of winning of all possible strategies? Both <i>x</i> and <i>p</i> are given as fractions with numerator and denominator not exceeding 10<sup>6</sup>, and you need to return the answer using division modulo 998244353.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-lHDeXZUTteY/XHWYtpFLh4I/AAAAAAACQMQ/Yz9lnr8xz4MNwpcvHpoLJSfg8un6-lhFwCLcBGAs/s1600/cf542top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="273" data-original-width="1104" height="158" src="https://3.bp.blogspot.com/-lHDeXZUTteY/XHWYtpFLh4I/AAAAAAACQMQ/Yz9lnr8xz4MNwpcvHpoLJSfg8un6-lhFwCLcBGAs/s640/cf542top5.png" width="640" /></a></div>Finally, Codeforces Round 542 wrapped up the week on Sunday evening (<a href="https://codeforces.com/contest/1129">problems</a>, <a href="https://codeforces.com/contest/1129/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/65520">analysis</a>). Three contestants solved all problems correctly, and there wasn't much challenge activity, so everything was decided by the problem solving order and speed. mnbvmar was the fastest to solve everything, and did (the slightly faster to solve) problem E before problem D unlike the others. Congratulations on the victory!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/--OBnfnWvW2g/XHYlDjmqLzI/AAAAAAACQMo/z2Ui6GhRBe8D0TIx5eSILlClsqq7UGn7gCLcBGAs/s1600/MVIMG_20190220_123030.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1200" data-original-width="1600" height="480" src="https://1.bp.blogspot.com/--OBnfnWvW2g/XHYlDjmqLzI/AAAAAAACQMo/z2Ui6GhRBe8D0TIx5eSILlClsqq7UGn7gCLcBGAs/s640/MVIMG_20190220_123030.jpg" width="640" /></a></div><a href="https://petr-mitrichev.blogspot.com/2019/02/a-snack-week.html">Last week</a> I have mentioned another Open Cup problem: there's a hidden not necessarily convex polygon with <i>n</i> vertices (<i>n</i><=200). Your goal is to find its area, but the only thing you can do is to pick a subset of its vertices by their numbers (the vertices are numbered in the order they appear along the polygon), and the system will tell you the area of the convex hull of the chosen points. You can retrieve the convex hull areas for at most <i>n</i>*(<i>n</i>-1)/2 subsets before you need to give back the area of the hidden polygon.<br /><br />During the contest we tried to invent a solution based on representing the area of the polygon as the sum of signed areas of triangles using one of its vertices as the base point. We could not figure out a way to deal with "signed" part: we need to determine the orientation of each triangle, and while in most cases we can determine orientation of triangle ACD given the orientation of triangle ABC and ability to ask convex hull area queries, we could not see a way to make it work in all cases. Is there one?<br /><br />The approach that works involves a completely different idea: first, let's find the area of the convex hull of all vertices. Since our polygon is not necessarily convex, then we need to subtract something from it.<br /><br />For each particular vertex, we can find whether it lies on the boundary of the convex hull or not by checking if the area of the convex hull of all vertices except this one is smaller. Now we know which vertices do not lie on the convex hull of everything.<br /><br />Now let's take segments of consecutive vertices that do not lie on the convex hull, together with one vertex of convex hull before and after such segment. We claim that those are precisely the polygons whose areas we need to subtract from the area of the big convex hull to find the answer.<br /><br />The only remaining step is to recursively apply the same algorithm to find the areas of those smaller polygons.<br /><br />Thanks for reading, and check back next week!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/YXoebqlJAAs" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com3http://petr-mitrichev.blogspot.com/2019/02/a-wtf-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-19842146769572369662019-02-18T02:51:00.002+03:002019-02-18T02:51:47.052+03:00A snack 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://1.bp.blogspot.com/-gA3qEJChOr8/XGmsRWZhflI/AAAAAAACP5w/UCOFloct6jYa7eE8tGdlJMLYVauhoveWwCLcBGAs/s1600/snackdown2019top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="450" data-original-width="1534" height="186" src="https://1.bp.blogspot.com/-gA3qEJChOr8/XGmsRWZhflI/AAAAAAACP5w/UCOFloct6jYa7eE8tGdlJMLYVauhoveWwCLcBGAs/s640/snackdown2019top5.png" width="640" /></a></div>CodeChef SnackDown 2019 onsite finals early on Saturday was the main event of the week (<a href="https://www.codechef.com/SNCKFL19">problems</a>, <a href="https://www.codechef.com/rankings/SNCKFL19">results</a>, top 5 on the left). Team ovuvuevuevue enyetuenwuevue ugbemugbem osas looked to have pretty good winning chances when they were the first to solve 8 problems with a couple of hours still left in the contest, but they could not make further progress in the remaining time. Team Dandelion solved the ninth problem with about five minutes remaining to go on top, but team pastry was working on the same problem and could still overtake them on penalty time. It turned out that they were comparing their solution locally against a slower but simpler one, and there were still cases of disagreement as the end of the contest was approaching. With nothing left to lose, they submitted whatever they had 30 seconds before the end of the round — and it passed the system test. Congratulations to team pastry on the super narrow victory!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-N2CB2w2WAnM/XGnvGvMsBYI/AAAAAAACP6E/sJ3joKu9TnYTed4dqmJtaYRAhfntOCjDgCLcBGAs/s1600/cf539top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="273" data-original-width="1105" height="158" src="https://4.bp.blogspot.com/-N2CB2w2WAnM/XGnvGvMsBYI/AAAAAAACP6E/sJ3joKu9TnYTed4dqmJtaYRAhfntOCjDgCLcBGAs/s640/cf539top5.png" width="640" /></a></div>Later that day, Codeforces hosted its Round 539 (<a href="https://codeforces.com/contest/1109">problems</a>, <a href="https://codeforces.com/contest/1109/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/65295">analysis</a>). The participants of the Codechef finals occupied most of the top spots in this round as well. wxhtxdy was the only contestant to solve all problems, but as his solution to E turned out to be incorrect, Um_nik emerged in the first place. Congratulations to Um_nik on the win!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-S5NJiVYxnNU/XGnxJ2FKbmI/AAAAAAACP6Y/Q_JreMTt7y0nifYOV737E6uwfoAmoWR7gCLcBGAs/s1600/oc1819belarustop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="213" data-original-width="725" height="188" src="https://1.bp.blogspot.com/-S5NJiVYxnNU/XGnxJ2FKbmI/AAAAAAACP6Y/Q_JreMTt7y0nifYOV737E6uwfoAmoWR7gCLcBGAs/s640/oc1819belarustop5.png" width="640" /></a></div></div>Finally, the Open Cup 2018-19 Grand Prix of Belarus wrapped up the week (<a href="http://opentrains.snarknews.info/~ejudge/res/res10452">results</a>, top 5 on the left). Team MIT THREE won the second round in a row, this time solving three in the last hour including two hardest ones in the last fifteen minutes. Amazing persistence once again, well done!<br /><br />Problem A was a very nice interactive one: there's a hidden not necessarily convex polygon with <i>n</i> vertices (<i>n</i><=200). Your goal is to find its area, but the only thing you can do is to pick a subset of its vertices by their numbers (the vertices are numbered in the order they appear along the polygon), and the system will tell you the area of the convex hull of the chosen points. You can retrieve the convex hull areas for at most <i>n*</i>(<i>n</i>-1)/2 subsets before you need to give back the area of the hidden polygon.<br /><br />Thanks for reading, and check back next week!<br /><br />I will also try to post something here and/or on <a href="https://twitter.com/petrmitrichev">Twitter</a> about the first ever <a href="https://codeforces.com/blog/entry/64174">AtCoder World Tour finals</a> in Tokyo on Thursday — already looking forward to the event! </div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/ALTvoy0ghSk" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com1http://petr-mitrichev.blogspot.com/2019/02/a-snack-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-69270846871127641422019-02-11T01:22:00.000+03:002019-02-11T01:22:27.875+03:00A tourist 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/-DuhFWevNeHk/XGCRIgyO4nI/AAAAAAACPrM/qbOeRZejpvcY_RS6v0aeV2yGI-_Rgw3FwCLcBGAs/s1600/cfglobal1top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="273" data-original-width="1102" height="158" src="https://3.bp.blogspot.com/-DuhFWevNeHk/XGCRIgyO4nI/AAAAAAACPrM/qbOeRZejpvcY_RS6v0aeV2yGI-_Rgw3FwCLcBGAs/s640/cfglobal1top5.png" width="640" /></a></div>Codeforces hosted its Global Round 1 on Thursday (<a href="https://codeforces.com/contest/1110">problems</a>, <a href="https://codeforces.com/contest/1110/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/65079">analysis</a>). tourist and Um_nik were quite close, both finishing the problem-solving part around 1:20 mark and having some challenge fun thereafter. However, in the end the challenges did not affect the standings, and tourist stayed in first place. Congratulations!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-oMTf78iu-1w/XGCR4am9uXI/AAAAAAACPrU/20RU_jaCAeYLxONYeMSo0UhWs7MIYa1uACLcBGAs/s1600/srm750top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="95" data-original-width="636" src="https://4.bp.blogspot.com/-oMTf78iu-1w/XGCR4am9uXI/AAAAAAACPrU/20RU_jaCAeYLxONYeMSo0UhWs7MIYa1uACLcBGAs/s1600/srm750top5.png" /></a></div>TopCoder SRM 750 followed a day later (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=17399">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17399&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://www.topcoder.com/blog/single-round-match-750-editorials/">analysis</a>). This time tourist managed to get a commanding lead thanks to solving the 1000-pointer in just 8 minutes, while rng_58 needed 22 minutes and others even more. Well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-IyNFhiDosPQ/XGCXjrN-E4I/AAAAAAACPrg/n3qLRmcHPsY18ktfKHmDXQjNmlGF1V8_gCLcBGAs/s1600/oc1819gomeltop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="205" data-original-width="753" height="174" src="https://3.bp.blogspot.com/-IyNFhiDosPQ/XGCXjrN-E4I/AAAAAAACPrg/n3qLRmcHPsY18ktfKHmDXQjNmlGF1V8_gCLcBGAs/s640/oc1819gomeltop5.png" width="640" /></a></div>Finally, the Open Cup returned on Sunday with the Grand Prix of Gomel (<a href="http://opentrains.snarknews.info/~ejudge/res/res10451">results</a>, top 5 on the left). This was the first of seven consecutive Open Cup Sundays stretching right up to the ICPC World Finals, and that will provide a good preview as many top-rated ICPC teams are competing. The team from MIT earned the first place with just four minutes remaining, solving two of the hardest problems in the last hour. Amazing performance!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-b2scHcycaNw/XGCj5OYjh_I/AAAAAAACPrs/P89q5tj8Y0gyOHZ3dBlsEXqupfz4V4KKACLcBGAs/s1600/IMG_20190204_081201.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1200" data-original-width="1600" height="480" src="https://1.bp.blogspot.com/-b2scHcycaNw/XGCj5OYjh_I/AAAAAAACPrs/P89q5tj8Y0gyOHZ3dBlsEXqupfz4V4KKACLcBGAs/s640/IMG_20190204_081201.jpg" width="640" /></a></div>In <a href="https://petr-mitrichev.blogspot.com/2019/02/a-mumbling-week.html">the previous summary</a>, I have mentioned a TopCoder problem: you are given a 9x47 grid of zeroes and ones. In one step, you can take any cell that contains a one, and another cell that is either in the same row but to the right or in the same column but to the bottom from the first cell, and flip both of them (so one changes to zero, and zero changes to one). You are given the initial and the final state of the grid, and need to produce any (not necessarily the shortest) sequence of operations that transforms one to the other with at most 947 operations.<br /><br />When we apply this operation to a one and a zero, we're effectively moving the one to the bottom or to the right. By applying this operation several times, the one can move to the bottom <i>and</i> to the right. Moreover, the opposite is true: for any position to the bottom and to the right, we can move the one there in exactly two operations. If the cell in the middle (in the same row or column as both source and target cells) contains a zero, then we just move the one twice in a straightforward manner. If the cell in the middle contains a one, then we can first move that one to the target, and then move the one from the source to the middle cell, restoring the one there.<br /><br />Finally, the other option of applying the operation to a one and a one, or moving a one onto a one in two operations as described above, results in both ones disappearing. Now we're in a very nice position: we understand the full structure of the problem, and have described everything that is possible in a very concise manner, which allows to see the solution.<br /><br />More precisely, we need find a "source" one in the initial grid to the left and/or to the top for each one from the final grid, which might also leave some ones in the initial grid unused. Note that if the number of unused ones is odd, there's no solution since all operations preserve parity, and if the number of unused ones is even, we can always get rid of them by moving each to the bottom-right corner in at most two operations.<br /><br />This observation leaves us with a matching problem which can actually be solved greedily because of the special structure of the graph. If we traverse the ones from the final grid in row-major order, we can simply always pick the rightmost yet-unused one in the initial grid to the left and/or to the top from the current position. This can be proven by a typical exchange argument: let's look at the first time in this row-major traversal when the optimal solution uses a different one to cover the final one in the current position, and uses the greedy choice to cover something else. We can swap the assignments of those two ones and still obtain a valid solution.<br /><br />Thanks for reading, and check back next week!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/RjEQewnPVGc" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com1http://petr-mitrichev.blogspot.com/2019/02/a-tourist-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-27624436295978650502019-02-03T22:09:00.000+03:002019-02-03T22:09:02.540+03:00A mumbling 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/-4pOqM2YSz8c/XFcymvpnqiI/AAAAAAACPmg/m8tNmYaxVL8wo1WmR8BbnOv3D-KxQxbvgCLcBGAs/s1600/srm749top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="97" data-original-width="637" src="https://1.bp.blogspot.com/-4pOqM2YSz8c/XFcymvpnqiI/AAAAAAACPmg/m8tNmYaxVL8wo1WmR8BbnOv3D-KxQxbvgCLcBGAs/s1600/srm749top5.png" /></a></div>TopCoder SRM 749 was the main event of this week (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=17398">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17398&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://youtu.be/hqCECmi_AJc">my screencast with mumbling</a>). All three problems were quite tricky, and passing the sample cases did not really mean that much. As he often does, rng_58 excelled in such circumstances and claimed the first place with a sizable margin — congratulations!<br /><br />The only other contestant to solve the hardest problem, pashka, was actually unable to figure out the proper algorithmic solution in time; so he decided to take his chances and treat the problem as a general hamiltonian cycle problem and solve it with a simple but powerful heuristic, <a href="https://petr-mitrichev.blogspot.com/2014/09/this-week-in-competitive-programming_14.html">just like I did in 2014</a>. It seems that participating in IOI 2002 has finally paid off for both of us :)<br /><br /><a href="https://community.topcoder.com/stat?c=problem_statement&pm=15298&rd=17398">The medium problem</a> was quite nice in this round. After removing some unnecessary complications, the statement boiled down to: you are given a 9x47 grid of zeroes and ones. In one step, you can take any cell that contains a one, and another cell that is either in the same row but to the right or in the same column but to the bottom from the first cell, and flip both of them (so one changes to zero, and zero changes to one). You are given the initial and the final state of the grid, and need to produce any (not necessarily the shortest) sequence of operations that transforms one to the other with at most 947 operations.<br /><br />Thanks for reading, and check back next week!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/w7YB5HavwmA" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com2http://petr-mitrichev.blogspot.com/2019/02/a-mumbling-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-28134008761600270852019-01-27T22:38:00.001+03:002019-01-27T23:35:43.802+03:00A Galois 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/-IeVOTbVFI7o/XE4FcJa5yKI/AAAAAAACPeM/HKB9S8DJNB0G1e07NkvQQkWSR7qHb6uoQCLcBGAs/s1600/cf534top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="272" data-original-width="1110" height="156" src="https://4.bp.blogspot.com/-IeVOTbVFI7o/XE4FcJa5yKI/AAAAAAACPeM/HKB9S8DJNB0G1e07NkvQQkWSR7qHb6uoQCLcBGAs/s640/cf534top5.png" width="640" /></a></div>Codeforces returned this week with its Round 534 on Tuesday (<a href="https://codeforces.com/contest/1103">problems</a>, <a href="https://codeforces.com/contest/1103/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/64722">analysis</a>). mnbvmar won not just thanks to being the only contestant to solve the hardest problem E, but also thanks to being much faster than his peers on the first three problems, which might've been the key to unlocking the strategy of solving E instead of D. Well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-vl1HU2OcmfM/XE3yor5U7AI/AAAAAAACPeA/1yUiHq58NicNCAl9nhfNZxQ7EzDopsfCQCLcBGAs/s1600/srm748top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="95" data-original-width="635" src="https://4.bp.blogspot.com/-vl1HU2OcmfM/XE3yor5U7AI/AAAAAAACPeA/1yUiHq58NicNCAl9nhfNZxQ7EzDopsfCQCLcBGAs/s1600/srm748top5.png" /></a></div>TopCoder SRM 748 on Saturday wrapped up the second stage of the race to TCO19 (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=17397">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17397&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://youtu.be/yDrUX0qQIkY">my screencast</a>, <a href="https://www.topcoder.com/blog/single-round-match-748-editorials/">analysis</a>). tourist was the only one able to solve the hard problem, but he also had the fastest time on both the easy and the medium. Congratulations on the very convincing victory!<br /><br /><a href="https://community.topcoder.com/stat?c=problem_statement&pm=15294&rd=17397">The hard problem</a> has introduced me to the concept of <a href="https://www.google.com/search?q=nim+multiplication">nim multiplication</a> which, on one side, allows <a href="https://www.stat.berkeley.edu/~mlugo/stat155-f11/tartan2.pdf">solving products of coin turning games</a>, and on the other side, together with the nim addition — bitwise xor — <a href="https://en.wikipedia.org/wiki/Nimber#Multiplication">induces a finite field</a> of characteristic 2 over the nimbers less than 2<sup>2<sup><i>n</i></sup></sup> for any <i>n</i>. I find this sudden appearance of finite fields exceedingly beautiful :)<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-JhIhJ40jLbg/XE4InRqauoI/AAAAAAACPew/_mBkvuCu1HMg51uZSaaIVmJ7SJ_wd_cXACLcBGAs/s1600/IMG_20190127_083801.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="764" data-original-width="1600" height="304" src="https://2.bp.blogspot.com/-JhIhJ40jLbg/XE4InRqauoI/AAAAAAACPew/_mBkvuCu1HMg51uZSaaIVmJ7SJ_wd_cXACLcBGAs/s640/IMG_20190127_083801.jpg" width="640" /></a></div><a href="https://en.wikipedia.org/wiki/Nimber#Multiplication">The Wikipedia article</a> implies that for computing the nim multiplication, we just need the following two facts:<br /><br /><ol style="text-align: left;"><li>The nim product of a Fermat power of two (numbers of the form 2<sup>2<sup><i>n</i></sup></sup>) with a smaller number is equal to their ordinary product;</li><li>The nim square of a Fermat power of two <i>x</i> is equal to 3<i>x</i>/2 as evaluated under the ordinary multiplication of natural numbers.</li></ol><br />It took me quite some time to understand how to compute the nim multiplication using those facts, but now I think I got it, so I'll try to explain (also, does anybody have a link to where this is explained nicely? I could not find one).<br /><br />First, suppose we know the nim products of powers of two. Then we can use the fact that we have a field to compute all other products by representing the multipliers as xors (nim-sums) of powers of two, for example (where all additions and multiplications are the nim ones): 3*6=(2+1)*(4+2)=2*4+2*2+1*4+1*2=8+3+4+2=8+4+1=13.<br /><br />Now, the above rules allow to multiply Fermat powers of two, but we need to learn to multiply arbitrary powers of two. Here we once again use the binary representation, this time of the exponent, to represent any power of two as a (both nim and ordinary) product of Fermat powers of two, and then rely on associativity of multiplication to rearrange the Fermat powers of two in sorted order. If they're all distinct, then we can go from smallest to largest to learn that their product is equal to their ordinary product according to the first rule above; and if a Fermat power is repeated, then we use the second rule above to effectively decompose the problem into two. If we always apply the second rule to the smallest repeated power, I think we never end up with more than two occurrences of any power in our intermediate computations.<br /><br />Here's an example: 2048*128=(256*4*2)*(16*4*2)=2*2*4*4*16*256=(1+2)*4*4*16*256=4*4*16*256+2*4*4*16*256=(2+4)*16*256+2*(2+4)*16*256=2*16*256+4*16*256+2*2*16*256+2*4*16*256=2*16*256+4*16*256+(1+2)*16*256+2*4*16*256=2*16*256+4*16*256+16*256+2*16*256+2*4*16*256=4*16*256+16*256+2*4*16*256=16384+4096+32768=53248.<br /><br />Those two ideas can be combined to obtain a single algorithm as described in the exercise 4 at the bottom of page 14 in <a href="https://openaccess.leidenuniv.nl/bitstream/handle/1887/2125/346_027.pdf">this article</a> from 1978.<br /><br />Thanks for reading, and check back next week!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/gFG3Nqa8cok" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com0http://petr-mitrichev.blogspot.com/2019/01/a-galois-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-64201223253251889262019-01-20T20:44:00.002+03:002019-01-20T20:46:47.367+03:00An anti-library 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/-YVk0JGOP6q0/XESjc1WFdpI/AAAAAAACPUc/0evKGCYe2FAb4Llxi6JXQXzgtazjtcVQQCLcBGAs/s1600/srm746top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="95" data-original-width="637" src="https://4.bp.blogspot.com/-YVk0JGOP6q0/XESjc1WFdpI/AAAAAAACPUc/0evKGCYe2FAb4Llxi6JXQXzgtazjtcVQQCLcBGAs/s1600/srm746top5.png" /></a></div>TopCoder held two SRMs this week. SRM 746 took place on Tuesday (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=17395">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17395&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://youtu.be/EhkGX648sNI">my screencast</a>, <a href="https://www.topcoder.com/blog/single-round-match-746-editorials/">analysis</a>). Once again the topic of floating-point precision took center stage: 27 solutions were submitted for <a href="https://community.topcoder.com/stat?c=problem_statement&pm=15268&rd=17395">the hard problem</a>, many relying on floating-point and/or ternary search, but only 5 passed, all computing the answer exactly and using either arbitrary-length integers, arbitrary-length floating point, or int128.<br /><br />I've already made this point in the <a href="https://codeforces.com/blog/entry/64554?#comment-485100">Codeforces discussion thread</a>, but let me repeat here: the super high precision requirement had a side effect of essentially penalizing the contestants that had a prewritten 3D geometry library: using the library as-is would fail because of precision issues, and adapting a set of interconnected methods from floating-point to big integers is actually much more time-consuming than figuring out the relatively simple required computation from scratch and implementing it. Looking at the five accepted solutions, four or maybe all five seem to be written from scratch.<br /><br />This has also provided for an unusual challenge phase, with 9 out of 26 successful challenges coming on the hardest problem. In most cases ending up in room 1 is a bad sign for the challenge phase (I believe the rooms are sorted by decreasing average rating, or something like that), but here it was exactly the opposite :)<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-IY1WsuVDDlk/XESljMRpW9I/AAAAAAACPUo/b3Kz5-si1bQ_4R6XjAt7zahBfC0mA8qEwCLcBGAs/s1600/srm747top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="98" data-original-width="638" src="https://3.bp.blogspot.com/-IY1WsuVDDlk/XESljMRpW9I/AAAAAAACPUo/b3Kz5-si1bQ_4R6XjAt7zahBfC0mA8qEwCLcBGAs/s1600/srm747top5.png" /></a></div>SRM 747 followed on Saturday (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=17396">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17396&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://youtu.be/EUP-kY-sZ18">my screencast</a>). The relatively standard medium and hard meant that the first place was decided during the challenge phase, and <a href="https://community.topcoder.com/stat?c=problem_statement&pm=15286&rd=17396">the easy problem</a> seemed to have been designed specifically to make the challenge phase more interesting: it was a constructive problem with such loose requirements that a lot of solutions worked, and even more solutions passed the sample cases. In fact, one could almost say that it was possible to pass the samples by accident :) However, challenging those solutions was also not trivial, as they might pass a challenge case by accident just as well.<br /><br />Thanks for reading, and check back next week!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/m6KswF-iV04" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com0http://petr-mitrichev.blogspot.com/2019/01/an-anti-library-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-67000391570987264442019-01-13T12:32:00.000+03:002019-01-13T12:32:06.861+03:00A Dilworth 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/-eSpx-iDJ4l8/XDsFL_ic9CI/AAAAAAACPFI/TNMkeAhj0DMkyPCuxizKtESJhajkZIg2gCLcBGAs/s1600/IMG_20181228_140312.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="989" data-original-width="1600" height="394" src="https://2.bp.blogspot.com/-eSpx-iDJ4l8/XDsFL_ic9CI/AAAAAAACPFI/TNMkeAhj0DMkyPCuxizKtESJhajkZIg2gCLcBGAs/s640/IMG_20181228_140312.jpg" width="640" /></a></div>This week was light on contests, so let me talk about the Codeforces problems I've mentioned in <a href="https://petr-mitrichev.blogspot.com/2019/01/a-radewoosh-week.html">last week's summary</a>. The <a href="https://codeforces.com/contest/1097/problem/E">first one</a> was: you are given a permutation of size <i>n</i> <= 100000, and you need to split it into subsequences such that each subsequence is either monotonically decreasing or monotonically increasing. The number of subsequences needs to be small, but does not need to be minimal. More precisely, your solution should have the optimal <i>worst</i> case performance for any given <i>n</i>: the number of subsequences should not exceed the maximum number of subsequences necessary for any permutation of size <i>n</i>.<br /><br />One fact that definitely looks helpful is the <a href="https://en.wikipedia.org/wiki/Dilworth%27s_theorem">Dilworth's theorem</a>: it tells us that we either have a long increasing subsequence, or can split our sequence into few decreasing subsequences. More formally, let's define f(<i>n</i>) to be the maximum number of subsequences our solution produces for any permutation of size <i>n</i>. Applying the Dilworth's theorem allows to build a solution with the following recurrence on f():<br /><br />f(<i>n</i>)=max<sub><i>k</i></sub>(min(<i>k</i>,1+f(<i>n</i>-<i>k</i>))<br /><br />where the inner minimum corresponds to the fact that we can either split everything into <i>k</i> decreasing subsequences, or remove an increasing subsequence of length <i>k</i> and apply our solution recursively.<br /><br />Printing a few first values of f(<i>n</i>) computed the recurrence above, we get:<br /><br /><span style="font-family: Courier New, Courier, monospace;">f(1) = 1</span><br /><span style="font-family: Courier New, Courier, monospace;">f(2) = 1</span><br /><span style="font-family: Courier New, Courier, monospace;">f(3) = 2</span><br /><span style="font-family: Courier New, Courier, monospace;">f(4) = 2</span><br /><span style="font-family: Courier New, Courier, monospace;">f(5) = 2</span><br /><span style="font-family: Courier New, Courier, monospace;">f(6) = 3</span><br /><span style="font-family: Courier New, Courier, monospace;">f(7) = 3</span><br /><span style="font-family: Courier New, Courier, monospace;">f(8) = 3</span><br /><span style="font-family: Courier New, Courier, monospace;">f(9) = 3</span><br /><span style="font-family: Courier New, Courier, monospace;">f(10) = 4</span><br /><span style="font-family: Courier New, Courier, monospace;">f(11) = 4</span><br /><span style="font-family: Courier New, Courier, monospace;">f(12) = 4</span><br /><span style="font-family: Courier New, Courier, monospace;">f(13) = 4</span><br /><span style="font-family: Courier New, Courier, monospace;">f(14) = 4</span><br /><span style="font-family: Courier New, Courier, monospace;">f(15) = 5</span><br /><span style="font-family: Courier New, Courier, monospace;">f(16) = 5</span><br /><div><span style="font-family: Courier New, Courier, monospace;">...</span></div><div><br /></div><div>Here we can notice that the smallest value of n such that f(<i>n</i>)=<i>k</i> is the <i>k</i>-th triangular number: 1+2+...+<i>k</i>=<i>k</i>*(<i>k</i>+1)/2. Having noticed it, it's relatively easy to prove it by induction.</div><div><br /></div><div>So we have a solution using Dilworth's theorem, but is it good enough for the problem? Does it have the same worst case performance as the best possible solution for any given <i>n</i>?</div><div><br /></div><div>The answer is yes, and the triangular numbers together with the recurrence above give us a hint how to see it. We need to come up with some permutation of size 1+2+...+<i>k</i> for which we can prove that it can't be split into less than k increasing or decreasing subsequences. </div><div><br /></div><div>Here is one such sequence for k=5: <span style="font-family: Courier New, Courier, monospace;">1, 3, 2, 6, 5, 4, 10, 9, 8, 7, 15, 14, 13, 12, 11.</span> In other words, we take a decreasing segment of length 1, then append a decreasing segment of length 2 with all numbers bigger than the previous segment, then append a decreasing segment of length 3 with all numbers bigger than the previous segment, and so on until a segment of length <i>k</i>. Consider any split of this sequence into increasing and decreasing subsequences. Suppose it has <i>x</i> increasing subsequences. Each increasing subsequence covers at most one element of each decreasing segment, so for <i>k</i>-<i>x</i> segments with more than <i>x</i> elements at least one number will be left uncovered. But a decreasing subsequence can't have numbers from two different segments, so we will need at least <i>k</i>-<i>x</i> decreasing subsequences to cover the rest, and the total will be at least <i>k</i>.</div><div><br /></div><div>This proves that our solution does in fact have the optimal worst case performance for any given <i>n</i>. One small thing that the Wikipedia article doesn't give is a constructive way to apply the theorem: finding the longest increasing subsequence is a well-known algorithm, but how do we actually split the sequence into as many decreasing subsequences quickly? Some quick googling helped me find the answer during the contest: in the longest increasing subsequence algorithm, let's call the length of the longest increasing subsequence ending in each element the <i>level</i> of this element. It turns out that the elements of the same level always form a non-increasing (and since we have a permutation, decreasing) subsequence, as otherwise the element to the right would have a higher level, so we just split by level.</div><div><br /></div><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-DFZgQfcKARg/XDsFTr1H_TI/AAAAAAACPFM/Kuv6nr3g-Hk5HgGCP3LyVBMDZ0bsRDgOQCLcBGAs/s1600/IMG_20181228_161345_1.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1200" data-original-width="1600" height="480" src="https://3.bp.blogspot.com/-DFZgQfcKARg/XDsFTr1H_TI/AAAAAAACPFM/Kuv6nr3g-Hk5HgGCP3LyVBMDZ0bsRDgOQCLcBGAs/s640/IMG_20181228_161345_1.jpg" width="640" /></a></div><div>The <a href="https://codeforces.com/contest/1098/problem/B">second problem</a> I mentioned <a href="https://petr-mitrichev.blogspot.com/2019/01/a-radewoosh-week.html?showComment=1546934865319#c6990024409469331025">turned out</a> to be <a href="https://community.topcoder.com/stat?c=problem_statement&pm=10758&rd=14154">a repeat</a> from 9 years ago: you are given a <i>n</i>x<i>m</i> matrix such that <i>n</i>*<i>m</i><=300000, with one character from the set A, C, G or T in each cell. You need to change as few characters as possible (to other characters from the set) in such a way that each 2x2 submatrix has all four different characters.</div><div><br /></div><div>Given that there are consequently <a href="https://apps.topcoder.com/wiki/display/tc/SRM+472">two</a> <a href="https://codeforces.com/blog/entry/64331">editorials</a> for it, I don't think I can add much :)</div><div><br /></div><div>Thanks for reading, and check back next week!</div></div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/uMrikDCpYkE" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com2http://petr-mitrichev.blogspot.com/2019/01/a-dilworth-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-42243977595853498372019-01-06T15:05:00.001+03:002019-01-06T15:25:45.160+03:00A Radewoosh 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/-3HPkNxoDxss/XDHeZtQm1LI/AAAAAAACOqQ/hkUSRigQEls69pqG8mX8-CRbqHhmSDNJgCLcBGAs/s1600/cfhello2019top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="270" data-original-width="1104" height="156" src="https://2.bp.blogspot.com/-3HPkNxoDxss/XDHeZtQm1LI/AAAAAAACOqQ/hkUSRigQEls69pqG8mX8-CRbqHhmSDNJgCLcBGAs/s640/cfhello2019top5.png" width="640" /></a></div>Codeforces did not take any breaks, and held two contests in the first week of 2019. The first one was appropriately named "Hello 2019" (<a href="https://codeforces.com/contest/1097">problems</a>, <a href="https://codeforces.com/contest/1097/standings">results</a>, top 5 on the left, <a href="https://youtu.be/UxtEMlc0sHM">my screencast</a>, <a href="https://codeforces.com/blog/entry/64310">analysis</a>). V--o_o--V took a gamble and started with problem G which looks doable on the surface but takes quite a lot of time to get right. This was not optimal in terms of the number of points, but it or the five incorrect attempts did not matter in the end as nobody else was able to solve all problems. Congratulations to V--o_o--V!<br /><br />I was actually quite close to getting all problems, as I've fixed the last bug in my solution for H just 30 seconds after the end of the contest (you can still see it on the screencast). And given the unexpectedly low point total of V--o_o--V, that would be enough for the first place :)<br /><br /><a href="https://codeforces.com/contest/1097/problem/E">Problem E</a> mostly relied on a well-known theorem, but had an interesting twist on top of it: you are given a permutation of size <i>n</i> <= 100000, and you need to split it into subsequences such that each subsequence is either monotonically decreasing or monotonically increasing. The number of subsequences needs to be small, but does not need to be minimal. More precisely, your solution should have the optimal <i>worst</i> case performance for any given <i>n</i>: the number of subsequences should not exceed the maximum number of subsequences necessary for any permutation of size <i>n</i>.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-hEzDShxtoN4/XDHenAcU7XI/AAAAAAACOqY/sy4XYO_1-H8z0F_WbI6M4SB4Z_EbbUvKACLcBGAs/s1600/cf530top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="272" data-original-width="1105" height="156" src="https://4.bp.blogspot.com/-hEzDShxtoN4/XDHenAcU7XI/AAAAAAACOqY/sy4XYO_1-H8z0F_WbI6M4SB4Z_EbbUvKACLcBGAs/s640/cf530top5.png" width="640" /></a></div>Codeforces Round 530 took place one day later (<a href="https://codeforces.com/contest/1098">problems</a>, <a href="https://codeforces.com/contest/1098/standings">results</a>, top 5 on the left, <a href="https://youtu.be/WR9rMvE-d9Y">my screencast</a>, <a href="https://codeforces.com/blog/entry/64331">analysis</a> so far partially in Russian). Problem E required a lot of careful implementation, and the speed of that implementation was the deciding factor in the standings. Of the four contestants finishing before the round ended, Radewoosh was the fastest. Well done!<br /><br />I found <a href="https://codeforces.com/contest/1098/problem/B">problem B</a> quite cute: you are given a <i>n</i>x<i>m</i> matrix such that <i>n</i>*<i>m</i><=300000, with one character from the set A, C, G or T in each cell. You need to change as few characters as possible (to other characters from the set) in such a way that each 2x2 submatrix has all four different characters. Can you see a way?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-6BCIFxIkf3Y/XDHs1rBr_RI/AAAAAAACOqw/k1OIIGuaN4k1pLFv2P7Cm4WtFWGqcLq6gCKgBGAs/s1600/IMG_20190106_125541.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1600" data-original-width="1507" height="400" src="https://4.bp.blogspot.com/-6BCIFxIkf3Y/XDHs1rBr_RI/AAAAAAACOqw/k1OIIGuaN4k1pLFv2P7Cm4WtFWGqcLq6gCKgBGAs/s400/IMG_20190106_125541.jpg" width="376" /></a></div>In <a href="https://petr-mitrichev.blogspot.com/2018/12/a-probably-prime-week.html">my previous summary</a>, I've mentioned a couple of problems. The <a href="https://atcoder.jp/contests/agc030/tasks/agc030_c">first one</a> came from AtCoder: you are given a number <i>k</i> which is at most 1000. You need to come up with any <i>n</i>x<i>n</i> toroidal grid (the first row is adjacent to the last row, and the first column is adjacent to the last column), where you choose the number <i>n</i> but it must be at most 500, such that each cell of the grid is colored with one of the <i>k</i> colors, each color is used at least once, and for all pairs of colors <i>i</i> and <i>j</i> all cells with color <i>i</i> must have the same number of neighbors with color <i>j</i>.<br /><br />During the round, I could only come up with approaches that produce a number of colors that is either smaller than <i>n</i>, or divisible by <i>n</i>. At some point I had an idea to write a backtracking solution that would find me any solution that does not have these properties, hoping that would help come up with its generalization. In retrospect, that might have done it, as the following approach (which seems to be the only one that works) does look recognizable from one example: let's pick an even <i>n</i>, and split the grid into <i>n</i> (toroidal) diagonals. For each diagonal, we either color it with one color, or with two alternating colors, thus making it possible to get any number of colors between <i>n</i> and 2<i>n</i>. Since each element of a diagonal has exactly two neighbors from each neighboring diagonal, the required properties hold.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-DWcam0BOwfA/XDHvAdvW6nI/AAAAAAACOrg/h0mBbc22z6sQB9kHjL4tSiIJEEglBfOKgCLcBGAs/s1600/IMG_20190101_125903.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1200" data-original-width="1600" height="480" src="https://4.bp.blogspot.com/-DWcam0BOwfA/XDHvAdvW6nI/AAAAAAACOrg/h0mBbc22z6sQB9kHjL4tSiIJEEglBfOKgCLcBGAs/s640/IMG_20190101_125903.jpg" width="640" /></a></div>The <a href="https://codeforces.com/contest/1091/problem/H">other problem</a> came from Codeforces. I've cited a simplified version of the statement: there is a pile with <i>n</i><=200000 stones, and two players are playing <a href="https://en.wikipedia.org/wiki/Nim">Nim</a> with a fixed set of possible moves <i>a</i><sub>1</sub>, <i>a</i><sub>2</sub>, ..., <i>a<sub>k</sub></i>: in each turn a player can take a number of stones that is equal to one of the <i>a<sub>i</sub></i>, and the player who can't make a move loses. Your goal is to find the <a href="https://en.wikipedia.org/wiki/Nimber">nimbers</a> for all values of <i>n</i> between 1 and 200000.<br /><br />I have forgot to mention one important additional property in this simplification: that the nimbers are guaranteed to be not too big (below 100), which is actually important for the solution below to be fast — sorry for that!<br /><br />Let's put all possible moves in one bitmask <i>m</i>, and also store a bitmask for each nimber value that represents which pile sizes have a move <i>to</i> a position with that nimber value. Those bitmasks start as empty. In order to determine the nimber for the next pile size, we go through those bitmasks until we find one that has a zero in the corresponding position. Then we need to update the bitmasks for higher pile sizes, and the key trick is that we only need to update one of them: the one corresponding to the newly determined nimber, and the update is simply applying bitwise or with the move bitmask <i>m</i> shifted left by the current pile size. This means that the solution runs in O(<i>n</i><sup>2</sup>/64+<i>n</i>*<i>max_nimber</i>) (I know, this is not a perfect use of the O-notation, but I hope you understand what I mean), which is fast enough.<br /><br />Thanks for reading, and check back next week!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/Q3Aw02QtiOU" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com8http://petr-mitrichev.blogspot.com/2019/01/a-radewoosh-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-51213542330639783992019-01-06T12:47:00.001+03:002019-01-06T12:47:16.042+03:00And the best problem of 2018 is...<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/-nRrE3L_gjjs/XDHOdw3o0YI/AAAAAAACOp8/B5XrWNHdioIYal9qDMKEhL17KZw9N8WhwCLcBGAs/s1600/IMG_20181208_153315%2B%25281%2529.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="984" data-original-width="1600" height="392" src="https://1.bp.blogspot.com/-nRrE3L_gjjs/XDHOdw3o0YI/AAAAAAACOp8/B5XrWNHdioIYal9qDMKEhL17KZw9N8WhwCLcBGAs/s640/IMG_20181208_153315%2B%25281%2529.jpg" width="640" /></a></div>According to <a href="https://petr-mitrichev.blogspot.com/2019/01/best-problems-of-2018.html">the vote</a>, the best problem of 2018 is <a href="https://drive.google.com/file/d/1yv_d9MYT5oeR8woWUdBs1N5GQa9Q8Aa2/view?usp=sharing">the Open Cup problem</a> about rolling a ball in a maze while collecting all targets in some order, by <a href="https://codeforces.com/profile/jh05013">jh05013</a>, with solution in <a href="https://petr-mitrichev.blogspot.com/2018/12/a-rolling-week.html">this post</a>. My vote also went to this problem.<br /><br />Here's its statement in an abridged form once again: you are given a 50x50 grid where some cells are empty, and some are walls. There are also walls surrounding the grid. Some empty cells are marked as targets, and there's also a ball in one of the empty cells. You can move the ball in each of the four cardinal directions, but once it starts rolling, it rolls in the same direction until it hits the wall, at which point you can pick a new direction, and so on. Can you roll the ball in such a way that it passes through all targets in some order?<br /><br />Congratulations to jh05013, to the Open Cup, and thanks to all problemsetters of 2018!<br /><br />More precisely, since there were only 91 people voting, I'd say we're about 60% confident that the best problem of 2018 is that one :) Here's <a href="https://colab.research.google.com/drive/1suQATpo3_5uYaJIoegttp7qjVYbWKLgm#scrollTo=iHt6M8jUeAMz">the Colab</a> where I try estimate that confidence. Of course that number is meaningless without explaining the assumed underlying model yada yada, but I hope it's good enough for a ballpark estimate. If people who actually, unlike myself, understand how statistics and polling work are reading this: is that a good way to get confidence numbers for a poll? What is a better way?<br /><br />Thanks for reading, and check back later today for this week's summary!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/_hZ3d8PemJA" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com6http://petr-mitrichev.blogspot.com/2019/01/and-best-problem-of-2018-is.htmltag:blogger.com,1999:blog-1953325079793449971.post-10932030889071531572019-01-02T12:22:00.000+03:002019-01-02T12:22:15.318+03:00Best problems of 2018<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/-MRTazCifeqU/XCyCcOIFnZI/AAAAAAACOe4/4f_ZvaG3ZQAXvcQzt7S_gKFNuzd4QDN2QCLcBGAs/s1600/IMG_20180623_122919.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" data-original-height="1200" data-original-width="1600" height="300" src="https://1.bp.blogspot.com/-MRTazCifeqU/XCyCcOIFnZI/AAAAAAACOe4/4f_ZvaG3ZQAXvcQzt7S_gKFNuzd4QDN2QCLcBGAs/s400/IMG_20180623_122919.jpg" width="400" /></a></div>Just like <a href="https://petr-mitrichev.blogspot.com/2017/12/best-problems-of-2017.html">last year</a>, I have reviewed the problems I've highlighted in this blog, and have picked the shortlist of five problems that I think were the best in 2018 (in chronological order):<br /><ul style="text-align: left;"><li><a href="https://agc023.contest.atcoder.jp/tasks/agc023_f">The AtCoder problem</a> about traversing the vertices of a 0/1-labeled tree minimizing the number of inversions, by <a href="https://codeforces.com/profile/maroonrk">maroonrk</a>, with solution in <a href="https://petr-mitrichev.blogspot.com/2018/05/a-prefix-xor-week.html">this post</a>.</li><li><a href="https://codeforces.com/contest/925/problem/C">The Codeforces problem</a> about rearranging an array in such a way that prefix xors are increasing, by <a href="https://codeforces.com/profile/Endagorion">Endagorion</a>, with solution in <a href="https://petr-mitrichev.blogspot.com/2018/05/a-prefix-xor-week.html">the same post</a>. </li><li><a href="https://agc026.contest.atcoder.jp/tasks/agc026_f">The AtCoder problem</a> about two players taking numbers from an array, where one must take adjacent number when available, by <a href="https://codeforces.com/profile/sugim48">sugim48</a>, with solution in <a href="https://petr-mitrichev.blogspot.com/2018/10/a-decision-tree-week.html">this post</a>.</li><li><a href="https://drive.google.com/file/d/1yv_d9MYT5oeR8woWUdBs1N5GQa9Q8Aa2/view?usp=sharing">The Open Cup problem</a> about rolling a ball in a maze while collecting all targets in some order, by <a href="https://codeforces.com/profile/jh05013">jh05013</a>, with solution in <a href="https://petr-mitrichev.blogspot.com/2018/12/a-rolling-week.html">this post</a>.</li><li><a href="https://community.topcoder.com/stat?c=problem_statement&pm=15159&rd=17348">The TopCoder problem</a> about creating a figure with exactly <i>n</i> domino tilings, by <a href="https://codeforces.com/profile/Alex_2oo8">Alex_2oo8</a>, with solution in <a href="https://petr-mitrichev.blogspot.com/2018/12/a-center-week.html">this post</a>.</li></ul>Which one do you think is the very best?<br /><div><br /></div><div><iframe frameborder="0" height="633" marginheight="0" marginwidth="0" src="https://docs.google.com/forms/d/e/1FAIpQLSc30po_IP9DVeBhse-yMQygb2h6Kil-PFdE_6Rx8K9Y6RItUg/viewform?embedded=true" width="640">Загрузка...</iframe></div><div><br /></div><div>There are other <a href="https://codeforces.com/blog/entry/64025">discussions</a> and <a href="https://codeforces.com/blog/entry/64186">votes</a> about the best problem of 2018, check those out :) In that second <a href="https://codeforces.com/blog/entry/64186">post</a>, snarknews is also announcing the Prime New Year contest, which consists of problems given at top-level team competitions in 2018 but not solved by anybody there. If you like real challenge and don't have much to do during the holidays, here's your <a href="https://contest.yandex.com/newyear2019/contest/11451/enter/">link</a>.<br /><div><div><br /></div><div>Happy New Year!</div></div></div></div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/B5mcLjbe0ic" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com0http://petr-mitrichev.blogspot.com/2019/01/best-problems-of-2018.htmltag:blogger.com,1999:blog-1953325079793449971.post-47373985870342108032018-12-30T21:39:00.000+03:002018-12-30T23:06:04.136+03:00A probably prime 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/-PRzEqN_F8tc/XCfPCg0xViI/AAAAAAACN3M/jkygrryL-8E70ZzaAPqv8fI3qQ8GZGWkgCLcBGAs/s1600/srm745top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="96" data-original-width="1057" height="58" src="https://2.bp.blogspot.com/-PRzEqN_F8tc/XCfPCg0xViI/AAAAAAACN3M/jkygrryL-8E70ZzaAPqv8fI3qQ8GZGWkgCLcBGAs/s640/srm745top5.png" width="640" /></a></div>This week had one contest from each of the major platforms to wrap up 2018. First off, TopCoder held an experimental SRM 745 on Friday (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=17392">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17392&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/64080?#comment-479298">analysis</a>). I did not participate myself, but I'd guess that solving 6 problems in 75 minutes felt a bit like <a href="http://snss2018.snarknews.info/">SnarkNews Winter/Summer Series</a>. The change of format did not stop Stonefeang from continuing his string of excellent results and winning this round. Well done!<br /><div><br /></div><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-mEQ5J96rC80/XCfRGTPWR5I/AAAAAAACN3Y/WPMzfxrZS-M2I_0XGdKWy9gUR9VbevifACLcBGAs/s1600/agc030top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="352" data-original-width="835" height="268" src="https://1.bp.blogspot.com/-mEQ5J96rC80/XCfRGTPWR5I/AAAAAAACN3Y/WPMzfxrZS-M2I_0XGdKWy9gUR9VbevifACLcBGAs/s640/agc030top5.png" width="640" /></a></div><div>AtCoder held its last contest of the year (and thus the last contest included in the onsite finals selection) on Saturday, the Grand Contest 030 (<a href="https://atcoder.jp/contests/agc030/tasks">problems</a>, <a href="https://atcoder.jp/contests/agc030/standings">results</a>, top 5 on the left, <a href="https://youtu.be/qRsyaYBmFeM">my screencast</a>, <a href="https://img.atcoder.jp/agc030/editorial.pdf">analysis</a>, <a href="https://docs.google.com/spreadsheets/d/1T-hKu_vIh8l4EiW6XTWOvP0evzsWj0f45JNNgou21Cc/edit#gid=695896678">onsite finals selection standings</a>, top 8 below on the right). Reading all problems really paid off in this round, as different contestants found different problems the hardest. For me problems B and C were the most difficult — in fact, I could not come up with a solution for any of them. It seems that the top two contestants cospleermusora and tourist had a similar story with problem C, but since it was worth less than problems E and F they ended up on top of the contestants with a different set of 5 problems solved. Congratulations to cospleermusora on the win!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-9_nur10wQJ4/XCfTnNGvq6I/AAAAAAACN3k/iBS0SmFd6aMjrKtLb2jZMy1_QDTYkYfjgCLcBGAs/s1600/atcoder2018top8.png" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" data-original-height="234" data-original-width="1338" height="110" src="https://2.bp.blogspot.com/-9_nur10wQJ4/XCfTnNGvq6I/AAAAAAACN3k/iBS0SmFd6aMjrKtLb2jZMy1_QDTYkYfjgCLcBGAs/s640/atcoder2018top8.png" width="640" /></a></div>Here is that <a href="https://atcoder.jp/contests/agc030/tasks/agc030_c">problem C</a> that was obvious for some and impossible to get for others: you are given a number <i>k</i> which is at most 1000. You need to come up with any <i>n</i>x<i>n</i> toroidal grid (the first row is adjacent to the last row, and the first column is adjacent to the last column), where you choose the number <i>n</i> but it must be at most 500, such that each cell of the grid is colored with one of the <i>k</i> colors, each color is used at least once, and for all pairs of colors <i>i</i> and <i>j</i> all cells with color <i>i</i> must have the same number of neighbors with color <i>j</i>. Can you see a way?<br /><br /><div class="separator" style="clear: both; text-align: center;"></div><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-hR9C-Wvdbt8/XCklIpDLAvI/AAAAAAACN9c/bLDihKFcyM8mmH3l9vMCfW4OsiLFEH79QCLcBGAs/s1600/cfgoodbye2018top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="273" data-original-width="1111" height="156" src="https://1.bp.blogspot.com/-hR9C-Wvdbt8/XCklIpDLAvI/AAAAAAACN9c/bLDihKFcyM8mmH3l9vMCfW4OsiLFEH79QCLcBGAs/s640/cfgoodbye2018top5.png" width="640" /></a></div>Codeforces held the Good Bye 2018 round on Sunday (<a href="https://codeforces.com/contest/1091">problems</a>, <a href="https://codeforces.com/contest/1091/standings">results</a>, top 5 on the left, <a href="https://youtu.be/KasLE9vzLaY">my screencast</a>, <a href="https://codeforces.com/blog/entry/64196">analysis</a>). tourist had one more great performance, going through the problems in order and finishing all of them more than 30 minutes faster than the only other contestant to solve everything, MakeRussiaGreatAgain. Congratulations to both!<br /><br />My round was going pretty well right up to the point when I <a href="https://crypto.stackexchange.com/questions/34061/factoring-large-n-given-oracle-to-find-square-roots-modulo-n">googled</a> the main idea of the solution for problem G, but then made a bug in the implementation (I forgot that the square roots are always returned modulo n, and not modulo the "remaining" number that I still need to factorize), and instead of looking for it I assumed there's a problem with BigInteger.isProbablePrime in Codeforces and tried to work around it for quite some time. I've found <a href="https://codeforces.com/blog/entry/14877">this post</a> with no answers and the post linked from it, and the fact that some of my submissions were getting "Denial of judgement" strongly supported the isProbablePrime failure theory.<br /><br /><a href="https://codeforces.com/contest/1091/problem/H">Problem H</a> had a pretty convoluted statement which boiled down to: there is a pile with <i>n</i><=200000 stones, and two players are playing <a href="https://en.wikipedia.org/wiki/Nim">Nim</a> with a fixed set of possible moves <i>a</i><sub>1</sub>, <i>a</i><sub>2</sub>, ..., <i>a<sub>k</sub></i>: in each turn a player can take a number of stones that is equal to one of the <i>a<sub>i</sub></i>, and the player who can't make a move loses. Your goal is to find the <a href="https://en.wikipedia.org/wiki/Nimber">nimbers</a> for all values of <i>n</i> between 1 and 200000.<br /><br />I've tried to solve this problem at the end of the contest, but my mental state after fighting with G for an hour was not ideal :) I realized that I needed to speed up the standard quadratic approach 64 times using bitsets, but could not find a good way to do that. Can you see a way?<br /><br />Thanks for reading, and check back [hopefully] tomorrow for my take on the best problems of 2018!</div></div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/XbGcdcPTNZU" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com0http://petr-mitrichev.blogspot.com/2018/12/a-probably-prime-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-72676656813418977902018-12-29T22:39:00.002+03:002018-12-29T22:39:53.485+03:00A wave 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/-9JUVjIDeiYg/XCe6tIvXYOI/AAAAAAACN10/Dfeq3n2XIOAI4ErFeoIph_m1RRT5zEjCgCLcBGAs/s1600/oc1819xiantop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="195" data-original-width="813" height="152" src="https://1.bp.blogspot.com/-9JUVjIDeiYg/XCe6tIvXYOI/AAAAAAACN10/Dfeq3n2XIOAI4ErFeoIph_m1RRT5zEjCgCLcBGAs/s640/oc1819xiantop5.png" width="640" /></a></div>The Dec 17 - Dec 23 week contained a surprise extra Open Cup round: Open Cup 2018-19 Grand Prix of Xi'An (<a href="http://opencup.ru/index.cgi?data=macros/stage&head=index&menu=index&stg=10&region=main&ncup=ocj&class=ocj">results</a>, top 5 on the left, <a href="http://acm.nwpu.edu.cn/Scoreboard.htm">official round results</a>, <a href="http://opencup.ru/index.cgi?data=macros/results&menu=index&head=index&ncup=ocj&class=ocj&region=main">overall Open Cup standings so far</a>). The Moscow SU team solved three problems in the last hour, including problem A which was solved by only three teams out of 150 attempts, and ended up winning by a problem. Congratulations on the great performance!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-PRuSj_3dLr4/XCe_CtHFPZI/AAAAAAACN2A/SFazE9oXDgwPed_tF0Uskh_o74YtvnYEgCLcBGAs/s1600/cf528top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="273" data-original-width="1106" height="156" src="https://1.bp.blogspot.com/-PRuSj_3dLr4/XCe_CtHFPZI/AAAAAAACN2A/SFazE9oXDgwPed_tF0Uskh_o74YtvnYEgCLcBGAs/s640/cf528top5.png" width="640" /></a></div>Codeforces Round 528 followed on Sunday evening (<a href="https://codeforces.com/contest/1086">problems</a>, <a href="https://codeforces.com/contest/1086/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/64078">analysis</a>). It was mnbvmar's turn to be the only contestant to solve the hardest problem F, and thus win with a huge margin. Congratulations on the victory!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-rzeBtqESbNQ/XCfMbgUupGI/AAAAAAACN2c/FcWIb6c2DmIbsbCeCq-0XiBi-67A4F3SwCKgBGAs/s1600/IMG_20181229_203412.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1033" data-original-width="1019" height="400" src="https://2.bp.blogspot.com/-rzeBtqESbNQ/XCfMbgUupGI/AAAAAAACN2c/FcWIb6c2DmIbsbCeCq-0XiBi-67A4F3SwCKgBGAs/s400/IMG_20181229_203412.jpg" width="393" /></a></div>In <a href="https://petr-mitrichev.blogspot.com/2018/12/a-kuhns-week.html">my previous summary</a>, I have mentioned several problems. <a href="https://community.topcoder.com/stat?c=problem_statement&pm=14587&rd=17373">The first one</a> came from TopCoder: you are given a rooted tree with 100000 vertices. Each vertex has a demand <i>d<sub>i</sub></i> and a cost <i>c<sub>i</sub></i>. Your goal is to assign some non-negative value <i>v<sub>i</sub></i> to each vertex so that the demand of each vertex is less than or equal to the sum of values on the path from this vertex to the root of the tree, and the sum of <i>c<sub>i</sub></i>*<i>v<sub>i</sub></i> is minimized.<br /><br />Let's look at the top-most vertices with non-zero value in the solution (such that all their parents and ancestors have zero value). Those vertices are not parents of one another, and thus they satisfy exactly one unit of demand of themselves and their descendants. If we now reduce their value by 1 and repeat, we can split into our solution into "waves" each wave satisfying one unit of demand in all remaining vertices with non-zero demand.<br /><br />We can also notice that each wave can be constructed as follows: first, start with a wave that contains only the root vertex. Then repeatedly do the following: take any vertex with zero demand that is in the wave, remove it from the wave but add all its children. Each such operation changes the cost of the wave by the sum of costs of the children minus the cost of the removed vertex. Let's call this value the <i>delta</i> of the removed vertex.<br /><br />Now we'll build the waves one by one while always maintaining the minimum cost wave. Initially such wave is just a root vertex. As soon as the number of waves we've built reaches the demand of a vertex, this vertex becomes available for replacement, which would change the weight of the wave by its delta. If the delta is positive, we don't need to do anything. If the delta is negative, and the vertex is in the minimum cost wave, then we need to do the replacement. If the delta is negative but the vertex is not yet in the minimum cost wave, we will need to do its replacement as soon as it gets into the wave, in other word we should add its delta to the delta of its parent. If the delta of the parent becomes negative, then we propagate it to its parent, and so on, so that at every moment we have only the optimal wave plus some non-negative deltas remaining.<br /><br />In order for this to run fast, we need to directly propagate to the closest non-zero ancestor instead of going through all parents in the chain to it, which can be accomplished by keeping a disjoint-set union data structure where each set has a vertex with non-zero delta as its representative, and contains all vertices with zero deltas which have it as the closest non-zero ancestor.<br /><br />This was quite tricky to come up with, but the implementation was rather simple and without any corner cases or data structures more complex than disjoint-set union.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-PJXyeUg79dw/XCfMfi9ffdI/AAAAAAACN2g/tiAdyiBwaR4QNuJmp-y1pWtBvLbKyvxpACKgBGAs/s1600/IMG_20181229_203406.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="818" data-original-width="941" height="347" src="https://3.bp.blogspot.com/-PJXyeUg79dw/XCfMfi9ffdI/AAAAAAACN2g/tiAdyiBwaR4QNuJmp-y1pWtBvLbKyvxpACKgBGAs/s400/IMG_20181229_203406.jpg" width="400" /></a></div><a href="https://atcoder.jp/contests/agc029/tasks/agc029_f">The second problem</a> I mentioned came from AtCoder: you are given <i>n</i> vertices, and <i>n</i>-1 sets of those vertices, each of size at least 2. Your goal is to pick exactly two vertices in each of the <i>n</i>-1 sets in such a way that if we draw the <i>n</i>-1 edges connecting each chosen pair to each other, we get a tree. <i>n</i> is at most 100000, and the total size of the given sets is at most 200000.<br /><br />The first step is to think when is this actually impossible. The sample cases provided a helpful example: there was a case where there were two vertices that belonged to just one set, and moreover to the same set. Since only one edge will come out of this set, we will not be able to connect both of those vertices to the rest of the graph.<br /><br />This obstacle can be generalized as follows: if there's a set of vertices of size <i>k</i> which is less than <i>n</i> such that the number of input sets containing at least one of those vertices is less than <i>k</i>, there's no solution.<br /><br />But wait, we <a href="https://en.wikipedia.org/wiki/Hall%27s_marriage_theorem#Graph_theoretic_formulation">have seen</a> such obstacles before! Consider the bipartite graph where the left part is the input vertices and the right part is the input sets, with edges connecting each set with its members. If there's no obstacle as described above, then by Hall's theorem in this graph there's a matching covering any (<i>n</i>-1)-element subset of the left part.<br /><br />Let's find any such matching, it covers some (<i>n</i>-1)-element subset of vertices. The fact that all other (<i>n</i>-1)-element subsets can also be covered by a matching means that if we run one more step of the maximum matching algorithm, it must find augmenting paths from the only remaining uncovered vertex to all covered vertices (so that flipping this augmenting path would result in the solution for the corresponding (<i>n</i>-1)-element subset). These augmenting paths form a subtree of the residual network.<br /><br />Now we can see that if we take any vertex covered by matching, its previous vertex in the augmenting path tree (which will be in the right part, so represent a set), and the set's previous vertex in the augmenting path tree (which will be in the left part, so represent a vertex), then we get two vertices belonging to the corresponding set, and those <i>n</i>-1 pairs are exactly the solution to our problem as they necessarily form a tree!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-r6KmCDrSPEY/XCfNRma-WgI/AAAAAAACN2w/OdUOJbf36DguotqoaFPbqiVctgH1zc8ngCLcBGAs/s1600/IMG_20181124_161730.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="879" data-original-width="1600" height="350" src="https://3.bp.blogspot.com/-r6KmCDrSPEY/XCfNRma-WgI/AAAAAAACN2w/OdUOJbf36DguotqoaFPbqiVctgH1zc8ngCLcBGAs/s640/IMG_20181124_161730.jpg" width="640" /></a></div>Finally, there was an Open Cup problem: two players are playing a game on a rooted tree with 100000 vertices. They make moves in turn. In each move of the first player, she colors one of the leaves of the tree black (initially all leaves are colored white). The root of the tree also initially contains a token. In each move of the second player, she can move the token from a vertex to any adjacent vertex. The second player wins if she moves the token to a leaf that is still white. The first player wins when all leaves are colored black and the second player has not yet won. Who will win if both players play optimally?<br /><br />First, we can notice that it doesn't make sense for the second player to go up, as they will end up in a strictly worse state than before. So for each subtree, there's at most one moment in the game when the token enters this subtree, and then the game continues just in this subtree.<br /><br />Moreover, suppose that the first player has made <i>x</i> moves into this subtree before the token enters it. Then it's clear that there's some boundary <i>b</i> such that when <i>x</i><<i>b</i> the second player wins if the token enters this subtree, and when <i>x</i>>=<i>b </i>the first player wins if the token enters this subtree. This finally gives us a linear-time dynamic programming solution: we will compute this boundary <i>b</i> for each subtree going from the bottom to the top.<br /><br />Thanks for reading, and check back tomorrow!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/hfCJCuvWWoE" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com3http://petr-mitrichev.blogspot.com/2018/12/a-wave-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-35698926208857489442018-12-29T21:06:00.000+03:002018-12-29T21:06:17.929+03:00A Kuhn's 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/-Occ7KdeJUtE/XCdTTK0cK7I/AAAAAAACN0o/PuHgi0t0AAUaItlAX6Q1bJi0ov5Sk6ZZQCLcBGAs/s1600/cf526top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="279" data-original-width="1102" height="162" src="https://2.bp.blogspot.com/-Occ7KdeJUtE/XCdTTK0cK7I/AAAAAAACN0o/PuHgi0t0AAUaItlAX6Q1bJi0ov5Sk6ZZQCLcBGAs/s640/cf526top5.png" width="640" /></a></div>The Dec 10 - Dec 16 week was livelier than a few previous ones. Codeforces Round 526 started the fun right on Monday (<a href="https://codeforces.com/contest/1083">problems</a>, <a href="https://codeforces.com/contest/1083/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/63753?locale=en">analysis</a>). Radewoosh continued his string of excellent results, was the only contestant to solve five problems, got the first place with a huge margin and also overtook tourist for the first place in the <a href="https://codeforces.com/ratings">rating list</a> — very well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-kjT162xDM8o/XCdWo1n7PWI/AAAAAAACN04/HBVgfXsVldABnu782QNK90snWKLCbrHewCLcBGAs/s1600/srm744top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="146" data-original-width="780" height="118" src="https://2.bp.blogspot.com/-kjT162xDM8o/XCdWo1n7PWI/AAAAAAACN04/HBVgfXsVldABnu782QNK90snWKLCbrHewCLcBGAs/s640/srm744top5.png" width="640" /></a></div>TopCoder SRM 744 took place on Friday (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=17373">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17373&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://youtu.be/Cn3JWz_ocPY">my screencast</a>, <a href="https://www.topcoder.com/blog/single-round-match-744-editorials/">analysis</a>). Trying to learn from <a href="https://petr-mitrichev.blogspot.com/2018/12/when-it-should-have-returned-30.html">my experience</a> in the TCO final, when approaching the hard problem I have decided to not implement relatively straightforward solutions involving either heavy-light decomposition or propagating piecewise-linear functions up the tree, but instead think a bit more to come up with an easier to implement solution. The strategy has almost backfired as I got my "simple" solution to work with less than two minutes into the contest. However, it did work in the end as a few other contestants going for the straightforward but complicated implementation approaches have failed because of subtle bugs (for example, ainta was above me after the coding phase but his solution failed as he should've used a multiset instead of a set, presumably inside the representation of a piecewise-linear function or something similar).<br /><br />Here's <a href="https://community.topcoder.com/stat?c=problem_statement&pm=14587&rd=17373">that problem</a>: you are given a rooted tree with 100000 vertices. Each vertex has a demand <i>d<sub>i</sub></i> and a cost <i>c<sub>i</sub></i>. Your goal is to assign some non-negative value <i>v<sub>i</sub></i> to each vertex so that the demand of each vertex is less than or equal to the sum of values on the path from this vertex to the root of the tree, and the sum of <i>c<sub>i</sub></i>*<i>v<sub>i</sub></i> is minimized. What's the easiest to implement approach, in your opinion?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-G2qleo2NfMI/XCesOUu3z6I/AAAAAAACN1Q/4PTwj2eOgnAdLZBT3RyxfqrAVTZMeOwTQCLcBGAs/s1600/agc029top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="352" data-original-width="836" height="268" src="https://2.bp.blogspot.com/-G2qleo2NfMI/XCesOUu3z6I/AAAAAAACN1Q/4PTwj2eOgnAdLZBT3RyxfqrAVTZMeOwTQCLcBGAs/s640/agc029top5.png" width="640" /></a></div>AtCoder Grand Contest 029 followed on Saturday (<a href="https://atcoder.jp/contests/agc029/tasks">problems</a>, <a href="https://atcoder.jp/contests/agc029/standings">results</a>, top 5 on the left, <a href="https://youtu.be/02VV330Avc8">my screencast with commentary</a>, <a href="https://img.atcoder.jp/agc029/editorial.pdf">analysis</a>). The problemset was relatively approachable this time, so to win one had to be fast and to minimize incorrect attempts. LHiC executed very well on both fronts and got first place with the margin of 12 penalty minutes. Well done!<br /><br />I was submitting my last problem around 88-th minute for the first time, but <a href="https://atcoder.jp/contests/agc029/submissions/3799908">got time limit exceeded</a> on just one testcase. My solution involved Dinic's maximum flow algorithm that I have copy-pasted from a previous solution. Later I <a href="https://atcoder.jp/contests/agc029/submissions/3801131">submitted</a> the same solution in C++ and it passed in just 0.5s, while the time limit is 4s. Maybe somebody can tell why Java is more than 8x slower this time?<br /><br />Of course, later I tried submitting Kuhn's maximum matching algorithm in Java instead, which is supposed to be quadratic in the worst case, but it actually passed within the time limit :)<br /><br />Reducing the problem to maximum matching is also quite fun. Here's <a href="https://atcoder.jp/contests/agc029/tasks/agc029_f">the statement</a>: you are given <i>n</i> vertices, and <i>n</i>-1 sets of those vertices, each of size at least 2. Your goal is to pick exactly two vertices in each of the <i>n</i>-1 sets in such a way that if we draw the <i>n</i>-1 edges connecting each chosen pair to each other, we get a tree. <i>n</i> is at most 100000, and the total size of the given sets is at most 200000.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/--8Gfw47N4tA/XCezQ-LrzxI/AAAAAAACN1c/pkQs6_eo60Mz3ITTd6evrcPt040lmkZIACLcBGAs/s1600/oc1819peterhoftop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="211" data-original-width="745" height="180" src="https://3.bp.blogspot.com/--8Gfw47N4tA/XCezQ-LrzxI/AAAAAAACN1c/pkQs6_eo60Mz3ITTd6evrcPt040lmkZIACLcBGAs/s640/oc1819peterhoftop5.png" width="640" /></a></div>Open Cup 2018-19 Grand Prix of Peterhof took place on Sunday (<a href="http://opencup.ru/index.cgi?data=macros/stage&head=index&menu=index&stg=9&region=main&ncup=ocj&class=ocj">results</a>, top 5 on the left). Compared to a few previous rounds, the Moscow SU team has cut down dramatically on incorrect attempts, and thus got their first win of the season. Congratulations!<br /><br />Problem G was a nice dynamic programming exercise. Two players are playing a game on a rooted tree with 100000 vertices. They make moves in turn. In each move of the first player, she colors one of the leaves of the tree black (initially all leaves are colored white). The root of the tree also initially contains a token. In each move of the second player, she can move the token from a vertex to any adjacent vertex. The second player wins if she moves the token to a leaf that is still white. The first player wins when all leaves are colored black and the second player has not yet won. Who will win if both players play optimally? Can you see a way to avoid traversing the entire ~2<sup>100000</sup> state space?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-ClToLlv9r2Q/XCe2yLj--XI/AAAAAAACN1o/BhefW2-HbG4rdk4dcV6u50-9ujbIwe8zQCLcBGAs/s1600/avitocool2018top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="271" data-original-width="1107" height="156" src="https://4.bp.blogspot.com/-ClToLlv9r2Q/XCe2yLj--XI/AAAAAAACN1o/BhefW2-HbG4rdk4dcV6u50-9ujbIwe8zQCLcBGAs/s640/avitocool2018top5.png" width="640" /></a></div>Finally, Codeforces ran Avito Cool Challenge 2018 later on Sunday (<a href="https://codeforces.com/contest/1081">problems</a>, <a href="https://codeforces.com/contest/1081/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/63888">analysis</a>). tourist was a bit slower than LHiC but was able to find two challenges and regain the first place in the round, and with it the first place in <a href="https://codeforces.com/ratings">the rating list</a>. Congratulations!<br /><br />Thanks for reading, and check back for more!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/AWW6NvL_ZVM" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com1http://petr-mitrichev.blogspot.com/2018/12/a-kuhns-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-49604325491289285122018-12-29T13:51:00.001+03:002018-12-29T13:51:48.906+03:00A lazy 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/-rBmdUSs58nk/XCdNZspKGpI/AAAAAAACN0c/y-KI-uAysK4zVPqm7AjkLJg3ZoS9XtZQgCLcBGAs/s1600/srm743top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="148" data-original-width="781" height="120" src="https://2.bp.blogspot.com/-rBmdUSs58nk/XCdNZspKGpI/AAAAAAACN0c/y-KI-uAysK4zVPqm7AjkLJg3ZoS9XtZQgCLcBGAs/s640/srm743top5.png" width="640" /></a></div>The Dec 3 - Dec 9 week featured TopCoder SRM 743 (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=17370">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17370&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://youtu.be/bAz3gdwEPyc">my screencast</a>, <a href="https://www.topcoder.com/blog/single-round-match-743-editorials/">analysis</a>). Stonefeang was quite close to increasing his lead in <a href="https://tco19.topcoder.com/home/algorithm/algorithm-leaderboard">the overall standings</a> as he was temporarily in first place during the challenge phase after finding a successful challenge. However, ksun48 then found a successful challenge of his own, regained his first place from the coding phase, and joined Stonefeang at the top of the overall leaderboard. Congratulations!<br /><br />Thanks for reading (was this the shortest post of the year?) and check back for more!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/726r3K4jfdI" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com0http://petr-mitrichev.blogspot.com/2018/12/a-lazy-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-86058028606857761342018-12-29T13:21:00.001+03:002018-12-29T13:21:34.216+03:00A colorful 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/-Fd7uYIask3o/XCdHzIW7OLI/AAAAAAACN0E/vsZYtNt1sTAnPvnIJBBR9SG3ylvb5q2aQCLcBGAs/s1600/srm742top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="148" data-original-width="781" height="121" src="https://2.bp.blogspot.com/-Fd7uYIask3o/XCdHzIW7OLI/AAAAAAACN0E/vsZYtNt1sTAnPvnIJBBR9SG3ylvb5q2aQCLcBGAs/s640/srm742top5.png" width="640" /></a></div>TopCoder SRM 742 was the first event of the Nov 26 - Dec 2 week (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=17354">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17354&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://www.topcoder.com/blog/single-round-match-742-editorials/">analysis</a>). This was the first round of a new three-month race to a TCO19 onsite spot, and Stonefeang got the best possible start to this race thanks to having the fastest time on two out of three problems. Congratulations!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-A9qwzGSP_cE/XCdJTX1N5vI/AAAAAAACN0Q/ywaO9On5MPokOrmQiW05kEUQl0JC2nYegCLcBGAs/s1600/neerc2018top12.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="585" data-original-width="1298" height="288" src="https://4.bp.blogspot.com/-A9qwzGSP_cE/XCdJTX1N5vI/AAAAAAACN0Q/ywaO9On5MPokOrmQiW05kEUQl0JC2nYegCLcBGAs/s640/neerc2018top12.png" width="640" /></a></div>NEERC 2018, now known as Northern Eurasia Programming Contest 2018, was the main event of the week in Russia and some neighboring countries (<a href="http://neerc.ifmo.ru/archive/2018/neerc-2018-statement.pdf">problems</a>, <a href="http://neerc.ifmo.ru/archive/2018/standings.html">results</a>, top 12 on the left, <a href="https://codeforces.com/contest/1089/standings">parallel round results</a>, <a href="http://neerc.ifmo.ru/archive/2018/neerc-2018-analysis.pdf">analysis</a>). The world champions from the Moscow SU were trailing during most of the contest, sometimes by more than one problem, but pulled themselves together in the end and still won the contest thanks to being the only team to solve problem H. Congratulations on the great comeback!<br /><br />The performance of the team White Sprite in the parallel round shows that there is still a lot of room for improvement for the Russian teams, though :)<br /><br />Thanks for reading, and check back for more!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/a6T822ARjg8" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com0http://petr-mitrichev.blogspot.com/2018/12/a-colorful-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-1449250038553801392018-12-29T13:04:00.000+03:002018-12-29T13:04:04.733+03:00A center 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/-73awOZ-wR18/XCc1Z_5xKhI/AAAAAAACNys/i4IqGZC33u4a7RleLOi9GppF_M5HADQ4ACLcBGAs/s1600/oc1819dolgoprudnytop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="204" data-original-width="692" height="188" src="https://4.bp.blogspot.com/-73awOZ-wR18/XCc1Z_5xKhI/AAAAAAACNys/i4IqGZC33u4a7RleLOi9GppF_M5HADQ4ACLcBGAs/s640/oc1819dolgoprudnytop5.png" width="640" /></a></div>The Nov 19 - Nov 25 week had its contests on Sunday, the first one being Open Cup 2018-19 Grand Prix of Dolgoprudny (<a href="http://opencup.ru/index.cgi?data=macros/stage&head=index&menu=index&stg=8&region=main&ncup=ocj&class=ocj">results</a>, top 5 on the left). For the third time in the last four Open Cup rounds, the team Past Glory was first and the team Moscow SU: Red Santa was second, with quite a huge gap stemming from the large amount of incorrect attempts for the Red Santa. Congratulations to both teams on yet another strong performance!<br /><div><br /></div><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-LtQgJ08K98E/XCc32bwmv1I/AAAAAAACNy4/oafD6hmRa_c7uewco-bDMzoijgie7-dOQCLcBGAs/s1600/mail2018r3top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="270" data-original-width="1105" height="156" src="https://3.bp.blogspot.com/-LtQgJ08K98E/XCc32bwmv1I/AAAAAAACNy4/oafD6hmRa_c7uewco-bDMzoijgie7-dOQCLcBGAs/s640/mail2018r3top5.png" width="640" /></a></div><div>Codeforces hosted Mail.Ru Cup 2018 Round 3 later that day (<a href="https://codeforces.com/contest/1056">problems</a>, <a href="https://codeforces.com/contest/1056/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/63462">overall results</a>, <a href="https://codeforces.com/blog/entry/63461">analysis</a>). Radewoosh continued his fine recent form, solving all problems with 15 minutes to spare and with just two incorrect attempts, compared to V--o_o--V's nine. Congratulations on the win!</div><div><br /></div><div><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-E6Rz9g0xGUM/XCdFIkBUvqI/AAAAAAACNzI/hLGzDo_4zZIcaGBG_KsWKI0TLJ748vpkQCLcBGAs/s1600/IMG_20181110_165857.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1200" data-original-width="1600" height="480" src="https://3.bp.blogspot.com/-E6Rz9g0xGUM/XCdFIkBUvqI/AAAAAAACNzI/hLGzDo_4zZIcaGBG_KsWKI0TLJ748vpkQCLcBGAs/s640/IMG_20181110_165857.jpg" width="640" /></a></div>In <a href="https://petr-mitrichev.blogspot.com/2018/12/a-2015-week.html">my previous summary</a>, I have mentioned two TCO onsite problems. <a href="https://community.topcoder.com/stat?c=problem_statement&pm=15159&rd=17348">The first one</a> was constructive: you are given an integer <i>n</i> up to 10<sup>18</sup>. You need to return any 4-connected figure which has exactly <i>n</i> different domino tilings, and which fits into a relatively small bounding box: the area of the bounding box must not exceed 14400, and the height of the bounding box must not exceed 13.<br /><br />It's very easy to build multiplication: given two figures with <i>a</i> and <i>b</i> tilings respectively we can build a figure with <i>a</i>*<i>b</i> tilings by concatenating them possibly with a small insertion in the middle so that no new spurious tilings appear.<br /><br />However, in order to build arbitrary numbers we usually need both multiplication and addition, and addition is where the main difficulty lies: since the number of domino tilings is a "global" object, it's not clear how we could achieve "either <i>a</i> or <i>b</i>" behavior.<br /><br /><a href="https://www.topcoder.com/blog/tco-semifinals-1-editorial/">The official analysis</a> shows two great ways to achieve addition, based on the idea that we can build figures that have only one tiling with one "parity" and lots of tilings with other "parity". Please look there for more details (the problem name is "DominoTiling").<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-IRDk0xbPXak/XCdFNg6IqRI/AAAAAAACNzM/Yvb1YUbwQ0ckoErIuugS5dnhcGeJw-VbACLcBGAs/s1600/IMG_20181111_114402.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="505" data-original-width="1600" height="202" src="https://2.bp.blogspot.com/-IRDk0xbPXak/XCdFNg6IqRI/AAAAAAACNzM/Yvb1YUbwQ0ckoErIuugS5dnhcGeJw-VbACLcBGAs/s640/IMG_20181111_114402.jpg" width="640" /></a></div><a href="https://community.topcoder.com/stat?c=problem_statement&pm=15151&rd=17351">The second problem</a> I mentioned was of the more traditional optimization style: you are given <i>n</i><=200 points on the plane. You need to connect some pairs of points with straight line edges, so that you build exactly <i>n</i>-1 edge and the result forms a tree. What is the minimum possible <i>diameter</i> of the resulting tree (the maximum distance between its vertices, were the length of each edge is equal to the corresponding Euclidean distance)?<br /><br />Solving this problem required a good understanding of how distances in trees work. More specifically, if we take any diameter of a tree, and find its middle point (which might be a vertex and might be in the middle of an edge), this point will be the <i>center</i> of the tree: all vertices of the tree will be at a distance of at most <i>d</i>/2 from it (where <i>d</i> is the diameter). Moreover, the opposite is also true: if there's a point in the tree such that all vertices are at a distance of at most <i>d</i>/2 from it, then the diameter of the tree is at most <i>d</i>. The important aspect here is that we don't have to consider the distances between pairs of vertices anymore — all that matters are the distances to the center.<br /><br />Suppose the center lies in the middle of the edge connecting vertices <i>u</i> and <i>v</i>. Then for the part of the tree containing <i>u</i> the distances to the center are going through <i>u</i>. Then we can notice that because Euclidean distance satisfies the triangle inequality, if we rearrange that part of the tree to have all other vertices connected directly to <i>u</i>, the distances to the center will not increase, which means that the diameter will not increase, too.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-zvJirK7Hkng/XCdGSVt7DdI/AAAAAAACNzs/N-r75xK_RB0AtqP5h0PxHX7ZfYiFGVrhACKgBGAs/s1600/IMG_20181229_110204.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" data-original-height="1007" data-original-width="1600" height="251" src="https://1.bp.blogspot.com/-zvJirK7Hkng/XCdGSVt7DdI/AAAAAAACNzs/N-r75xK_RB0AtqP5h0PxHX7ZfYiFGVrhACKgBGAs/s400/IMG_20181229_110204.jpg" width="400" /></a></div>In other words, we can assume that the optimal tree always looks like an edge <i>u</i>-<i>v</i>, and all other vertices are connected to either <i>u</i> or <i>v</i>.<br /><br />Moreover, we can see from the above argument that all that matters in the optimal tree is the maximum distance from <i>u</i> to a vertex connected to it, and the maximum distance from <i>v</i> to a vertex connected to it, and thus when deciding whether to connect each other vertex to <i>u</i> or <i>v</i> we just need to think about those two numbers. For example, suppose that <i>w</i> is the vertex farthest from <i>u</i> that is connected to <i>u</i>. Then we can connect to <i>u</i> all vertices that are closer to <i>u</i> than <i>w</i> without increasing the diameter, so the set of vertices connected to <i>u</i> will be a prefix of all vertices sorted by distance to <i>u</i> (during the contest I've sorted by the difference of distances to <i>u</i> and <i>v</i>, which also works).<br /><br />This allows an O(<i>n</i><sup>3</sup>) solution: try all possibilities for <i>u</i> and <i>v</i>, all prefixes of the list vertices sorted by distance to <i>u</i>. Connect the vertices from the prefix to <i>u</i> and the rest to <i>v</i>, and find the minimum diameter of all trees built in this way.<br /><br />Note that we still need to find the diameters of those trees properly, as we're not guaranteed that the center will be on the <i>u</i>-<i>v</i> edge for any such tree, and finding the diameter properly requires finding the maximum and second maximum edge connected to each of <i>u</i> and <i>v</i>, which can be done by computing prefix and suffix maximums and second maximums.<br /><br />The "second maximum" part can be avoided if we remember that we don't really care about the cases where the center is on the <i>u</i>-<i>v</i> edge — we just need to make sure that those cases don't incorrectly get a too small diameter computed. For example, Kevin does in fact check in his solution if the diameter is on the <i>u</i>-<i>v</i> edge and throws away the tree if it's not; however, since the distances are floating-point we might get rounding issues here if the optimal center is in fact a vertex, so he had to handle that by adding an epsilon to the comparison. Gennady, on the other hand, just computes the diameter in pessimistic fashion for such trees: if the center ends up being outside the <i>u</i>-<i>v</i> edge, we compute the diameter as 2 times the maximum distance from <i>u</i> and <i>v</i> to other vertices. This will never be less than the actual diameter, and for the cases where the center is <i>u</i> or <i>v</i> this will be equal to it, just as we need.<br /><br />Thanks for reading, and check back for more!</div></div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/mv_5YQfH6uA" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com0http://petr-mitrichev.blogspot.com/2018/12/a-center-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-62175916390227302022018-12-28T23:54:00.000+03:002018-12-28T23:54:06.638+03:00A 2015 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/-kMqujLM9ZT0/XCZ88YuViwI/AAAAAAACNxU/kFcsR_Z6SUMYl4m_Q43vpPqwuBsqGOfZACLcBGAs/s1600/tco18semi1top8.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="216" data-original-width="785" height="176" src="https://4.bp.blogspot.com/-kMqujLM9ZT0/XCZ88YuViwI/AAAAAAACNxU/kFcsR_Z6SUMYl4m_Q43vpPqwuBsqGOfZACLcBGAs/s640/tco18semi1top8.png" width="640" /></a></div>TopCoder Open 2018 onsite event in Dallas was headlining the Nov 12 - Nov 18 week. The first semifinal took place earlier on Thursday (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=17348">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17348&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a> on the left, <a href="https://www.facebook.com/topcoder/videos/1950057318396864/">broadcast</a>, <a href="https://www.topcoder.com/blog/tco-semifinals-1-editorial/">analysis</a>). tourist ended up dominating the proceedings by solving the 1000-pointer in just 15 minutes, but of course the main goal in this round was getting into the top 4. There was quite some drama involved as Egor ended up fifth after resubmitting his solution for the 250-pointer because the original solution could not handle exactly one case correctly: 1x1 grid. Congratulations to tourist, Errichto, Um_nik and ACRush on advancing to the final!<br /><br />The <a href="https://community.topcoder.com/stat?c=problem_statement&pm=15159&rd=17348">medium problem</a> in this round was a great combination of simple statement and exciting problem solving, while still being medium difficulty: you are given an integer <i>n</i> up to 10<sup>18</sup>. You need to return any 4-connected figure which has exactly <i>n</i> different domino tilings, and which fits into a relatively small bounding box: the area of the bounding box must not exceed 14400, and the height of the bounding box must not exceed 13 (I guess this second condition was required to make it possible to check the output for correctness in reasonable time). Can you see a way?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-sY-6PzarXPg/XCaAAKKEd8I/AAAAAAACNxk/_UQpREwvrA4yy5eosqTWCyfvSsVhcjjWgCLcBGAs/s1600/tco18semi2top8.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="216" data-original-width="774" height="178" src="https://3.bp.blogspot.com/-sY-6PzarXPg/XCaAAKKEd8I/AAAAAAACNxk/_UQpREwvrA4yy5eosqTWCyfvSsVhcjjWgCLcBGAs/s640/tco18semi2top8.png" width="640" /></a></div>Semifinal 2 followed very late on Thursday (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=17350">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17350&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a> on the left, <a href="https://www.facebook.com/topcoder/videos/264309227607284/">broadcast</a>, <a href="https://youtu.be/9jVDhtCatH8">my screencast</a>, <a href="https://www.topcoder.com/blog/tco-semifinals-2-editorial/">analysis</a>). Before the semifinal rounds I was telling other contestants that I expect that a fast 250 should be mostly enough to get to 4 out of 8, as you can expect some people to fail the system tests and ending up above them is enough with such generous advancement rules. Well, apparently I had to support my theory by example this time :) You can see from the screencast that I knew that my medium solution was incorrect, but I could not fix it (it turned out that the approach is probably impossible to get to work), and there was just too much implementation involved in the hard problem. During the challenge phase I was very happy when my medium was challenged because the challenger was not Kankuro, and thus I was still solidly in top 4.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-PAgLC4Tfofk/XCaB0V2W46I/AAAAAAACNxw/4MEmnei2ohIHGFEvR15l7WyaG3suZFGZQCLcBGAs/s1600/tco18finaltop8.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="219" data-original-width="783" height="178" src="https://1.bp.blogspot.com/-PAgLC4Tfofk/XCaB0V2W46I/AAAAAAACNxw/4MEmnei2ohIHGFEvR15l7WyaG3suZFGZQCLcBGAs/s640/tco18finaltop8.png" width="640" /></a></div>The final round took place one day later, on Friday (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=17351">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17351&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a> on the left, <a href="https://www.facebook.com/topcoder/videos/772228229777309/">broadcast</a>, <a href="https://youtu.be/OB-uSW9uOlQ">my screencast</a>, <a href="https://www.topcoder.com/blog/tco-algorithm-final-editorial/">analysis</a>). There were a couple of important decisions that shaped this round for me.<br /><br />First, I've decided to implement a quite tedious solution for the easy problem (which <a href="https://petr-mitrichev.blogspot.com/2018/12/when-it-should-have-returned-30.html">was actually incorrect</a> but not caught by system tests). That led to the situation where after submitting the easy I was quite a bit behind, and seeing as the leader tourist has opened the medium problem after solving easy, it felt that going for the hard would increase my chances for the first place.<br /><br />Then I was actually able to solve the hard problem quite quickly thanks to coming up almost immediately with the key solution idea: that diagonals can be handled independently. This might've been helped by the fact that I have seen this idea before, and in a very similar setting: my <a href="https://petr-mitrichev.blogspot.com/2015/11/a-8-connected-day.html">previous TopCoder Open victory in 2015</a> had <a href="https://community.topcoder.com/stat?c=problem_statement&pm=14044">medium problem</a> with the reference solution using exactly this idea (I did not come up with this idea in 2015, so you can't say that one idea got me two wins, but still the parallels are amusing).<br /><br />Then I've tried to solve the medium problem, had some good ideas but could not make the solution work, and had almost given up — but then Kevin has submitted his medium with about 9 minutes to go and overtook me in the standings. This was apparently just the extra bit of motivation I needed, as I've then resumed my attempts at solving the medium and managed to submit it with just about 50 seconds remaining in the coding phase! Once again some remarkable parallels to <a href="https://petr-mitrichev.blogspot.com/2015/11/a-8-connected-day.html">the situation three years ago</a> :)<br /><br />Here's <a href="https://community.topcoder.com/stat?c=problem_statement&pm=15151&rd=17351">the medium problem</a> that caused all this excitement: you are given <i>n</i><=200 points on the plane. You need to connect some pairs of points with straight line edges, so that you build exactly <i>n</i>-1 edge and the result forms a tree. What is the minimum possible <i>diameter</i> of the resulting tree (the maximum distance between its vertices, were the length of each edge is equal to the corresponding Euclidean distance)?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-BtVWVz1PxWE/XCaH4l9IsVI/AAAAAAACNx8/tQbkllyMyaMy6YgzjehH6jd5d3wSCCGSwCLcBGAs/s1600/oc1819siberiatop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="216" data-original-width="771" height="178" src="https://2.bp.blogspot.com/-BtVWVz1PxWE/XCaH4l9IsVI/AAAAAAACNx8/tQbkllyMyaMy6YgzjehH6jd5d3wSCCGSwCLcBGAs/s640/oc1819siberiatop5.png" width="640" /></a></div>After the dust from the TCO finals had settled a bit, Open Cup Grand Prix of Siberia took place on Sunday (<a href="http://opencup.ru/index.cgi?data=macros/stage&head=index&menu=index&stg=7&region=main&ncup=ocj&class=ocj">results</a>, top 5 on the left). Both the team Past Glory and the ICPC world champion team from Moscow SU were able to solve 11 problems, but with 13 penalty attempts against 3 and corresponding debugging time the Moscow team had almost 50% higher penalty time. Congratulations to the team Past Glory on the victory!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/-m3m64qe5so" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com0http://petr-mitrichev.blogspot.com/2018/12/a-2015-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-85048924647196325492018-12-28T13:04:00.002+03:002018-12-28T13:04:29.556+03:00A -17 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/-PH1LdUi7w7Y/XCXcTC7OcNI/AAAAAAACNp4/OzEEACLl84sRMrgcgMs-lsKlWC7c8OvHQCLcBGAs/s1600/mail2018r2top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="273" data-original-width="1107" height="156" src="https://3.bp.blogspot.com/-PH1LdUi7w7Y/XCXcTC7OcNI/AAAAAAACNp4/OzEEACLl84sRMrgcgMs-lsKlWC7c8OvHQCLcBGAs/s640/mail2018r2top5.png" width="640" /></a></div>Codeforces hosted Mail.Ru Cup 2018 Round 2 during the Nov 5 - Nov 11 week (<a href="https://codeforces.com/contest/1055">problems</a>, <a href="https://codeforces.com/contest/1055/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/63099">analysis</a>, <a href="https://youtu.be/WHvUs3YHkWA">my screencast</a>). aid has claimed the victory thanks to solving problem G (that was already a very tricky geometry problem, and then let me quote the official analysis: "One thing you need to note here is that at given constraints you can't do those computations in floating point numbers, because the relative difference between <i>r</i><sub>1</sub>+<i>r</i><sub>2</sub> and the distance from a vector to a polygon may be as low as 10<sup>−17</sup>. Therefore, you need to do all calculations in integers."). Moreover, his submission for G came with just 35 seconds remaining in the round. Congratulations on the persistence and the win!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-ET6SJZXjLB8/XCXfFFtpd1I/AAAAAAACNqE/ga8KW9xYULAvJZ-1aHBazv3AGiwJxz2iQCLcBGAs/s1600/oc1819polandtop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="364" data-original-width="1392" height="166" src="https://3.bp.blogspot.com/-ET6SJZXjLB8/XCXfFFtpd1I/AAAAAAACNqE/ga8KW9xYULAvJZ-1aHBazv3AGiwJxz2iQCLcBGAs/s640/oc1819polandtop5.png" width="640" /></a></div>One day later the Open Cup returned with the Grand Prix of Poland (<a href="http://opencup.ru/index.cgi?data=macros/stage&head=index&menu=index&stg=6&region=main&ncup=ocj&class=ocj">results</a>, top 5 on the left). 4 hours were enough for 13 problems for team Past Glory, while teams MIT THREE and Moscow SU: Red Santa required a bit more time but still solved everything. Congratulations to the top three!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-SIFnrXPDifM/XCX0oO9P6BI/AAAAAAACNrg/9u6-oMihq_cZDYjZT4Qemaaz800jIrcCQCLcBGAs/s1600/IMG_20181029_111129.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1200" data-original-width="1600" height="480" src="https://4.bp.blogspot.com/-SIFnrXPDifM/XCX0oO9P6BI/AAAAAAACNrg/9u6-oMihq_cZDYjZT4Qemaaz800jIrcCQCLcBGAs/s640/IMG_20181029_111129.jpg" width="640" /></a></div>In <a href="https://petr-mitrichev.blogspot.com/2018/12/a-week-with-ethan.html">my previous summary</a>, I have mentioned a Hacker Cup problem: there are <i>w</i><=80 windows and <i>s</i><=50 stars, both cells on a grid which represents a skyline. One must draw several buildings, each represented by a rectangle on the grid with line <i>y</i>=0 as the bottom side. Several buildings may intersect. Each window must be inside at least one building, and each star must not be inside any building. We need to find the minimum number of buildings required to satisfy those constraints. Such a problem would be too easy, so there's an extra twist: suppose we remove a random subset of windows (each window is removed independently with probability 0.5), what is the expected value of the minimum number of buildings required to cover all remaining windows without covering the stars?<br /><br />First, suppose no windows are removed. It turns out that we can solve the problem greedily: let's go from top to bottom until we encounter a window that is not yet covered by any building. It's clear that we need to have some building covering this window, and since there are no uncovered windows above this one, the height of this building should be exactly equal to the height of this window. Then there's no reason not to extend this building as much as possible to the left and to the right, until we reach the boundary of the grid or the columns where there is a star at the same level or below this window. After that we exclude all windows covered by the newly added building and continue going from top to bottom.<br /><br />Now we need to understand how we can run 2<sup><i>w</i></sup> instances of this greedy at the same time, one per possible subset of windows that are removed. The usual way to run so many greedys in parallel is dynamic programming: we need share large parts of the greedy execution between different problem instances. But what can we share?<br /><br />Consider the bottom-most star. While the greedy operates at its level or above, the computations to the left and to the right of it are completely independent, and when the greedy passes its level, there are no more relevant stars, and thus the only thing that matters is whether there's any yet uncovered window below that bottom-most star level: if there is at least one, we'll need to add exactly one building, otherwise we're already done.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-D4eHTKQ6d-Q/XCXyvr_jZOI/AAAAAAACNrM/8Y2H1RcrmIcYHURY5IoH1DLDiT3ordXfgCKgBGAs/s1600/IMG_20181228_105144.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" data-original-height="1277" data-original-width="1600" height="318" src="https://3.bp.blogspot.com/-D4eHTKQ6d-Q/XCXyvr_jZOI/AAAAAAACNrM/8Y2H1RcrmIcYHURY5IoH1DLDiT3ordXfgCKgBGAs/s400/IMG_20181228_105144.jpg" width="400" /></a></div>So far, this seems like a promising way to organize the dynamic programming as we have split the problem into two almost independent sub-problems. We can repeat the same step again for each of the sub-problems by finding the bottom-most star in each. This way our sub-problem can be viewed as a segment together with a level, such that all stars within the segment are above that level, and we have only O(<i>s</i>) such sub-problems as we get two new sub-problems per one star.<br /><br />However, there's a catch: for windows that are below the level, we need to know if they have been covered from above or not, in order to determine whether we need to add one to the answer on subsequent steps. The first idea of keeping a set of windows which are not yet covered results in exponential state space.<br /><br />Here comes the key idea that puts everything together: consider one of our sub-problems, a segment together with a threshold level such that there are no stars below that level. Suppose we have already decided which windows there are removed and which are not, <i>including</i> the windows there that are below the threshold level, and ran the greedy until the threshold level. Then it turns out that instead of remembering the subset of windows below the threshold level which are not removed and not covered, it is enough to remember the top-most such window (and left-most of those if there are several top-most ones), because any building that will cover the top-most window and have height below the threshold level will also cover all those windows!<br /><br />This means our dynamic programming has just O(<i>w</i>*<i>s</i>) states, and thus easily runs in time almost no matter how we implement the transition.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-H6v4DVMcZIE/XCXyndhlWvI/AAAAAAACNrI/D3AuBlkC5a83r7fHYVDSxDulp-m4XC6ygCKgBGAs/s1600/MVIMG_20181228_105134.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1600" data-original-width="1451" height="400" src="https://3.bp.blogspot.com/-H6v4DVMcZIE/XCXyndhlWvI/AAAAAAACNrI/D3AuBlkC5a83r7fHYVDSxDulp-m4XC6ygCKgBGAs/s400/MVIMG_20181228_105134.jpg" width="361" /></a></div>I have also mentioned a Codeforces problem: you are given a tree with nodes numbered from 1 to <i>n</i> (<i>n</i><=1000) and a subset of nodes in it which forms a connected subtree, given as a list of numbers of the nodes. There's also a second, hidden numbering of all nodes with distinct numbers from 1 to <i>n</i>, and a second subset of nodes which also forms a connected subtree, which is given to you as a list of hidden numbers of its nodes. However, you don't know how the hidden numbers of the nodes correspond to the visible ones. You can ask an oracle questions of two types:<br /><ul style="text-align: left;"><li>What is the hidden number of the node with [visible] number <i>x</i>?</li><li>What is the visible number of the node with hidden number <i>y</i>?</li></ul>Your goal is to find any vertex that belongs to both given subsets, or report that there isn't any. You can ask at most 5 questions.<br /><br />The solution here is beautifully simple. Let's take any hidden number that belongs to the second subset, and ask about its visible number, this way we find one node belonging to the second subset in our tree. Now let's find the node in the first subset that is closest to the known node of the second subset (since we're in a tree and the subset is connected, there will be exactly one closest node). It turns out that in case there is intersection between the two subsets, this node will belong to the intersection (again because the subsets are connected)!<br /><br />All that remains is to ask the oracle about the hidden number of this node, and to check if it belongs to the second subset. We end up requiring just two questions to the oracle no matter how big the tree is.<br /><br />Thanks for reading, and check back for more!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/EjhFVeUeLq8" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com0http://petr-mitrichev.blogspot.com/2018/12/a-17-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-3283269993026742452018-12-27T22:43:00.001+03:002018-12-27T22:43:32.738+03:00A week with Ethan<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/-0n9eiSTJGHI/XCUfdW2LLII/AAAAAAACNpQ/H5n76obghEQdK9KkYr3tJsvCK8ULQkB1wCLcBGAs/s1600/srm741top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="150" data-original-width="780" height="122" src="https://4.bp.blogspot.com/-0n9eiSTJGHI/XCUfdW2LLII/AAAAAAACNpQ/H5n76obghEQdK9KkYr3tJsvCK8ULQkB1wCLcBGAs/s640/srm741top5.png" width="640" /></a></div>TopCoder SRM 741 was the first event of the Oct 28 - Nov 4 week (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=17316">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17316&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://www.topcoder.com/blog/single-round-match-741-editorials/">analysis</a>). xudyh and tourist came to this event having the same number of points in the TCO19 qualification race (<a href="https://tco19.topcoder.com/home/algorithm/algorithm-leaderboard">link</a>, click on "Stage 1"), and this was the last round of the first stage so one of them would become the first TCO19 finalist. tourist had much better tie-breaker before this round, and has made it a habit to be in top 10, so the qualification boiled down to: if xudyh can win, he would qualify, otherwise it would most likely be tourist. xudyh came quite close, but was stopped by the great performance of fjzzq2002. Congratulations to xudyh on the great performance, to fjzzq2002 on the win and to tourist on making it to the TCO19 finals so early!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-hFCOV9Vbf8w/XCUhV6D7u-I/AAAAAAACNpc/I7X_E6lGK2otU6ZuAEmECqX1_ffLIRT-QCLcBGAs/s1600/fbhc2018finaltop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="421" data-original-width="1162" height="230" src="https://1.bp.blogspot.com/-hFCOV9Vbf8w/XCUhV6D7u-I/AAAAAAACNpc/I7X_E6lGK2otU6ZuAEmECqX1_ffLIRT-QCLcBGAs/s640/fbhc2018finaltop5.png" width="640" /></a></div>Facebook Hacker Cup 2018 onsite final round took place on Saturday (<a href="https://www.facebook.com/hackercup/problem/1983047265329089/">problems</a>, <a href="https://www.facebook.com/hackercup/scoreboard/228440181128818/?filter=everyone">results</a>, top 5 on the left, <a href="https://www.facebook.com/notes/facebook-hacker-cup/hacker-cup-2018-final-round-solutions/2417497708266116/">analysis</a>). There was quite tense competition until the very end, but ultimately Mikhail's (LHiC) speed could not be matched. Congratulations on the huge victory!<br /><br />I've spent a huge chunk of the contest thinking that I almost have a solution to the problem "<a href="https://www.facebook.com/hackercup/problem/162710881087828/">City Lights</a>" (as in, "now it should finally start working in a few minutes after I handle this surely last corner case"), however it stayed as "almost" until the end of the contest. Here's what the problem was about: there are <i>w</i><=80 windows and <i>s</i><=50 stars, both cells on a grid which represents a skyline. One must draw several buildings, each represented by a rectangle on the grid with line <i>y</i>=0 as the bottom side. Several buildings may intersect. Each window must be inside at least one building, and each star must not be inside any building. We need to find the minimum number of buildings required to satisfy those constraints. Such a problem would be too easy, so there's an extra twist: suppose we remove a random subset of windows (each window is removed independently with probability 0.5), what is the expected value of the minimum number of buildings required to cover all remaining windows without covering the stars?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-QU5gOXWetbc/XCUlkdRIxsI/AAAAAAACNpo/ZdPojpqmq8MAgHu4hnjdGGbS-ai7tKpPQCLcBGAs/s1600/lyft2018finaltop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="276" data-original-width="1109" height="158" src="https://2.bp.blogspot.com/-QU5gOXWetbc/XCUlkdRIxsI/AAAAAAACNpo/ZdPojpqmq8MAgHu4hnjdGGbS-ai7tKpPQCLcBGAs/s640/lyft2018finaltop5.png" width="640" /></a></div>Codeforces ran another onsite contest on Sunday, the Lyft Level 5 Challenge Final Round (<a href="https://codeforces.com/contest/1074">problems</a>, <a href="https://codeforces.com/contest/1044/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/contest/1074/standings">parallel round results</a>, <a href="https://codeforces.com/blog/entry/62985">analysis</a>). tourist was unstoppable this time, solving all problems and doing it 20 minutes faster than scott_wu, the only other onsite contestant to solve everything. Congratulations to both!<br /><br /><a href="https://codeforces.com/contest/1074/problem/B">Problem B</a> in this round was a very nice interactive problem: you are given a tree with nodes numbered from 1 to <i>n</i> (<i>n</i><=1000) and a subset of nodes in it which forms a connected subtree, given as a list of numbers of the nodes. There's also a second, hidden numbering of all nodes with distinct numbers from 1 to <i>n</i>, and a second subset of nodes which also forms a connected subtree, which is given to you as a list of hidden numbers of its nodes. However, you don't know how the hidden numbers of the nodes correspond to the visible ones. You can ask an oracle questions of two types:<br /><br /><ul style="text-align: left;"><li>What is the hidden number of the node with [visible] number <i>x</i>?</li><li>What is the visible number of the node with hidden number <i>y</i>?</li></ul><br />Your goal is to find any vertex that belongs to both given subsets, or report that there isn't any. You can ask at most 5 questions.<br /><br />Thanks for reading, and check back for more!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/KmCnDpFubuQ" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com0http://petr-mitrichev.blogspot.com/2018/12/a-week-with-ethan.htmltag:blogger.com,1999:blog-1953325079793449971.post-49110247896964119082018-12-27T21:42:00.000+03:002018-12-27T21:42:17.482+03:00A first hour 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/-NIwynwyIEo8/XCUVxivGb_I/AAAAAAACNo4/n4JmnsQmc60hyoubBV2uXFzdFZHKPBFDQCLcBGAs/s1600/cf518top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="270" data-original-width="1118" height="154" src="https://3.bp.blogspot.com/-NIwynwyIEo8/XCUVxivGb_I/AAAAAAACNo4/n4JmnsQmc60hyoubBV2uXFzdFZHKPBFDQCLcBGAs/s640/cf518top5.png" width="640" /></a></div>The Oct 22 - Oct 28 week had two Codeforces rounds. On Wednesday, it was time for Round 518 (<a href="https://codeforces.com/contest/1067">problems</a>, <a href="https://codeforces.com/contest/1067/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/62688">analysis</a>). Radewoosh could not pass pretests in problem D even after 8 attempts, but it turned out to be not necessary for the first place as ksun48 has failed the same problem on systests. Congratulations to Radewoosh on the win!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-h1chKOTMTvE/XCUa3K2KXkI/AAAAAAACNpE/TpnX2xzSExAqujLJHYDfatv46Aiwy3GTACLcBGAs/s1600/cf519top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="272" data-original-width="1109" height="156" src="https://1.bp.blogspot.com/-h1chKOTMTvE/XCUa3K2KXkI/AAAAAAACNpE/TpnX2xzSExAqujLJHYDfatv46Aiwy3GTACLcBGAs/s640/cf519top5.png" width="640" /></a></div>Codeforces Round 519 took place on Sunday (<a href="https://codeforces.com/contest/1043">problems</a>, <a href="https://codeforces.com/contest/1043/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/62797">analysis</a>, <a href="https://youtu.be/pDOOk70x9HM">my screencast</a>). With 6 problems solvable under an hour and the last problem which was too difficult to crack during the contest, the fight for the first place quite naturally came down to challenges. scott_wu extracted the most from the available opportunities and won by more than 100 points — well done!<br /><br />Thanks for reading (not so much to read this time :)), and check back for more!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/5Z872xkYLR8" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com0http://petr-mitrichev.blogspot.com/2018/12/a-first-hour-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-90772229412524876072018-12-27T11:56:00.001+03:002018-12-27T11:56:37.536+03:00A rolling 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/-uWBMTxtlfR8/XCPT5YSfyUI/AAAAAAACNmk/cxQpRTOBb14Sc91_hl6MDp6KO24g2REGACLcBGAs/s1600/mail2018r1top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="272" data-original-width="1115" height="154" src="https://1.bp.blogspot.com/-uWBMTxtlfR8/XCPT5YSfyUI/AAAAAAACNmk/cxQpRTOBb14Sc91_hl6MDp6KO24g2REGACLcBGAs/s640/mail2018r1top5.png" width="640" /></a></div>The Oct 15 - Oct 21 week started with Codeforces hosting Mail.Ru Cup 2018 Round 1 (<a href="https://codeforces.com/contest/1054">problems</a>, <a href="https://codeforces.com/contest/1054/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/62563">analysis</a>). Despite the round's slightly longer 2:30 duration, the usual two hours were enough for mnbvmar to claim the first place. Congratulations!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-20avDGedTIU/XCPb_B2MppI/AAAAAAACNnA/UD4UyCS0EZEInkar2n6kuPiB-fG5qHK8gCLcBGAs/s1600/srm740top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="148" data-original-width="784" height="120" src="https://2.bp.blogspot.com/-20avDGedTIU/XCPb_B2MppI/AAAAAAACNnA/UD4UyCS0EZEInkar2n6kuPiB-fG5qHK8gCLcBGAs/s640/srm740top5.png" width="640" /></a></div>TopCoder SRM 740 followed on Saturday (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=17310">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17310&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://www.topcoder.com/blog/single-round-match-740-editorials/">analysis</a>). With the win in this round, xudyh has joined tourist at the top of the TCO19 points scoreboard (<a href="https://tco19.topcoder.com/home/algorithm/algorithm-leaderboard">link</a>, click on "Stage 1") and made sure it's just the two of them fighting for the single TCO19 direct qualification spot in the final October SRM a bit later. Well done!<br /><br />My solution for the hard problem has failed the system test, and I was trying to recall why when I'm writing this post now, two months later. I did not remember, so I've decided to look at the diff between my solution during the round and the one I got accepted afterwards:<br /><br /><span style="font-family: "courier new" , "courier" , monospace; font-size: x-small;">31,33c31,33</span><br /><span style="font-family: "courier new" , "courier" , monospace; font-size: x-small;">< matrix[limbo][start * 2 + startState] += old;</span><br /><span style="font-family: "courier new" , "courier" , monospace; font-size: x-small;">< if (matrix[limbo][start * 2 + startState] >= MODULO)</span><br /><span style="font-family: "courier new" , "courier" , monospace; font-size: x-small;">< matrix[limbo][start * 2 + startState] -= MODULO;</span><br /><span style="font-family: "courier new" , "courier" , monospace; font-size: x-small;">---</span><br /><span style="font-family: "courier new" , "courier" , monospace; font-size: x-small;">> matrix[limbo][start + 2 * startState] += old;</span><br /><span style="font-family: "courier new" , "courier" , monospace; font-size: x-small;">> if (matrix[limbo][start + 2 * startState] >= MODULO)</span><br /><span style="font-family: "courier new" , "courier" , monospace; font-size: x-small;">> matrix[limbo][start + 2 * startState] -= MODULO;</span><br /><div><br /></div><div>When I first saw this diff today, there were also a few spurious formatting diffs here and there, and I could not actually notice that this one is meaningfully different. I guess this is what happened during the round as well, and is similar to what happens when reading those <a href="https://www.mrc-cbu.cam.ac.uk/people/matt.davis/cmabridge/">"jumbled" English sentences</a>: we most likely don't read the programs character by character or token by token, but rather read the statements as a whole, and thus can assume parts which are not there. Anyway, enough psychology speculation, the diff is: the first block has "* 2 +", and the second one has "+ 2 *" (the former is correct).</div><div><br /></div><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-c4PV1z1yebs/XCSJmg9h55I/AAAAAAACNn0/0cps_sVASNY0V6BNu2pEyzSncvUk-4R_QCLcBGAs/s1600/cf517top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="271" data-original-width="1103" height="156" src="https://3.bp.blogspot.com/-c4PV1z1yebs/XCSJmg9h55I/AAAAAAACNn0/0cps_sVASNY0V6BNu2pEyzSncvUk-4R_QCLcBGAs/s640/cf517top5.png" width="640" /></a></div><div>Finally, one more Codeforces round, the 517-th one, took place on Sunday (<a href="https://codeforces.com/contest/1071">problems</a>, <a href="https://codeforces.com/contest/1071/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/62612">analysis</a>). It was Radewoosh this time who earned enough points for the first place just one hour into the contest, which was a bit more risky in this round given that ainta did in fact solve a hard problem that Radewoosh did not. Congratulations on the victory!</div><div><br /></div><div><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-ovsWJW7fl5E/XCSSfESLpiI/AAAAAAACNoA/MsXCtRMmHMMybN6bf20WyQoB5EBzICaAQCLcBGAs/s1600/IMG_20180915_122149-EFFECTS.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1200" data-original-width="1600" height="480" src="https://2.bp.blogspot.com/-ovsWJW7fl5E/XCSSfESLpiI/AAAAAAACNoA/MsXCtRMmHMMybN6bf20WyQoB5EBzICaAQCLcBGAs/s640/IMG_20180915_122149-EFFECTS.jpg" width="640" /></a></div>In <a href="https://petr-mitrichev.blogspot.com/2018/12/a-bmerry-week.html">my previous summary</a>, I have mentioned a few problems. First one was from TopCoder: you are given a number <i>n</i> between 3 and 500. You need to generate any simple (not necessarily convex) polygon with <i>n</i> vertices, where all vertices have integer coordinates between 1 and 25, inclusive, and which has the smallest possible area among such polygons.<br /><br />The mathematical part of the solution is rather standard: <a href="https://en.wikipedia.org/wiki/Pick%27s_theorem">Pick's theorem</a> tells us that to minimize the area it is necessary and sufficient to have no integer points inside the polygon, and no extra integer points except the <i>n</i> vertices on the boundary of the polygon.<br /><br />Now we need to figure out a way to draw such polygon without extra integer vertices on a relatively small grid. <a href="https://codeforces.com/blog/entry/62317?#comment-463144">This picture</a> by fjzzq2002 demonstrates a very good approach to do that.<br /><br />The second mentioned problem from AtCoder has a <a href="https://img.atcoder.jp/agc028/editorial.pdf">very good editorial</a> (problem D "Chords" there), I don't have much to add to it.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-qFuOPRAfFdk/XCSTYcXT2FI/AAAAAAACNoU/u3bD4BvoRrQuv3C4G3obqBq_49Gqrm3MwCKgBGAs/s1600/IMG_20181227_095403.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" data-original-height="1208" data-original-width="1451" height="332" src="https://4.bp.blogspot.com/-qFuOPRAfFdk/XCSTYcXT2FI/AAAAAAACNoU/u3bD4BvoRrQuv3C4G3obqBq_49Gqrm3MwCKgBGAs/s400/IMG_20181227_095403.jpg" width="400" /></a></div>Finally, there was an Open Cup problem which is actually not explained in the corresponding analysis: you are given a 50x50 grid where some cells are empty, and some are walls. There are also walls surrounding the grid. Some empty cells are marked as targets, and there's also a ball in one of the empty cells. You can move the ball in each of the four cardinal directions, but once it starts rolling, it rolls in the same direction until it hits the wall, at which point you can pick a new direction, and so on. Can you roll the ball in such a way that it passes through all targets in some order?<br /><br />Here's the key observation: suppose we roll the ball to the right at some point. Then we can immediately roll it to the left and to the right again, end up in exactly the same position, but be guaranteed to have covered an entire horizontal segment of the grid. Similarly, rolling the ball up or down can be viewed as traversing an entire vertical segment of the grid.<br /><br />So instead of thinking in terms of moving the ball from cell to cell, we can enumerate all non-extendable horizontal and vertical segments in the grid, and think of our movement as jumping from one such segment to another. For example, from a horizontal segment we can jump to one of the two vertical segments containing the endpoints of the horizontal segment.<br /><br />The key benefit from such formulation comes from the fact that every target belongs to just two such segments: one horizontal and one vertical. The number two points us towards reducing this problem to <a href="https://en.wikipedia.org/wiki/2-satisfiability">2-SAT</a>: let's introduce one variable per segment, which will be true if our path visits this segment, and false otherwise. The condition about visiting all targets can now be encoded as a set of "one of those two variables must be true" clauses, which are permissible in 2-SAT.<br /><br />The other condition that we must enforce is that all visited segments can be put on one path that starts from the starting position. In order to achieve that, we add two types of restrictions:<br /><ol style="text-align: left;"><li>If a segment is not reachable from the starting position, the corresponding variable must be false.</li><li>For each pair of segments such that none is reachable from the other, at least one of the two corresponding variables must be false.</li></ol>The second restriction guarantees us a total linear order of the visited segments, which is exactly what a path is, and the first one makes sure this path can start in the right place. Both restrictions are already expressed in the form of 2-SAT clauses.<br /><br />Our 2-SAT problem has O(<i>n</i><sup>2</sup>) variables and O(<i>n</i><sup>4</sup>) clauses, where <i>n</i>=50 is the size of the grid. Since 2-SAT is solved in linear time, this is fast enough. One more potentially slow part is discovering all restrictions of the second type as we need to find the transitive closure of a graph with O(<i>n</i><sup>2</sup>) vertices. However, the number of edges in the graph is also O(<i>n</i><sup>2</sup>), so the transitive closure can be found in O(<i>n</i><sup>4</sup>) as well.<br /><br />Thanks for reading, and check back for more!</div></div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/Q1WTQ-U_abQ" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com6http://petr-mitrichev.blogspot.com/2018/12/a-rolling-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-61415420715639099622018-12-25T22:24:00.002+03:002018-12-27T11:32:10.430+03:00A bmerry 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/-JrL9GJ_4ZUY/XB4ozHNnvoI/AAAAAAACM6w/hZDquwoLCwgHiOTelkeXtImY6vTMDuVIQCLcBGAs/s1600/srm739top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="152" data-original-width="789" height="122" src="https://4.bp.blogspot.com/-JrL9GJ_4ZUY/XB4ozHNnvoI/AAAAAAACM6w/hZDquwoLCwgHiOTelkeXtImY6vTMDuVIQCLcBGAs/s640/srm739top5.png" width="640" /></a></div>TopCoder SRM 739 was the first round of Oct 8 - Oct 14 week (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=17298">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17298&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://www.topcoder.com/blog/single-round-match-739-editorials/">analysis</a>, <a href="https://youtu.be/2SU1hVhFiHk">my screencast</a>). Nobody was able to solve all three problems correctly this time, but pashka's very fast solution to the hard problem earned him a comfortable first place. Congratulations on the win!<br /><br />Here's that <a href="https://community.topcoder.com/stat?c=problem_statement&pm=15097&rd=17298">hard problem</a>: you are given a number <i>n</i> between 3 and 500. You need to generate any simple (not necessarily convex) polygon with <i>n</i> vertices, where all vertices have integer coordinates between 1 and 25, inclusive, and which has the smallest possible area among such polygons.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-JrC_h-B78Cs/XB4oKgeApEI/AAAAAAACM6k/wwFFCirVbeoz2h8gXzkI_ZBxDfkXlmh4gCLcBGAs/s1600/agc028top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="449" data-original-width="1170" height="244" src="https://3.bp.blogspot.com/-JrC_h-B78Cs/XB4oKgeApEI/AAAAAAACM6k/wwFFCirVbeoz2h8gXzkI_ZBxDfkXlmh4gCLcBGAs/s640/agc028top5.png" width="640" /></a></div>AtCoder Grand Contest 028 took place on Saturday (<a href="https://agc028.contest.atcoder.jp/assignments">problems</a>, <a href="https://agc028.contest.atcoder.jp/standings">results</a>, top 5 on the left, <a href="https://img.atcoder.jp/agc028/editorial.pdf">analysis</a>, <a href="https://youtu.be/FPGJ0GWrOyE">my screencast</a>). With just a few rounds left in the year, the fight for the top 8 in the <a href="https://docs.google.com/spreadsheets/d/1T-hKu_vIh8l4EiW6XTWOvP0evzsWj0f45JNNgou21Cc/edit#gid=695896678">AtCoder Race Ranking</a> is entering its deciding phase. Not so much for tourist, who is head and shoulders ahead of everybody else, and who has further cemented his Race Ranking lead with a win here. Well done!<br /><br /><a href="https://agc028.contest.atcoder.jp/tasks/agc028_d">Problem D</a> in this round was a cute combinatorics exercise. You are given 2<i>n</i> points on the circumference of a circle, <i>n</i> is up to 300. We're going to form <i>n</i> pairs of points, such that each point is in exactly one pair, and draw straight line segments between the points in each pair. After all segments are drawn, we're going to count the number of connected components of segments (two segments are connected directly if they intersect). We have already formed <i>k</i> such pairs, and need to form the remaining <i>n</i>-<i>k</i>. You need to find the sum of the numbers of connected components over all possible ways to form the remaining <i>n</i>-<i>k</i> pairs.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-yZJlUevIkD0/XB4n1irhDWI/AAAAAAACM6c/KsDfpnjPLdAu90IkTrsMqINEN6uAIyn-ACLcBGAs/s1600/oc1819koreatop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="209" data-original-width="857" height="156" src="https://2.bp.blogspot.com/-yZJlUevIkD0/XB4n1irhDWI/AAAAAAACM6c/KsDfpnjPLdAu90IkTrsMqINEN6uAIyn-ACLcBGAs/s640/oc1819koreatop5.png" width="640" /></a></div>Open Cup 2018-19 Grand Prix of Korea followed on Sunday (<a href="http://opencup.ru/index.cgi?data=macros/stage&head=index&menu=index&stg=5&region=main&ncup=ocj&class=ocj">results</a>, top 5 on the left, <a href="http://run.kaist.ac.kr/contest18f/editorial.pdf">partial analysis</a>). Just like last week, team Past Glory did not really need the whole 5 hours — congratulations on another convincing win!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-rgrct7xhvtA/XCIqXo5LMqI/AAAAAAACNkw/Ka0SrkiBREAaicvvOgCmKpqpwlZjVwdZgCLcBGAs/s1600/ocdiff.png" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" data-original-height="153" data-original-width="749" height="81" src="https://4.bp.blogspot.com/-rgrct7xhvtA/XCIqXo5LMqI/AAAAAAACNkw/Ka0SrkiBREAaicvvOgCmKpqpwlZjVwdZgCLcBGAs/s400/ocdiff.png" width="400" /></a></div>Our team, on the other hand, used all available time, and solved the last problem with less than a minute remaining on the clock. You can see the diff between the previous incorrect submission and the last-minute correct one on the right. Just imagine: there's almost no time left, we got wrong answer, have implemented a stress-test and found a discrepancy, but there's no time to debug. What <i>could </i>be wrong in this code, anyway? Let's try swapping left and right — and voilà, stress-test passes, and there're still a few seconds to submit :)<br /><br />Problem B in this round left me with a feeling "wow, how come such problem hadn't been set before!": you are given a 50x50 grid where some cells are empty, and some are walls. There are also walls surrounding the grid. Some empty cells are marked as targets, and there's also a ball in one of the empty cells. You can move the ball in each of the four cardinal directions, but once it starts rolling, it rolls in the same direction until it hits the wall, at which point you can pick a new direction, and so on. Can you roll the ball in such a way that it passes through all targets in some order?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-L_cjxa5iEbo/XB4nkvEUPPI/AAAAAAACM6U/xZhb1ihXXwEspjNKnENwkNvi824E2brsACLcBGAs/s1600/cf516top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="269" data-original-width="1101" height="156" src="https://1.bp.blogspot.com/-L_cjxa5iEbo/XB4nkvEUPPI/AAAAAAACM6U/xZhb1ihXXwEspjNKnENwkNvi824E2brsACLcBGAs/s640/cf516top5.png" width="640" /></a></div>Codeforces Round 516 ran in parallel with the Open Cup (<a href="https://codeforces.com/contest/1063">problems</a>, <a href="https://codeforces.com/contest/1063/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/62455">analysis</a>). With nobody able to solve everything, choosing the right problems to solve was a necessary part of winning, and mnbvmar found the right set of problems and solved them faster than everybody else. Congratulations on the victory!<br /><br />This round also brought somewhat <a href="https://codeforces.com/blog/entry/62540">sad news</a>: Bruce, who placed second and regained his nutella status, is retiring from rated contests on a high note. I've certainly enjoyed competing against Bruce for a really long time (and competing in a team once, as we solved a World Finals mirror together a few years ago!), so I'm still hoping to chat to him at the onsites which don't have a rating system :)<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-CUpnJzsizSQ/XCKDwCUYW6I/AAAAAAACNlk/2Ci6tNcry5wl1VJHBe3P81bysKspnR_ygCLcBGAs/s1600/IMG_20180908_125431.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1200" data-original-width="1600" height="480" src="https://3.bp.blogspot.com/-CUpnJzsizSQ/XCKDwCUYW6I/AAAAAAACNlk/2Ci6tNcry5wl1VJHBe3P81bysKspnR_ygCLcBGAs/s640/IMG_20180908_125431.jpg" width="640" /></a></div>In my previous summary, I have mentioned <a href="https://ipsc.ksp.sk/2018/real/problems/e.html">an IPSC problem</a>: you are given a prime number <i>p</i> up to 10<sup>100</sup>, a number <i>k</i>, and <i>n</i><=100 triples of numbers <i>a<sub>i</sub></i>, <i>b<sub>i</sub></i>, <i>m<sub>i</sub></i>. Your goal is to count how many numbers <i>x</i> between 0 and <i>p</i>-1 satisfy the equation ((<i>a<sub>i</sub></i> * <i>x</i> + <i>b<sub>i</sub></i>) mod <i>p</i>) mod <i>m<sub>i</sub></i> = ((<i>a<sub>i</sub></i> * <i>k</i> + <i>b<sub>i</sub></i>) mod <i>p</i>) mod <i>m<sub>i</sub></i> for at least one <i>i</i>. Moreover, you need just the approximate count: an error of up to 1% is fine. There are 100 testcases to solve, and the duration of the contest is 5 hours.<br /><br />A rather straightforward first step in solving this problem is to figure out how to solve each individual modular equation. I won't go into the details as it's not the most exciting part of the problem, so I will just state that we can find the number of solutions, test if a given number is a solution, and describe all solutions in a way that allows sampling a uniformly random solution, for example.<br /><br />Now we have 100 huge sets of numbers that we know the size of and can test and generate, and need to estimate the size of their union with at most 1% error. The allowed error probability strongly hints at some kind of Monte-Carlo approach. The most straightforward Monte-Carlo approach would be: just repeatedly take a random number between 0 and <i>p</i>-1, and check if it belongs to one of the sets. This can give us an estimate with an error that's certainly less than 1% of our sampling pool, in other words less than 1% of <i>p</i>.<br /><br />To see it more formally, we can say that in each trial, we sample from a random variable that is equal to either 0 or <i>p</i>, and is equal to <i>p</i> with probability <i>a</i>/<i>p</i> where <i>a</i> is our answer, and then give a mean of <i>k</i> such samples as our estimate. The <a href="https://en.wikipedia.org/wiki/Central_limit_theorem">central limit theorem</a> tells us that such mean tends to behave like a normal variable with mean equal to the mean of individual sample, which is <i>p</i>*<i>a</i>/<i>p</i>=<i>a</i>, just as we need. The central limit theorem also tells us how to estimate the error: the standard deviation of that normal variable will be equal to the standard deviation of the individual sample divided by the square root of <i>k</i>. The standard deviation of the individual sample is sqrt(<i>p</i>*<i>p</i>*<i>a</i>/<i>p</i>-<i>a</i>*<i>a</i>)=sqrt(<i>a</i>*(<i>p</i>-<i>a</i>)), and we can assume that a normal variable will never exceed, say, its 6 standard deviations, so our error will be at most 6*sqrt(<i>a</i>*(<i>p</i>-<i>a</i>)/<i>k</i>). Unfortunately when <i>a</i> is very small relative to <i>p</i>, this is still very big relative to <i>a</i>.<br /><br />At this point during the contest I've tried to come up with some ad-hoc fixes using common sense, and did not succeed. However, I should've simply continued using more formal statistics! The problem in the above approach is that we're sampling from the individual distribution with too big standard deviation — so let's come up with another one. Instead of sampling from all <i>p</i> possible numbers, let's use the fact that we can generate solutions for each equation: let's sample a random (<i>i</i>, <i>x</i>) pair where <i>x</i> is a solution to the <i>i</i>-th equation, in such a way that every valid (<i>i</i>, <i>x</i>) pair is equally likely. We can do that by first sampling <i>i</i> proportionally to the number of solutions of each equation, and then sampling a uniformly random solution <i>x</i> to the <i>i</i>-th equation.<br /><br />Now we need to come up with a random variable with the mean equal to our answer. Let <i>t<sub>i</sub></i> be the number of solutions of the <i>i</i>-th equation, and let <i>t</i> be the sum of <i>t<sub>i</sub></i>. Given a sample (<i>i</i>, <i>x</i>) let's make our random variable equal to <i>t</i> if there's no other equation with a smaller index <i>j</i> < <i>i</i> such that <i>x</i> is also a solution of the <i>j</i>-th equation, or 0 otherwise. It's not hard to see that for each distinct <i>x</i> from the union of all solutions our random variable will be equal to <i>t</i> for exactly one <i>i</i>, and thus the mean of our random variable is equal to <i>a</i>*<i>t</i>/<i>t</i>=<i>a</i>, just as required (Another way to achieve the same mean would be to make our random variable equal to <i>t</i> divided by the number of equations that <i>x</i> is a solution for).<br /><br />The standard deviation of this variable is equal to sqrt(<i>a</i>*(<i>t</i>-<i>a</i>)), and we know that <i>t</i> is at most <i>a</i>*<i>n</i>, so it is at most sqrt(<i>a</i>*<i>a</i>*(<i>n</i>-1))<=<i>a</i>*sqrt(<i>n</i>). Now we need to pick such k that 6*<i>a</i>*sqrt(<i>n</i>)/sqrt(<i>k</i>)<=0.01*<i>a</i>, or 600*sqrt(<i>n</i>)<=sqrt(<i>k</i>), or <i>k</i>>=<i>n</i>*360000, so as <i>n</i>=100 we get <i>k</i>>=36 million. This is already doable in a few seconds per testcase, but in reality we need even less attempts as 6 standard deviations is a very conservative bound.<br /><br />During the contest I could not come up with such sampling idea, and instead tried to return the result as a sum of estimates of sizes of first set, second set minus first set, third set minus first two sets and so on, where each particular estimate is built using essentially the above approach. However, it meant I needed to decide how to allocate my samples between the n estimates, and I could not get that part right (from the above solution, it is clear that I simply needed to have sample counts proportional to <i>t<sub>i</sub></i> — and indeed, I did get my solution accepted after the end with this fix).<br /><br />Thanks for reading, and check back for more!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/TcVbydLYKdw" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com0http://petr-mitrichev.blogspot.com/2018/12/a-bmerry-week.html