tag:blogger.com,1999:blog-19533250797934499712020-02-25T13:00:07.510+03:00Algorithms Weekly by Petr MitrichevPetr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.comBlogger463125PetrMitrichevhttps://feedburner.google.comtag:blogger.com,1999:blog-1953325079793449971.post-30757702860449876182020-02-17T17:49:00.001+03:002020-02-17T17:49:59.117+03:00A frontier 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/-hY7zSF_Rbxs/XkqWLpJ77rI/AAAAAAACcsg/KDsRO-0N2kM0QKmYv1qok7-vQopMNOmOwCLcBGAsYHQ/s1600/srm778top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="97" data-original-width="637" height="96" src="https://1.bp.blogspot.com/-hY7zSF_Rbxs/XkqWLpJ77rI/AAAAAAACcsg/KDsRO-0N2kM0QKmYv1qok7-vQopMNOmOwCLcBGAsYHQ/s640/srm778top5.png" width="640" /></a></div>TopCoder SRM 778 took place last week (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=17805">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17805&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://youtu.be/JDiaeE6qie4">my screencast</a>, <a href="https://www.topcoder.com/single-round-match-778-editorials/">analysis</a>). I and many others have come up with a O(<i>k</i><sup>3</sup>) solution for the medium problem that was unexpected for the problemsetters, which however required some squeezing into the time limit with <i>k</i>=1000. I have used two main insights to do so:<br /><ul style="text-align: left;"><li>A "backward" DP which computes a number based on previous numbers is faster than a "forward" DP that updates further numbers based on the already computed number, presumably because it does less memory writes and those writes are sequential.</li><li>C++ is faster than Java :)</li></ul><div>The intended solution for the problem was actually much nicer than that. Here is <a href="https://community.topcoder.com/stat?c=problem_statement&pm=15944&rd=17805">the problem statement</a>, after some unwrapping: you start in position 0 on a line, and can make jumps of integer size between 1 and <i>k</i> (<i>k</i><=1000) to the right, increasing your position. You are given the costs of such jumps as <i>c</i><sub>1</sub>, <i>c</i><sub>2</sub>, ..., <i>c</i><sub><i>k</i></sub>. What is the minimum cost to reach position <i>m </i>(<i>m</i><=10<sup>9</sup>)?</div><br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-gHa2y6CwHUw/XkqX1ch2VQI/AAAAAAACcss/UTbNEPg3uUgRCAfhbEF7ag3Ci_CkKhSqQCLcBGAsYHQ/s1600/oc1920gomeltop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="199" data-original-width="729" height="174" src="https://1.bp.blogspot.com/-gHa2y6CwHUw/XkqX1ch2VQI/AAAAAAACcss/UTbNEPg3uUgRCAfhbEF7ag3Ci_CkKhSqQCLcBGAsYHQ/s640/oc1920gomeltop5.png" width="640" /></a></div>Open Cup 2019-20 Grand Prix of Gomel has then resumed the Open Cup season after the New Year break (<a href="http://opentrains.snarknews.info/~ejudge/res/res10491">results</a>, top 5 on the left, <a href="https://www.dropbox.com/s/lfh3g8aixw200oc/gkc5-tutorial.pdf?dl=0">analysis</a>). Team Polish Mafia was just 100 penalty minutes ahead of Yuhao Du, who was seemingly competing alone. Congratulations to the Mafia but also very impressive from Yuhao!<br /><br />Thanks for reading, and check back next week!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/tAO-EHrzMtE" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com4http://petr-mitrichev.blogspot.com/2020/02/a-frontier-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-77195553279906272602020-02-09T20:19:00.001+03:002020-02-09T20:19:27.341+03:00An almost retired 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/-J9JA0IYrJLw/XkAMWsYJ_rI/AAAAAAACchk/a5-km5dc0o8g8k_lBM7U_sDM5aQtJzsUwCLcBGAsYHQ/s1600/srm777top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="95" data-original-width="629" src="https://1.bp.blogspot.com/-J9JA0IYrJLw/XkAMWsYJ_rI/AAAAAAACchk/a5-km5dc0o8g8k_lBM7U_sDM5aQtJzsUwCLcBGAsYHQ/s1600/srm777top5.png" /></a></div>TopCoder SRM 777 was the first round of this week (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=17802">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17802&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://www.topcoder.com/single-round-match-777-editorials/">analysis</a>). The hard problem was way too grungy for a 75-minute round, while easy and medium both had nasty corner cases to deal with. This has led to quite low coding phase scores which were partially compensated by quite high challenge phase scores :) neal_wu and scott_wu got 250 challenge points each and took home <a href="https://codeforces.com/blog/entry/73555">the monetary prizes</a>. Well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-GXHIS5vOnkQ/XkAPWx8odoI/AAAAAAACchw/V3ixYiISlnwhD5gulnGWVn4xL5xumS_5ACLcBGAsYHQ/s1600/pzw2020top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="230" data-original-width="1300" height="112" src="https://1.bp.blogspot.com/-GXHIS5vOnkQ/XkAPWx8odoI/AAAAAAACchw/V3ixYiISlnwhD5gulnGWVn4xL5xumS_5ACLcBGAsYHQ/s640/pzw2020top5.png" width="640" /></a></div>The winter 2020 Petrozavodsk training camp concluded on Friday (<a href="http://karelia.snarknews.info/index.cgi?data=macros/results&menu=index&head=index&round=09&class=2020w&sbname=2020w">results</a>, top 5 on the left). NNSU Almost Retired team enjoyed a really dominant performance, especially compared to other teams who would be coming to the ICPC World Finals in Moscow in June. Congratulations!<br /><br />Some of those contests will return as Open Cup rounds in the coming weeks.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-nrHvTSIdCFU/XkA97TaqGTI/AAAAAAACciY/YNqAawvL2pQEXxUwAyHVj-e0_Rutb3GwQCLcBGAsYHQ/s1600/cf618top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="272" data-original-width="1100" height="158" src="https://1.bp.blogspot.com/-nrHvTSIdCFU/XkA97TaqGTI/AAAAAAACciY/YNqAawvL2pQEXxUwAyHVj-e0_Rutb3GwQCLcBGAsYHQ/s640/cf618top5.png" width="640" /></a></div>Finally, Codeforces Round 618 wrapped up the week on Sunday (<a href="https://codeforces.com/contest/1299">problems</a>, <a href="https://codeforces.com/contest/1299/standings">results</a>, top 5 on the left). MiFaFaOvO, TLE and Radewoosh were the only contestants to solve the hardest interactive problem, and a mere two points separated MiFaFaOvO and TLE at the top. TLE was briefly in first place when he scored a successful challenge two minutes before the end of the round, only to be overtaken by MiFaFaOvO's own challenge with one minute remaining. Congratulations to both!<br /><br />Thanks for reading, and check back next week.</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/YLzGyjpkiB0" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com0http://petr-mitrichev.blogspot.com/2020/02/an-almost-retired-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-53986928480836400952020-02-09T15:46:00.002+03:002020-02-09T15:46:51.965+03:00A week without branching and the best problem of 2019<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/-kRZaeHyOsp8/Xj_1M8cGA-I/AAAAAAACcgw/ytnrJAJ_egMwLjXy_pyMJRz3Nb6HnXZfwCLcBGAsYHQ/s1600/cf616top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="275" data-original-width="1105" height="158" src="https://1.bp.blogspot.com/-kRZaeHyOsp8/Xj_1M8cGA-I/AAAAAAACcgw/ytnrJAJ_egMwLjXy_pyMJRz3Nb6HnXZfwCLcBGAsYHQ/s640/cf616top5.png" width="640" /></a></div>Codeforces Round 616 took place last week (<a href="https://codeforces.com/contest/1290">problems</a>, <a href="https://codeforces.com/contest/1290/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/73563">analysis</a>). Three contestants could solve five problems, but tourist's solution for the hardest problem F was so fast that he got almost a thousand points more. Congratulations on the win!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-Zlf4i4crxJg/Xj_-_42FL7I/AAAAAAACchQ/f9-YSUNVndkXSh25U_NjsAUNmWwMaIOpACLcBGAsYHQ/s1600/IMG_20200112_151342.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/-Zlf4i4crxJg/Xj_-_42FL7I/AAAAAAACchQ/f9-YSUNVndkXSh25U_NjsAUNmWwMaIOpACLcBGAsYHQ/s640/IMG_20200112_151342.jpg" width="640" /></a></div>In <a href="https://petr-mitrichev.blogspot.com/2020/01/a-cyclotomic-week.html">my previous summary</a>, I have mentioned <a href="https://community.topcoder.com/stat?c=problem_statement&pm=15916&rd=17799">a TopCoder problem</a>: there are <i>n</i>=2*<i>a</i>+<i>b</i> pieces of string, out of which <i>a</i> have both ends red, <i>a</i> have both ends green, and <i>b</i> have one red and one green end, so we have <i>n</i> red ends and <i>n</i> green ends in total. We will randomly pair the red and green ends in one of <i>n</i>! possible ways, and tie the corresponding ends together. What is the expected number of cycles we will get? <i>a</i> and <i>b</i> are up to a million.<br /><br />The first idea is to notice that if we pair just one green end with just one red end, then one of the two things can happen:<br /><ul style="text-align: left;"><li>either they have belonged to two different strings, in which case we have effectively replaced two strings with one, and the colors of its ends correspond to the colors of the other ends of the original two strings, or</li><li>they have belonged to the same string, in which case we have formed a cycle.</li></ul>In either case, the problem reduces to the same problem with <i>n</i>-1 strings, which means that a dynamic programming solution is on the cards. However, since both <i>a</i> and <i>b</i> are up to a million, a naive dynamic programming approach would have on the order of 10<sup>12</sup> states, which is too much.<br /><br />However, we still have the freedom of choosing which pair of green and red ends we use for reducing the problem to size <i>n</i>-1. If <i>b</i>>0, then we will choose which green end is one of the red ends of the first green-red string paired with. The key fact is that no matter which string (green-green, or green-red) we attach to the red end of a green-red string, the new string is of the same type, since we just "extend" its green end effectively! Moreover, if we tie this string to itself (the probability of which is 1/<i>n</i>), we also just reduce the number of green-red strings by one. Therefore we always go from the state (<i>a</i>,<i>b</i>) to the state (<i>a</i>,<i>b</i>-1) this way, and there is no branching:<br /><br />f(<i>a</i>,<i>b</i>)=f(<i>a</i>,<i>b</i>-1)+1/(2*<i>a</i>+<i>b</i>)<br /><br />When <i>b</i>=0, we have only red-red strings and green-green strings, and thus all our choices for the first move are symmetric: we will tie a red-red string and a green-green string to obtain a red-green string. Therefore there is no branching as well:<br /><br />f(<i>a</i>,0)=f(<i>a</i>-1,1)<br /><br />Now we can unroll this recursion to get a simple formula that can be computed in O(<i>a</i>+<i>b</i>).<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-wIncYCz4Q5Y/Xj_8CQlZcYI/AAAAAAACcg8/ngj6caJ9_lssQZXkbTWOtuw6Paj19caVwCLcBGAsYHQ/s1600/best2019.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="295" data-original-width="671" src="https://1.bp.blogspot.com/-wIncYCz4Q5Y/Xj_8CQlZcYI/AAAAAAACcg8/ngj6caJ9_lssQZXkbTWOtuw6Paj19caVwCLcBGAsYHQ/s1600/best2019.png" /></a></div>I have also ran <a href="https://petr-mitrichev.blogspot.com/2020/01/best-problems-of-2019.html">a poll</a> for the best problem of 2019. You can see the results on the left, and the best problem with 68 out of 174 votes is the problem Split the Attractions from IOI 2019 by <a href="https://codeforces.com/profile/lgm">LGM</a> and <a href="https://codeforces.com/profile/Saeed_Reza">Saeed_Reza</a>. Congratulations to them and to all problemsetters of 2019!<br /><br />Here is what that problem is about: you are given a connected undirected graph with <i>n</i> vertices and <i>m</i> edges, and you are also given three positive integers <i>a</i>,<i>b</i>,<i>c</i> such that <i>a</i>+<i>b</i>+<i>c</i>=<i>n</i>. Your goal is to split all vertices of the graph into three parts, the first of size <i>a</i>, the second of size <i>b</i>, and the third of size <i>c</i>, in such a way that <i>at least two</i> of those parts are connected using only the graph edges within the part. <i>n</i><=100000, <i>m</i><=200000.<br /><br />Thanks for reading, and check back for more.</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/gBdwitDjTAM" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com2http://petr-mitrichev.blogspot.com/2020/02/a-week-without-branching-and-best.htmltag:blogger.com,1999:blog-1953325079793449971.post-27520953943923383672020-01-28T00:11:00.000+03:002020-01-29T20:11:55.149+03:00Best problems of 2019<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/-kzEyJhrKmNA/Xi9RUfNaXhI/AAAAAAACcOQ/acIhmj82cvgO1Puj1xd2eg5YyRzjpTvCQCLcBGAsYHQ/s1600/IMG_20200111_142128.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/-kzEyJhrKmNA/Xi9RUfNaXhI/AAAAAAACcOQ/acIhmj82cvgO1Puj1xd2eg5YyRzjpTvCQCLcBGAsYHQ/s640/IMG_20200111_142128.jpg" width="640" /></a></div>Just like last couple of years (<a href="https://petr-mitrichev.blogspot.com/2017/12/best-problems-of-2017.html">2017</a>, <a href="https://petr-mitrichev.blogspot.com/2019/01/best-problems-of-2018.html">2018</a>), I've went through the problems I mentioned in 2019 to find the ones I liked the most. I have also looked at some of the problems recommended in <a href="https://codeforces.com/blog/entry/72458">this post</a>, in <a href="https://codeforces.com/blog/entry/72856#comments">this post</a>, and in various private messages. Of course, this is still an entirely subjective exercise, and it is certainly easier for me to like a problem that I have solved or tried to solve than one that I did not. Here is the shortlist (for those interested, here is <a href="https://docs.google.com/spreadsheets/d/1xfn4aMrMjbJY4-OGuF-3yZmRz75VAEyK61oK1tagzUc/edit?usp=sharing">a slightly bigger one</a>), as usual in chronological order:<br /><div class="separator" style="clear: both; text-align: center;"></div><ul style="text-align: left;"><li>The Open Cup problem "<a href="https://drive.google.com/file/d/1MdVYRf5elorgZlX7cZ8wREdF5pBNpBvn/view?usp=sharing">Alien Invasion</a>" about finding an area of a polygon by interactively asking about areas of convex hulls, by ???, with solution in <a href="https://petr-mitrichev.blogspot.com/2019/02/a-wtf-week.html">this post</a>.</li><li>The AtCoder problem "<a href="https://atcoder.jp/contests/wtf19-open/tasks/wtf19_c2">Triangular Lamps Hard</a>" about finding the original state of a cellular automaton on a triangular grid, by <a href="https://codeforces.com/profile/rng_58">rng_58</a> and <a href="https://codeforces.com/profile/yosupo">yosupo</a>, with solution in <a href="https://petr-mitrichev.blogspot.com/2019/03/an-oracle-week.html">this post</a>.</li><li>The Open Cup problem "<a href="https://drive.google.com/file/d/1VuU0WuLxuhPx-pEhD-x-YZOy8h90iZek/view?usp=sharing">Equanimous</a>" about inserting + and - between digits of a number to get the smallest positive value and grouping all numbers in a large segment by that value, by <a href="https://codeforces.com/profile/Tangjz">tangjz</a>, with solution in <a href="https://petr-mitrichev.blogspot.com/2019/04/a-week-of-715.html">this post</a>.</li><li>The TopCoder problem "<a href="https://community.topcoder.com/stat?c=problem_statement&pm=15279&rd=17592">SpanningSubgraphs</a>" about counting spanning subgraphs with each number of edges, by <a href="https://codeforces.com/profile/lewin">lewin</a>, with solution in <a href="https://petr-mitrichev.blogspot.com/2019/10/a-fusion-week.html">this post</a>.</li><li>The IOI problem "<a href="https://ioinformatics.org/files/ioi2019problem2.pdf">Split the Attractions</a>" about splitting a graph into three parts of given size such that at least two are connected, by <a href="https://codeforces.com/profile/lgm">LGM</a> and <a href="https://codeforces.com/profile/Saeed_Reza">Saeed_Reza</a>, with solutions discussed in <a href="https://codeforces.com/blog/entry/68940">this Codeforces post</a>.</li></ul>Which one do you think is the very best? Also, please help me fill the unknown problem authors in comments!<br /><iframe frameborder="0" height="606" marginheight="0" marginwidth="0" src="https://docs.google.com/forms/d/e/1FAIpQLSdQenG979HA2LD-0mVdmHihdJ8w5wZJDpjE6K3Hnj3VBd1OTg/viewform?embedded=true" width="640">Загрузка…</iframe></div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/NgsjLKwGHIA" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com3http://petr-mitrichev.blogspot.com/2020/01/best-problems-of-2019.htmltag:blogger.com,1999:blog-1953325079793449971.post-87460750411083490542020-01-27T11:27:00.000+03:002020-01-27T11:27:02.372+03:00TCO20 stage 2 leaderboard<div dir="ltr" style="text-align: left;" trbidi="on">Since <a href="https://tco20.topcoder.com/competition-overview/algorithm/leaderboard">the official leaderboard</a> for TCO20 stage 2 is not yet ready, I've put together <a href="https://colab.research.google.com/drive/11UM7lZQ7-CCJiLAwVH1ENGfoyEEC28qs#scrollTo=e-1f_v5jFwEE">a small script</a> to compute it. Here's the current top 30:<br /><br /><table border="1" class="dataframe" style="background-color: white; border-collapse: collapse; border-spacing: 0px; border: none; color: #212121; font-family: Roboto, Noto, sans-serif; font-size: 14px; table-layout: fixed;"><thead style="border-bottom: 1px solid var(--colab-border-color); font-family: var(--colab-code-font-family); text-align: right;"><tr style="border: none; padding: 0.5em;"><th style="border: none; padding: 0.5em;">Rank</th><th style="border: none; padding: 0.5em;">Handle</th><th style="border: none; padding: 0.5em;">Score</th><th style="border: none; padding: 0.5em;">Points</th></tr></thead><tbody><tr style="background: var(--colab-secondary-surface-color); border: none; padding: 0.5em;"><td style="border: none; padding: 0.5em; text-align: right;">1</td><td style="border: none; padding: 0.5em; text-align: right;">Petr</td><td style="border: none; padding: 0.5em; text-align: right;">14</td><td style="border: none; padding: 0.5em; text-align: right;">3206.22</td></tr><tr style="border: none; padding: 0.5em;"><td style="border: none; padding: 0.5em; text-align: right;">2</td><td style="border: none; padding: 0.5em; text-align: right;">tourist</td><td style="border: none; padding: 0.5em; text-align: right;">13</td><td style="border: none; padding: 0.5em; text-align: right;">3309.85</td></tr><tr style="background: var(--colab-secondary-surface-color); border: none; padding: 0.5em;"><td style="border: none; padding: 0.5em; text-align: right;">3</td><td style="border: none; padding: 0.5em; text-align: right;">lyrically</td><td style="border: none; padding: 0.5em; text-align: right;">12</td><td style="border: none; padding: 0.5em; text-align: right;">2646.81</td></tr><tr style="border: none; padding: 0.5em;"><td style="border: none; padding: 0.5em; text-align: right;">4</td><td style="border: none; padding: 0.5em; text-align: right;">bqi343</td><td style="border: none; padding: 0.5em; text-align: right;">12</td><td style="border: none; padding: 0.5em; text-align: right;">2301.09</td></tr><tr style="background: var(--colab-secondary-surface-color); border: none; padding: 0.5em;"><td style="border: none; padding: 0.5em; text-align: right;">5</td><td style="border: none; padding: 0.5em; text-align: right;">Um_nik</td><td style="border: none; padding: 0.5em; text-align: right;">10</td><td style="border: none; padding: 0.5em; text-align: right;">2383.93</td></tr><tr style="border: none; padding: 0.5em;"><td style="border: none; padding: 0.5em; text-align: right;">6</td><td style="border: none; padding: 0.5em; text-align: right;">hitonanode</td><td style="border: none; padding: 0.5em; text-align: right;">10</td><td style="border: none; padding: 0.5em; text-align: right;">1588.43</td></tr><tr style="background: var(--colab-secondary-surface-color); border: none; padding: 0.5em;"><td style="border: none; padding: 0.5em; text-align: right;">7</td><td style="border: none; padding: 0.5em; text-align: right;">yosupo</td><td style="border: none; padding: 0.5em; text-align: right;">9</td><td style="border: none; padding: 0.5em; text-align: right;">1537.25</td></tr><tr style="border: none; padding: 0.5em;"><td style="border: none; padding: 0.5em; text-align: right;">8</td><td style="border: none; padding: 0.5em; text-align: right;">_aid</td><td style="border: none; padding: 0.5em; text-align: right;">9</td><td style="border: none; padding: 0.5em; text-align: right;">1506.97</td></tr><tr style="background: var(--colab-secondary-surface-color); border: none; padding: 0.5em;"><td style="border: none; padding: 0.5em; text-align: right;">9</td><td style="border: none; padding: 0.5em; text-align: right;">natsugiri</td><td style="border: none; padding: 0.5em; text-align: right;">9</td><td style="border: none; padding: 0.5em; text-align: right;">1485.10</td></tr><tr style="border: none; padding: 0.5em;"><td style="border: none; padding: 0.5em; text-align: right;">10</td><td style="border: none; padding: 0.5em; text-align: right;">kmjp</td><td style="border: none; padding: 0.5em; text-align: right;">9</td><td style="border: none; padding: 0.5em; text-align: right;">1464.26</td></tr><tr style="background: var(--colab-secondary-surface-color); border: none; padding: 0.5em;"><td style="border: none; padding: 0.5em; text-align: right;">11</td><td style="border: none; padding: 0.5em; text-align: right;">maroon_kuri</td><td style="border: none; padding: 0.5em; text-align: right;">9</td><td style="border: none; padding: 0.5em; text-align: right;">1232.54</td></tr><tr style="border: none; padding: 0.5em;"><td style="border: none; padding: 0.5em; text-align: right;">12</td><td style="border: none; padding: 0.5em; text-align: right;">neal_wu</td><td style="border: none; padding: 0.5em; text-align: right;">9</td><td style="border: none; padding: 0.5em; text-align: right;">1152.15</td></tr><tr style="background: var(--colab-secondary-surface-color); border: none; padding: 0.5em;"><td style="border: none; padding: 0.5em; text-align: right;">13</td><td style="border: none; padding: 0.5em; text-align: right;">IH19980412</td><td style="border: none; padding: 0.5em; text-align: right;">9</td><td style="border: none; padding: 0.5em; text-align: right;">1134.90</td></tr><tr style="border: none; padding: 0.5em;"><td style="border: none; padding: 0.5em; text-align: right;">14</td><td style="border: none; padding: 0.5em; text-align: right;">ShadoWsaZ</td><td style="border: none; padding: 0.5em; text-align: right;">8</td><td style="border: none; padding: 0.5em; text-align: right;">1328.25</td></tr><tr style="background: var(--colab-secondary-surface-color); border: none; padding: 0.5em;"><td style="border: none; padding: 0.5em; text-align: right;">15</td><td style="border: none; padding: 0.5em; text-align: right;">KevinWan</td><td style="border: none; padding: 0.5em; text-align: right;">7</td><td style="border: none; padding: 0.5em; text-align: right;">1516.60</td></tr><tr style="border: none; padding: 0.5em;"><td style="border: none; padding: 0.5em; text-align: right;">16</td><td style="border: none; padding: 0.5em; text-align: right;">ksun48</td><td style="border: none; padding: 0.5em; text-align: right;">7</td><td style="border: none; padding: 0.5em; text-align: right;">1349.06</td></tr><tr style="background: var(--colab-secondary-surface-color); border: none; padding: 0.5em;"><td style="border: none; padding: 0.5em; text-align: right;">17</td><td style="border: none; padding: 0.5em; text-align: right;">Egor</td><td style="border: none; padding: 0.5em; text-align: right;">7</td><td style="border: none; padding: 0.5em; text-align: right;">1149.52</td></tr><tr style="border: none; padding: 0.5em;"><td style="border: none; padding: 0.5em; text-align: right;">18</td><td style="border: none; padding: 0.5em; text-align: right;">redocpod</td><td style="border: none; padding: 0.5em; text-align: right;">7</td><td style="border: none; padding: 0.5em; text-align: right;">1140.82</td></tr><tr style="background: var(--colab-secondary-surface-color); border: none; padding: 0.5em;"><td style="border: none; padding: 0.5em; text-align: right;">19</td><td style="border: none; padding: 0.5em; text-align: right;">Vasyl[alphacom]</td><td style="border: none; padding: 0.5em; text-align: right;">7</td><td style="border: none; padding: 0.5em; text-align: right;">1120.55</td></tr><tr style="border: none; padding: 0.5em;"><td style="border: none; padding: 0.5em; text-align: right;">20</td><td style="border: none; padding: 0.5em; text-align: right;">cerberus97</td><td style="border: none; padding: 0.5em; text-align: right;">7</td><td style="border: none; padding: 0.5em; text-align: right;">781.12</td></tr><tr style="background: var(--colab-secondary-surface-color); border: none; padding: 0.5em;"><td style="border: none; padding: 0.5em; text-align: right;">21</td><td style="border: none; padding: 0.5em; text-align: right;">socketnaut</td><td style="border: none; padding: 0.5em; text-align: right;">7</td><td style="border: none; padding: 0.5em; text-align: right;">552.92</td></tr><tr style="border: none; padding: 0.5em;"><td style="border: none; padding: 0.5em; text-align: right;">22</td><td style="border: none; padding: 0.5em; text-align: right;">Kalam132</td><td style="border: none; padding: 0.5em; text-align: right;">6</td><td style="border: none; padding: 0.5em; text-align: right;">1623.00</td></tr><tr style="background: var(--colab-secondary-surface-color); border: none; padding: 0.5em;"><td style="border: none; padding: 0.5em; text-align: right;">23</td><td style="border: none; padding: 0.5em; text-align: right;">KKT89</td><td style="border: none; padding: 0.5em; text-align: right;">6</td><td style="border: none; padding: 0.5em; text-align: right;">1396.76</td></tr><tr style="border: none; padding: 0.5em;"><td style="border: none; padding: 0.5em; text-align: right;">24</td><td style="border: none; padding: 0.5em; text-align: right;">ecnerwal</td><td style="border: none; padding: 0.5em; text-align: right;">6</td><td style="border: none; padding: 0.5em; text-align: right;">1245.65</td></tr><tr style="background: var(--colab-secondary-surface-color); border: none; padding: 0.5em;"><td style="border: none; padding: 0.5em; text-align: right;">25</td><td style="border: none; padding: 0.5em; text-align: right;">darnley</td><td style="border: none; padding: 0.5em; text-align: right;">6</td><td style="border: none; padding: 0.5em; text-align: right;">846.29</td></tr><tr style="border: none; padding: 0.5em;"><td style="border: none; padding: 0.5em; text-align: right;">26</td><td style="border: none; padding: 0.5em; text-align: right;">kuniavski</td><td style="border: none; padding: 0.5em; text-align: right;">6</td><td style="border: none; padding: 0.5em; text-align: right;">821.25</td></tr><tr style="background: var(--colab-secondary-surface-color); border: none; padding: 0.5em;"><td style="border: none; padding: 0.5em; text-align: right;">27</td><td style="border: none; padding: 0.5em; text-align: right;">square1001</td><td style="border: none; padding: 0.5em; text-align: right;">6</td><td style="border: none; padding: 0.5em; text-align: right;">788.87</td></tr><tr style="border: none; padding: 0.5em;"><td style="border: none; padding: 0.5em; text-align: right;">28</td><td style="border: none; padding: 0.5em; text-align: right;">keymoon</td><td style="border: none; padding: 0.5em; text-align: right;">6</td><td style="border: none; padding: 0.5em; text-align: right;">777.42</td></tr><tr style="background: var(--colab-secondary-surface-color); border: none; padding: 0.5em;"><td style="border: none; padding: 0.5em; text-align: right;">29</td><td style="border: none; padding: 0.5em; text-align: right;">nwin</td><td style="border: none; padding: 0.5em; text-align: right;">6</td><td style="border: none; padding: 0.5em; text-align: right;">763.49</td></tr><tr style="border: none; padding: 0.5em;"><td style="border: none; padding: 0.5em; text-align: right;">30</td><td style="border: none; padding: 0.5em; text-align: right;">Jatana</td><td style="border: none; padding: 0.5em; text-align: right;">6</td><td style="border: none; padding: 0.5em; text-align: right;">640.78</td></tr></tbody></table><br />Enjoy! In the future I will most likely just rerun <a href="https://colab.research.google.com/drive/11UM7lZQ7-CCJiLAwVH1ENGfoyEEC28qs#scrollTo=e-1f_v5jFwEE">the notebook</a> instead of making new posts, so the updated standings will appear there.<br /><br /></div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/c0Ua15EC5U4" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com0http://petr-mitrichev.blogspot.com/2020/01/tco20-stage-2-leaderboard.htmltag:blogger.com,1999:blog-1953325079793449971.post-91879430948228914872020-01-26T23:07:00.001+03:002020-01-26T23:07:45.735+03:00A cyclotomic 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/-YLOoz7-QDyk/Xi3nQ1oRrLI/AAAAAAACcM0/sQL7G3fh61AEMSjFg57Ty2LazZit9w0kACLcBGAsYHQ/s1600/srm776top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="98" data-original-width="634" src="https://1.bp.blogspot.com/-YLOoz7-QDyk/Xi3nQ1oRrLI/AAAAAAACcM0/sQL7G3fh61AEMSjFg57Ty2LazZit9w0kACLcBGAsYHQ/s1600/srm776top5.png" /></a></div>TopCoder SRM 776 was the main event of this week (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=17799">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17799&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://docs.google.com/document/d/e/2PACX-1vSYxMnTExGygpm_69HpnOZdzAzEvzeV2tNDb9VxB1GN7pdp0HLZdFqi7Fqvmhet2LpcBx9NfZOYYR-2/pub">analysis</a>). After the coding phase it seemed as if bqi343 would catch up with me in the TCO20 race, but I was quite lucky twice: first, since my <a href="https://codeforces.com/blog/entry/73322?#comment-575649">incorrect solution</a> for the 1000 passed the system tests; second, since bqi343's 250 has failed. As a bonus, now I have learned about <a href="https://en.wikipedia.org/wiki/Cyclotomic_polynomial">cyclotomic polynomials</a> (I guess it's more like re-learned — surely my mathematician degree should have got me covered here).<br /><br /><a href="https://community.topcoder.com/stat?c=problem_statement&pm=15916&rd=17799">The medium problem</a> was very nice as well. There are <i>n</i>=2*<i>a</i>+<i>b</i> pieces of string, out of which <i>a</i> have both ends red, <i>a</i> have both ends green, and <i>b</i> have one red and one green end, so we have <i>n</i> red ends and <i>n</i> green ends in total. We will randomly pair the red and green ends in one of <i>n</i>! possible ways, and tie the corresponding ends together. What is the expected number of cycles we will get? <i>a</i> and <i>b</i> are up to a million.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-GC-Q36PZdXQ/Xi3xRfgxNPI/AAAAAAACcNU/geleQ4rI-hEstRTwBxeyoqg7bEiomCViQCLcBGAsYHQ/s1600/IMG_20200118_144816.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="963" data-original-width="1600" height="384" src="https://1.bp.blogspot.com/-GC-Q36PZdXQ/Xi3xRfgxNPI/AAAAAAACcNU/geleQ4rI-hEstRTwBxeyoqg7bEiomCViQCLcBGAsYHQ/s640/IMG_20200118_144816.jpg" width="640" /></a></div>In <a href="https://petr-mitrichev.blogspot.com/2020/01/a-mathematics-week.html">my previous summary</a>, I have mentioned a sub-problem of <a href="https://community.topcoder.com/stat?c=problem_statement&pm=15894&rd=17776">another TopCoder problem</a>: for which pairs of positive integers <i>a</i> <= <i>b</i> can we split all integers from the set {<i>a</i>, <i>a</i>+1, <i>a</i>+2, ..., <i>b</i>-1, <i>b</i>} into two parts with equal sum?<br /><br />First of all, the sum of all numbers (<i>a</i>+<i>b</i>)*(<i>b</i>-<i>a</i>+1)/2 must be even. Since the two parts in the product (<i>a</i>+<i>b</i>)*(<i>b</i>-<i>a</i>+1) have different parity, one of the parts must be divisible by 4 for the sum to be even. In case the size of the set (<i>b</i>-<i>a</i>+1) is divisible by 4, we can always make such a split: for each four consecutive numbers, we can split them independently as <i>x</i>+(<i>x</i>+3)=(<i>x</i>+1)+(<i>x</i>+2).<br /><br />Now, what happens when (<i>a</i>+<i>b</i>) is divisible by 4? The size of the set is odd in this case, so we must split into two unequal parts, the smaller part will have at most (<i>b</i>-<i>a</i>)/2 elements, and the bigger part at least (<i>b</i>-<i>a</i>)/2+1 elements. The sum of (<i>b</i>-<i>a</i>)/2 biggest elements in the set is equal to (<i>b</i>-<i>a</i>)/2*(<i>b</i>+<i>b</i>-(<i>b</i>-<i>a</i>)/2+1)/2=(<i>b</i>-<i>a</i>)*(3<i>b</i>+<i>a</i>+2)/8. The sum of (<i>b</i>-<i>a</i>)/2+1 smallest elements in the set is equal to ((<i>b</i>-<i>a</i>)/2+1)*(<i>a</i>+<i>a</i>+(<i>b</i>-<i>a</i>)/2)/2=(<i>b</i>-<i>a</i>+2)*(3<i>a</i>+<i>b</i>)/8. If the former is smaller than the latter, clearly there's no good split as the smaller part will always have the smaller sum.<br /><br />It turns out that this condition is not just necessary but also sufficient: if we can somehow get the smaller part to have bigger or equal sum, we can make it have equal sum because we can always repeatedly decrease the sum by 1: find two numbers <i>x</i> and <i>x</i>+1 such that <i>x</i> is in the bigger part and <i>x</i>+1 is in the smaller part, and swap them. This argument is the most beautiful part of the solution in my opinion.<br /><br />The condition (<i>b</i>-<i>a</i>)*(3<i>b</i>+<i>a</i>+2)/8>=(<i>b</i>-<i>a</i>+2)*(3<i>a</i>+<i>b</i>)/8 can be simplified as <i>b</i>>=<i>a</i>+2*sqrt(<i>a</i>), thus our final answer looks like:<br /><ul style="text-align: left;"><li>either <i>b</i>-<i>a</i>+1 is divisible by 4, or</li><li><i>a</i>+<i>b</i> is divisible by 4 and <i>b</i>>=<i>a</i>+2*sqrt(<i>a</i>).</li></ul>Thanks for reading, and check back next week (hopefully for the best problem of 2019 vote as well)!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/-W6QPD6mFO0" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com0http://petr-mitrichev.blogspot.com/2020/01/a-cyclotomic-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-15906011639577326652020-01-21T21:38:00.001+03:002020-01-21T21:38:51.492+03:00A mathematics 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/-eayjB5lBfhk/XidBpLw3U5I/AAAAAAACb-4/7iyUIGvgGz4bVXQj3VNzi_E0oqit4lCDACLcBGAsYHQ/s1600/srm775top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="97" data-original-width="633" src="https://1.bp.blogspot.com/-eayjB5lBfhk/XidBpLw3U5I/AAAAAAACb-4/7iyUIGvgGz4bVXQj3VNzi_E0oqit4lCDACLcBGAsYHQ/s1600/srm775top5.png" /></a></div>There were two rounds last week. TopCoder SRM 775 took place on Thursday (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=17776">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17776&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://www.topcoder.com/single-round-match-775-editorials/">analysis</a>). Tourist has earned a commanding victory while having the fastest time on all three problems, which also meant that nobody could get the 5 points towards the TCO20 qualification. Well done :)<br /><br />The main part of <a href="https://community.topcoder.com/stat?c=problem_statement&pm=15894&rd=17776">the hard problem</a> was a nice puzzle that could well appear in a mathematics olympiad: for which pairs of positive integers <i>a</i> <= <i>b</i> can we split all integers from the set {<i>a</i>, <i>a</i>+1, <i>a</i>+2, ..., <i>b</i>-1, <i>b</i>} into two parts with equal sum?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-KnIyko_AAeU/XidCOrmI_kI/AAAAAAACb_A/QgoTD-PqIJc4vy0kfDh7p3P1FXfvunz5QCLcBGAsYHQ/s1600/cf614top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="273" data-original-width="1100" height="158" src="https://1.bp.blogspot.com/-KnIyko_AAeU/XidCOrmI_kI/AAAAAAACb_A/QgoTD-PqIJc4vy0kfDh7p3P1FXfvunz5QCLcBGAsYHQ/s640/cf614top5.png" width="640" /></a></div>Codeforces Round 614 followed on Sunday (<a href="https://codeforces.com/contest/1292">problems</a>, <a href="https://codeforces.com/contest/1292/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/73051">analysis</a>). There was just one accepted solution for each of the two hardest problems, coming from Um_nik and tourist who have therefore occupied the first two places with a huge margin. Um_nik's problem was worth more points, and he had therefore won the round. Congratulations!<br /><br />Thanks for reading, and check back next week!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/WxQifsMGcrk" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com1http://petr-mitrichev.blogspot.com/2020/01/a-mathematics-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-77445880080983659092020-01-21T01:12:00.000+03:002020-01-21T01:12:14.175+03:00A matroid 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/-ILFQLCXm8PQ/XiH5eGi8JhI/AAAAAAACb14/PjxZWCj924UWAUz8b83vg6jJaiRZbzZywCLcBGAsYHQ/s1600/srm774top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="102" data-original-width="636" src="https://1.bp.blogspot.com/-ILFQLCXm8PQ/XiH5eGi8JhI/AAAAAAACb14/PjxZWCj924UWAUz8b83vg6jJaiRZbzZywCLcBGAsYHQ/s1600/srm774top5.png" /></a></div>Two weeks ago, TopCoder SRM 774 has started a new race for a TCO20 spot (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=17773">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17773&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left). The 1000-pointer was tricky both algorithmically and from the implementation standpoint, causing a few resubmissions and a few failed systests for high-scoring solutions. As a result, the total scores were not that high and the importance of the challenge phase was amplified.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-AtYdVsx-V3E/XiYkHY-_coI/AAAAAAACb9Y/xfXLMERD__gbZ-iNc4mTng7r_c8fbn7egCLcBGAsYHQ/s1600/IMG_20200111_113829.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1064" data-original-width="1600" height="424" src="https://1.bp.blogspot.com/-AtYdVsx-V3E/XiYkHY-_coI/AAAAAAACb9Y/xfXLMERD__gbZ-iNc4mTng7r_c8fbn7egCLcBGAsYHQ/s640/IMG_20200111_113829.jpg" width="640" /></a></div>In <a href="https://petr-mitrichev.blogspot.com/2020/01/a-red-maxflow-week.html">my previous summary</a>, I have mentioned <a href="https://codeforces.com/contest/1284/problem/G">a Codeforces problem</a>: you are given a 20x20 grid colored as a chessboard, with the top-left corner colored black. Some of the cells are removed from the grid, the remaining cells form a 4-connected piece and include the top-left corner. You need to insert some walls between the remaining cells in such a way that we get a <i>good</i> labyrinth: there must be exactly one way to get from each cell to each other cell. Moreover, we want each black cell (remember the chessboard coloring) except the top-left cell to not be a dead-end in the labyrinth: each such cell must have at least two accessible neighbors.<br /><br />When solving this problem during the round, I have made the correct first step: we want to find a spanning tree where the degree of each black cell is at least two, which is equivalent to finding a spanning forest where the degree of each black cell is at least two as we can always add more edges to get a tree.<br /><br />But then I've tried to find some greedy approach that takes two edges for each black vertex without forming cycles, realized that it's not always possible, thought that if we want to add an edge that forms a cycle we need to remove some other edge from this cycle and choose another edge for its black vertex, and then somehow failed to notice that I'm just describing finding an alternating path for a <a href="https://en.wikipedia.org/wiki/Matroid_intersection">matroid intersection problem</a> :) The matroids in question are the cycle matroid and the matroid where independent sets have degree <=2 for each black vertex, and we need to check if the biggest independent set in their intersection has degree of exactly 2 for each black vertex.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-RQZNNQbf440/XiYkNP_1N6I/AAAAAAACb9g/v1UcNlIXDF4atNyr_KVVQvS9unIyenecwCLcBGAsYHQ/s1600/IMG_20200111_094425.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1012" data-original-width="1600" height="404" src="https://1.bp.blogspot.com/-RQZNNQbf440/XiYkNP_1N6I/AAAAAAACb9g/v1UcNlIXDF4atNyr_KVVQvS9unIyenecwCLcBGAsYHQ/s640/IMG_20200111_094425.jpg" width="640" /></a></div>In that summary, I have also described a solution to an AtCoder problem that felt like unexplained magic. Um_nik has brought a simpler quadratic solution to my attention: instead of starting from <i>n</i> scores of 1 and adding 1 to a suffix <i>n</i>-1 times, we can start from <i>n</i> scores of <i>n</i> and subtract 1 from a prefix <i>any</i> number of times! The reason we don't need to limit the number of operations to <i>n</i>-1 in this approach is that if the first problem has zero or negative score, then the constraint about the sum of the first <i>k</i>+1 numbers being greater than the sum of the last <i>k</i> numbers would be necessarily violated.<br /><br />This means we can remove the number of operations dimension from our dynamic programming and it becomes quadratic. This is not directly equivalent to the magical solution, but at least it explains why there's a fertile ground for one.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-Hrr-rlA4J8g/XiYkSVqh8wI/AAAAAAACb9k/OwEF_t55A6ckpmF1re4yptVHIJ52Jh2jgCLcBGAsYHQ/s1600/IMG_20200112_151340.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/-Hrr-rlA4J8g/XiYkSVqh8wI/AAAAAAACb9k/OwEF_t55A6ckpmF1re4yptVHIJ52Jh2jgCLcBGAsYHQ/s640/IMG_20200112_151340.jpg" width="640" /></a></div>I have also promised to organize a poll about the best problem of 2019, but for that I need to review all my posts from last year and also the other excellent candidates you shared with me <a href="https://codeforces.com/blog/entry/72856#comments">on Codeforces</a>, so this will take some more time. Stay tuned :)<br /><br />Thanks for reading, and check back for more!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/4abPEG_wzMY" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com2http://petr-mitrichev.blogspot.com/2020/01/a-matroid-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-31490626733225802822020-01-06T00:26:00.000+03:002020-01-06T00:26:08.692+03:00A red maxflow 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/-ncQcvvrRQXU/XhIyLcvKQZI/AAAAAAACbZc/lxrhdL_rETs5LM2WxFdoazpdRy_Sa4rKgCLcBGAsYHQ/s1600/cfhello2020top5.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://1.bp.blogspot.com/-ncQcvvrRQXU/XhIyLcvKQZI/AAAAAAACbZc/lxrhdL_rETs5LM2WxFdoazpdRy_Sa4rKgCLcBGAsYHQ/s640/cfhello2020top5.png" width="640" /></a></div>Codeforces ran two contests this week. Hello 2020, as the name suggests, was the first round of the year (<a href="https://codeforces.com/contest/1284">problems</a>, <a href="https://codeforces.com/contest/1284/standings">results</a>, top 5 on the left, <a href="https://youtu.be/bmXB_zmh6PE">my screencast</a>, <a href="https://codeforces.com/blog/entry/72804">analysis</a>). Only four contestants could solve the hardest problem G, and only two of them also solved the remaining problems: mnbvmar and TLE. They had roughly the same speed as well, but mnbvmar only had two attempts that failed pretests compared to TLE's ten, and that's what made the difference. Congratulations to both!<br /><br />I could solve the first five problems reasonably quickly, and I was quite excited about inventing the randomized solution to problem D and quickly recognizing that problem E is more or less equivalent to a very old problem about counting the number of 4-tuples of points that form a convex quadrilateral (I have a feeling that I wrote about it in this blog, but I seem to be unable to find the entry). However, the last two problems proved insurmountable for me, and I spent most of the time trying to get solutions that were clearly not the intended ones to work: max-flow on a graph of size n*log(n) in F (it turns out it was possible to succeed in this way — check out <a href="https://codeforces.com/contest/1284/submission/68194361">izban's solution</a> as an example), and repeated randomized search in G. I guess the time might have been better spent just thinking on paper, but then the screencast would not be so exciting :)<br /><br />On a related note, quite a few people have noticed that I've switched to C++ in the recent contests, and asked why. I don't have much to add to <a href="https://codeforces.com/blog/entry/72415?#comment-566810">this Egor's comment</a>. In the past I have tried switching to C++ a few times and noticed that I keep fighting with it during the contests instead of solving problems, and I do have a similar feeling now as well despite the better tools. However, I will try to keep using C++ for a longer time to see if things improve :)<br /><br />Here is <a href="https://codeforces.com/contest/1284/problem/G">the hardest problem</a> from this round for you to try as well: you are given a 20x20 grid colored as a chessboard, with the top-left corner colored black. Some of the cells are removed from the grid, the remaining cells form a 4-connected piece and include the top-left corner. You need to insert some walls between the remaining cells in such a way that we get a <i>good</i> labyrinth: there must be exactly one way to get from each cell to each other cell. Moreover, we want each black cell (remember the chessboard coloring) except the top-left cell to not be a dead-end in the labyrinth: each such cell must have at least two accessible neighbors.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-ixhaybRu060/XhIzIJhG7qI/AAAAAAACbZk/C_1z14t_p9YeeAWhPGDXheTTHh4qo-ZAQCLcBGAsYHQ/s1600/cf612top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="277" data-original-width="1104" height="160" src="https://1.bp.blogspot.com/-ixhaybRu060/XhIzIJhG7qI/AAAAAAACbZk/C_1z14t_p9YeeAWhPGDXheTTHh4qo-ZAQCLcBGAsYHQ/s640/cf612top5.png" width="640" /></a></div>Codeforces Round 612 followed a day later (<a href="https://codeforces.com/contest/1286">problems</a>, <a href="https://codeforces.com/contest/1286/standings">results</a>, top 5 on the left). The sets of problems solved by the top contestants were very diverse (even though not visible in the top 5 screenshot, problem F was also solved by two contestants), but in the end ainta just solved more problems and won. Well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-09PPUiz-oP8/XhJRs7xLzPI/AAAAAAACbZ8/FP7snmdzoaslpIwz4kBjmlPZRBob82UBACLcBGAsYHQ/s1600/IMG_20200105_135015.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/-09PPUiz-oP8/XhJRs7xLzPI/AAAAAAACbZ8/FP7snmdzoaslpIwz4kBjmlPZRBob82UBACLcBGAsYHQ/s640/IMG_20200105_135015.jpg" width="640" /></a></div>In <a href="https://petr-mitrichev.blogspot.com/2020/01/a-mobile-first-week.html">my previous summary</a>, I have mentioned a couple of problems. <a href="https://atcoder.jp/contests/agc041/tasks/agc041_d">The first one</a> came from AtCoder: an assignment of integer scores between 1 and <i>n</i> (not necessarily distinct) to <i>n</i> programming contest problems (<i>n</i><=5000) is called <i>good</i> if for each <i>k</i> the total score of every set of <i>k</i> problems is strictly less than the total score of every set of <i>k</i>+1 problems. How many good assignments of scores exist, modulo the given prime <i>m</i>?<br /><br />The first step to solve this problem is to notice that we can get rid of "for each <i>k</i>" qualifier, replacing it with just <i>k</i>=(<i>n</i>-1)/2, rounded down. The reason for this is that in case the constraint is violated for smaller <i>k</i>, we can just add the same problems to both sides to reach <i>k</i>=(<i>n</i>-1)/2, and in case it is violated for larger <i>k</i>, the two sets necessarily have an intersection, so we can remove the intersection until we reach <i>k</i>=(<i>n</i>-1)/2 as well. Also, instead of "every set" we can say: the total score of <i>k</i> problems with the largest scores must be less than the total score of <i>k</i>+1 problems with the lowest scores.<br /><br />To enforce that last constraint, it would be useful if our problem scores were sorted. This can be achieved with the following more or less standard process: we start with all problem scores equal to 1. Now we do the following <i>n</i>-1 times: add 1 to a suffix of problem scores (this suffix could also be empty or all problems).<br /><br />Now we can keep track how each such operation affects the value we're interested in: the sum of (<i>n</i>-1)/2+1 smallest elements minus the sum of (<i>n</i>-1)/2 largest elements. Going from the empty suffix to the full suffix, they change that value by 0,-1,-2,...,-(<i>n</i>-1)/2,-(<i>n</i>-1)/2 (if <i>n</i> is even),-((<i>n</i>-1)/2-1),...,-2,-1,0,1. Let's denote that multiset of changes as <i>C</i>. In the end we need the value to be positive, and it starts with 1 (when all problem scores are 1).<br /><br />Our problem can then be restated as follows: consider all ways to choose <i>n</i>-1 values with replacement from the multiset <i>C</i> (the same value can be chosen as many times as we want). How many ways have a non-negative sum?<br /><br />Since the sum needs to be non-negative and the only possible positive change is 1, this yields a O(<i>n</i><sup>3</sup>) dynamic programming solution that can be sped up to O(<i>n</i><sup>2</sup>*log<i>n</i>) and get accepted by skipping the states from which we can't reach the final state: let's process the elements of <i>C</i> in decreasing order, and maintain dp<sub><i>i</i>,<i>j</i>,<i>k</i></sub> as the number of ways to choose <i>j</i> values from the first <i>i</i> elements of <i>C</i> such that their sum is <i>k</i>. The answer is the sum of dp<sub><i>n+1</i>,<i>n-1</i>,<i>k</i></sub> over all <i>k</i>>=0.<br /><br />However, there exists a magical way to speed this up to O(<i>n</i><sup>2</sup>). Let's rearrange our dynamic programming slightly: now we will process the elements of C in increasing order, and dp<sub><i>i</i>,<i>j</i>,<i>k</i></sub> will now be the number of ways to choose <i>j</i> values from the first <i>i</i> elements of <i>C</i> such that their sum is -<i>k</i>. Also, we will stop before we process the only positive element 1 (because that would need special handling anyway as the sums stop being only negative), but also (!) before we process one of the two zeros that we have — in other words, we will only consider the first <i>n</i>-1 elements of C in increasing order.<br /><br />How to compute the answer from the last row of this dynamic programming? Suppose we have computed dp<sub><i>n</i>-1,<i>j</i>,<i>k</i></sub>. Now we need to add some number of 0s and some number of 1s, let's denote those as <i>z</i> and <i>o</i> respectively. We need to have <i>j</i>+<i>z</i>+<i>o</i>=<i>n</i>-1 to get <i>n</i>-1 total changes, and <i>k</i><=<i>o</i> to get a non-negative sum. The solutions to these two constraints look like: <i>o</i>=<i>k</i>, <i>z</i>=<i>n</i>-1-<i>j</i>-<i>k</i>; <i>o</i>=<i>k</i>+1, <i>z</i>=<i>n</i>-1-<i>j</i>-<i>k</i>-1, and so on until <i>z</i> reaches 0. The number of solutions is thus max(0, <i>n</i>-<i>j</i>-<i>k</i>), so our answer is a sum of max(0, <i>n</i>-<i>j</i>-<i>k</i>)*dp<sub><i>n</i>-1,<i>j</i>,<i>k</i></sub>.<br /><br />Here comes the magic: since max(0, <i>n</i>-<i>j</i>-<i>k</i>) only depends on <i>j</i>+<i>k</i> and not on <i>j</i> and <i>k</i> separately, and since our transitions just add one to <i>j</i> and the current element of <i>C</i> to <i>k</i>, and so the thing being added does not depend on the values of <i>j</i> and <i>k</i> themselves, we can collapse our dynamic programming states to keep track of <i>j</i>+<i>k</i> only, instead of <i>j</i> and <i>k</i> separately! This means we'll have O(<i>n</i><sup>2</sup>) states and O(<i>n</i><sup>2</sup>) complexity.<br /><br />What remains a mystery is: how does one come up with this magic? I guess one could just stumble upon it while trying different approaches. Maybe a more principled way is to use the approach from <a href="https://petr-mitrichev.blogspot.com/2014/05/coming-up-with-tough-dynamic.html">my old post</a>: if we just implement the O(<i>n</i><sup>3</sup>) dynamic programming which processes the elements of <i>C</i> in increasing order, and find out the contribution of each state to the final answer, we can notice that the contributions of states with the same value of <i>j</i>+<i>k</i> are the same and collapse them. Is there any other way that makes this observation look less magical?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-N-TG_-c-Hw0/XhJRyKyGuhI/AAAAAAACbaA/KMZUJi5ydjgHuyIItGIqIeKCVLHxmdqMACLcBGAsYHQ/s1600/IMG_20200105_140147.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/-N-TG_-c-Hw0/XhJRyKyGuhI/AAAAAAACbaA/KMZUJi5ydjgHuyIItGIqIeKCVLHxmdqMACLcBGAsYHQ/s640/IMG_20200105_140147.jpg" width="640" /></a></div><a href="https://codeforces.com/contest/1270/problem/G">The second problem</a> I mentioned was from Codeforces: you are given <i>n</i> integers <i>a<sub>i</sub></i> such that <i>i</i>-<i>n</i><=<i>a<sub>i</sub></i><=<i>i</i>-1 (<i>i</i> goes from 1 to <i>n</i>), in other words one integer from [-(<i>n</i>-1),0], one from [-(<i>n</i>-2),1], ..., one from [0,<i>n</i>-1]. You need to find any nonempty subset with a zero sum. You are guaranteed that such subset always exists, which is by itself quite a hint. <i>n</i> is up to a million.<br /><br />The key idea here is to realize that keeping integers from different segments is a bit clumsy, so let's shift the segments: the first one by <i>n</i>-1, the second one by <i>n</i>-2, and so on. Now all integers are chosen from the segment [0, <i>n</i>-1] which is nice and symmetric, but instead of a zero-sum subset we need to find a subset where the sum of values equals to the sum of shifts.<br /><br />To restate, we have reduced our problem to the following: you are given n integers <i>a</i><sub>0</sub>, <i>a</i><sub>1</sub>, ..., a<sub><i>n</i>-1</sub>, each between 0 and <i>n</i>-1. You need to find a set <i>S</i> of indices such that Σ<sub><i>i</i>∈<i>S</i></sub><i>i</i>=Σ<sub><i>i</i>∈<i>S</i></sub>a<sub><i>i</i></sub>.<br /><br />When I obtained this reduced problem during the round, it felt really familiar to me, so I've tried to google the answer without much success. It turns out that it's simply quite easy: build a graph from the arrows <i>i</i>->a<sub><i>i</i></sub>, and just find any cycle in this graph. The indices corresponding to this cycle will satisfy the equality above since the sums will just be the same numbers but in different order.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-1A3kIaToaFA/XhJSmHLUuaI/AAAAAAACbak/w_CHOQpE_QsHyaZdFwmnNMFKyY3jMYZbACLcBGAsYHQ/s1600/IMG_20191231_140455_MP.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1017" data-original-width="1600" height="406" src="https://1.bp.blogspot.com/-1A3kIaToaFA/XhJSmHLUuaI/AAAAAAACbak/w_CHOQpE_QsHyaZdFwmnNMFKyY3jMYZbACLcBGAsYHQ/s640/IMG_20191231_140455_MP.jpg" width="640" /></a></div>I will be doing a poll for the best problem of 2019 soon, and I will mostly be picking the candidates from the problems I explained in this blog. However, I realize that there were many great problems in 2019 that I just did not encounter, so if there is a problem you feel should be included in the shortlist that was in a contest that I did not participate in, please mention it in comments! Feel free to also post links to similar discussions, such as <a href="https://codeforces.com/blog/entry/72458">this post</a>.<br /><br />Thanks for reading, and see you next week!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/uvSei85282s" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com3http://petr-mitrichev.blogspot.com/2020/01/a-red-maxflow-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-60912934860934086512020-01-04T00:27:00.000+03:002020-01-04T00:27:39.853+03:00A mobile-first 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/-TjBbKHV2Jko/Xg94SZIWIYI/AAAAAAACbKY/1NabV84zH_w0_QEo3DfUdL-xiaB7gVYHACLcBGAsYHQ/s1600/agc041top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="352" data-original-width="809" height="278" src="https://1.bp.blogspot.com/-TjBbKHV2Jko/Xg94SZIWIYI/AAAAAAACbKY/1NabV84zH_w0_QEo3DfUdL-xiaB7gVYHACLcBGAsYHQ/s640/agc041top5.png" width="640" /></a></div>Last week has wrapped up the competitive 2019 with two rounds. AtCoder Grand Contest 041 took place on Saturday (<a href="https://atcoder.jp/contests/agc041/tasks">problems</a>, <a href="https://atcoder.jp/contests/agc041/standings">results</a>, top 5 on the left, <a href="https://img.atcoder.jp/agc041/editorial.pdf">analysis</a>). mnbvmar, ecnerwal and Um_nik in first three places all have a different set of problems solved, and mnbvmar's set was the best one. He also tried to submit a solution that just tries random decisions until time runs out for E in the last minute, but that did not fly. Nevertheless, congratulations on the win!<br /><br />I was writing this round on the go, and around the middle of the round my laptop shut down because of low battery, which was very exciting as you might guess :) After I've turned it back on it continued to work for a long time somehow, suggesting that the problem lies with the battery level detection. A few minutes before the end of the round it shut down again, so I've tried to fix my solution to problem A from my phone. Unfortunately I was a few seconds too slow, otherwise it would have been a nice achievement :)<br /><br /><a href="https://atcoder.jp/contests/agc041/tasks/agc041_d">Problem D</a> in this round had an awesome intended solution, even though most contestants managed to squeeze in a more boring one: an assignment of integer scores between 1 and <i>n</i> (not necessarily distinct) to <i>n</i> programming contest problems (<i>n</i><=5000) is called <i>good</i> if for each <i>k</i> the total score of every set of <i>k</i> problems is strictly less than the total score of every set of <i>k</i>+1 problems. How many good assignments of scores exist, modulo the given prime <i>m</i>?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-JH4HWrJ7Iko/Xg948iB7TeI/AAAAAAACbKg/tT8YbChYzJI5ml6Vy9aseJ98dlgdW3xoACLcBGAsYHQ/s1600/atcoder2019top8.png" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" data-original-height="307" data-original-width="1274" height="154" src="https://1.bp.blogspot.com/-JH4HWrJ7Iko/Xg948iB7TeI/AAAAAAACbKg/tT8YbChYzJI5ml6Vy9aseJ98dlgdW3xoACLcBGAsYHQ/s640/atcoder2019top8.png" width="640" /></a></div>This round has concluded the selection of 8 AtCoder World Tour finalists that would come to Japan in February for the onsite finals (<a href="https://img.atcoder.jp/file/GP30.html">results</a>, top 8 on the right). With this win, mnbvmar has jumped onto a departing train (there is such idiom in Russian, вскочить на подножку уходящего поезда, but I'm not sure if there is a direct English equivalent or a different idiom with the same meaning — is there?) and overtook eatmore by just 6 points. See you all in Japan!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-OlgF3PJFVO0/Xg968bqKRvI/AAAAAAACbLc/C9ep_7DiZfkZO4kFKqBnJhq_hm81ltJkQCLcBGAsYHQ/s1600/cfgoodbye2019top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="272" data-original-width="1104" height="156" src="https://1.bp.blogspot.com/-OlgF3PJFVO0/Xg968bqKRvI/AAAAAAACbLc/C9ep_7DiZfkZO4kFKqBnJhq_hm81ltJkQCLcBGAsYHQ/s640/cfgoodbye2019top5.png" width="640" /></a></div>Codeforces Good Bye 2019 followed on Sunday (<a href="https://codeforces.com/contest/1270">problems</a>, <a href="https://codeforces.com/contest/1270/standings">results</a>, top 5 on the left, <a href="https://youtu.be/U5VrM6Q-t-k">my screencast</a>, <a href="https://codeforces.com/blog/entry/72611">analysis</a>). Not without help from a <a href="https://codeforces.com/blog/entry/72439?#comment-568987">notorious coincidence</a> and a bad day for tourist, Radewoosh has solved everything, won the round, ended the 2019 <a href="https://codeforces.com/ratings">top rated</a>, and was still <a href="https://codeforces.com/blog/entry/72439?#comment-569046">a bit salty</a>. Still, congratulations!<br /><br />Problem G generated some <a href="https://codeforces.com/blog/entry/72439?#comment-569131">conflicting opinions</a>, but I have enjoyed solving it quite a bit: you are given <i>n</i> integers <i>a<sub>i</sub></i> such that <i>i</i>-<i>n</i><=<i>a<sub>i</sub></i><=<i>i</i>-1 (<i>i</i> goes from 1 to <i>n</i>), in other words one integer from [-(<i>n</i>-1),0], one from [-(<i>n</i>-2),1], ..., one from [0,<i>n</i>-1]. You need to find any nonempty subset with a zero sum. You are guaranteed that such subset always exists, which is by itself quite a hint. <i>n</i> is up to a million.<br /><br />Thanks for reading, and see you in the present!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/APxk94g3Vl8" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com0http://petr-mitrichev.blogspot.com/2020/01/a-mobile-first-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-12173838139536067202020-01-03T20:16:00.000+03:002020-01-03T20:46:22.261+03:00An overall 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/-rI2rnj9Wads/Xg9wjcEGP_I/AAAAAAACbJY/99EMeZSnMHwSf1qO8Sc34Bxiom8cgkCSACLcBGAsYHQ/s1600/cfglobal6top5.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/-rI2rnj9Wads/Xg9wjcEGP_I/AAAAAAACbJY/99EMeZSnMHwSf1qO8Sc34Bxiom8cgkCSACLcBGAsYHQ/s640/cfglobal6top5.png" width="640" /></a></div>Codeforces Global Rounds series of 2019 has concluded during the Dec 16 - Dec 22 week with the Round 6 (<a href="https://codeforces.com/contest/1266">problems</a>, <a href="https://codeforces.com/contest/1266/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/72243">analysis</a>). With problem F being tricky to implement but quite standard, problem G requiring to notice a complex pattern after implementing an ineffective solution, and problem H relying on some cool maths coming almost out of nowhere, there was plenty of ways for top contestants to pick their poison. Only 1919810 and sunset could solve two of those three, and 1919810 got all easier problems correct as well thus securing a confident victory. Well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-Mpn9Q7g-W8w/Xg9vR10eOtI/AAAAAAACbJM/J38PnTIs2CQuemzyn8jvuzoW48MOCKktQCLcBGAsYHQ/s1600/cfglobal19overalltop5.png" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" data-original-height="309" data-original-width="903" height="219" src="https://1.bp.blogspot.com/-Mpn9Q7g-W8w/Xg9vR10eOtI/AAAAAAACbJM/J38PnTIs2CQuemzyn8jvuzoW48MOCKktQCLcBGAsYHQ/s640/cfglobal19overalltop5.png" width="640" /></a></div>The choice of counting the 4 best performances out of 6 for the <a href="https://codeforces.com/blog/entry/72245">overall standings</a> (top 5 on the right) seemed to turn out quite nicely, allowing contestants to skip some rounds and/or to enjoy a really bad day sometimes, although maybe Radewoosh would prefer 2 out of 6 :) Thanks to Codeforces and to XTX Markets for organizing the series!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-Ajrc-fL4wM8/Xg9zTzhBgbI/AAAAAAACbJk/HM1rXF0IGtsVKlMYIN4a58nppyFKQHM0ACLcBGAsYHQ/s1600/srm773top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="95" data-original-width="633" src="https://1.bp.blogspot.com/-Ajrc-fL4wM8/Xg9zTzhBgbI/AAAAAAACbJk/HM1rXF0IGtsVKlMYIN4a58nppyFKQHM0ACLcBGAsYHQ/s1600/srm773top5.png" /></a></div>TopCoder Open 2020 points-based qualification stage 1 also concluded that week, with the SRM 773 (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=17770">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17770&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://youtu.be/EARmGaB88Xg">my screencast</a>, <a href="https://tco20.topcoder.com/competition-overview/algorithm/leaderboard">TCO20 qualification standings</a>). There was no stopping tourist this time, with yet another dominating coding phase performance and another 175 challenge points he was simply out of reach and thus finally earned the 5 qualification points he needed to qualify for TCO20. I do not have my TopCoder stats scripts working anymore to support this claim with data, but it feels like he has really stepped up the challenge game a lot recently. Huge congratulations!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-OaA0YjZRyR8/Xg9tr1O0aSI/AAAAAAACbI4/cQAAIE94yREbh6gEdIrfKUZUXUkiGpslgCLcBGAsYHQ/s1600/oc1920xiantop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="210" data-original-width="685" height="196" src="https://1.bp.blogspot.com/-OaA0YjZRyR8/Xg9tr1O0aSI/AAAAAAACbI4/cQAAIE94yREbh6gEdIrfKUZUXUkiGpslgCLcBGAsYHQ/s640/oc1920xiantop5.png" width="640" /></a></div>Open Cup 2019-20 Grand Prix of Xi'An on Sunday sent two problems to the New Year Prime contest (<a href="http://opencup.ru/index.cgi?data=macros/stage&head=index&menu=index&stg=10&region=main&ncup=ock&class=ock">results</a>, top 5 on the left). Having penalty time almost twice as big as that of the second-placed NNSU Almost Retired, team USA1 had no other way to victory except solving more problems, which they delivered by becoming the only team to solve L in the last hour, and then finally getting F from the 24-th attempt. Congratulations!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-PlfW2CiyEPI/Xg9uH0SeUNI/AAAAAAACbJA/tnVmZYBVWvI4sFbBMFQfQa5IHXM24wupwCLcBGAsYHQ/s1600/oc1920overallafter19top5.png" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" data-original-height="218" data-original-width="1115" height="124" src="https://1.bp.blogspot.com/-PlfW2CiyEPI/Xg9uH0SeUNI/AAAAAAACbJA/tnVmZYBVWvI4sFbBMFQfQa5IHXM24wupwCLcBGAsYHQ/s640/oc1920overallafter19top5.png" width="640" /></a></div>With this win, team USA1 has almost caught up with team Past Glory in the <a href="http://opencup.ru/index.cgi?data=macros/results&menu=index&head=index&ncup=ock&class=ock&region=main">overall standings</a> after 2019 (top 5 on the right), promising us an exciting second half of the season in 2020!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-WJDu6zwbbls/Xg92cewv38I/AAAAAAACbJ8/ZSYSo0kKahsB2-2CiauUG0l2Pnf5YeK0wCLcBGAsYHQ/s1600/IMG_20191228_125614.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://1.bp.blogspot.com/-WJDu6zwbbls/Xg92cewv38I/AAAAAAACbJ8/ZSYSo0kKahsB2-2CiauUG0l2Pnf5YeK0wCLcBGAsYHQ/s640/IMG_20191228_125614.jpg" width="640" /></a></div>In <a href="https://petr-mitrichev.blogspot.com/2020/01/a-generating-week.html">my previous summary</a>, I have mentioned <a href="https://community.topcoder.com/stat?c=problem_statement&pm=15761&rd=17746">a TopCoder problem</a>: you are given 100000 points on the plane and a number <i>k</i>. Given a subset <i>S</i> of the set of given points, and denoting all other given points as its complement <i>T</i>, we define the <i>score</i> of <i>S</i> as the sum of pairwise Manhattan distances between the points in <i>S</i> minus the sum of pairwise Manhattan distances between the points in <i>T</i>. What is the largest (by the number of elements) subset of the set of given points such that its score does not exceed the given number <i>k</i>?<br /><br />The key insight in this problem is to consider how does the score of a set change when we add one more point to it. The distances from this point to the points already in <i>S</i> are added to the score; the distances from this point to the points not in <i>S</i> are <i>also</i> added to the score as they used to be subtracted from it and now they are not! Therefore adding a point to <i>S</i> simply increases the score of <i>S</i> by the sum of distances from this point to all other points.<br /><br />Now it is clear that we should just start with empty <i>S</i> and add points in order by this sum of distances until we exceed <i>k</i>.<br /><br />Thank for reading, and check back for more!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/aBWf7kp5zjs" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com0http://petr-mitrichev.blogspot.com/2020/01/an-overall-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-5930430417192385612020-01-03T19:24:00.001+03:002020-01-03T19:32:26.837+03:00A generating 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/-oZM4UMw0ufk/Xg9kbdiC97I/AAAAAAACbIc/ijotD0gQCWU6QPQGya3v6o_XuxK5wgsIACLcBGAsYHQ/s1600/srm772top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="96" data-original-width="630" src="https://1.bp.blogspot.com/-oZM4UMw0ufk/Xg9kbdiC97I/AAAAAAACbIc/ijotD0gQCWU6QPQGya3v6o_XuxK5wgsIACLcBGAsYHQ/s1600/srm772top5.png" /></a></div>TopCoder returned with its SRM 772 during the Dec 9 - Dec 15 week (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=17746">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17746&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://youtu.be/l4OZguE3f8c">my screencast</a>). Once again tourist had to settle for the second place despite great coding and challenge phases because ksun48 could solve the hardest problem. We were discussing during the TopCoder Open onsite that ecnerwal seems to just think in generating functions, and apparently so does ksun48, even though he tried to hide the fact by explaining his <a href="https://codeforces.com/blog/entry/72077?#comment-563412">combinatorial-ish solution</a> :) Congratulations on the win!<br /><br />I was comfortably in the top 10 this time, meaning that both me and tourist each got 4 TCO20 qualification points again and I kept my 1-point lead going into the final SRM of the stage.<br /><br /><a href="https://community.topcoder.com/stat?c=problem_statement&pm=15761&rd=17746">The medium problem</a> in this round was very nice. You are given 100000 points on the plane and a number <i>k</i>. Given a subset <i>S</i> of the set of given points, and denoting all other given points as its complement <i>T</i>, we define the <i>score</i> of <i>S</i> as the sum of pairwise Manhattan distances between the points in <i>S</i> minus the sum of pairwise Manhattan distances between the points in <i>T</i>. What is the largest (by the number of elements) subset of the set of given points such that its score does not exceed the given number <i>k</i>?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-G-FQuxwR9S8/Xg9lWwRWG0I/AAAAAAACbIk/lpB65cfOAhobXUT1qNkYiAybeR23kVHqACLcBGAsYHQ/s1600/cf606top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="269" data-original-width="1105" height="154" src="https://1.bp.blogspot.com/-G-FQuxwR9S8/Xg9lWwRWG0I/AAAAAAACbIk/lpB65cfOAhobXUT1qNkYiAybeR23kVHqACLcBGAsYHQ/s640/cf606top5.png" width="640" /></a></div>Codeforces then hosted two rounds on the weekend. Round 606 took place on Saturday (<a href="https://codeforces.com/contest/1276">problems</a>, <a href="https://codeforces.com/contest/1276/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/72239">analysis</a>). With a whole 1 accepted solution for both E and F combined, the round was effectively decided on the first four problems. Ainta was the fastest and won the round, well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-8CHa8Jv7C7k/Xg9ltyt1qOI/AAAAAAACbIs/N31pRCEO-ykUXg-0clEJxhC1pB9A2dPNwCLcBGAsYHQ/s1600/cf607top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="272" data-original-width="1101" height="158" src="https://1.bp.blogspot.com/-8CHa8Jv7C7k/Xg9ltyt1qOI/AAAAAAACbIs/N31pRCEO-ykUXg-0clEJxhC1pB9A2dPNwCLcBGAsYHQ/s640/cf607top5.png" width="640" /></a></div>Round 607 followed on Sunday (<a href="https://codeforces.com/contest/1280">problems</a>, <a href="https://codeforces.com/contest/1280/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/72212">analysis</a>). This round got a quite different top 5, with only Radewoosh appearing in both. ksun48 got most of his speed advantage over Um_nik on the easier three problems, and then kept the lead by solving D and E in a comparable amount of time. Congratulations on the win!<br /><br />Thanks for reading, and check back for more!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/kUByqQvea94" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com6http://petr-mitrichev.blogspot.com/2020/01/a-generating-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-19510098443722830392020-01-03T18:48:00.002+03:002020-01-03T18:52:04.318+03:00An intriguing 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/-wqqMTJ0yEoc/Xg9cWbSB2zI/AAAAAAACbHg/U0jZBfP0X9ctOdVWOx59UFUaTQGsw7JQACLcBGAsYHQ/s1600/cf604top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="272" data-original-width="1106" height="156" src="https://1.bp.blogspot.com/-wqqMTJ0yEoc/Xg9cWbSB2zI/AAAAAAACbHg/U0jZBfP0X9ctOdVWOx59UFUaTQGsw7JQACLcBGAsYHQ/s640/cf604top5.png" width="640" /></a></div>Codeforces Round 604 took place during the Dec 2 - Dec 8 week (<a href="https://codeforces.com/contest/1264">problems</a>, <a href="https://codeforces.com/contest/1264/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/71995">analysis</a>). MiFaFaOvO has won the round, taking some advantage from the fact that problem E has <a href="https://codeforces.com/blog/entry/71916?#comment-562386">appeared before</a>, but still solving F in a bit more than half an hour while his competitors could not do that in an hour. Well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-rvEkgw1MSOU/Xg9bW-HvjKI/AAAAAAACbHY/CNUL2okZpFw36Y6uNyoveAhrcPsr8ORywCLcBGAsYHQ/s1600/oc1920beijingtop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="209" data-original-width="756" height="176" src="https://1.bp.blogspot.com/-rvEkgw1MSOU/Xg9bW-HvjKI/AAAAAAACbHY/CNUL2okZpFw36Y6uNyoveAhrcPsr8ORywCLcBGAsYHQ/s640/oc1920beijingtop5.png" width="640" /></a></div>Open Cup 2019-20 Grand Prix of Beijing wrapped up the week on Sunday (<a href="http://opencup.ru/index.cgi?data=macros/stage&head=index&menu=index&stg=9&region=main&ncup=ock&class=ock">results</a>, top 5 on the left). Team Past Glory has continued to break away in the overall standings, winning the round and solving all problems to boot (they would still have won even without solving D at the end of the contest). Congratulations on the win!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-DcDjohdn07g/Xg9iRkmdLBI/AAAAAAACbIE/_LUvAKZc9cwgOdWmDbsvypb2VuX7OONQgCLcBGAsYHQ/s1600/IMG_20191223_080142%2B%25281%2529.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="753" data-original-width="1600" height="300" src="https://1.bp.blogspot.com/-DcDjohdn07g/Xg9iRkmdLBI/AAAAAAACbIE/_LUvAKZc9cwgOdWmDbsvypb2VuX7OONQgCLcBGAsYHQ/s640/IMG_20191223_080142%2B%25281%2529.jpg" width="640" /></a></div>In <a href="https://petr-mitrichev.blogspot.com/2020/01/a-4-point-week.html">my previous summary</a>, I have mentioned <a href="https://codeforces.com/contest/1267/problem/I">my NEF problem</a>: there are 2<i>n</i> elements (<i>n</i>>=3). We can compare any two elements, and there are no equal ones, so one will compare bigger than the other. Our goal is to make such set of comparisons that uniquely determines the <i>n</i> biggest elements out of 2<i>n</i>, but <i>not</i> the ordering of those <i>n</i> elements. In other words, there must be at least two possible orderings of those <i>n</i> elements that are consistent with the outcomes of comparisons.<br /><br />For large values of <i>n</i>, since the <i>n</i> biggest elements can be determined in O(<i>n</i>) and sorting them requires O(<i>n</i>*log<i>n</i>), just applying any O(<i>n</i>) algorithm will do as we will not do enough comparisons to determine the order, and some randomized approaches also work. The real problem lies in tackling small values of <i>n</i>, roughly between 3 and 7.<br /><br />One could imagine that for such small inputs we could do some kind of exhaustive search, but it turns out that already for <i>n</i>=6 the state space is enormous as we have 12! possible inputs. Therefore, we need to come up with an actual algorithm :)<br /><br />Initially I did implement the exhaustive search to find a solution for <i>n</i>=3, and then came up with a way to obtain a solution for <i>n</i>+1 from a solution for <i>n</i>. However, together with Pavel Kunyavskiy we could come up with a simpler approach.<br /><br />Let us take arbitrary <i>n</i>+1 elements and split them arbitrarily into two groups of size at least 2, for example of size 2 and <i>n</i>-1. Now let's find the smallest element in each group in any possible way (using only comparisons within the group), and then compare those two elements between themselves. The one which compares smaller is the smallest among the <i>n</i>+1 chosen elements, and therefore is not among the <i>n</i> biggest elements, so we can discard it from consideration.<br /><br />Now let's add one more element to one of the two groups in such a way that both have size at least 2, and repeat the step above, discarding one more element from consideration. We repeat this until there are no more elements to add (discarding <i>n</i> elements in total).<br /><br />In the end we're left with the <i>n</i> biggest elements split into two groups, and we have never compared any element from the first group to any element of the second group, therefore there are at least two (more precisely, at least three) possible orderings of those <i>n</i> elements.<br /><br />Thanks for reading, and check back for more!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/uBnWR9Vgt7Q" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com0http://petr-mitrichev.blogspot.com/2020/01/an-intriguing-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-69127485569098547732020-01-03T18:04:00.001+03:002020-01-03T18:49:37.432+03:00A 4-point 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/-8fSQe4s2kgM/Xg8x4MnKc0I/AAAAAAACbGY/_dFR17o4s8kuV7RWg0NdmJu_6xb9zLL2ACLcBGAsYHQ/s1600/srm771top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="96" data-original-width="637" height="96" src="https://1.bp.blogspot.com/-8fSQe4s2kgM/Xg8x4MnKc0I/AAAAAAACbGY/_dFR17o4s8kuV7RWg0NdmJu_6xb9zLL2ACLcBGAsYHQ/s640/srm771top5.png" width="640" /></a></div>With TCO19 over, the qualification for TCO20 is well underway, and TopCoder SRM 771 was a part of that during the Nov 25 - Dec 1 week (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=17743">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17743&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://youtu.be/Y-kADKSd17U">my screencast</a>, <a href="https://www.topcoder.com/single-round-match-771-editorials/">analysis</a>). Tourist did all he can to bounce back from a resubmit on the 1000-pointer, found 175 challenge points but was just 2 points short to overtake majk with his <a href="https://codeforces.com/blog/entry/71752?#comment-560908">wonderful</a> 800+-point solution :) Congratulations to both!<br /><br />I was implementing the solution described in <a href="https://codeforces.com/blog/entry/71752?#comment-560920">this comment</a>, but an internal assertion kept failing on one of the samples. With just seconds left in the round I've removed the assertion and submitted, but of course it still failed the system tests. It turns out the idea was incorrect as well, but the system tests would not have caught that, so one could say I was close :) Luckily for me, many others have failed the system tests and I barely climbed into the top 10, so both myself and tourist gathered 4 points for the <a href="https://tco20.topcoder.com/competition-overview/algorithm/leaderboard">TCO20 qualification standings</a>.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-WcZpeUhLEAU/Xg8xE_ytLrI/AAAAAAACbGQ/Y3xRoRw_-ywayI_f0Pn4QsfccirwAyy1wCLcBGAsYHQ/s1600/neerc2019top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="269" data-original-width="1154" height="148" src="https://1.bp.blogspot.com/-WcZpeUhLEAU/Xg8xE_ytLrI/AAAAAAACbGQ/Y3xRoRw_-ywayI_f0Pn4QsfccirwAyy1wCLcBGAsYHQ/s640/neerc2019top5.png" width="640" /></a></div>On the ICPC side, the Northern Eurasia Finals took place in St. Petersburg, Barnaul, Tbilisi and Almaty on Sunday (<a href="http://nerc.itmo.ru/archive/2019/nerc-2019-statement.pdf">problems</a>, <a href="http://nerc.itmo.ru/archive/2019/standings.html">results</a>, top 5 on the left, <a href="https://www.youtube.com/watch?v=ZuzBPpBy-sE">broadcast</a>, <a href="https://codeforces.com/contest/1267/standings">online mirror results</a>, <a href="http://nerc.itmo.ru/archive/2019/nerc-2019-tutorial.pdf">analysis</a>). The strong favorite team NNSU Almost Retired did well but team SPbSU 25 was a bit faster and won, both teams at 10 problems while others got at most 9. Congratulations to both teams!<br /><br />In the online mirror, three teams placed above them but as I understand none of those are active/eligible for ICPC. Team Cafe Mountain in the 7th place actually is a current ICPC team competing for Seoul NU (please correct me if I'm wrong!)<br /><br />I have set the interactive <a href="https://codeforces.com/contest/1267/problem/I">problem I</a> for this round, which went like this: there are 2<i>n</i> elements (<i>n</i>>=3). We can compare any two elements, and there are no equal ones, so one will compare bigger than the other. Our goal is to make such set of comparisons that uniquely determines the <i>n</i> biggest elements out of 2<i>n</i>, but <i>not</i> the ordering of those <i>n</i> elements. In other words, there must be at least two possible orderings of those <i>n</i> elements that are consistent with the outcomes of comparisons. Can you come up with an algorithm with a requirement that it does not do something? :)<br /><br />Note that this would not be possible for <i>n</i>=2, as it might happen that the first two elements we try to compare are the two biggest elements, and thus we would learn a unique order for them.<br /><br />Thanks for reading, and check back for more!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/eN7MdJlXiJI" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com2http://petr-mitrichev.blogspot.com/2020/01/a-4-point-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-71724359108834758272020-01-02T12:20:00.002+03:002020-01-02T17:54:20.624+03:00A birthday 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/-6IQb-nwq8Sk/Xg2wkO8Ic5I/AAAAAAACbBI/4q8FxZ_X3NUJxATqm09arf6R1Dj9tmvEgCLcBGAsYHQ/s1600/cf601top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="272" data-original-width="1100" height="158" src="https://1.bp.blogspot.com/-6IQb-nwq8Sk/Xg2wkO8Ic5I/AAAAAAACbBI/4q8FxZ_X3NUJxATqm09arf6R1Dj9tmvEgCLcBGAsYHQ/s640/cf601top5.png" width="640" /></a></div>Codeforces hosted two rounds during the Nov 18 - Nov 24 week. Round 601 took place on Tuesday (<a href="https://codeforces.com/contest/1254">problems</a>, <a href="https://codeforces.com/contest/1254/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/71594">analysis</a>). Five contestants could solve all problems, and Radewoosh was quite a bit faster than others on problems C and D which gave him the victory. Well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-jvCZT1BvTpI/Xg2yRvpatfI/AAAAAAACbBU/qyLnGSFJunISJhWjEPn2TKJubbzC01kDACLcBGAsYHQ/s1600/cf602top5.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://1.bp.blogspot.com/-jvCZT1BvTpI/Xg2yRvpatfI/AAAAAAACbBU/qyLnGSFJunISJhWjEPn2TKJubbzC01kDACLcBGAsYHQ/s640/cf602top5.png" width="640" /></a></div>Round 602 followed on Sunday (<a href="https://codeforces.com/contest/1261">problems</a>, <a href="https://codeforces.com/contest/1261/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/71740">analysis</a>). This time even more competitors solved everything, and this time it was sunset who was slightly faster than others (some of whom <a href="https://codeforces.com/blog/entry/71678?#comment-560063">have made great sacrifices to compete</a>). Congratulations on the win!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-PTYoM2dhqQU/Xg2y446bu-I/AAAAAAACbBk/LhpQiMYmoewFxEi-6uX6Ce36ajgsMbgdACLcBGAsYHQ/s1600/IMG_20191220_081457%2B%25281%2529.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/-PTYoM2dhqQU/Xg2y446bu-I/AAAAAAACbBk/LhpQiMYmoewFxEi-6uX6Ce36ajgsMbgdACLcBGAsYHQ/s640/IMG_20191220_081457%2B%25281%2529.jpg" width="640" /></a></div>In <a href="https://petr-mitrichev.blogspot.com/2020/01/a-houston-week.html">my previous summary</a>, I have mentioned <a href="https://community.topcoder.com/stat?c=problem_statement&pm=15790&rd=17738">a TopCoder problem</a>: you are given three integers <i>n</i> (1<=<i>n</i><=10<sup>11</sup>), <i>d</i> (40<=<i>d</i><=120) and <i>b</i> (5<=<i>b</i><=62). Your goal is to return any base-<i>b</i> number that has exactly <i>d</i> digits when written without leading zeros, is divisible by <i>n</i>, and has <i>at most four distinct digits</i> when written in base-<i>b</i> without leading zeros.<br /><br />I have found the correct idea almost immediately after reading the problem: we need to somehow make use of <a href="https://en.wikipedia.org/wiki/Birthday_problem">the birthday paradox</a>, which is closely related to meet-in-the-middle algorithm. Roughly speaking, if we generate random numbers, then after generating O(sqrt(<i>n</i>)) numbers we will have generated two that have the same remainder modulo <i>n</i>.<br /><br />However, it is important to find the right way to apply it. My approach was to split the number in two parts, keep generating random numbers with the same four distinct digits for the first and second part, and wait until we generate two that add up to 0 modulo <i>n</i>. This is not an exact application of the birthday paradox as we have two different random distributions rather than one, therefore it no longer guarantees that we're going to find such pair after generating just O(sqrt(<i>n</i>)) numbers. However, there is a hand-wavy argument: remainders modulo <i>n</i> of such large numbers are more or less random both for the first and for the second part, therefore the birthday paradox should still apply.<br /><br />Unfortunately, there are cases where the distribution is not random at all. For example, when <i>b</i>=10 and <i>n</i>=10<sup>11</sup>, all digits before the 11-th one from the end do not affect the remainder modulo <i>n</i>, and therefore all randomly generated first parts will have remainder 0, therefore we'll need on the order of 10<sup>11</sup> randomly generated second parts in order to find a match, instead of sqrt(10<sup>11</sup>). This case is easy to handle separately of course, as we can just include "all zeros" as one of the candidates for the second part. However, there are more tricky cases where gcd(<i>n</i>,<i>b</i>)>1, or when gcd(<i>n</i>,<i>b</i>-1)>1. I have managed to find a way to make this solution pass the system tests, but it was a very dangerous thing to do and the solution could have easily failed.<br /><br />The right idea is to find a way to apply the birthday paradox directly. Let's generate random numbers of the full length until we find two that give the same remainder modulo <i>n</i>, this is bound to happen within O(sqrt(10<sup>11</sup>)) steps. The difference between these two is divisible by <i>n</i>, but there are two issues:<br /><ul style="text-align: left;"><li>the difference might have less than <i>d</i> digits</li><li>even if each of the numbers has only four distinct digits, the difference might have more</li></ul>It turns out that both issues can be taken care of if we generate random numbers consisting only of digits 0 and 1 in our process. The difference of any two such numbers will have only digits 0, 1, <i>b</i>-2 and <i>b</i>-1, satisfying the at most four distinct digits constraint. And in case the difference has less than <i>d</i> digits, we can just append enough zeros at the end since zero is one of the allowed digits, and appending zeros keeps the number divisible by <i>n</i>.<br /><br />This solution provably terminates within O(sqrt(10<sup>11</sup>)) steps with very high probability, and one can submit it with confidence. Note that the fact that we generate numbers consisting only of digits 0 and 1, and therefore their remainders modulo <i>n</i> might not be uniformly distributed, does not hurt us: if the choices are not uniformly distributed, the birthday paradox collision just becomes more likely.<br /><br />Thanks for reading, and check back for more!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/EIP3ezs-Ulg" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com0http://petr-mitrichev.blogspot.com/2020/01/a-birthday-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-84131243725149533102020-01-01T01:03:00.000+03:002020-01-01T01:03:06.512+03:00A Houston week<div dir="ltr" style="text-align: left;" trbidi="on">The Nov 11 - Nov 17 week was the week of TopCoder Open finals in Houston.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-985D8s7M1GQ/Xgt1emyt3jI/AAAAAAACa5g/HpaQUYrW3GE_QR8sHU31_yQ6yhrjftgvgCLcBGAsYHQ/s1600/tco19semi1top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="215" data-original-width="766" height="178" src="https://1.bp.blogspot.com/-985D8s7M1GQ/Xgt1emyt3jI/AAAAAAACa5g/HpaQUYrW3GE_QR8sHU31_yQ6yhrjftgvgCLcBGAsYHQ/s640/tco19semi1top5.png" width="640" /></a></div>The first semifinal took place on Thursday (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=17726">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17726&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a> on the left, <a href="https://youtu.be/lzUO_WmJQ-I?t=1895">broadcast</a>, <a href="https://twitter.com/i/status/1195052483887976451">my Twitter thread</a>, <a href="https://www.topcoder.com/2019-tco-algorithm-semi-final-1-editorials/">analysis</a>). The easy problem was quite tricky and the sample cases did not really help check correctness, so the first five submissions in <a href="https://twitter.com/PetrMitrichev/status/1195056854067486721/photo/1">this photo</a> were all incorrect. tourist, Egor and scott_wu later resubmitted, and this turned out crucial for Egor who was able to advance on the easy and medium. tourist, lyrically and uwi solved the hard as well, and therefore it did not actually matter if their easy was correct. Congratulations to the four finalists!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-4ZzG3C4_Ny8/Xgt3rjYBe3I/AAAAAAACa54/MsHqGLBJLKwKGqWXgeMkWEZbAdCymBoTACLcBGAsYHQ/s1600/tco19semi2top8.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="213" data-original-width="763" height="178" src="https://1.bp.blogspot.com/-4ZzG3C4_Ny8/Xgt3rjYBe3I/AAAAAAACa54/MsHqGLBJLKwKGqWXgeMkWEZbAdCymBoTACLcBGAsYHQ/s640/tco19semi2top8.png" width="640" /></a></div>The second semifinal followed on Friday (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=17738">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17738&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a> on the left, <a href="https://youtu.be/IvoPvHqF4Tk">broadcast</a>, <a href="https://www.topcoder.com/2019-tco-algorithm-semi-final-2-editorials/">analysis</a>). Five competitors solved everything during the coding phase, and I was in fourth place but with less than 25 point gap to the fifth. During the intermission, I have correctly concluded that it only makes sense for me to challenge one of the other three contestants, since if any solution of the first five fails, and it's not my solution, then I would advance anyway. However, right after the challenge phase started I've opened Um_nik's 1000, noticed that it does not handle a special case that I had to handle in my solution, and challenged with it. The challenge was unsuccessful, and I dropped to fifth place.<br /><br />Luckily, it did not end that way and got even curioser after ecnerwal found two unsuccessful challenges of his own, and dropped below me — imagine how surprised and relieved I was at that point :) It turned out that he already knew that his medium was going to fail, so the challenge phase did not matter in the end as everybody who solved three problems advanced to the finals. Congratulations to xudyh, Um_nik and mnbvmar!<br /><br />Here is <a href="https://community.topcoder.com/stat?c=problem_statement&pm=15790&rd=17738">the 1000-pointer</a> that got me so excited that I failed to exercise good challenge phase judgement: you are given three integers <i>n</i> (1<=<i>n</i><=10<sup>11</sup>), <i>d</i> (40<=<i>d</i><=120) and <i>b</i> (5<=<i>b</i><=62). Your goal is to return any base-<i>b</i> number that has exactly <i>d</i> digits when written without leading zeros, is divisible by <i>n</i>, and has <i>at most four distinct digits</i> when written in base-<i>b</i> without leading zeros.<br /><br />Can you see a way to solve it without having to handle any special cases?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-JlA7Te-LshY/Xgt4PKK775I/AAAAAAACa6A/CbVSChzqFhcGSsQhbMCyo4BzvVr45JV6QCLcBGAsYHQ/s1600/tco19finaltop8.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="214" data-original-width="772" height="176" src="https://1.bp.blogspot.com/-JlA7Te-LshY/Xgt4PKK775I/AAAAAAACa6A/CbVSChzqFhcGSsQhbMCyo4BzvVr45JV6QCLcBGAsYHQ/s640/tco19finaltop8.png" width="640" /></a></div>The final round completed the competition on Saturday (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=17741">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17741&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a> on the left, <a href="https://youtu.be/LLXREXaGNCE">broadcast</a>, <a href="https://youtu.be/qu6td2smaX4">my screencast</a>, <a href="https://www.topcoder.com/2019-tco-algorithm-finals/">analysis</a>). I got stuck in the easy problem, trying to be too clever and to avoid constructing the graph explicitly backfired, and I could not debug my solution during the round. I am notoriously bad at giving up on a problem, and it always felt that I was so close :) I have eventually switched to the hard problem and almost got it right — but only almost. The solution I submitted at the end did not even pass the samples, and it turned out that even though it had 5 different bugs, all were of "j instead of i" kind and probably preventable if I was coding it in less of a rush.<br /><br />This is exactly what lyrically did, as she started with the hard problem and spent most of the contest solving it, and ended up being the only competitor to do so. In fact, the situation was <a href="https://codeforces.com/blog/entry/71439?#comment-558467">a bit more complicated</a> as her solution has initially failed my challenge case as well, but it turned out that my challenge case has exposed an issue with the problem itself: it seemed virtually impossible to return an output that would pass the checker because of floating-point precision issues. The admins were put in a difficult spot, and ultimately decided to let me keep the 50 challenge points, but also lowered the required precision and let lyrically's solution pass.<br /><br />I did not realize myself that the problem was broken, and simply tried to put together a challenge case that could expose potential precision issues in other solutions.<br /><br />In any case, all this did not affect the first place as tourist was the undisputed champion with good times on easy and medium. Huge congratulations!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-KsT5aDGw8zw/Xgt5u7EnioI/AAAAAAACa6M/3HPoOFnyuHYJgKHx8xEJti8EcY5PvO1vQCLcBGAsYHQ/s1600/lockout0results.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="856" data-original-width="1600" height="342" src="https://1.bp.blogspot.com/-KsT5aDGw8zw/Xgt5u7EnioI/AAAAAAACa6M/3HPoOFnyuHYJgKHx8xEJti8EcY5PvO1vQCLcBGAsYHQ/s640/lockout0results.png" width="640" /></a></div>Right after the final round, scott_wu and ecnerwal ran a fun double-elimination competition in a new 1:1 format called <i>Lockout</i> (<a href="https://codeforces.com/blog/entry/72557">more info</a>, <a href="https://challonge.com/lockout0">results</a> on the left), trying to make competitive programming more exciting to watch<i>.</i> The competition was indeed very fast-paced and had a lot of plot twists depending on the strategy choices. The format before the last round has placed quite a lot of emphasis on the speed of solving easy problems, though, as all problems cost 1 point. The last round of the competition, the <a href="https://codeforces.com/blog/entry/72667">Grand Finals</a> where tourist met Um_nik, took place much later, had different point values and a <a href="https://youtu.be/Dk-nWqwyE8g?t=1275">very nice broadcast</a> — check it out! And of course congratulations to tourist on winning the whole thing :)<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-GmWdpQdYBDY/Xgt7JyjdFdI/AAAAAAACa6Y/gy4DWudm0Q0CamYN6Ww0f3c1UxK-FOSkwCLcBGAsYHQ/s1600/IMG_20191212_115855.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/-GmWdpQdYBDY/Xgt7JyjdFdI/AAAAAAACa6Y/gy4DWudm0Q0CamYN6Ww0f3c1UxK-FOSkwCLcBGAsYHQ/s640/IMG_20191212_115855.jpg" width="640" /></a></div>In <a href="https://petr-mitrichev.blogspot.com/2019/12/an-exponential-week.html">my previous summary</a>, I have mentioned an Open Cup problem: there are <i>n</i> drones (<i>n</i><=500000), the <i>i</i>-th drone initially in the point (<i>x<sub>i</sub></i>,<i>y<sub>i</sub></i>,0). Some pairs of drones are connected with cables, those cables are straight lines and they <i>do not intersect</i> except at endpoints. We are then performing <i>k</i> moves (<i>k</i><=500000), in each move we change the z-coordinate of one of the drones (x- and y-coordinates always remain constant). The cables connected to this drone have to change their length correspondingly, and each cable has a known maximum length — in case it needs to become longer than that, it breaks and stays broken for the remainder of the process. Finally, you are given <i>q</i> (<i>q</i><=500000) queries, each query being a pair of drones. For each query, you need to find the move which caused the two given drones to become disconnected (using the cables), if any.<br /><br />If we find out for each cable at which move does it break, the processing of <i>q</i> "when did these two vertices become disconnected" queries offline is a standard problem that is solved by going in reverse order of time and keeping a set of connected components and for each component keeping a list of queries with at least one end in it, and traversing this list for the smaller component when merging two of them.<br /><br />Finding out the moment each cable breaks is the more interesting part of the problem. A naive approach would traverse all cables connected to the vertex being moved at each step, but that would of course be quadratic in case our graph is a star.<br /><br />How can we improve the performance of our solution on the star graph? We can notice that we can process the outer vertices of the star quickly as the have only one incident edge, the slowdown only arises when we move the center vertex. In order to process the movements of the center vertex faster, we can notice that for each particular edge, the values of z-coordinate where the corresponding cable does not break form a segment, therefore there are two interesting values — the endpoints of this segment — which should trigger the breakage. We can put all interesting values for the center vertex into a data structure, then whenever we move the center vertex we can just query the data structure to retrieve all interesting values that we have passed when moving from the old value of z-coordinate to the new one, and break the corresponding edges.<br /><br />Since every edge breaks at most once, this will have the total running time of O(<i>m</i>*log<i>m</i>) where <i>m</i> is the number of edges, and assuming the data structure can retrieve the next edge to break in O(log<i>m</i>). We can use a balanced tree or a pair of priority queues as the data structure.<br /><br />Note that we should also update this data structure for the center vertex when processing the outer vertices, as the interesting values for the corresponding edge will change, but since each outer vertex has only one incident edge this is also O(log<i>m</i>).<br /><br />How do we generalize this improvement from the star graph to an arbitrary graph? Let's choose an orientation for each edge. Whenever we move a vertex, we will process its outgoing edges directly. For the incoming edges, we will maintain the data structure with the interesting values of z-coordinate and query it for the new breakages. We also need to update this data structure for the neighboring vertices for each outgoing edge. If the maximum out-degree of a vertex is <i>d</i>, this solution runs in O((<i>k</i>*<i>d</i>+<i>m</i>)*log<i>m</i>).<br /><br />Now the standard idea would be to orient each edge from the vertex of the smaller degree to the vertex of the larger degree. This would mean that the out-degree of each vertex is at most sqrt(2<i>m</i>), since there can't be more than sqrt(2<i>m</i>) vertices each of degree sqrt(2<i>m</i>) adjacent to a vertex, since the sum of all degrees is 2<i>m</i>. I have managed to squeeze this solution in, but it required some extra optimizations.<br /><br />However, we can make use of the fact that the cables do not intersect, in other words that our graph is <i>planar</i>. Each planar graph has a vertex of degree at most 5. So we can do the following: repeatedly take the vertex with the smallest number of adjacent non-oriented edges, and orient those edges from this vertex. This will give us an orientation where all out-degrees do not exceed 5, so our complexity becomes just O((<i>k</i>+<i>m</i>)*log<i>m</i>) and no squeezing is required :)<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-o5ym0MIeKN4/XgvFRQDafDI/AAAAAAACa90/FXL3PRsbB2wALmZ8hEI40gc4TsRmDSv9QCLcBGAsYHQ/s1600/IMG_20191212_120827.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/-o5ym0MIeKN4/XgvFRQDafDI/AAAAAAACa90/FXL3PRsbB2wALmZ8hEI40gc4TsRmDSv9QCLcBGAsYHQ/s640/IMG_20191212_120827.jpg" width="640" /></a></div>Finally, now is a good time to remind you about the <a href="https://codeforces.com/blog/entry/72651">New Year Prime contest</a>, where you can try your hand at solving the problems from 2019 that were not solved by anybody in contest time. Best of luck, and Happy New Year!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/fwyll1eLbSE" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com2http://petr-mitrichev.blogspot.com/2020/01/a-houston-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-55163577770399797642019-12-31T13:37:00.000+03:002019-12-31T13:37:49.930+03:00An exponential 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/-BFZUsc2r8TU/XgYNNsEEAoI/AAAAAAACayU/BkI3DowdFNglxfxxe4zBg5gwvKLJRsFLwCLcBGAsYHQ/s1600/oc1920siberiatop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="234" data-original-width="712" height="210" src="https://1.bp.blogspot.com/-BFZUsc2r8TU/XgYNNsEEAoI/AAAAAAACayU/BkI3DowdFNglxfxxe4zBg5gwvKLJRsFLwCLcBGAsYHQ/s640/oc1920siberiatop5.png" width="640" /></a></div>Before we come to the Nov 4 - Nov 10 week, I've realized that I forgot to cover the Open Cup 2019-20 Grand Prix of Siberia that took place on Nov 3 (<a href="https://olympic.nsu.ru/files/problems_2_0.pdf">problems</a>, <a href="http://opencup.ru/index.cgi?data=macros/stage&head=index&menu=index&stg=7&region=main&ncup=ock&class=ock">results</a>, top 5 on the left). Team USA1 was once again the fastest, but Team Past Glory got their third stage win thanks to solving 11 problems in 11 submissions. Amazing accuracy!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-_DbLvW3DLcM/Xgskus7th6I/AAAAAAACa4Q/xrXrxyXTCtwdhUDHT85yQ47jw-YXBpOlgCLcBGAsYHQ/s1600/IMG_20191211_121423.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/-_DbLvW3DLcM/Xgskus7th6I/AAAAAAACa4Q/xrXrxyXTCtwdhUDHT85yQ47jw-YXBpOlgCLcBGAsYHQ/s640/IMG_20191211_121423.jpg" width="640" /></a></div>One other very notable thing from the Oct 28 - Nov 3 week that I forgot to mention was <a href="https://codeforces.com/blog/entry/70740">this post</a> by ouuan which highlighted <a href="https://min-25.hatenablog.com/entry/2018/03/19/235802">this post</a> by min_25. It turns out that the "successive shortest paths" min-cost-max-flow algorithm that I was taught a long time ago and was implementing ever since is actually exponential, and can time out on graphs as small as 50 vertices! Before this post, I have assumed that it's actually polynomial, and even if the power of that polynomial is high, it is fast enough on graphs with thousands of edges. I guess some people in the community already knew this as the original post in Japanese is from 1.5 years ago, but it was news for me and maybe for you as well :)<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-8WgZh_QOlvc/XgYO6XgWV5I/AAAAAAACayk/3G1WCJmA16A_Oz9F9NVFaaKkKX_kL8JvgCLcBGAsYHQ/s1600/cf599to5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="273" data-original-width="1123" height="154" src="https://1.bp.blogspot.com/-8WgZh_QOlvc/XgYO6XgWV5I/AAAAAAACayk/3G1WCJmA16A_Oz9F9NVFaaKkKX_kL8JvgCLcBGAsYHQ/s640/cf599to5.png" width="640" /></a></div>Coming back to the main topic of this summary, the Nov 4 - Nov 10 week, Codeforces Round 599 took place on Wednesday (<a href="https://codeforces.com/contest/1242">problems</a>, <a href="https://codeforces.com/contest/1242/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/71216">analysis</a>). Problems D and E were both quite hard to get, and Benq got E, which gives more points, reasonably fast. It means that he won the round and jumped to the first place in the rating list — huge congratulations!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-uN_QtCmfvi8/XgYODPbO4OI/AAAAAAACayc/P1quDTeVC5M7sDGA4MjosRcPNVJeQzfAQCLcBGAsYHQ/s1600/oc1920polandtop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="234" data-original-width="726" height="206" src="https://1.bp.blogspot.com/-uN_QtCmfvi8/XgYODPbO4OI/AAAAAAACayc/P1quDTeVC5M7sDGA4MjosRcPNVJeQzfAQCLcBGAsYHQ/s640/oc1920polandtop5.png" width="640" /></a></div>The Open Cup returned with the Grand Prix of Poland on Sunday (<a href="https://amppz.tcs.uj.edu.pl/2019/data/amppz-en.pdf">problems</a>, <a href="http://opencup.ru/index.cgi?data=macros/stage&head=index&menu=index&stg=8&region=main&ncup=ock&class=ock">results</a>, top 5 on the left, <a href="https://amppz.tcs.uj.edu.pl/2019/data/amppz-slajdy.pdf">analysis in Polish</a>). This time team Past Glory actually had more incorrect attempts than the only other team that solved all problems, but they had enough speed advantage to overcome that. Congratulations to them and to the team japan02!<br /><br />Problem E used a nice trick that I did not know before. There are <i>n</i> drones (<i>n</i><=500000), the <i>i</i>-th drone initially in the point (<i>x<sub>i</sub></i>,<i>y<sub>i</sub></i>,0). Some pairs of drones are connected with cables, those cables are straight lines and they <i>do not intersect</i> except at endpoints. We are then performing <i>k</i> moves (<i>k</i><=500000), in each move we change the z-coordinate of one of the drones (x- and y-coordinates always remain constant). The cables connected to this drone have to change their length correspondingly, and each cable has a known maximum length — in case it needs to become longer than that, it breaks and stays broken for the remainder of the process. Finally, you are given <i>q</i> (<i>q</i><=500000) queries, each query being a pair of drones. For each query, you need to find the move which caused the two given drones to become disconnected (using the cables), if any.<br /><br />The time limit is 30 seconds, so some O(<i>n</i>*sqrt(<i>n</i>)) or even O(<i>n</i>*sqrt(<i>n</i>*log(<i>n</i>))) solutions could pass. Can you see a O(<i>n</i>*polylog(<i>n</i>)) approach, though?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-Zvp3EhyLSQs/Xgsko1svoLI/AAAAAAACa4M/3EL0XyTZcvsfEJ46Ew2D2fxphb-FNFHpwCLcBGAsYHQ/s1600/IMG_20191211_115814.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/-Zvp3EhyLSQs/Xgsko1svoLI/AAAAAAACa4M/3EL0XyTZcvsfEJ46Ew2D2fxphb-FNFHpwCLcBGAsYHQ/s640/IMG_20191211_115814.jpg" width="640" /></a></div>In <a href="https://petr-mitrichev.blogspot.com/2019/12/a-week-to-make-1.html">my previous summary</a>, I have mentioned <a href="https://atcoder.jp/contests/agc040/tasks/agc040_c">an AtCoder problem</a>: a string of even length of characters <span style="font-family: "courier new" , "courier" , monospace;">A</span>, <span style="font-family: "courier new" , "courier" , monospace;">B</span> and <span style="font-family: "courier new" , "courier" , monospace;">C</span> is called <i>valid</i> if you can reduce it to an empty string by repeating the following operation: take any substring of length 2 that is neither <span style="font-family: "courier new" , "courier" , monospace;">A</span><span style="font-family: "courier new" , "courier" , monospace;">B</span> nor <span style="font-family: "courier new" , "courier" , monospace;">B</span><span style="font-family: "courier new" , "courier" , monospace;">A</span>, and erase it (pushing the two remaining parts back together). You are given an even number <i>n</i> up to 10<sup>7</sup>. How many strings of length <i>n</i> are valid, modulo 998244353?<br /><br />The problem becomes much easier if we make the following substitution: let's take our string, and in every second position (for example, in all even positions) we replace every <span style="font-family: "courier new", courier, monospace;">A</span> with <span style="font-family: "courier new", courier, monospace;">B</span> and vice versa. Each substring that used to be <span style="font-family: "courier new" , "courier" , monospace;">A</span><span style="font-family: "courier new" , "courier" , monospace;">B</span> or <span style="font-family: "courier new" , "courier" , monospace;">B</span><span style="font-family: "courier new" , "courier" , monospace;">A</span> will then become <span style="font-family: "courier new" , "courier" , monospace;">A</span><span style="font-family: "courier new", courier, monospace;">A</span> or <span style="font-family: "courier new" , "courier" , monospace;">B</span><span style="font-family: "courier new", courier, monospace;">B</span>! Therefore we can now erase any substring of length 2 that is neither <span style="font-family: "courier new" , "courier" , monospace;">A</span><span style="font-family: "courier new", courier, monospace;">A</span> nor <span style="font-family: "courier new" , "courier" , monospace;">B</span><span style="font-family: "courier new", courier, monospace;">B</span>, in other words we can erase any substring of length 2 which has at most 1 occurrence of both <span style="font-family: "courier new", courier, monospace;">A</span> and <span style="font-family: "courier new", courier, monospace;">B</span>. It is relatively easy to notice that it is impossible only if more than half of all characters of our string are <span style="font-family: "courier new", courier, monospace;">A</span>, or more than half of all characters of our string are <span style="font-family: "courier new", courier, monospace;">B</span>. Counting such strings of the given length can be done using combination numbers.<br /><br />Thanks for reading, and check back for more!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/idV-ux0o3B0" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com0http://petr-mitrichev.blogspot.com/2019/12/an-exponential-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-3137100019862168502019-12-27T02:00:00.002+03:002019-12-27T02:00:50.992+03:00A week to make 1<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/-pwanqLgDJ-w/XgUvaTjhILI/AAAAAAACaw8/uovp_WvBNqokW7dVZyknilqjHHxBkgxggCLcBGAsYHQ/s1600/srm770top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="99" data-original-width="636" src="https://1.bp.blogspot.com/-pwanqLgDJ-w/XgUvaTjhILI/AAAAAAACaw8/uovp_WvBNqokW7dVZyknilqjHHxBkgxggCLcBGAsYHQ/s1600/srm770top5.png" /></a></div>The Oct 28 - Nov 3 week had two weekend rounds. TopCoder SRM 770 was the first (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=17723">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17723&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://youtu.be/3oIrxt5Btvc">my screencast with commentary</a>). bqi343 has demonstrated excellent raw speed and was ahead by a bit less than 100 points before the challenge phase, but then tourist has added his excellent challenge form to the mix and overtook bqi343. Congratulations to both!<br /><br />I was struggling quite a bit in this round, and ended up solving both the 450 and the 900 with the solutions that were more complex than the intended ones. For the 450, instead of a direct min-cost-max-flow formulation, I've used <a href="https://community.topcoder.com/stat?c=problem_solution&rd=17723&rm=333188&cr=10574855&pm=15702">a combination</a> of min-cost matching of the given size and greedy which might or might not be equivalent.<br /><br />For the 900, I've taken the solution that was intended to fail because of precision issues and <a href="https://community.topcoder.com/stat?c=problem_solution&rm=333188&rd=17723&pm=15687&cr=10574855">made it pass</a> using quite some squeezing, including switching to C++ to use long double and having a magic constant of 1.02 that allowed to balance between time limit exceeded and floating point overflow (it turned out that it was possible to squeeze in this solution in Java using doubles, too — but only with the magic constant equal to 1.007, while 1.008 led to overflows and 1.005 to time limit exceeded).<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-noFJUuhuKXg/XgU1GEY-7uI/AAAAAAACaxI/YH0ZOTOwjts6me4oslihH3HJ6jQaSiDSQCLcBGAsYHQ/s1600/agc040top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="343" data-original-width="829" height="264" src="https://1.bp.blogspot.com/-noFJUuhuKXg/XgU1GEY-7uI/AAAAAAACaxI/YH0ZOTOwjts6me4oslihH3HJ6jQaSiDSQCLcBGAsYHQ/s640/agc040top5.png" width="640" /></a></div>AtCoder Grand Contest 040 followed on Sunday (<a href="https://atcoder.jp/contests/agc040/tasks">problems</a>, <a href="https://atcoder.jp/contests/agc040/standings">results</a>, top 5 on the left, <a href="https://youtu.be/_k7ADEJGrTM">my screencast with commentary in Russian</a>, <a href="https://img.atcoder.jp/agc040/editorial.pdf">analysis</a>). The same two contestants occupied the top two spots as in the SRM, but the margin was much bigger this time, with tourist solving five problems a good half an hour before the others. Well done!<br /><br />This was already the fifth AGC authored by maroonrk this year — amazing productivity at such high level! My <a href="https://img.atcoder.jp/file/GP30.html">GP30 scores</a> for those are 29, 100, 0, 0, 2 :) While it started nicely, I seem to be unable to crack his problems in most recent rounds (I think I did skip one of the rounds altogether, though).<br /><br />I was mostly stuck with problem D in this round, but let me highlight <a href="https://atcoder.jp/contests/agc040/tasks/agc040_c">problem C</a> which uses an <a href="https://codeforces.com/blog/entry/70988?#comment-556200">apparently well-known</a> but still beautiful trick: a string of even length of characters <span style="font-family: Courier New, Courier, monospace;">A</span>, <span style="font-family: Courier New, Courier, monospace;">B</span> and <span style="font-family: Courier New, Courier, monospace;">C</span> is called <i>valid</i> if you can reduce it to an empty string by repeating the following operation: take any substring of length 2 that is neither <span style="font-family: Courier New, Courier, monospace;">A</span><span style="font-family: Courier New, Courier, monospace;">B</span> nor <span style="font-family: Courier New, Courier, monospace;">B</span><span style="font-family: "Courier New", Courier, monospace;">A</span>, and erase it (pushing the two remaining parts back together). You are given an even number <i>n</i> up to 10<sup>7</sup>. How many strings of length <i>n</i> are valid, modulo 998244353?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-V10eNPyFQzM/XgU7JLm7c3I/AAAAAAACaxs/qQX1fjoi8CM9J7SZeK1qIrdfk0oyLrAAQCLcBGAsYHQ/s1600/IMG_20191206_131623%2B%25281%2529.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1600" data-original-width="1146" height="640" src="https://1.bp.blogspot.com/-V10eNPyFQzM/XgU7JLm7c3I/AAAAAAACaxs/qQX1fjoi8CM9J7SZeK1qIrdfk0oyLrAAQCLcBGAsYHQ/s640/IMG_20191206_131623%2B%25281%2529.jpg" width="458" /></a></div>In <a href="https://petr-mitrichev.blogspot.com/2019/12/a-3-person-week.html">my previous summary</a>, I have mentioned <a href="https://codeforces.com/contest/1246/problem/E">a Codeforces problem</a>: you have <i>n</i><=16 positive integers such that their sum does not exceed 2000 (let's denote that constraint as <i>m</i>), and another integer <i>k</i>, 2<=<i>k</i><=2000. All <i>n</i> integers are not divisible by <i>k</i>. In one step, we can erase two numbers and instead write their sum divided by <i>k</i> repeatedly until the result is no longer divisible by <i>k</i>. For example, if <i>k</i>=2 and we have numbers 5 and 19, we can erase them and instead write 3 as 3=(5+19)/2/2/2 and 3 is not divisible by 2. Our goal is to end up with having just the number 1.<br /><br />The solution with a 3<sup><i>n</i></sup> term in its complexity is somewhat straightforward: for each subset of numbers, we will compute which integers we can obtain from them. To process a subset, we will iterate over all ways to split it into two subsets which will be collapsed into the last two numbers we erase for this subset to obtain its final number, and over all possibilities for those two numbers. Since all numbers we get do not exceed <i>m</i>, and the number of (set, subset) pairs is 3<sup><i>n</i></sup>, this solution runs in O(3<sup><i>n</i></sup>*<i>m</i><sup>2</sup>) which is too slow.<br /><br />The key to obtaining a faster solution lies in an observation that looks almost trivial from the first glance: since each number is divided by <i>k</i> one or more times, either by itself or after being added to some other numbers, in the end we represent one as 1=sum(<i>a</i><sub><i>i</i></sub>*<i>k</i><sup>-<i>b</i><sub><i>i</i></sub></sup>). It turns out that the inverse is also true: if we can find the values of <i>b</i><sub><i>i</i></sub> that satisfy the above equation, then there is a way to collapse everything into 1. To see that, we can find the highest value among <i>b</i><sub><i>i</i></sub>, notice that it will be repeated at least twice (as otherwise sum(<i>a</i><sub><i>i</i></sub>*<i>k</i><sup>-<i>b</i><sub><i>i</i></sub></sup>) will not be an integer), and therefore we can take the two <i>a</i><sub><i>i</i></sub>'s corresponding to the highest value among <i>b</i><sub><i>i</i></sub> and combine them according to the procedure to the problem statement to get a smaller set of values <i>a'</i><sub><i>i</i></sub> and <i>b'</i><sub><i>i</i></sub> where 1=sum(<i>a'</i><sub><i>i</i></sub>*<i>k</i><sup>-<i>b'</i><sub><i>i</i></sub></sup>) still holds.<br /><br />We have reformulated our problem in a more mathematical way, but did we actually change anything compared to the original formulation? It turns out we did, as now our search can disregard the tree-like order in which we combine the elements in the original formulation. Instead, let's accumulate the terms of sum(<i>a</i><sub><i>i</i></sub>*<i>k</i><sup>-<i>b</i><sub><i>i</i></sub></sup>) in decreasing order of <i>b</i><sub><i>i</i></sub>. Note that this is not equivalent to the original tree-like order even though the first two elements being joined are the same (two with the highest value of <i>b</i><sub><i>i</i></sub>). The joins after those first two elements can be different, as it can happen that we divide their sum by <i>k</i> a lot of times.<br /><br />Accumulating in decreasing order of <i>b</i><sub><i>i</i></sub> can be reformulated in the following way: we have our current sum <i>s</i> that starts with 0, and can do two things with it: either we take a number <i>a</i><sub><i>i</i></sub> that was not previously taken and add it to the sum (<i>s</i>+=<i>a</i><sub><i>i</i></sub>), or we divide the sum by <i>k</i> (<i>s</i>/=<i>k</i>). Note that we can only divide the sum by <i>k</i> when the current sum is divisible, but unlike the original process from the problem statement we are not forced to divide if it is.<br /><br />This means that the dynamic programming which computes "what value of <i>s</i> can be obtained if we have taken the numbers from a given set" does not need to iterate over subsets, and instead can add items one by one, leading to O(<i>n</i>*2<sup><i>n</i></sup>*<i>m</i>) complexity.<br /><br />Thanks for reading, and check back for more!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/gVs8WZFAD_M" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com0http://petr-mitrichev.blogspot.com/2019/12/a-week-to-make-1.htmltag:blogger.com,1999:blog-1953325079793449971.post-51711441453925989822019-12-26T00:39:00.001+03:002019-12-26T01:49:57.106+03:00A 3-person 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/-9taJjmRFJxk/XgPgh3wQbXI/AAAAAAACauk/R06TQ3jnrcgNW8ptM-kx11Pvc3faNka6ACLcBGAsYHQ/s1600/fbhc2019finaltop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="411" data-original-width="1099" height="238" src="https://1.bp.blogspot.com/-9taJjmRFJxk/XgPgh3wQbXI/AAAAAAACauk/R06TQ3jnrcgNW8ptM-kx11Pvc3faNka6ACLcBGAsYHQ/s640/fbhc2019finaltop5.png" width="640" /></a></div>Facebook Hacker Cup 2019 Final in Dublin was the main event of the Oct 21 - Oct 27 week (<a href="https://www.facebook.com/hackercup/problem/546199162815522/">problems</a>, <a href="https://www.facebook.com/hackercup/scoreboard/327966064573355/?filter=everyone">results</a>, top 5 on the left, <a href="https://www.facebook.com/hackercup/videos/783011162119849/">results announcement video</a>, <a href="https://www.facebook.com/hackercup/videos/419438048968346/">recap video</a>, <a href="https://www.facebook.com/notes/facebook-hacker-cup/hacker-cup-2019-final-round-solutions/3069366303079250/">analysis</a>). Gennady was so much faster solving the first few problems that he could afford to test his solution for the last one extensively, giving myself a glimmer of hope as I was the first to finish all solutions. It turned out to be just that, a glimmer of hope :) Congratulations to Gennady!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-tuiE45npIH4/XgO_qkDzNpI/AAAAAAACas4/xlRkVn-SuQwYKEsJuMShvxFZQvQg7_2NACLcBGAsYHQ/s1600/cf596top5.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://1.bp.blogspot.com/-tuiE45npIH4/XgO_qkDzNpI/AAAAAAACas4/xlRkVn-SuQwYKEsJuMShvxFZQvQg7_2NACLcBGAsYHQ/s640/cf596top5.png" width="640" /></a></div>Codeforces Round 596 happened a day later (<a href="https://codeforces.com/contest/1246">problems</a>, <a href="https://codeforces.com/contest/1246/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/70898">analysis</a>). Benq ended up winning the round after he found 10 successful challenges and wxhtxdy's solution for F exceeded the time limit. There was a bit of luck involved as not all rooms even had so many incorrect submissions available for challenging, but still finding and executing those challenges is no small feat. Congratulations to Benq!<br /><br />I have ruined my contest by trying to squeeze in a solution for E that was just too slow. I got into this very bad state where I thought repeatedly that after one more small optimization it will work, while having no proof that it will be the case. My solution had a 3<sup><i>n</i></sup> term in its complexity, while the correct one only has a 2<sup><i>n</i></sup> :(<br /><br />Here is <a href="https://codeforces.com/contest/1246/problem/E">the problem</a>: you have <i>n</i><=16 positive integers such that their sum does not exceed 2000, and another integer <i>k</i>, 2<=<i>k</i><=2000. All <i>n</i> integers are not divisible by <i>k</i>. In one step, we can erase two numbers and instead write their sum divided by <i>k</i> repeatedly until the result is no longer divisible by <i>k</i>. For example, if <i>k</i>=2 and we have numbers 5 and 19, we can erase them and instead write 3 as 3=(5+19)/2/2/2 and 3 is not divisible by 2. Our goal is to end up with having just the number 1. Can you find a way to do that without iterating over 3<sup><i>n</i></sup> of something?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-BslPkF52-vU/XgPVoGhDtJI/AAAAAAACauI/s6BGu-ISUsEttfgUGaGZlxInHPYDjasngCLcBGAsYHQ/s1600/IMG_20191115_115802.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/-BslPkF52-vU/XgPVoGhDtJI/AAAAAAACauI/s6BGu-ISUsEttfgUGaGZlxInHPYDjasngCLcBGAsYHQ/s640/IMG_20191115_115802.jpg" width="640" /></a></div>In <a href="https://petr-mitrichev.blogspot.com/2019/12/a-perfectly-balanced-week.html">my previous summary</a>, I have mentioned a bunch of problems. <a href="https://codeforces.com/contest/1237/problem/H">The first one</a> came from Codeforces: you are given two strings of even length, <i>a</i> and <i>b, </i>consisting of characters 0 and 1. You start with the string <i>a</i>. In one step, you can choose any prefix of the current string that has even length and reverse it. Your goal is to obtain the string <i>b</i> in at most <i>n</i>+1 steps. You don't need to minimize the number of steps. The length of each string is even and at most 4000.<br /><br />Since we only ever reverse prefixes of even length, it's natural to see what happens to blocks of two consecutive characters. Blocks of 00 and 11 stay the same, 01 turns into a 10 and vice versa. Therefore, in order for this transformation to be possible at all, we need the number of 00 blocks to be the same between the two strings, and the number of 11 blocks to be the same between the two strings (and therefore the total number of remaining blocks, which are 01 and 10, will also be the same).<br /><br />It turns out that this is both necessary and sufficient for a transformation to exist. One way to do it is to keep converting the string <i>a</i> into the string <i>b</i> from right to left. Consider the rightmost block of <i>b</i>, for example it's 00. Then we can find the same block anywhere in <i>a</i>, reverse the prefix ending with this block so that it moves to the first position, and then reverse the entire string <i>a</i> so that it moves to the end, and then we can forget about the last two characters of <i>a</i> and repeat the process.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-qyyFgqvhpxs/XgPTwVtc3jI/AAAAAAACatY/dwCgCK_VgoA919381DjiVg15m81jyTqdgCKgBGAsYHg/s1600/IMG_20191225_222405.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" data-original-height="1522" data-original-width="1558" height="312" src="https://1.bp.blogspot.com/-qyyFgqvhpxs/XgPTwVtc3jI/AAAAAAACatY/dwCgCK_VgoA919381DjiVg15m81jyTqdgCKgBGAsYHg/s320/IMG_20191225_222405.jpg" width="320" /></a></div>We have handled two characters in two reversals, so it looks like we will finish in at most <i>n</i> steps. However, there is one tricky case: when the block we need is a 01, and <i>a</i> does not have any 01s, just 10s (or vice versa). In this case we might need an extra reversal in the middle to turn one into the other when it's in the first position of <i>a</i>, so we will end up spending 3 reversals per 2 characters, potentially using up to 1.5<i>n</i> steps which is too much.<br /><br />The official solution modifies this process a bit to make sure we need at most one such extra reversal — <a href="https://codeforces.com/blog/entry/70620">check it out</a>. I have tried to come up with something in that vein but could not make it work, so I've used a randomized approach: I've noticed that in some cases we can only spend 1 reversal per 2 characters, namely when the required block is already in the beginning of <i>a</i> (in reversed form). If the number of times we spend 1 reversal is the same or at most one less than the number of times we spend 3 reversals, then we're good. And intuitively the "1 reversal" situation is much more likely to happen as we just need the right type of block in the beginning, while for the "3 reversals" situation to happen we need some type of block to not exist at all. Since we have quite some freedom in choosing which block to move to the last place at each step, making this choice randomly, and then starting from scratch in case we exceed <i>n</i>+1 steps turned out to be good enough.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-G2seNThLTlE/XgPVu86tDpI/AAAAAAACauM/v-OZA4QSkG4QYzv_EsUkX9Ddtjx3QgFSgCLcBGAsYHQ/s1600/MVIMG_20191101_125346.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1118" data-original-width="1600" height="446" src="https://1.bp.blogspot.com/-G2seNThLTlE/XgPVu86tDpI/AAAAAAACauM/v-OZA4QSkG4QYzv_EsUkX9Ddtjx3QgFSgCLcBGAsYHQ/s640/MVIMG_20191101_125346.jpg" width="640" /></a></div><a href="https://community.topcoder.com/stat?c=problem_statement&pm=15754&rd=17720">The second problem</a> was from TopCoder: you are given a number <i>n</i> between 1 and 1000, and need to construct any tree with <i>n</i> vertices that has at least 2.62<sup><i>n</i></sup> colorings of the following kind: each vertex is colored red, green or blue in such a way that the distance between any two red vertices is at least 3 (there are no constraints on green and blue vertices).<br /><br /><a href="https://community.topcoder.com/stat?c=problem_solution&cr=10574855&rd=17720&pm=15754">My solution</a>, which ended up being the only one that passed the system tests, was very simple: we start with a tree that looks like a chain. Then we repeatedly make random changes to the tree, keeping the change if the number of colorings increases, and reverting the change if it decreases, until we reach the required number of colorings.<br /><br />This still requires to solve the sub-problem of counting the number of colorings, but it is solved with a relatively standard dynamic programming algorithm.<br /><br />Since there were only 1000 possible inputs, I've ran my solution on all of them and was sure that it works when submitting it. And then I ended up resubmitting it with just seconds left in the round :) When running it on the 1000 inputs for the first time, I've noticed that it takes some time to converge to the required number of colorings for inputs under ~700, but the solution becomes instant for inputs larger than that. Somehow I did not think this was bad at the time, but of course it was. The reason for this was that the number of colorings overflowed the double floating-point type, so it was immediately finding a tree with "positive infinity" colorings :)<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-IxNlQ3t6qK0/XgPV1EuhrQI/AAAAAAACauU/3yVKEgazDxU7UZ-OF91CYv1PzXQjsZYsQCLcBGAsYHQ/s1600/IMG_20191115_124316.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" data-original-height="1200" data-original-width="1600" height="480" src="https://1.bp.blogspot.com/-IxNlQ3t6qK0/XgPV1EuhrQI/AAAAAAACauU/3yVKEgazDxU7UZ-OF91CYv1PzXQjsZYsQCLcBGAsYHQ/s640/IMG_20191115_124316.jpg" width="640" /></a></div>Finally, I have also mentioned an Open Cup problem: there is a hidden array <i>a</i> with at most 250 elements, and you need to determine its contents after asking at most 30 queries. Initially, you just know that size of <i>a</i> and that each element of <i>a</i> is an integer between 1 and 10<sup>9</sup>, inclusive. In one query, you can either ask for the value of a particular element of <i>a</i>, or choose a set of indices of elements of <i>a</i>, and get back the multiset of <i>k</i>*(<i>k</i>-1)/2 absolute values of pairwise differences between elements with those indices (where <i>k</i> is the number of indices you've chosen). Note that for a query of the second type you get back a multiset, in other words there is no order and you don't know which difference corresponds to which pair.<br /><br />The first crucial trick that our team came up with is the following: if we send two queries of the second type for a set <i>S</i> and for a set <i>S</i>+{<i>x</i>}, and then find the difference between the returned multisets, then you get a set of absolute values of differences between <i>x</i> and all elements of <i>S</i>.<br /><br />Now, if we somehow magically knew an element <i>x</i> which is the global minimum or maximum, we could solve the problem in the following way: let's repeat the above trick 8 times, on the <i>i</i>-th try asking for differences between <i>x</i> and a set of indices which have the <i>i</i>-th bit set to 1.<br /><br />Since we have less than 2<sup>8</sup> elements, and all differences will be unique thanks to <i>x</i> being the global minimum or maximum, this will allow us to uniquely identify the element corresponding to each difference by looking at whether each bit in its index is 0 or 1. The difference corresponding to all bits being 0 will never appear in our output, but we can just start the indexes from 1 to avoid this issue.<br /><br />Now we just need to find the value of <i>x</i> and whether it is the minimum or the maximum, which we can do with two queries of the first type, and all other elements can be obtained by adding (when x is the minimum) or subtracting (when x is the maximum) the corresponding difference. We have spent only 8*2+2=18 queries in this part.<br /><br />How to find the global maximum or minimum using the remaining 12 queries? It turns out that we can craft a binary search using the presence of the overall maximum absolute difference as our test. First, we send a query of the second type for all indices, and find the overall maximum absolute difference — it will be the difference between the global maximum and the global minimum.<br /><br />Then, suppose we have identified a subset <i>S</i> which contains the global maximum, the global minimum, or both (initially <i>S</i> will be equal to all indices), and let <i>T</i> be its complement (initially empty). Let's split <i>S</i> into two equal parts <i>A</i> and <i>B</i>. Let's ask send a query of the second type for the set <i>A</i>+<i>T</i>. In case this query returns the overall maximum absolute difference, then <i>A</i> contains at least one of the global maximum and minimum (because otherwise <i>T</i> would have to contain both, which is a contradiction). In case it does not, then <i>B</i> must contain at least one of them. So we can reduce our set of candidates in half using one query of the second type, and therefore find our global maximum or minimum in 1+8=9 queries, solving the entire problem in 27 queries.<br /><br />This problem was one of the few cases where we have actually used the whole Open Cup 3-person team to discuss it and make incremental progress until all pieces of the puzzle fell together. I found the "uncertain" binary search quite cool in particular, as we manage to look for one of the two elements without knowing which one of the two it is, and without even knowing if the remaining subset contains only one of the elements or both :)<br /><br />Thanks for reading, and check back for more!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/oaReBJGxrfg" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com0http://petr-mitrichev.blogspot.com/2019/12/a-3-person-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-62418577766027959722019-12-24T16:09:00.000+03:002019-12-24T21:03:19.864+03:00A perfectly balanced 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/-T0GRp5Taj1E/XgIB3N2tk-I/AAAAAAACamM/gO2fKoUACvYl0t4Z6EUkpTLpucMR8Y_swCLcBGAsYHQ/s1600/cfglobal5top5.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://1.bp.blogspot.com/-T0GRp5Taj1E/XgIB3N2tk-I/AAAAAAACamM/gO2fKoUACvYl0t4Z6EUkpTLpucMR8Y_swCLcBGAsYHQ/s640/cfglobal5top5.png" width="640" /></a></div>Codeforces Global Round 5 started the Oct 14 - Oct 20 week (<a href="https://codeforces.com/contest/1237">problems</a>, <a href="https://codeforces.com/contest/1237/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/70620">analysis</a>). Radewoosh solved 8 problems with almost an hour left in the round, and since nobody was able to get all 9, his first place was quite clear. Well done!<br /><br />I was stuck trying to squeeze my solution for <a href="https://codeforces.com/contest/1237/problem/H">problem H</a> into the constraints for quite some time, and as the round was coming to its end I've decided to make it do multiple passes with some randomization until it fits and submitted. It turns out that this approach worked, and I think it's likely impossible to create a counter-test.<br /><br />Here's what the problem was about: you are given two strings of even length, <i>a</i> and <i>b, </i>consisting of characters 0 and 1. You start with the string <i>a</i>. In one step, you can choose any prefix of the current string that has even length and reverse it. Your goal is to obtain the string <i>b</i> in at most <i>n</i>+1 steps. You don't need to minimize the number of steps. The length of each string is even and at most 4000.<br /><br />Can you see a deterministic, or at least a randomized solution?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-_zZC-gGfaVI/XgICkv4N2JI/AAAAAAACamY/eTrZmwzHFikqp1G6w5RwZhJ7Kpos58x9ACLcBGAsYHQ/s1600/srm769top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="97" data-original-width="628" src="https://1.bp.blogspot.com/-_zZC-gGfaVI/XgICkv4N2JI/AAAAAAACamY/eTrZmwzHFikqp1G6w5RwZhJ7Kpos58x9ACLcBGAsYHQ/s1600/srm769top5.png" /></a></div>TopCoder SRM 769 followed on Saturday (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=17720">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17720&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left). Unlike the previous round, <a href="https://community.topcoder.com/stat?c=problem_statement&pm=15754&rd=17720">the hard problem</a> in this round had only 1000 possible inputs, so this time I went for a randomized solution intentionally as I could verify that it works on all inputs before submitting. This turned out to be the right approach :)<br /><br />Here's the problem: you are given a number <i>n</i> between 1 and 1000, and need to construct any tree with <i>n</i> vertices that has at least 2.62<sup><i>n</i></sup> colorings of the following kind: each vertex is colored red, green or blue in such a way that the distance between any two red vertices is at least 3 (there are no constraints on green and blue vertices).<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/--s9RTk2seHI/XgIBZDRYhmI/AAAAAAACamE/wY5f_h9gmOE0_Oq6z8TyD06AvWRBUTkHACLcBGAsYHQ/s1600/oc1920seerctop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="238" data-original-width="789" height="192" src="https://1.bp.blogspot.com/--s9RTk2seHI/XgIBZDRYhmI/AAAAAAACamE/wY5f_h9gmOE0_Oq6z8TyD06AvWRBUTkHACLcBGAsYHQ/s640/oc1920seerctop5.png" width="640" /></a></div>Open Cup 2019-20 Grand Prix of Southeastern Europe took place on Sunday (<a href="https://codeforces.com/gym/102392">problems</a>, <a href="http://opencup.ru/index.cgi?data=macros/stage&head=index&menu=index&stg=6&region=main&ncup=ock&class=ock">results</a>, top 5 on the left, <a href="http://olymp.sumdu.edu.ua:8080/acm-real-2019.php">onsite results</a>, <a href="https://oi.in.ua/wp-content/uploads/2019/10/seerc-2019-editorial.pdf">analysis</a>). Team USA1 needed just half of the contest to solve all problems, amazing performance! The stage win counts for the 3 strongest veteran teams are now at 2-2-2.<br /><br />Solving the interactive <a href="https://codeforces.com/gym/102392/problem/C">problem C</a> was a lot of fun. There is a hidden array <i>a</i> with at most 250 elements, and you need to determine its contents after asking at most 30 queries. Initially, you just know that size of <i>a</i> and that each element of <i>a</i> is an integer between 1 and 10<sup>9</sup>, inclusive. In one query, you can either ask for the value of a particular element of <i>a</i>, or choose a set of indices of elements of <i>a</i>, and get back the multiset of <i>k</i>*(<i>k</i>-1)/2 absolute values of pairwise differences between elements with those indices (where <i>k</i> is the number of indices you've chosen). Note that for a query of the second type you get back a multiset, in other words there is no order and you don't know which difference corresponds to which pair.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-xD8z_6Rnrrw/XgIDCiRMdbI/AAAAAAACamg/4XKxrmHcY_IF5TdS5AIIzW4vCAznay0RQCLcBGAsYHQ/s1600/cf594top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="270" data-original-width="1102" height="156" src="https://1.bp.blogspot.com/-xD8z_6Rnrrw/XgIDCiRMdbI/AAAAAAACamg/4XKxrmHcY_IF5TdS5AIIzW4vCAznay0RQCLcBGAsYHQ/s640/cf594top5.png" width="640" /></a></div>Finally, Codeforces Round 594 happened right in the middle of the Open Cup round (<a href="https://codeforces.com/contest/1239">problems</a>, <a href="https://codeforces.com/contest/1239/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/70720">analysis</a>). tlwpdus was able to claim the first place even though they solved one problem less than rhrnald, thanks to the fast solutions for D and E and having no incorrect attempts compared to rhrnald's five. Congratulations to both!<br /><br />Thanks for reading, and check back for more.<br /><br /><br /></div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/CRzi8ch0mKg" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com0http://petr-mitrichev.blogspot.com/2019/12/a-perfectly-balanced-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-74405168166438273082019-12-24T15:06:00.001+03:002019-12-24T15:06:58.633+03:00A trigonometric 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/-0LrVnTNZokw/XgH2K-lJOEI/AAAAAAACakg/x5VM3YJRSRYttxnngzWkjpEeCfbnl2ejQCLcBGAsYHQ/s1600/srm768top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="150" data-original-width="781" height="122" src="https://1.bp.blogspot.com/-0LrVnTNZokw/XgH2K-lJOEI/AAAAAAACakg/x5VM3YJRSRYttxnngzWkjpEeCfbnl2ejQCLcBGAsYHQ/s640/srm768top5.png" width="640" /></a></div>The Oct 7 - Oct 13 week had TopCoder SRM 768 (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=17687">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17687&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://www.topcoder.com/single-round-match-768-editorials/">analysis</a>). <a href="https://codeforces.com/blog/entry/70445?#comment-549389">My solution</a> to <a href="https://community.topcoder.com/stat?c=problem_statement&pm=15494&rd=17687">the medium problem</a> turned out to be a bit simpler than the author's approach. Here is the problem statement: <i>n</i> players are competing in a tournament. Each player has an integer strength which is 1, 2 or 3. In one round of the tournament, we pick two random remaining players, and the one with the lower strength is eliminated. In case their strengths are equal, we eliminate one of them at random (each with probability 0.5). In the end only one player remains, and the order of elimination is the ranking of the players. What is the expected rank of a player with strength 2? Your input is three numbers, the number of players with strength 1, 2 and 3 respectively, each up to 2000.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-wHGaNhs5eIg/XgH3j-jx5tI/AAAAAAACaks/51YOf6kFm8g41Q2DeTLRkWqmr1IgSxF3QCLcBGAsYHQ/s1600/oc1920koreatop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="194" data-original-width="857" height="144" src="https://1.bp.blogspot.com/-wHGaNhs5eIg/XgH3j-jx5tI/AAAAAAACaks/51YOf6kFm8g41Q2DeTLRkWqmr1IgSxF3QCLcBGAsYHQ/s640/oc1920koreatop5.png" width="640" /></a></div>The fifth Open Cup stage, the Grand Prix of Korea, took place on Sunday (<a href="https://codeforces.com/gym/102391">problems</a>, <a href="http://opencup.ru/index.cgi?data=macros/stage&head=index&menu=index&stg=5&region=main&ncup=ock&class=ock">results</a>, top 5 on the left, <a href="https://www.dropbox.com/s/xgte0ifu9g4o1lg/gp6div1sol.pdf?dl=0">analysis</a>). Team Polish Mafia was way ahead of everybody else this time, solving 10 problems to the second place's 8, and bringing the number of stage victories between the three strongest veteran teams to 2-2-1 (as a sneak peek into the present, no other team managed to win a stage in 2019). Congratulations!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-iUd2RdV6M3E/XgH832F3zDI/AAAAAAACalE/VWEJiGmq1tQTjikzXGNshFAIW2rYu1jQACLcBGAsYHQ/s1600/IMG_20191027_125001.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1190" data-original-width="1600" height="475" src="https://1.bp.blogspot.com/-iUd2RdV6M3E/XgH832F3zDI/AAAAAAACalE/VWEJiGmq1tQTjikzXGNshFAIW2rYu1jQACLcBGAsYHQ/s640/IMG_20191027_125001.jpg" width="640" /></a></div>In <a href="https://petr-mitrichev.blogspot.com/2019/12/a-fork-week.html">my previous summary</a>, I have mentioned <a href="https://atcoder.jp/contests/agc039/tasks/agc039_d">an AtCoder problem</a>: you are given 3000 points on the circumference of the unit circle. What is the expected position of the center of the circle inscribed in a triangle formed by a random triple of those points?<br /><br />A cubic solution is straightforward: iterate over all triples, find the center of the incircle, find the average of those. However, it will not fit in the time limit.<br /><br />The most typical way to speed up this type of computation is to somehow decompose the inner expression into parts which depend on only one or two out of three points, and then depending on what "decompose" means exactly we can use partial sums, or FFT, or some other trick to find the sum while only iterating over points or pairs of points, therefore obtaining a quadratic solution.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-WcP9yPlwoQk/XgH_AG_j4vI/AAAAAAACalo/ImEouKEtoj05WnnN4wA_EK6H-irpUDDkQCKgBGAsYHg/s1600/IMG_20191224_130421.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" data-original-height="1600" data-original-width="1535" height="320" src="https://1.bp.blogspot.com/-WcP9yPlwoQk/XgH_AG_j4vI/AAAAAAACalo/ImEouKEtoj05WnnN4wA_EK6H-irpUDDkQCKgBGAsYHg/s320/IMG_20191224_130421.jpg" width="306" /></a></div>At this point I've looked at <a href="https://en.wikipedia.org/wiki/Incircle_and_excircles_of_a_triangle">the Wikipedia article</a> to find a formula that can be decomposed. The barycentric coordinates sin(<i>A</i>):sin(<i>B</i>):sin(<i>C</i>) caught my eye for the following reason: since in this problem all points lie on a circle, the angle <i>A</i> only depends on the locations of the points <i>B</i> and C and not on the location of point <i>A</i> (this is a middle/high school geometry theorem; more precisely, there are two possibilities for the angle <i>A</i> depending on which side of <i>BC</i> does the point <i>A</i> lie). This is exactly the "depends on only two out of three points" property we're looking for.<br /><br />The barycentric coordinates formula looks like<br /><br />(<i>x<sub>A</sub></i>,<i>y<sub>A</sub></i>)*sin(<i>CAB</i>)/(sin(<i>CAB</i>)+sin(<i>ABC</i>)+sin(<i>BCA</i>))+... (the rest is symmetric terms for <i>B</i> and <i>C</i>)<br /><br />We need to sum this over all triples, so the total coefficient next to (<i>x<sub>A</sub></i>,<i>y<sub>A</sub></i>) is the sum of<br /><br />sin(<i>CAB</i>)/(sin(<i>CAB</i>)+sin(<i>ABC</i>)+sin(<i>BCA</i>))<br /><br />over all values of B and C. Each individual sin() depends only on two points, but they are still combined together in one term, so we need to decompose further.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-a-j--tpciuI/XgH_DgSBmMI/AAAAAAACals/Kb4o8qxVx0gaKm6r5z8x250ShUsJr3b9ACKgBGAsYHg/s1600/MVIMG_20191224_130425.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1556" data-original-width="1600" height="310" src="https://1.bp.blogspot.com/-a-j--tpciuI/XgH_DgSBmMI/AAAAAAACals/Kb4o8qxVx0gaKm6r5z8x250ShUsJr3b9ACKgBGAsYHg/s320/MVIMG_20191224_130425.jpg" width="320" /></a></div>Let's denote the angle <i>ABC</i> as β, and the angle <i>BCA</i> as γ, the angle CAB can be found as <span style="background-color: #f9f9f9; color: #222222; font-family: sans-serif; font-size: 12.32px;">π</span>-β-γ, and since sin(<span style="background-color: #f9f9f9; color: #222222; font-family: sans-serif; font-size: 12.32px;">π</span>-β-γ)=sin(β+γ) we have<br /><br />sin(β+γ)/(sin(β)+sin(γ)+sin(β+γ))<br /><br />The main difficulty here lies in the fact that we have a sum in denominator, but we want a product, since those are easier to decompose. We can use another fact from middle/high school (which I googled of course), this time from trigonometry, and replace sin(β)+sin(γ) with a product like this:<br /><br />sin(β+γ)/(2*sin((β+γ)/2)*cos((β-γ)/2)+sin(β+γ))<br /><br />Now we have trigonometric functions of (β+γ)/2 and of β+γ, to make things simpler we can replace sin(β+γ) using another middle/high school formula to get:<br /><br />2*sin((β+γ)/2)*cos((β+γ)/2)/(2*sin((β+γ)/2)*cos((β-γ)/2)+2*sin((β+γ)/2)*cos((β+γ)/2))<br /><br />Here we get a confirmation that we are on the right track: the multiplier 2*sin((β+γ)/2) appears both in the numerator and in the denominator and cancels out! So we have just<br /><br />cos((β+γ)/2)/(cos((β-γ)/2)+cos((β+γ)/2))<br /><br />Now we can use yet another trigonometric formula, for the cosine of sum, to get:<br /><br />(cos(β/2)*cos(γ/2)-sin(β/2)*sin(γ/2))/(cos(β/2)*cos(γ/2)+sin(β/2)*sin(γ/2)+cos(β/2)*cos(γ/2)-sin(β/2)*sin(γ/2))<br /><br />The term sin(β/2)*sin(γ/2) cancels out in the denominator, so we have just:<br /><br />(cos(β/2)*cos(γ/2)-sin(β/2)*sin(γ/2))/(2*cos(β/2)*cos(γ/2))<br /><br />Or even simpler<br /><br />1/2*(1-tan(β/2)*tan(γ/2))<br /><br />Finally, this is decomposed enough. Even though β and γ are not chosen completely independently (the points have to be in the right order on a circle), for each particular value of β (in other words, after fixing the points <i>A</i> and <i>C</i>) we need to find a prefix sum of tan(γ/2) over a range of possible points <i>B</i>, therefore we can precompute those prefix sums after fixing the value of <i>A</i> and obtain a quadratic solution (<a href="https://atcoder.jp/contests/agc039/submissions/7869150">here is my code</a>).<br /><br />I agree that this does look a bit like <a href="https://codeforces.com/blog/entry/70291?#comment-547862">bashing the formula</a> until some parts magically cancel out, but for me it felt like that both choosing the formula to bash (the one with angles, since those depend only on two points), and the way of bashing (trying to get a product instead of a sum in the denominator) were actually guided by the algorithmic constraints of the problem, and therefore were not so dependent on luck.<br /><br />Thanks for reading, and check back for more!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/NgnoVqxfaG0" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com0http://petr-mitrichev.blogspot.com/2019/12/a-trigonometric-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-30081291627252109342019-12-24T00:23:00.001+03:002019-12-24T09:18:38.495+03:00A fork 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/-y7ne7gS-0lI/XgEqcrDsvDI/AAAAAAACajk/-Iyih5B4YuMzHRkj9COlh_fOQUV4UPc8QCLcBGAsYHQ/s1600/agc039top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="346" data-original-width="830" height="266" src="https://1.bp.blogspot.com/-y7ne7gS-0lI/XgEqcrDsvDI/AAAAAAACajk/-Iyih5B4YuMzHRkj9COlh_fOQUV4UPc8QCLcBGAsYHQ/s640/agc039top5.png" width="640" /></a></div>AtCoder Grand Contest 039 was the highlight of the Sep 30 - Oct 6 week (<a href="https://atcoder.jp/contests/agc039/tasks">problems</a>, <a href="https://atcoder.jp/contests/agc039/standings">results</a>, top 5 on the left, <a href="https://img.atcoder.jp/agc039/editorial.pdf">analysis</a>). ksun48 was the fastest on five problems, but ecnerwal was also able to finish problem F in about an hour, something that other top finishers could not match. Congratulations on the win!<br /><br /><a href="https://atcoder.jp/contests/agc039/tasks/agc039_d">Problem D</a> has gathered quite some heat (see <a href="https://codeforces.com/blog/entry/70291?#comment-547862">this comment</a> and the thread below), but I think the problem was actually very nice: you are given 3000 points on the circumference of the unit circle. What is the expected position of the center of the circle inscribed in a triangle formed by a random triple of those points?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-tA6Qezkf6ws/XgEwIluZpQI/AAAAAAACaj8/2k4kVQgU5q4t-1G8zUGhYemPYoEcEwC-gCLcBGAsYHQ/s1600/MVIMG_20191006_152814%2B%25282%2529.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1197" data-original-width="1600" height="478" src="https://1.bp.blogspot.com/-tA6Qezkf6ws/XgEwIluZpQI/AAAAAAACaj8/2k4kVQgU5q4t-1G8zUGhYemPYoEcEwC-gCLcBGAsYHQ/s640/MVIMG_20191006_152814%2B%25282%2529.jpg" width="640" /></a></div>In <a href="https://petr-mitrichev.blogspot.com/2019/12/a-bridge-week.html">my previous summary</a>, I have mentioned <a href="https://codeforces.com/contest/1229/problem/E1">a Codeforces problem</a>: consider a bipartite graph with 6 vertices in each half, and each edge existing with a certain probability (these 36 probabilities are given to you). What is the probability that this graph has a perfect matching? The probability needs to be computed modulo 10<sup>9</sup>+7, and the time limit is 7 seconds.<br /><br />My approach is already described in <a href="https://codeforces.com/blog/entry/70008?#comment-545320">this comment</a>, but let me repeat it here since it's short anyway. Let us run the normal dfs-based algorithm for finding maximum matching, but whenever the algorithm needs to check if an edge exists, we will fork the search, one branch continuing as if it does, and one branch continuing as if it does not. Why would something like this work fast: the intuition is, since dfs stops right after finding any augmenting path, in most branches we won't care about the state of many edges, therefore the total amount of branches won't be too big.<br /><br />Here is <a href="https://codeforces.com/contest/1229/submission/61184672">my implementation</a>, the number of branches it considers for a 6x6 graph is 16404365 (much less than 2<sup>36</sup>, as expected), practically it means getting accepted in 5.3s out of 7s time limit.<br /><br />This approach is quite tricky to get right, though. Since we have to branch a recursive algorithm (dfs), we need to rewrite it to maintain the stack in arrays we control so that we can copy those. This process is quite tedious and error-prone, and it took me quite a lot of time to find a bug in that part of the code (if I remember correctly, I was missing line 113 "<span style="font-family: "courier new" , "courier" , monospace;">stack[sp - 1] = cur;</span>").<br /><br />Here's my question: is there a programming language or an approach where implementing such branching search on a recursive algorithm would be easy, and that would still fit into the 7 second time limit for 16 million branches? fork() in C/C++ comes to mind as the first choice, but I think its overhead is way too high for such number of branches to be practical.<br /><br />Thanks for reading, and check back for more!<br /><br /></div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/ZXSQTaFdCkg" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com0http://petr-mitrichev.blogspot.com/2019/12/a-fork-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-30820805579957836592019-12-23T19:21:00.001+03:002019-12-24T09:18:52.166+03:00A bridge 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/-AeYWUOd-E48/XgDiXu3tbZI/AAAAAAACaiY/vBh3d5PYjT0cV0uP1WvZs7dhFMUSyikFACLcBGAsYHQ/s1600/cf588top5.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://1.bp.blogspot.com/-AeYWUOd-E48/XgDiXu3tbZI/AAAAAAACaiY/vBh3d5PYjT0cV0uP1WvZs7dhFMUSyikFACLcBGAsYHQ/s640/cf588top5.png" width="640" /></a></div>Codeforces Round 588 started the Sep 23 - Sep 29 week (<a href="https://codeforces.com/contest/1229">problems</a>, <a href="https://codeforces.com/contest/1229/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/contest/1210/standings">onsite results with one more easy problem</a>, <a href="https://codeforces.com/blog/entry/70008">analysis</a>). Um_nik solved six problems almost half an hour faster than other top finishers, therefore it's even surprising that his advantage is only 233 points. Congratulations on the convincing victory!<br /><br />I have enjoyed coming up and implementing <a href="https://codeforces.com/blog/entry/70008?#comment-545320">a weird approach</a> to <a href="https://codeforces.com/contest/1229/problem/E1">problem E1</a>: consider a bipartite graph with 6 vertices in each half, and each edge existing with a certain probability (these 36 probabilities are given to you). What is the probability that this graph has a perfect matching? The probability needs to be computed modulo 10<sup>9</sup>+7, and the time limit is 7 seconds.<br /><br />How would you approach this problem?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-et-7TagL9Ew/XgDjCpxctKI/AAAAAAACaig/Ta7AM_7P6EEaTxOa-_8gfdEX5zJ183IogCLcBGAsYHQ/s1600/oc1920eurasiatop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="236" data-original-width="853" height="176" src="https://1.bp.blogspot.com/-et-7TagL9Ew/XgDjCpxctKI/AAAAAAACaig/Ta7AM_7P6EEaTxOa-_8gfdEX5zJ183IogCLcBGAsYHQ/s640/oc1920eurasiatop5.png" width="640" /></a></div>Almost six days later, Open Cup 2019-20 Grand Prix of Eurasia has wrapped up the week (<a href="http://opencup.ru/index.cgi?data=macros/stage&head=index&menu=index&stg=4&region=main&ncup=ock&class=ock">results</a>, top 5 on the left). The winners of the first three stages lined up on the podium this time, team Past Glory prevailing once again thanks to having much, much fewer incorrect attempts than its competitors. Congratulations!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-yJFLv97frZY/XgDoUtNKQ5I/AAAAAAACaiw/Z7LLDpxUjjcojYwQOSEIZTN3sP6vVI4HgCLcBGAsYHQ/s1600/IMG_20190928_114757.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/-yJFLv97frZY/XgDoUtNKQ5I/AAAAAAACaiw/Z7LLDpxUjjcojYwQOSEIZTN3sP6vVI4HgCLcBGAsYHQ/s640/IMG_20190928_114757.jpg" width="640" /></a></div>In <a href="https://petr-mitrichev.blogspot.com/2019/12/a-bfs-week.html">my previous summary</a>, I have mentioned a supposedly medium-difficulty AtCoder problem: does there exist a simple connected undirected graph with exactly <i>n</i> vertices and exactly <i>m</i> edges that satisfies the <i>q</i> given constraints (<i>n</i>, <i>m, q</i><=10<sup>5</sup>) of the following two types:<br /><ul style="text-align: left;"><li>for a pair of vertices, there must be exactly one simple path between them</li><li>for a pair of vertices, there must be at least two simple paths between them</li></ul>For most of the time during the round, I was trying to start from constraints of the second type, incorrectly assuming that such pairs of vertices must be in the same biconnected component. In fact, this is not necessary, since the two paths do not have to be completely disjoint, they just need to differ at some point.<br /><br />The other approach direction turns out to be more fruitful: consider the (only) path between two vertices from a constraint of the first type. All its edges must necessarily be bridges in our graph, as otherwise we could remove one of them and find another path. Now if we group the vertices into connected components using the constraints of the first type, each such connected component is connected with bridges only (possibly via some intermediate vertices). Therefore for any pair of vertices in such connected component there is exactly one simple path between them, which in turn means that if any two vertices in a constraint of the second type are in one such component, then there is no solution.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-Bai1QBCWqT4/XgDpVpkQcuI/AAAAAAACajA/WrkqqI9gVG4FOr1T2l19yGdxtevAOty8gCKgBGAsYHg/s1600/IMG_20191223_171947.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" data-original-height="1420" data-original-width="955" height="400" src="https://1.bp.blogspot.com/-Bai1QBCWqT4/XgDpVpkQcuI/AAAAAAACajA/WrkqqI9gVG4FOr1T2l19yGdxtevAOty8gCKgBGAsYHg/s400/IMG_20191223_171947.jpg" width="268" /></a></div>Notwithstanding the requirement to have exactly <i>m</i> edges, the above case is the only one when there is no solution at all, because of the following construction: let's take the connected components using the constraints of the first type, build an arbitrary tree of bridges inside each such component, then pick one vertex in each component and connect all of them in one big cycle. In such a construction, for any two vertices inside one component there is exactly one path between them, and for any two vertices from different components there is at least two paths between them.<br /><br />This construction has <i>n</i> edges (since it has exactly one cycle), which is the minimum possible number of edges if we have at least one constraint of the second type (since we must have at least one cycle then). Now, if instead of connecting the chosen vertices in one big cycle we connect them using a complete graph, we get another valid solution but with a lot more edges: if we have <i>k</i> components, the number of edges is <i>n</i>-<i>k+k</i>*(<i>k</i>-1)/2=<i>n</i>+<i>k</i>*(<i>k</i>-3)/2. It is also easy to see how to achieve any number of edges in between those two values, as we can keep adding edges to the cycle until it becomes the complete graph.<br /><br />The only remaining step is to notice that we can't have more edges than that. The reason for that is that we can't have more than one edge between two components (otherwise one of the component's edges would not be a bridge, as we could bypass it), and adding more vertices to a component only makes things worse as we're replacing a lot of edges with a single new bridge.<br /><br />Thanks for reading, and check back for more!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/tiZKwJ9tVgE" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com0http://petr-mitrichev.blogspot.com/2019/12/a-bridge-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-7458013713269538582019-12-22T21:33:00.002+03:002019-12-22T21:33:40.080+03:00A bfs 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/-nF1D-_utCTE/Xf-XGg_TN6I/AAAAAAACabM/UfB3n66uocskpI0OCSnYqcdnLwTRyNyfwCLcBGAsYHQ/s1600/cf586top5.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://1.bp.blogspot.com/-nF1D-_utCTE/Xf-XGg_TN6I/AAAAAAACabM/UfB3n66uocskpI0OCSnYqcdnLwTRyNyfwCLcBGAsYHQ/s640/cf586top5.png" width="640" /></a></div>Codeforces hosted its Round 586 during the Sep 16 - Sep 22 week (<a href="https://codeforces.com/contest/1220">problems</a>, <a href="https://codeforces.com/contest/1220/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/69899">analysis</a>). The somewhat unusual problem difficulty distribution meant the differences between the top competitors were quite tiny, but still mnbvmar was the fastest of all solving six problems in 37 minutes. Well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-JMS8dvDGXAI/Xf-XmGY0HuI/AAAAAAACabU/xF2__z9C-2kUYi76gzFuyBfW9wDERRDRACLcBGAsYHQ/s1600/agc038top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="351" data-original-width="837" height="268" src="https://1.bp.blogspot.com/-JMS8dvDGXAI/Xf-XmGY0HuI/AAAAAAACabU/xF2__z9C-2kUYi76gzFuyBfW9wDERRDRACLcBGAsYHQ/s640/agc038top5.png" width="640" /></a></div>AtCoder Grand Contest 038 took place on Saturday (<a href="https://atcoder.jp/contests/agc038/tasks">problems</a>, <a href="https://atcoder.jp/contests/agc038/standings">results</a>, top 5 on the left, <a href="https://img.atcoder.jp/agc038/editorial.pdf">analysis</a>). It was one of those days where tourist solved six problems in 79 minutes, and I ended up with three problems after the whole 110-minute round :) Congratulations to him but also to ksun48 and hbi1998 on solving all problems, too!<br /><br /><a href="https://atcoder.jp/contests/agc038/tasks/agc038_d">Problem D</a> has got me stumbled: does there exist a simple connected undirected graph with exactly <i>n</i> vertices and exactly <i>m</i> edges that satisfies the <i>q</i> given constraints (<i>n</i>, <i>m, q</i><=10<sup>5</sup>) of the following two types:<br /><ul style="text-align: left;"><li>for a pair of vertices, there must be exactly one simple path between them</li><li>for a pair of vertices, there must be at least two simple paths between them</li></ul>The general approach was somewhat clear, but I could not dig through all details. Can you?<br /><br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-1OlKmobmCBw/Xf-VyrRuMLI/AAAAAAACabA/jyHUaWKVfI0t63Vks9qAigXl45XomFaoACLcBGAsYHQ/s1600/oc1920spbtop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="237" data-original-width="743" height="204" src="https://1.bp.blogspot.com/-1OlKmobmCBw/Xf-VyrRuMLI/AAAAAAACabA/jyHUaWKVfI0t63Vks9qAigXl45XomFaoACLcBGAsYHQ/s640/oc1920spbtop5.png" width="640" /></a></div>For the third week in a row, Open Cup was the last round of the week, this time the Grand Prix of SPb (<a href="http://opencup.ru/index.cgi?data=macros/stage&head=index&menu=index&stg=3&region=main&ncup=ock&class=ock">results</a>, top 5 on the left). Even though team Past Glory was the fifth team to solve all problems, more than an hour later than team USA1, they have returned to the top of the standings thanks to having fewer incorrect attempts. Congratulations!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-pasRMWFa66E/Xf-2uu-7XmI/AAAAAAACabo/BEwWaOduAIgbNR7k7ZA89xBoYPubpxbXgCLcBGAsYHQ/s1600/IMG_20190922_181146.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/-pasRMWFa66E/Xf-2uu-7XmI/AAAAAAACabo/BEwWaOduAIgbNR7k7ZA89xBoYPubpxbXgCLcBGAsYHQ/s640/IMG_20190922_181146.jpg" width="640" /></a></div>In <a href="https://petr-mitrichev.blogspot.com/2019/12/a-dasha-week.html">my previous summary</a>, I have mentioned <a href="https://codeforces.com/contest/1209/problem/F">a Codeforces problem</a>: you are given a connected graph with <i>m</i><=10<sup>5</sup> edges, numbered with consecutive integers from 1 to <i>m</i>. For any path, we obtain its cost by writing down the numbers of its edges in sequence without spaces to obtain one huge number. What is the smallest cost of a path from vertex 1 to each other vertex? You need to return the costs modulo 10<sup>9</sup>+7 (but the smallest cost is chosen before the modulo).<br /><br />The first idea is to notice that multiple-digit numbers are unwieldy, and that we can avoid them by replacing each undirected edge with two directed edges and then inserting auxiliary vertices in the middle of each directed edge splitting it into single-digit edges: instead of a-1204-b, we would have a->1->u->2->v->0->w->4->b and b->1->x->2->y->0->z->4->a. This does not change the costs of simple paths in the original graph, and since our cost function still satisfies the property that taking a subset of edges in a path results in smaller cost, we do not need to consider non-simple paths.<br /><br />Now we have a directed graph with only single-digit edges, and need to find the shortest path from vertex 1 to each other vertex, breaking ties by taking the lexicographically smallest one. It turns out that we can modify breadth-first search to do it: in the breadth-first search queue, we will maintain which pairs of adjacent elements have exactly the same distance from vertex 1, and which have different distances. Now, when we need to take the next vertex out of the queue to process, we will instead take out the whole block of vertices with the same distance from 1, and then first process all 0 edges from all vertices from the block, then all 1 edges from all vertices from the block, and so on. This allows us to keep adding vertices to the queue in the correct order (by length, then lexicographically), and to maintain the "blocks by equality" in it.<br /><br />Note that we never need to compare the actual path costs in this solution, therefore we can store them modulo 10<sup>9</sup>+7.<br /><br />Thanks for reading, and check back for more!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/427ABMUaZWQ" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com0http://petr-mitrichev.blogspot.com/2019/12/a-bfs-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-3897412360481416262019-12-22T19:05:00.001+03:002019-12-22T19:58:31.475+03:00A Dasha week<div dir="ltr" style="text-align: left;" trbidi="on">Welcome to the Christmas marathon :)<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-hlHO3sDqGg0/XeKi9NkknDI/AAAAAAACZ50/yAtal6ep7ykk_Jvnp96hlS7uVm4Nwo_0gCLcBGAsYHQ/s1600/srm766top5.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://1.bp.blogspot.com/-hlHO3sDqGg0/XeKi9NkknDI/AAAAAAACZ50/yAtal6ep7ykk_Jvnp96hlS7uVm4Nwo_0gCLcBGAsYHQ/s640/srm766top5.png" width="640" /></a></div>TopCoder SRM 766 was the first round of the Sep 9 - Sep 15 week (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=17681">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17681&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://docs.google.com/document/d/e/2PACX-1vRbWqjm89cJmWguX8IalTv8a6B4n5M8RTpot3InHXFsVMf_WWBJ08jiIlUxTGyRiPayrlsuaWc76__l/pub">analysis</a>). With his 44th SRM win, tourist has matched SnapDragon's second place in <a href="https://community.topcoder.com/stat?c=division_wins&dn=1">the record book</a> (he has won two more since that week, but I will tell that slightly sad story later :)). Congratulations!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-DEM9vLk39Iw/XeKjq_zn--I/AAAAAAACZ58/GXKV7FdDxpINLcx7s-Uh3gUfQIk2-RGMACLcBGAsYHQ/s1600/cf584top5.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://1.bp.blogspot.com/-DEM9vLk39Iw/XeKjq_zn--I/AAAAAAACZ58/GXKV7FdDxpINLcx7s-Uh3gUfQIk2-RGMACLcBGAsYHQ/s640/cf584top5.png" width="640" /></a></div>Codeforces Round 584 followed on Saturday (<a href="https://codeforces.com/contest/1209">problems</a>, <a href="https://codeforces.com/contest/1209/standings">results</a>, top 5 on the left, <a href="https://youtu.be/coYxbF7xwFA">my screencast</a>, <a href="https://codeforces.com/blog/entry/69791">analysis</a>). <a href="https://codeforces.com/contest/1209/problem/F">Problem F</a> in this round reminded about a nice, if a bit standard, trick: you are given a connected graph with <i>m</i><=10<sup>5</sup> edges, numbered with consecutive integers from 1 to <i>m</i>. For any path, we obtain its cost by writing down the numbers of its edges in sequence without spaces to obtain one huge number. What is the smallest cost of a path from vertex 1 to each other vertex? You need to return the costs modulo 10<sup>9</sup>+7 (but the smallest cost is chosen before the modulo).<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-UUKWxlH9NgE/XeKhjSTpbsI/AAAAAAACZ5o/_-5vUl6nVt4jKSDfeQxL1B-R4D0L-vVVgCLcBGAsYHQ/s1600/oc1920warsawtop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="239" data-original-width="709" height="214" src="https://1.bp.blogspot.com/-UUKWxlH9NgE/XeKhjSTpbsI/AAAAAAACZ5o/_-5vUl6nVt4jKSDfeQxL1B-R4D0L-vVVgCLcBGAsYHQ/s640/oc1920warsawtop5.png" width="640" /></a></div>Open Cup 2019-20 Grand Prix of Warsaw was the last event of the week (<a href="https://codeforces.com/gym/102341">problems</a>, <a href="http://opencup.ru/index.cgi?data=macros/stage&head=index&menu=index&stg=2&region=main&ncup=ock&class=ock">results</a>, top 5 on the left, <a href="https://drive.google.com/file/d/1ymS9INds6_w06CobKjP0QJILuM2oTNp4/view">analysis</a>), with another relatively new veteran team taking the top spot: team USA1 shares 2/3 with the last year's team MIT THREE, but this is the first season in the [ICPC] veteran status for them. Congratulations on the win and keep it going!<br /><br />Thanks for reading, and check back for more.</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/MIEaZBGp5yA" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com0http://petr-mitrichev.blogspot.com/2019/12/a-dasha-week.html