tag:blogger.com,1999:blog-19533250797934499712021-05-05T23:02:28.573+03:00Algorithms Weekly by Petr MitrichevPetr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.comBlogger494125PetrMitrichevhttps://feedburner.google.comtag:blogger.com,1999:blog-1953325079793449971.post-26556211181167212222021-04-25T21:59:00.001+03:002021-04-25T21:59:22.229+03:00A cycle week<p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-FPzcFfZ6kI0/YIWfIf9fHDI/AAAAAAAC2-M/AX5QmP4kUYwSwuFhrwTNOQg7sNFIUuGZACLcBGAsYHQ/s1101/cf718top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="271" data-original-width="1101" height="158" src="https://1.bp.blogspot.com/-FPzcFfZ6kI0/YIWfIf9fHDI/AAAAAAAC2-M/AX5QmP4kUYwSwuFhrwTNOQg7sNFIUuGZACLcBGAsYHQ/w640-h158/cf718top5.png" width="640" /></a></div>Codeforces Round 718 (also known as "Contest 2050") took place on Friday (<a href="https://codeforces.com/contest/1517">problems</a>, <a href="https://codeforces.com/contest/1517/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/89968">analysis</a>). Benq solved the first seven problems 20 minutes faster than Um_nik, who in turn solved them almost half an hour faster than all other contestants. They were the only two top contestants who therefore had time to submit something in the last problem, it did not work out but nevertheless their first and second place were safe with a big margin. Congratulations on the impressive performance!<p></p><p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-Ry9FyTeMzZM/YIW6ifKNA0I/AAAAAAAC2_E/WAFJRe5JlbwfmLFQ9OxI6zH6YTqheoXDACLcBGAsYHQ/s1410/gcj21r1btop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="468" data-original-width="1410" height="212" src="https://1.bp.blogspot.com/-Ry9FyTeMzZM/YIW6ifKNA0I/AAAAAAAC2_E/WAFJRe5JlbwfmLFQ9OxI6zH6YTqheoXDACLcBGAsYHQ/w640-h212/gcj21r1btop5.png" width="640" /></a></div>Google Code Jam 2021 Round 1B finished a few minutes ago (<a href="https://codingcompetitions.withgoogle.com/codejam/round/0000000000435baf/00000000007ae37b">problems</a>, <a href="https://codingcompetitions.withgoogle.com/codejam/round/0000000000435baf">results</a>, top 5 on the left, <a href="https://codingcompetitions.withgoogle.com/codejam/round/0000000000435baf/00000000007ae37b#analysis">analysis</a>). neal_wu was the first to score 100 provisional points, but he made one incorrect attempt and therefore had to sit and wait for 4 minutes to see if somebody will overtake him. Nobody else was as fast, though, so Neal kept the first place. Congratulations to him and to all 1500 Round 2 advancers!<p></p><p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-fznd3Tfwtuc/YIWkQFAHjCI/AAAAAAAC2-4/Txvo8HGzQuMfxx_YmkmQ-pLjHQBLahrvgCLcBGAsYHQ/s2048/PXL_20210223_204846679.NIGHT.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1536" data-original-width="2048" height="480" src="https://1.bp.blogspot.com/-fznd3Tfwtuc/YIWkQFAHjCI/AAAAAAAC2-4/Txvo8HGzQuMfxx_YmkmQ-pLjHQBLahrvgCLcBGAsYHQ/w640-h480/PXL_20210223_204846679.NIGHT.jpg" width="640" /></a></div>In <a href="https://petr-mitrichev.blogspot.com/2021/04/a-yuri-week.html">my previous summary</a>, I have mentioned <a href="https://codeforces.com/contest/1508/problem/D">a Codeforces problem</a>: You are given <i>n</i><=2000 points on the plane such that no three points lie on the same line. Each point has an integer label between 1 and <i>n</i>, and all labels are distinct. Your goal is to rearrange the labels in such a way that the <i>i</i>-th point has label <i>i</i>. You are allowed to take any two points and swap their labels, but when you do that you must draw a straight line segment connecting those two points. The segments you draw must not intersect except at their endpoints (in particular, you are not allowed to draw the same segment twice).<p></p><p>The key trick to make progress in the problem is to find a less general, but still non-trivial case which we can solve. It turns out that such case is the one when the initial labeling of points forms a single cycle, for example: point 1 has label 2, point 2 has label 3, and so on, until point <i>n</i> which has label 1. In this case we can solve the problem using only the swaps that include point 1, and therefore their segments will not intersect: we start with labels 234...<i>n</i>1. We swap the labels of points 1 and 2, and we get 324...<i>n</i>1. We swap the labels of points 1 and 3, and we get 423...<i>n</i>1. We continue with swapping the labels of points 1 and 4, and so on, and eventually we get <i>n</i>234...(<i>n</i>-1)1, and finally we swap the labels of the first and last points to get the identity permutation. Note that our choice of point 1 as the "pivot" of all swaps was arbitrary, and we could do the same with any other point.</p><p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-GQLlFv0XkpA/YIWivRuOW0I/AAAAAAAC2-k/-4i3tnDdxGwWVpR_ADSe3e6uu5VpvmDZwCPcBGAsYHg/s2580/PXL_20210425_170948827.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" data-original-height="2062" data-original-width="2580" height="319" src="https://1.bp.blogspot.com/-GQLlFv0XkpA/YIWivRuOW0I/AAAAAAAC2-k/-4i3tnDdxGwWVpR_ADSe3e6uu5VpvmDZwCPcBGAsYHg/w400-h319/PXL_20210425_170948827.jpg" width="400" /></a></div>What should we do if the labels do not form a single cycle? Let's make some additional swaps <i>before</i> using the above approach to make sure they do! More specifically, let's assume our points are sorted by angle with respect to point 1. The above solution will only draw segments between point 1 and other points. Therefore we are free to swap the labels between adjacent points in this sorted order, as those segments will not intersect each other and the segments to point 1.<p></p><p>The initial permutation has some number of cycles, and whenever we swap two elements from different cycles they merge into one. While we have more than one cycle, we can find two adjacent points in the sorted order that belong to different cycles, and swap them to merge those cycles. We repeat this until we have just one cycle remaining, and then apply the single-cycle solution.</p><p>There are some additional small details to be figured out, which you can find in <a href="https://codeforces.com/blog/entry/89644">the official editorial</a>. I could not solve this problem myself, in part because the space of possible approaches is so vast, and yet most of them do not seem to work. I've checked the solutions for this problem from the top finishers, and they all seem to use this approach. In fact, I'm really curious: is some fundamentally different solution possible here? If not, does there exist some intuition why?</p><p>Thanks for reading, and check back next week.</p><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/0Nr9_jnmm9g" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com2http://petr-mitrichev.blogspot.com/2021/04/a-cycle-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-35694315671565790952021-04-18T12:32:00.000+03:002021-04-18T12:32:21.153+03:00A yuri week<p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-dxAaXRF-kME/YHvc5WSaQcI/AAAAAAAC22M/-RjrRPe3lsYCrrNlBsobz9td5bKnspddgCLcBGAsYHQ/s1324/cf715top5.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="337" data-original-width="1324" height="162" src="https://1.bp.blogspot.com/-dxAaXRF-kME/YHvc5WSaQcI/AAAAAAAC22M/-RjrRPe3lsYCrrNlBsobz9td5bKnspddgCLcBGAsYHQ/w640-h162/cf715top5.png" width="640" /></a></div>Codeforces Round 715 was the main round of this week (<a href="https://codeforces.com/contest/1508">problems</a>, <a href="https://codeforces.com/contest/1508/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/89644">analysis</a>). The first three problems were quite approachable, and the real fight for the top spots started on the remaining three. ecnerwala went for the 4000-point F instead of the 2250-point D, and this turned out to be exactly the right plan, as there was not enough time to solve all problems. Congratulations on the victory!<p></p><div>I have tried to make the same plan work, but unfortunately I could not solve F in time — my solution was written at the end of the contest, but it had two issues:</div><div><ul style="text-align: left;"><li>It did not work on the samples</li><li>Its complexity was O(<i>n</i><sup>2</sup>*log(<i>n</i>)) in the worst case (even though with a 7-second time limit this was not obviously bad)</li></ul><div>I could make it work on the samples in just a couple of minutes after the end of the contest, and the solution <a href="https://codeforces.com/contest/1508/submission/113261349">passed the system tests</a> — only to be hacked as the complexity was in fact too big. I would've probably reached the second place if I had those couple of minutes, and I'm still on the fence whether the fact that I'd have squeezed in an incorrect solution makes me regret this more or less :)</div></div><div><br /></div><div>I'd like to highlight another problem though, for which I had completely no working ideas during the contest: <a href="https://codeforces.com/contest/1508/problem/D">problem D</a>. You are given <i>n</i><=2000 points on the plane such that no three points lie on the same line. Each point has an integer label between 1 and <i>n</i>, and all labels are distinct. Your goal is to rearrange the labels in such a way that the <i>i</i>-th point has label <i>i</i>. You are allowed to take any two points and swap their labels, but when you do that you must draw a straight line segment connecting those two points. The segments you draw must not intersect except at their endpoints (in particular, you are not allowed to draw the same segment twice). Can you see a way to achieve the goal?</div><div><br /></div><div><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-D0yeyqq8R0o/YHv46Qo8yYI/AAAAAAAC22k/57ImKYh3E603tYC7FVXCevO49ZZr20kggCLcBGAsYHQ/s2048/PXL_20210214_131942502.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1536" data-original-width="2048" height="480" src="https://1.bp.blogspot.com/-D0yeyqq8R0o/YHv46Qo8yYI/AAAAAAAC22k/57ImKYh3E603tYC7FVXCevO49ZZr20kggCLcBGAsYHQ/w640-h480/PXL_20210214_131942502.jpg" width="640" /></a></div>In <a href="https://petr-mitrichev.blogspot.com/2021/04/an-esp-week.html">my previous summary</a>, I have mentioned <a href="https://codingcompetitions.withgoogle.com/codejam/round/000000000043585d/00000000007543d8">a Code Jam problem</a>: you are given up to 10<sup>15</sup> cards, each with a prime number between 2 and 499. You need to split the cards into two piles, such that the sum of the numbers in the first pile is equal to the product of the numbers in the second pile, or tell that it's impossible.</div><div><br /></div><div>The key idea here is that the product grows very quickly, so the second pile will always be very small. Therefore the sum of the numbers in the second pile will be small. But the sum of the numbers in the first pile is the sum of all given numbers minus the sum of the numbers in the second pile. If the sum of all given numbers is <i>S</i>, we just need to check all numbers in the segment [<i>S</i>-<i>C</i>,<i>S</i>] as the candidates for the sum of the numbers in the first pile (which is equal to the product of the numbers in the second pile) for some relatively small value of <i>C</i>.</div><div><br /></div><div>How do we check a particular candidate? Here the fact that all numbers are prime comes into play: since we know that the candidate is a product of some subset of the given numbers, and all of them are prime, there is in fact a unique decomposition for it as a product of primes. Factorizing a number this big can still be problematic, but since we're only interested in prime factors up to 499, it is fast enough.</div><div><br /></div><div>You can check <a href="https://codingcompetitions.withgoogle.com/codejam/round/000000000043585d/00000000007543d8#analysis">the official analysis</a> for more details, such as what is a reasonable value for <i>C</i>. Thanks for reading, and check back next week!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/0IDkpxJlBAc" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com2http://petr-mitrichev.blogspot.com/2021/04/a-yuri-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-4380984800207476392021-04-11T22:30:00.001+03:002021-04-11T22:30:12.873+03:00An ESP week<p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-aW1z65dM97g/YHNBkL7ZAiI/AAAAAAAC2wY/F1IAusL4IDMBS3iw5OZY9INKWnUfycpeQCLcBGAsYHQ/s1526/gcj21r1atop5.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="474" data-original-width="1526" height="198" src="https://1.bp.blogspot.com/-aW1z65dM97g/YHNBkL7ZAiI/AAAAAAAC2wY/F1IAusL4IDMBS3iw5OZY9INKWnUfycpeQCLcBGAsYHQ/w640-h198/gcj21r1atop5.png" width="640" /></a></div>Google Code Jam Round 1A was the first round of this week (<a href="https://codingcompetitions.withgoogle.com/codejam/round/000000000043585d/00000000007543d8">problems</a>, <a href="https://codingcompetitions.withgoogle.com/codejam/round/000000000043585d">results</a>, top 5 on the left, <a href="https://codingcompetitions.withgoogle.com/codejam/round/000000000043585d/00000000007543d8#analysis">analysis</a>). The top 1500 have made it to Round 2, with 3000 further spots up for grabs in the remaining two Round 1s. Nevertheless, the spirit of competition was there, and it is of course a great achievement to get the first place. Congratulations to Um_nik, and his achievement is even more impressive given that the round was probably at 4 in the morning :)<p></p><p>I have prepared the test data for the second problem, Prime Time, and I (humbly, of course :)) think it was a great example of how a not particularly difficult problem can still be nice. The problem went like this: you are given up to 10<sup>15</sup> cards, each with a prime number between 2 and 499. You need to split the cards into two piles, such that the sum of the numbers in the first pile is equal to the product of the numbers in the second pile, or tell that it's impossible. Can you see how to handle such a huge amount of cards?</p><p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-Z2vd4dSefCI/YHNJ8J-mI9I/AAAAAAAC2wg/J3w4uAq1iNM4nnr2VjjxZOyPMY2f-yZ6wCLcBGAsYHQ/s1001/agc053top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="418" data-original-width="1001" height="268" src="https://1.bp.blogspot.com/-Z2vd4dSefCI/YHNJ8J-mI9I/AAAAAAAC2wg/J3w4uAq1iNM4nnr2VjjxZOyPMY2f-yZ6wCLcBGAsYHQ/w640-h268/agc053top5.png" width="640" /></a></div>AtCoder has returned with its Grand Contest 053 a few hours later (<a href="https://atcoder.jp/contests/agc053/tasks">problems</a>, <a href="https://atcoder.jp/contests/agc053/standings">results</a>, top 5 on the left, <a href="https://atcoder.jp/contests/agc053/editorial">analysis</a>). I have solved the first three problems in less than 50 minutes, which was great, but then I could not score any additional points in the remaining 2 hours and 10 minutes, which was a bit frustrating :) I've tried to approach all three remaining problems in the beginning, but eventually focused on the problem E, and it turns out I was really close: I did identify the two cases from <a href="https://atcoder.jp/contests/agc053/editorial/1070">the official analysis</a>, I have correctly (I think) handled the first case and tried various formulas that looked very similar to the correct one for the second case, but I could neither figure out all details and come up with a formula on paper, nor get the correct answers for the sample cases by trying small changes to the formulas. It turns out that my problem was that I was inserting the segments in the increasing order of the starting time, instead of the decreasing order of the ending time. These two ideas look symmetric on the surface, but they actually are not equivalent because the problem asks about local maxima, and the symmetric case would be local minima. However, my idea can still handle the first case just as well (because the first case is in fact symmetric, as we have <i>n</i>-1 local minima there as well), which made it hard to move away from it for the second case.<p></p><p>Congratulations to the seven contestants who have managed to handle all details correctly and solve one of the harder problems, and especially to jiangly on the win!</p><p>Thanks for reading, and check back next week.</p><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/Yj-9-gp9iq4" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com2http://petr-mitrichev.blogspot.com/2021/04/an-esp-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-24295828694684681002021-04-05T17:38:00.001+03:002021-04-05T17:38:58.152+03:00A no-regret week<div><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-IgEEqWDADOU/YGsRlnlamxI/AAAAAAAC2nw/xMgoYWBDV3sjX2dtjEFPp6aLqAzQNaZ_QCLcBGAsYHQ/s634/srm803top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="97" data-original-width="634" src="https://1.bp.blogspot.com/-IgEEqWDADOU/YGsRlnlamxI/AAAAAAAC2nw/xMgoYWBDV3sjX2dtjEFPp6aLqAzQNaZ_QCLcBGAsYHQ/s16000/srm803top5.png" /></a></div>TopCoder SRM 803 last week wrapped up the third stage of the race for TCO21 qualification (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=18601">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=18601&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://clist.by/standings/tco21-algorithm-stage-3-20723471/">TCO21 race results</a>, <a href="https://www.topcoder.com/blog/single-round-match-803-editorials/">analysis</a>). Even though tourist had already guaranteed himself the first place and the direct ticket (or a direct login, in case it takes place online again :)) to TCO21, he has won the round with a big margin once again. This was his fourth SRM win in a row, which has happened before, but nobody else could win five in a row in the past. tourist has also claimed the all-time high rating during this streak. Congratulations Gennady, and no pressure at all for SRM 804 ;)</div><div><br /></div><div><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-gEUvlasWx5g/YGsTI_O4eTI/AAAAAAAC2n4/l5Gtpg8uImst4pE4sWJA3Qn3tSRIht5agCLcBGAsYHQ/s1105/cf712top5.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/-gEUvlasWx5g/YGsTI_O4eTI/AAAAAAAC2n4/l5Gtpg8uImst4pE4sWJA3Qn3tSRIht5agCLcBGAsYHQ/w640-h158/cf712top5.png" width="640" /></a></div>Codeforces Round 712 followed on Saturday (<a href="https://codeforces.com/contest/1503">problems</a>, <a href="https://codeforces.com/contest/1503/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/89319">analysis</a>). The last problem kind of screamed that some sort of a greedy approach for embedding each cycle should work, but figuring out all details of the approach, as well as implementing it, was still extremely hard. Very well done to ksun48 on doing that and getting a clear first place!</div><div><br /></div><div><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-rrg_DvQq--g/YGsUVIY9pzI/AAAAAAAC2oA/Q4JWZyM6d2oT3xmht3UL8rU8U0GngAaDgCLcBGAsYHQ/s1165/nerc2020onsitetop12.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="597" data-original-width="1165" height="328" src="https://1.bp.blogspot.com/-rrg_DvQq--g/YGsUVIY9pzI/AAAAAAAC2oA/Q4JWZyM6d2oT3xmht3UL8rU8U0GngAaDgCLcBGAsYHQ/w640-h328/nerc2020onsitetop12.png" width="640" /></a></div>Finally, the Northern Eurasia region of the ICPC held its onsite finals for the 2020-21 season on Sunday (<a href="http://nerc.itmo.ru/archive/2020/problems.pdf">problems</a>, <a href="http://nerc.itmo.ru/archive/2020/standings.html">results</a>, top 12 on the left, <a href="https://codeforces.com/contest/1510/standings">online mirror results</a>, <a href="http://nerc.itmo.ru/archive/2020/nerc-2020-offline-tutorial.pdf">analysis</a>). The top 50 teams from the online finals were invited to this round (how does one actually call the round between a semifinal and a final? A 2/3-final? A 1/sqrt(2)-final? :)). In the end, solving the 6 relatively easier problems was the bar for getting a medal, while getting a gold medal required also solving either the traditionally cactus-themed problem C, or the also traditionally interactive problem I. Congratulations to all medalists and especially to the team "Insert your name" from ITMO on the victory!</div><div><br /></div><div>I set that <a href="https://codeforces.com/contest/1510/problem/I">interactive problem I</a> for this round. Given that the contestants were onsite and did not have internet access during the round, it was a good opportunity to give a problem involving a beautiful but googleable algorithm: <a href="https://en.wikipedia.org/wiki/Randomized_weighted_majority_algorithm">the randomized weighted majority algorithm</a>. Preparing the test cases for this problem was extremely tricky, as the space of possible approaches is virtually unlimited, and there seems to be no single way to fail all of them. It turned out that the testcases were good enough for the onsite round, with the only two passing solutions using the provably correct approach, and with the top two teams probably accumulating quite some love for me with their -35 and -29 on this problem.</div><div><br /></div><div>In the online mirror, some more questionable, but at the same time really creative, <a href="https://codeforces.com/blog/entry/89224?#comment-777750">approaches</a> passed all tests. In fact, the ML approach pwns the test set, making several times <i>less</i> mistakes than <i>b</i> (the smallest the number of mistakes of experts) in most test cases. It only has difficulties on test cases with a really small <i>b</i> (say, 7 out of 10000), where the allowed leeway of 100 extra mistakes is barely enough for the neural network training to converge.</div><div><br /></div><div>It looks like I need to add some simple gradient descent and boosted decision forest algorithms to my prewritten code library for the future :)</div><div><div><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-FoQfk5cLnlU/YARt0dZqGQI/AAAAAAAC0p8/tSdeIfYdV402y3krGcheJbEVCTT2ylGKACLcBGAsYHQ/s2048/PXL_20210110_103620535.jpg" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1536" data-original-width="2048" height="480" src="https://1.bp.blogspot.com/-FoQfk5cLnlU/YARt0dZqGQI/AAAAAAAC0p8/tSdeIfYdV402y3krGcheJbEVCTT2ylGKACLcBGAsYHQ/w640-h480/PXL_20210110_103620535.jpg" width="640" /></a></div>In <a href="https://petr-mitrichev.blogspot.com/2021/01/a-samara-week.html">my previous summary</a>, I have mentioned <a href="https://codeforces.com/contest/1466/problem/I">a Codeforces problem</a>: there is a hidden array of <i>n</i> <i>b</i>-bit integers (in other words, each element is between 0 and 2<sup><i>b</i></sup>-1). You do not know the elements of the array, but you can ask questions about them: in one question, you can ask "is it true that the <i>i</i>-th element of the array is greater than <i>j</i>?" for some value of <i>i</i> between 1 and <i>n</i> and <i>j</i> between 0 and 2<sup><i>b</i></sup>-1. Your goal is to find the value of the maximum element in the array, and you need to do it in O(<i>n</i>+<i>b</i>) queries.<p></p></div></div><div>The first question is kind of expected: let's compare the first element of the array with 2<sup><i>b-1</i></sup>-1, in other words let's learn the highest bit of the first element. If that bit is 1, we're all good: we then know that the highest bit of the answer is also 1, therefore we have effectively reduced <i>b</i> by 1 using just one query, so we're on track for O(<i>n</i>+<i>b</i>) queries overall.</div><div><br /></div><div>The case where that bit is 0 is more interesting. We can't really afford to keep asking about the first bit of all numbers, since in case they are all 0, we would've spent <i>n</i> queries to reduce <i>b</i> by 1, which does not lead to a linear number of queries. This issue kind of points us to a better approach: in case the answers are always "less than", we want to be left with a really small range after asking the <i>n</i> queries. Therefore let's compare the second number with 2<sup><i>b-2</i></sup>-1, in other words let's ask "is it true that the two highest bits of the second number are 0"?</div><div><br /></div><div>In case we keep getting "less than" answers, after <i>n</i> queries we will know that the first number starts with 0, the second with 00, the third with 000, and so on. Now let's go from right to left, and ask "does the <i>n</i>-1-th number start with <i>n</i> zeros?". If not, then we know that the <i>n</i>-th number is smaller than the (<i>n</i>-1)-th number, and can be discarded for the rest of the solution, and we continue by asking "does the (<i>n</i>-2)-th number start with <i>n</i>-1 zeros?" If the (<i>n</i>-1)-th number does start with <i>n</i> zeros, we continue by asking "does the (<i>n</i>-2)-th number start with <i>n</i> zeros"? After we complete this process going from right to left, we will have discarded some amount <i>k</i> of all numbers, and will know that the remaining numbers all start with <i>n</i>-<i>k</i> zeros. Therefore we have reduced <i>n</i> by <i>k</i>, and <i>b</i> by <i>n</i>-<i>k</i>, so <i>n</i>+<i>b</i> was reduced by <i>n</i> using 2<i>n</i> queries, which is good enough for a linear solution!</div><div><br /></div><div>Finally, we need to figure out what to do in case we get some "greater" answer after a few "less than" answers, for example when we learn that the first number starts with 0, the second with 00, the third with 000, but the fourth does not start with 0000. We will then ask: does the fourth number start with 0001? If the answer is also no, then we know that the fourth number starts with at least 001, therefore it's greater than the third number which can be discarded, and we continue by asking if the fourth number really starts with 001, potentially discarding the second number if not, and so on. If the fourth number does start with 0001, then we continue with the fifth number, but instead of asking if it starts with 00000, we ask if its prefix is at least 00010 (since we're not really interested in numbers smaller than 0001, given that we already have evidence of a number that starts with 0001).</div><div><br /></div><div>At any moment, our algorithm therefore maintains a stack of numbers, where for each number we know a prefix that is equal to the prefix we know for the previous number in the stack plus one more bit. When we run out of bits, we do the backwards pass as described above, and obtain a problem of reduced size. Just like in the all-zeros case, we spend O(<i>n</i>) queries to reduce <i>n</i>+<i>b</i> by <i>n</i>, therefore achieving a linear solution.</div><div><br /></div><div>This is the main idea of the solution. There are still some small details to be figured out, which you can find in <a href="https://codeforces.com/blog/entry/86126">the official editorial</a>.</div><div><br /></div><div>Thanks for reading, and check back next week!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/ZB5jrqHeuME" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com4http://petr-mitrichev.blogspot.com/2021/04/a-no-regret-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-9759634526834961792021-01-04T20:30:00.002+03:002021-01-04T20:30:59.527+03:00A Samara week<p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-Xo134K7ZYnE/X_NGgZIIiTI/AAAAAAAC0DU/rAN9JcdxstAfWpcqP1T9l5v62rq9fnjjgCLcBGAsYHQ/s1325/cfgoodbye2020top5.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="335" data-original-width="1325" height="162" src="https://1.bp.blogspot.com/-Xo134K7ZYnE/X_NGgZIIiTI/AAAAAAAC0DU/rAN9JcdxstAfWpcqP1T9l5v62rq9fnjjgCLcBGAsYHQ/w640-h162/cfgoodbye2020top5.png" width="640" /></a></div>"Good Bye 2020" was the last round of the year on Codeforces (<a href="https://codeforces.com/contest/1466">problems</a>, <a href="https://codeforces.com/contest/1466/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/86126">analysis</a>). The round has left me with mixed feelings, as I've spent almost the whole 3 hours solving relatively standard problems, and did not have enough time to solve the very exciting problem I. The main reason for that was that I forgot how to count DAGs, and tried to reinvent the wheel in problem H for a very long time. tourist, on the other hand, did not struggle so much with H, and won the round. Well done! Also well done to scott_wu, fivedemands, mnbvmar and qwerty787788 who were able to solve the last problem.<p></p><p>Here's <a href="https://codeforces.com/contest/1466/problem/I">that exciting problem</a>: there is a hidden array of <i>n</i> <i>b</i>-bit integers (in other words, each element is between 0 and 2<sup><i>b</i></sup>-1). You do not know the elements of the array, but you can ask questions about them: in one question, you can ask "is it true that the <i>i</i>-th element of the array is greater than <i>j</i>?" for some value of <i>i</i> between 1 and <i>n</i> and <i>j</i> between 0 and 2<sup><i>b</i></sup>-1. Your goal is to find the value of the maximum element in the array, and you need to do it in O(<i>n</i>+<i>b</i>) queries. The problem actually asked to do it in at most 3*(<i>n</i>+<i>b</i>) queries, but I think just doing it in a linear number of queries is the most interesting part.</p><p>Note that simply finding each element with binary search would lead to <i>n</i>*<i>b</i> queries, and it's not clear initially how we can do any better as each query only asks about one element, and the elements are somewhat independent. Can you see the way? <i>n</i> and <i>b</i> are up to 200, and the interactor is adaptive (so your solution most likely needs to be deterministic).</p><p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-zZ5TKa5OyG0/X_NHZx01DrI/AAAAAAAC0Dc/NJExTi2-YsYErQFPxxdazdiDHKbAKoQDwCLcBGAsYHQ/s993/oc1920samaratop5.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="239" data-original-width="993" height="154" src="https://1.bp.blogspot.com/-zZ5TKa5OyG0/X_NHZx01DrI/AAAAAAAC0Dc/NJExTi2-YsYErQFPxxdazdiDHKbAKoQDwCLcBGAsYHQ/w640-h154/oc1920samaratop5.png" width="640" /></a></div>The new year pause was not long, and Open Cup 2020-21 Grand Prix of Samara took place on Sunday (<a href="http://opencup.ru/index.cgi?data=macros/stage&head=index&menu=index&stg=8&region=main&ncup=ocl&class=ocl">results</a>, top 5 on the left, <a href="https://drive.google.com/file/d/1ce5JkVcxmShnz7MLaiF4U7gwPRHeWrkA/view">analysis</a>, <a href="http://opencup.ru/index.cgi?data=macros/results&menu=index&head=index&ncup=ocl&class=ocl&region=main">overall Open Cup standings</a>). Unlike last year, which saw a fierce competition at the top of the overall Open Cup scoreboard between three teams, this year team USA1 really dominates the proceedings, and they won their 7th Grand Prix out of 8 this time, finishing all problems in 3.5 hours. Congratulations!<p></p><p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-PTvPIClge8o/X_NNdJSQMmI/AAAAAAAC0Ds/tt2yeq7TtVYJ8MDK-f6jmQ2GLA5FzDNiwCLcBGAsYHQ/s2048/IMG_20200705_143815.jpg" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1536" data-original-width="2048" height="480" src="https://1.bp.blogspot.com/-PTvPIClge8o/X_NNdJSQMmI/AAAAAAAC0Ds/tt2yeq7TtVYJ8MDK-f6jmQ2GLA5FzDNiwCLcBGAsYHQ/w640-h480/IMG_20200705_143815.jpg" width="640" /></a></div>The <a href="https://contest.yandex.com/newyear2021/contest/23945/enter/">Prime New Year Contest</a> is another staple of the holidays. It is running until the end of this week, and features the problems from 2020 which were not solved by anybody during respective contests. Good luck getting something accepted there, and huge respect to those who already did!<p></p><p><a href="https://1.bp.blogspot.com/-Z_GDqsUpzsA/X-uJH8ucHwI/AAAAAAACz2s/4kzQ_u1jyRkw4EikQNRBNZoRSTn8MQz0ACLcBGAsYHQ/s250/48a379ab79ee4edf503b84c8b7984d50.png" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em; text-align: center;"><img border="0" data-original-height="250" data-original-width="250" src="https://1.bp.blogspot.com/-Z_GDqsUpzsA/X-uJH8ucHwI/AAAAAAACz2s/4kzQ_u1jyRkw4EikQNRBNZoRSTn8MQz0ACLcBGAsYHQ/s0/48a379ab79ee4edf503b84c8b7984d50.png" /></a>In <a href="https://petr-mitrichev.blogspot.com/2020/12/a-rng58-week.html">my previous summary</a>, I have mentioned <a href="https://atcoder.jp/contests/agc051/tasks/agc051_d">an AtCoder problem</a>: you are given an undirected graph with four vertices and four edges that looks like a square (the picture from the statement on the right). You know that a walk started from vertex S, finished at vertex S, has passed the ST edge (in any direction) <i>a</i> times, the TU edge <i>b</i> times, the VU edge <i>c</i> times, and the SV edge <i>d</i> times. How many different walks fit that description? <i>a</i>, <i>b</i>, <i>c</i> and <i>d</i> are up to 500000, and you need to compute the answer modulo 998244353.</p><p>If we replace the ST edge with <i>a</i> parallel edges, the TU edge with <i>b</i> parallel edges, and so on, then we're looking for the number of <a href="https://en.wikipedia.org/wiki/Eulerian_path#Definition">Euler tours</a> in the resulting graph modulo dividing by some factorials to account for the fact that all parallel edges are equivalent. However, counting Euler tours in undirected graphs is hard.</p><p>But given the simple structure of our graph, we can actually reduce our problem to counting Euler tours in directed graphs, which can be done using the <a href="https://en.wikipedia.org/wiki/BEST_theorem">BEST theorem</a>! We can iterate over the number of times we pass the ST edge in the direction from S to T, in other words over how many ST arcs would our directed graph have. This determines the number of TS arcs by subtracting from <i>a</i>, then the number of SV and VS arcs from the constraint that the in-degree and out-degree of S must be the same, and so on until we know the number of times we pass each edge in each direction, and we can then count the Euler tours in the resulting graph in constant time (because the graph has 4 vertices and 8 "arc types", and the actual number of parallel arcs does not affect the running time of the BEST theorem). Since <i>a</i> is up to 500000, we have to do this constant time computation 500000 times, which is fast enough.</p><p>Thanks for reading, and check back next week!</p><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/rKRbuGPwTg8" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com0http://petr-mitrichev.blogspot.com/2021/01/a-samara-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-77419509064278823032020-12-29T23:09:00.000+03:002020-12-29T23:09:05.315+03:00A rng_58 week<p>Last week wrapped up the year for two major contest platforms — TopCoder and AtCoder — and with it the races to qualify to the corresponding onsites.</p><p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-905yNAVr2AU/X-s7RphMbLI/AAAAAAACz10/XNxamcWMCXASyT8a9Qr1aSClP4DELxpSACLcBGAsYHQ/s952/srm796top5.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="143" data-original-width="952" height="96" src="https://1.bp.blogspot.com/-905yNAVr2AU/X-s7RphMbLI/AAAAAAACz10/XNxamcWMCXASyT8a9Qr1aSClP4DELxpSACLcBGAsYHQ/w640-h96/srm796top5.png" width="640" /></a></div>TopCoder SRM 796 was the first round of the week (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=18432">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=18432&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-796-editorials/">analysis</a>). maroon_kuri was leading after the coding phase but failed the system tests; none of myself, tourist and Egor could find a challenge opportunity even though there were lots of them available, including in the 500-pointer which screamed "look for challenges here!" as it had just one sample case.<p></p><p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-L2TLMUsymK4/X-tCyEnPizI/AAAAAAACz2E/C4VV-e1hI3UzCVmP_5xvwOiSIzCEXi4gACLcBGAsYHQ/s1378/tco21stage2top5.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="458" data-original-width="1378" height="212" src="https://1.bp.blogspot.com/-L2TLMUsymK4/X-tCyEnPizI/AAAAAAACz2E/C4VV-e1hI3UzCVmP_5xvwOiSIzCEXi4gACLcBGAsYHQ/w640-h212/tco21stage2top5.png" width="640" /></a></div>This round concluded the three-month race for the second TCO21 spot (<a href="https://clist.by/standings/tco21-algorithm-stage-2-20723470/">results</a>, top 5 on the left). Even though six SRMs is quite a lot, the race came down to the wire and to a lot of very close calls: in SRM 792, neal_wu produced an amazing 200-point challenge phase to get a 3-point advantage and deny Um_nik the 5 race points; in SRM 793, tourist's easy was challenged but he would still win the round had ksun48 not taken his turn to earn 200 challenge points; you can see the story of SRM 796 above.<p></p><p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-DRb8X5T-PPo/X-tD2OPlRAI/AAAAAAACz2Q/-I1TUEeik-M7c0r8DhoqeizEIpKWvPFKQCLcBGAsYHQ/s1005/agc050top5.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="425" data-original-width="1005" height="270" src="https://1.bp.blogspot.com/-DRb8X5T-PPo/X-tD2OPlRAI/AAAAAAACz2Q/-I1TUEeik-M7c0r8DhoqeizEIpKWvPFKQCLcBGAsYHQ/w640-h270/agc050top5.png" width="640" /></a></div>AtCoder held its two last rounds of the year on the weekend, starting with AtCoder Grand Contest 050 on Saturday (<a href="https://atcoder.jp/contests/agc050/tasks">problems</a>, <a href="https://atcoder.jp/contests/agc050/standings">results</a>, top 5 on the left, <a href="https://atcoder.jp/contests/agc050/editorial">analysis</a>). Um_nik was the fastest on the four relatively easier problems, and protected his lead by finding the main insight <i>and</i> figuring out all details in the very tricky problem F. Congratulations on the win! duality and newbiedmy were also able to solve the hardest problem, and rounded up the top three. newbiedmy in particular must've had one hell of a contest: he started with this problem, and did not give up after 11 incorrect attempts. This unusual strategy was richly rewarded!<div><p></p><p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-TyLtFK3f6JI/X-tEM8oZoyI/AAAAAAACz2Y/JExHgnfUmSwoIr_f_bvTd7-N4eN2YsqhACLcBGAsYHQ/s1006/agc051top5.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="424" data-original-width="1006" height="270" src="https://1.bp.blogspot.com/-TyLtFK3f6JI/X-tEM8oZoyI/AAAAAAACz2Y/JExHgnfUmSwoIr_f_bvTd7-N4eN2YsqhACLcBGAsYHQ/w640-h270/agc051top5.png" width="640" /></a></div>AtCoder Grand Contest 051 on Sunday was the last contest of rng_58 as AtCoder admin (<a href="https://atcoder.jp/contests/agc051/tasks">problems</a>, <a href="https://atcoder.jp/contests/agc051/standings">results</a>, top 5 on the left, <a href="https://atcoder.jp/contests/agc051/editorial">analysis</a>). Even though the point values were different, the scoreboard looks very similar: the first four problems were solved by many, while the last two were very hard and only got accepted solutions in the last 45 minutes of the 4.5-hour contest. semiexp and yutaka1999 went for problem F which gave them more points and the first two places. Congratulations!</div><div><br /></div><div><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-Z_GDqsUpzsA/X-uJH8ucHwI/AAAAAAACz2s/4kzQ_u1jyRkw4EikQNRBNZoRSTn8MQz0ACLcBGAsYHQ/s250/48a379ab79ee4edf503b84c8b7984d50.png" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" data-original-height="250" data-original-width="250" src="https://1.bp.blogspot.com/-Z_GDqsUpzsA/X-uJH8ucHwI/AAAAAAACz2s/4kzQ_u1jyRkw4EikQNRBNZoRSTn8MQz0ACLcBGAsYHQ/s0/48a379ab79ee4edf503b84c8b7984d50.png" /></a></div>I'd like to highlight <a href="https://atcoder.jp/contests/agc051/tasks/agc051_d">problem D</a>: you are given an undirected graph with four vertices and four edges that looks like a square (the picture from the statement on the right). You know that a walk started from vertex S, finished at vertex S, has passed the ST edge (in any direction) <i>a</i> times, the TU edge <i>b</i> times, the VU edge <i>c</i> times, and the SV edge <i>d</i> times. How many different walks fit that description? <i>a</i>, <i>b</i>, <i>c</i> and <i>d</i> are up to 500000, and you need to compute the answer modulo 998244353.</div><div><br /></div><div>Given that Makoto (rng_58) is retiring as AtCoder admin, I'd like to thank him for bringing AtCoder to the English-speaking world, and for making it <i>the</i> place for solving awesome problems. Extremely well done!<br /><p></p><p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-VMJtioOJD54/X-tEuiVx-pI/AAAAAAACz2g/IBzGYLR-FZwfHdeOhRu_EUCYxWGClRGuwCLcBGAsYHQ/s1681/atcoder2020top5.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="465" data-original-width="1681" height="178" src="https://1.bp.blogspot.com/-VMJtioOJD54/X-tEuiVx-pI/AAAAAAACz2g/IBzGYLR-FZwfHdeOhRu_EUCYxWGClRGuwCLcBGAsYHQ/w640-h178/atcoder2020top5.png" width="640" /></a></div>The two rounds have concluded the race for the 8 AtCoder World Tour Finals spots (<a href="https://clist.by/standings/atcoder-race-ranking-2020-19846514/">results</a>, top 8 on the left). Congratulations to all finalists! This is the third season of the AtCoder points system. The top 8 has quite a big intersection with those from the two previous years (<a href="https://docs.google.com/spreadsheets/d/1T-hKu_vIh8l4EiW6XTWOvP0evzsWj0f45JNNgou21Cc/edit#gid=695896678">2018</a>, <a href="https://clist.by/standings/atcoder-race-ranking-2019-19844250/">2019</a>), with tourist, Um_nik and myself qualifying all three times, and ecnerwala and mnbvmar qualifying last year. It will be the first WTF for Benq, Stonefeang and endagorion, assuming it does actually take place of course :)<p></p><p>Thanks for reading, and Happy New Year!</p></div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/AuoTAXQhakg" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com0http://petr-mitrichev.blogspot.com/2020/12/a-rng58-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-73402610658738997332020-11-23T01:49:00.002+03:002020-11-25T17:55:38.698+03:00A Seattle week<p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-9-SyqOpvnIc/X7rUzVWwhvI/AAAAAAACy7k/exSrOSrAUTE2pi7pyeX6-zKaEaTOrFOTACLcBGAsYHQ/s1103/cf684top5.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="274" data-original-width="1103" height="158" src="https://1.bp.blogspot.com/-9-SyqOpvnIc/X7rUzVWwhvI/AAAAAAACy7k/exSrOSrAUTE2pi7pyeX6-zKaEaTOrFOTACLcBGAsYHQ/w640-h158/cf684top5.png" width="640" /></a></div>Codeforces Round 684 warmed the contestants up before the remaining TCO20 rounds (<a href="https://codeforces.com/contest/1439">problems</a>, <a href="https://codeforces.com/contest/1439/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/84731">analysis</a>). It was very close between the top 3, but ecnerwala has managed to avoid getting TLE on pretests in the last problem (and therefore having to spend more time speeding up the solution) and thus gained a very small edge. Congratulations on the first place!<p></p><p>The problemsetters received <a href="https://codeforces.com/blog/entry/84662?#comment-722438">a lot of flak</a> for the tight time limits. I have not solved the round myself, so I can't offer any firsthand experience. However, I found it quite impressive that three different coders were complaining about having to squeeze their solutions only to learn that the have bad asymptotic complexity (<a href="https://codeforces.com/blog/entry/84662?#comment-722615">1</a>, <a href="https://codeforces.com/blog/entry/84662?#comment-722724">2</a>, <a href="https://codeforces.com/blog/entry/84662?#comment-722580">3</a> — thanks a lot to dorijanlendvaj for investigating those!). </p><p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-klynYHNBo20/X7rZcfVM4MI/AAAAAAACy7w/5z7K4UtUydYVhU-4Eglb85deWA3ULZJngCLcBGAsYHQ/s766/tco20semi2top8.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="214" data-original-width="766" height="178" src="https://1.bp.blogspot.com/-klynYHNBo20/X7rZcfVM4MI/AAAAAAACy7w/5z7K4UtUydYVhU-4Eglb85deWA3ULZJngCLcBGAsYHQ/w640-h178/tco20semi2top8.png" width="640" /></a></div>TCO20 Semifinal 2 followed next day (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=18399">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=18399&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a> on the left, <a href="https://youtu.be/4MY3HZPkFUY">stream recording</a>, <a href="https://www.topcoder.com/2020-tco-algorithm-semi-final2-editorials/">analysis</a>). The problems were significantly easier compared to Semifinal 1, with a relatively standard easy, a unique but not very hard medium, and a hard which was mostly solved by printing out the nimbers for small inputs and figuring out a pattern. Solving all three problems was enough to advance without any additional concerns; Egor and uwi solved two each, and Egor got ahead thanks to uwi's resubmit and his own successful challenge.<div><br /></div><div><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-N8L_qLvhnpg/X75wWcX3xCI/AAAAAAACy-k/MKahwVJLyWo30KzZpSkotOXYeUc6pLGiwCLcBGAsYHQ/s880/Screenshot%2B2020-11-25%2Bat%2B3.54.12%2BPM%2B-%2BDisplay%2B2.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="268" data-original-width="880" height="194" src="https://1.bp.blogspot.com/-N8L_qLvhnpg/X75wWcX3xCI/AAAAAAACy-k/MKahwVJLyWo30KzZpSkotOXYeUc6pLGiwCLcBGAsYHQ/w640-h194/Screenshot%2B2020-11-25%2Bat%2B3.54.12%2BPM%2B-%2BDisplay%2B2.png" width="640" /></a></div>The top 4 from this round, together with the top 5 from the first round, competed in the TCO20 Final on Saturday (results on the left, <a href="https://youtu.be/-wuSA5c-xWM">stream recording</a>). The problems were also not too difficult, and the competition came down to speed and random bugs, with less than 50 points separating many contestants at the top. tourist was just a tiny bit faster than everybody except Um_nik, and Um_nik's hard failed the system tests paving the way for the second TCO victory in a row for tourist — congratulations!<div><br /></div><div>My contest was compromised early by two things: first, I had to resubmit the easy because I forgot to apply the modulo in one of the operations and therefore got an integer overflow. I guess it is a good lesson that tells me to start using a "modint" class that everybody else is using (which might be prohibitively slow in Java, but fine in C++). Second, after opening the medium I've immediately started to implement a brute force solution that computes the losing positions for small inputs, inspired by what happened in the semifinal. This strategy has backfired in this problem, as just a tiny bit of thinking on paper could've allowed me to achieve the same insight (that the losing positions are exactly the same as in the normal Nim) much quicker. I was therefore more than 100 points behind tourist and Um_nik after the first two problems.</div><div><br /></div><div>I have managed to recover a big part of that gap on the hard problem, using the same strategy — implementing a brute force solution to see a pattern that enables a real solution (that all interesting states are the multiples of interesting 0/1 states), so one could say that this strategy worked out about even if one looks at the medium and hard combined.</div><div><br /></div><div>I was therefore less than 50 points behind the first place, and needed just one successful challenge to win. I could not find any incorrect solutions, though, so I went with a last-second challenge on neal_wu's medium, which used an approach that was different from the approach that I and most others have taken, and which I hypothesized could TLE. It turned out it was fast enough, but I think it was definitely worth a try.</div><div><br /></div><div>It is also interesting that the only incorrect solution in this round — Um_nik's hard — had a bug that I considered during the coding phase: it computed differences with the previous element instead of differences with the next element on every iteration. However, I was not sure if this bug can affect the results, so I've ran both variants of my solution on the biggest testcase (26, 10<sup>18</sup>), and they indeed gave the same output. I've thought that maybe the parity of <i>n</i> plays a role, so I've also tried (25, 10<sup>18</sup>) and the results were also the same, which got me completely convinced that the direction does not matter :) It turns out that both (24, 10<sup>18</sup>) and (26, 10<sup>17</sup>) have different outputs for those two solutions, so I was really close to discovering this and then checking all other solutions for this bug and challenging Um_nik successfully.</div><div><br /></div><div>It is a bit more painful to come so close to winning in multiple ways (compared to for example 2019 where I did not really have any chance). Well, better luck next time, and congratulations to tourist once again!</div><div><br /></div><div><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-uMKsSpb6czc/X7rqPDRVhjI/AAAAAAACy8M/McADCjGCpHIVlK4VAhLfPJlRm0W1YGy3ACLcBGAsYHQ/s2048/IMG_20200621_152620.jpg" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1299" data-original-width="2048" height="406" src="https://1.bp.blogspot.com/-uMKsSpb6czc/X7rqPDRVhjI/AAAAAAACy8M/McADCjGCpHIVlK4VAhLfPJlRm0W1YGy3ACLcBGAsYHQ/w640-h406/IMG_20200621_152620.jpg" width="640" /></a></div>In <a href="https://petr-mitrichev.blogspot.com/2020/11/a-clean-slate-week.html">my previous summary</a>, I have mentioned <a href="https://atcoder.jp/contests/agc049/tasks/agc049_e">an AtCoder problem</a>: you start with a sequence of <i>n</i> zeros (<i>n</i><=50), and can apply the following four operations any number of times:</div><div><ol style="text-align: left;"><li>Add one to any number. This operation costs 1.</li><li>Subtract one from any number. This operation costs 1.</li><li>Add one to any contiguous segment of numbers. This operation costs C.</li><li>Subtract one from any contiguous segment of numbers. This operation costs C.</li></ol>Now, you are given <i>k</i> (<i>k</i><=50) candidates for each value in the final state of the sequence, each candidate is between 1 and 10<sup>9</sup>. You need to find sum of the minimum costs to obtain the final state for each of <i>k<sup>n</sup></i> possible final states, modulo 10<sup>9</sup>+7.</div><div><br /></div><div>Swistakk has explained my approach in <a href="https://codeforces.com/blog/entry/84664?#comment-721679">this comment</a>, so I will only clarify that reducing the problem to O(<i>n</i>*<i>k</i>) problems where each element is 0 or 1 is done by considering independent problems "how to add 1 to all numbers which must be >=1 in the end", "how to add 1 to all numbers which must be >=2 in the end" and so on.</div><div><br /></div><div>November was quite packed with onsite finals that were in limbo given the circumstances, and ended up happening online close to the end of the year. Now most of them have passed (VK Cup, Yandex Cup, TopCoder Open), AtCoder WTF is most likely postponed further (judging from the list of upcoming contests <a href="https://atcoder.jp/contests/">here</a>), so the only remaining big onsite-turned-online final (and my last chance to win something this year) is the Facebook Hacker Cup on December 5.</div><div><br /></div><div>Thanks for reading, and check back next week!</div></div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/nqpDDMpW9Rg" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com3http://petr-mitrichev.blogspot.com/2020/11/a-seattle-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-83216147263540721582020-11-15T23:34:00.005+03:002020-11-16T00:14:44.362+03:00A clean slate week<p>I think it's really past time to admit that I can't keep up with the weekly schedule, and start enjoying writing the posts instead of stressing about the backlog of several months. So, here comes: </p><p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-p0HqkjJ93OE/X7F4zqpJ1lI/AAAAAAACywc/M7wG0ytcrVILJb_6szXsOvkmv6MfIa7awCLcBGAsYHQ/s1125/kotlin5top5.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="270" data-original-width="1125" height="154" src="https://1.bp.blogspot.com/-p0HqkjJ93OE/X7F4zqpJ1lI/AAAAAAACywc/M7wG0ytcrVILJb_6szXsOvkmv6MfIa7awCLcBGAsYHQ/w640-h154/kotlin5top5.png" width="640" /></a></div>This week's competitive programming events started with the Kotlin Heroes 5 on Codeforces (<a href="https://codeforces.com/contest/1431">problems</a>, <a href="https://codeforces.com/contest/1431/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/84563">analysis</a>). Gone is the idea to auto-convert from Java, as everyone in top 5 seemingly writes somewhat idiomatic Kotlin directly (however I'm wondering if it looks idiomatic to Roman Elizarov :)). tourist and Benq were the only contestants to solve all problems, but Benq's chance to catch tourist was mostly gone with the incorrect attempt on problem D on the 12-th minute, which he took 9 minutes to correct and therefore fell behind so much he could not really recover. Congratulations to both on the great performance!<p></p><p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-r90CRK324Is/X7GBtbiQp8I/AAAAAAACyxU/lB29WouBxIM8Ib9Mc9-XtBxz-VNr4uA4gCLcBGAsYHQ/s758/tco20semi1top8.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="216" data-original-width="758" height="182" src="https://1.bp.blogspot.com/-r90CRK324Is/X7GBtbiQp8I/AAAAAAACyxU/lB29WouBxIM8Ib9Mc9-XtBxz-VNr4uA4gCLcBGAsYHQ/w640-h182/tco20semi1top8.png" width="640" /></a></div>TopCoder Open 2020 has opened its virtual doors with Semifinal 1 (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=18398">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=18398&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a> on the left, <a href="https://youtu.be/51TmU_Y72UE">stream recording</a>). The round was marred by <a href="https://codeforces.com/blog/entry/84570?#comment-720801">an incorrect reference solution</a> for the 500, seemingly making the problem unsolvable, at least within the time of the round, and resulting in neal_wu's challenge requests not being processed. In the end, the organizers have awarded him 50 challenge points as well (so we got +100 challenge points with just one incorrect submission :)), and advanced five competitors to the finals instead of four. Congratulations to all five! I think this is a decent solution to this situation, but I'm wondering if rerunning the round from scratch with a different set of problems would (arguably, of course) be more fair.<p></p><p>I have been commentating the round on the stream, and I didn't really do it well. First of all, I've had one job — to read the handles of the Russian competitors correctly — and still managed to mispronounce Um_nik's handle :( To add insult to injury, I did not name him in my list of contestants who have been doing very well recently, which was of course an obvious oversight. I'd like to take this opportunity and apologize to Alexey!</p><p>There were also serious connection issues which resulted in my voice not making it to the stream in many cases, and in us talking over each other a few times :( In addition, I have <a href="https://codeforces.com/blog/entry/84570?#comment-720811">assumed</a> that the first solution for the medium that came to our mind would run in time, while it actually did not. Streaming is hard! Please share any improvement suggestions that you have, I hope to do better next time.</p><p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-fG6zHSL5Lvc/X7GJBlzvSII/AAAAAAACyxo/e5Dad5xNj80MeJkVNo6zVtnqAoojURQOQCLcBGAsYHQ/s832/agc049top5.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="347" data-original-width="832" height="266" src="https://1.bp.blogspot.com/-fG6zHSL5Lvc/X7GJBlzvSII/AAAAAAACyxo/e5Dad5xNj80MeJkVNo6zVtnqAoojURQOQCLcBGAsYHQ/w640-h266/agc049top5.png" width="640" /></a></div>AtCoder Grand Contest 049 followed on Saturday (<a href="https://atcoder.jp/contests/agc049/tasks">problems</a>, <a href="https://atcoder.jp/contests/agc049/standings">results</a>, top 5 on the left, <a href="https://atcoder.jp/contests/agc049/editorial">analysis</a>). Um_nik breezed through the first five problems, and since the last problem was too tough to crack, his first place was not really in doubt. Well done! <a href="https://clist.by/standings/atcoder-race-ranking-2020-19846514/">The race</a> towards the 8 WTF spots is close to its conclusion (assuming there will be 1 or 2 more qualifying AGCs), with the top 4 most likely already booking their spots, mnbvmar being almost there, and maybe maroonrk as well if he keeps being a writer in the remaining rounds :)<div><br /></div><div>In keeping with the meta-story of <a href="https://atcoder.jp/contests/agc049/tasks/agc049_e">problem E</a>, I came up with a solution that seems to have exactly zero things in common with <a href="https://atcoder.jp/contests/agc049/editorial/335">the editorial</a> :) Here is the problem statement: you start with a sequence of <i>n</i> zeros (<i>n</i><=50), and can apply the following four operations any number of times:</div><div><ol style="text-align: left;"><li>Add one to any number. This operation costs 1.</li><li>Subtract one from any number. This operation costs 1.</li><li>Add one to any contiguous segment of numbers. This operation costs C.</li><li>Subtract one from any contiguous segment of numbers. This operation costs C.</li></ol>Now, you are given <i>k</i> (<i>k</i><=50) candidates for each value in the final state of the sequence, each candidate is between 1 and 10<sup>9</sup>. You need to find sum of the minimum costs to obtain the final state for each of <i>k<sup>n</sup></i> possible final states, modulo 10<sup>9</sup>+7.</div><div><div><p></p><p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-93mmzbCcIh0/X7F-4m6kGtI/AAAAAAACyw0/ww5xbptNoqEwLWH1ueWSIRhUvyxmUnQeACLcBGAsYHQ/s923/lockout1top8.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="923" data-original-width="785" height="400" src="https://1.bp.blogspot.com/-93mmzbCcIh0/X7F-4m6kGtI/AAAAAAACyw0/ww5xbptNoqEwLWH1ueWSIRhUvyxmUnQeACLcBGAsYHQ/w340-h400/lockout1top8.png" width="340" /></a></div>Right after the end of the AtCoder round, Errichto hosted the final 8 of the first open Lockout tournament organized by Geothermal (<a href="https://codeforces.com/blog/entry/81395">details</a>, <a href="https://youtu.be/y2UmXiwzlco">stream recording</a>, top 8 bracket on the left). pseudocoder10 has created an <a href="https://codeforces.com/blog/entry/78546">excellent bot</a> that runs the matches and automatically picks Codeforces problems of appropriate difficulty that both participants have not solved yet, and the system with 6 problems and 100-200-300-400-500-600 point values provided for a big strategic variety and made the matches very exciting to watch. Well done to everyone involved, and congratulations to Um_nik on the victory!</div><div><br /></div><div>rng_58 is running <a href="https://codeforces.com/blog/entry/84506">another iteration</a> on new problems (future AtCoder Regular Contests), consider signing up if you're 2800+ on AtCoder!<br /><p></p><p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-qpa5wGy07t8/X7F_gVoZfNI/AAAAAAACyw8/Uz8CLjXPRSwjG_RvIXRsG2T9dTIgjUTLgCLcBGAsYHQ/s1102/cf683top5.png" 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/-qpa5wGy07t8/X7F_gVoZfNI/AAAAAAACyw8/Uz8CLjXPRSwjG_RvIXRsG2T9dTIgjUTLgCLcBGAsYHQ/w640-h156/cf683top5.png" width="640" /></a></div>Codeforces Round 683 wrapped up the week (<a href="https://codeforces.com/contest/1446">problems</a>, <a href="https://codeforces.com/contest/1446/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/82067">analysis</a>). Um_nik has solved problem E in a seemingly normal rhythm, and went on to solve everything with almost half an hour to spare and win the round. Most of the others could not get past pretest 3 in problem E (Um_nik also had two attempts that stopped there), with ksun48 advancing as far as pretest 5. Congratulations to Um_nik on the convincing victory!</div><div><br /></div><div><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-zM_Rgoj9Z9A/X7GQBc361pI/AAAAAAACyyE/eVrw7emL2D8sROf6BKIee1sHEEajnd7DQCLcBGAsYHQ/s474/umnikdiff.png" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" data-original-height="346" data-original-width="474" height="234" src="https://1.bp.blogspot.com/-zM_Rgoj9Z9A/X7GQBc361pI/AAAAAAACyyE/eVrw7emL2D8sROf6BKIee1sHEEajnd7DQCLcBGAsYHQ/w320-h234/umnikdiff.png" width="320" /></a></div>The diff between his passing solution and "wrong answer on pretest 3" attempt is small, but it does seem to be a substantial fix to the solution logic (see it on the right).<p></p><p>Thanks for reading, and check back (maybe) next week!</p></div></div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/6FJzZwhBEnw" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com5http://petr-mitrichev.blogspot.com/2020/11/a-clean-slate-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-26373016900243832332020-09-20T12:44:00.003+03:002020-09-20T12:46:48.104+03:00An unexpected verdict week<p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-MG5pIEvPGoA/X15HjebHdqI/AAAAAAACw5c/clPXdnG3WPwTf3Qqcz1a4e_6C6vN9jpZQCLcBGAsYHQ/s1105/cf658top5.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="269" data-original-width="1105" height="156" src="https://1.bp.blogspot.com/-MG5pIEvPGoA/X15HjebHdqI/AAAAAAACw5c/clPXdnG3WPwTf3Qqcz1a4e_6C6vN9jpZQCLcBGAsYHQ/w640-h156/cf658top5.png" width="640" /></a></div>Codeforces Round 658 was the first event of the Jul 20 - Jul 26 week (<a href="https://codeforces.com/contest/1381" target="_blank">problems</a>, <a href="https://codeforces.com/contest/1381/standings" target="_blank">results</a>, top 5 on the left, <a href="https://youtu.be/VaCa0CQpYbo" target="_blank">my screencast</a>, <a href="https://codeforces.com/blog/entry/80427" target="_blank">analysis</a>). Benq has managed to finish all six problems in time, even though the first five would be enough for the first place anyway. Congratulations on the confident victory!<div><br /></div><div>I have managed to dig myself out of the piecewise quadratic function world with just 8 minutes to go, which was still quite satisfying even though competing with Benq was completely out of question :)<br /><p></p><p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-8xOmECgfwZ0/X2cPQ4zjIBI/AAAAAAACxDg/cKgTW-Wev3sMcv2dl7BNEsZGF9xiG4kKwCLcBGAsYHQ/s784/srm788top5.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="146" data-original-width="784" height="120" src="https://1.bp.blogspot.com/-8xOmECgfwZ0/X2cPQ4zjIBI/AAAAAAACxDg/cKgTW-Wev3sMcv2dl7BNEsZGF9xiG4kKwCLcBGAsYHQ/w640-h120/srm788top5.png" width="640" /></a></div>TopCoder SRM 788 started the race for the first TCO21 spot (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=18085" target="_blank">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=18085&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc" target="_blank">results</a>, top 5 on the left, <a href="https://youtu.be/yrFAMaDVbOo" target="_blank">my screencast</a>, <a href="https://www.topcoder.com/single-round-match-788-editorials/">analysis</a>). My easy-hard-medium strategy has hurt me this time, as after submitting the hard I saw others get 500+ points for the medium and submitted it without enough thinking, leading to a resubmit later. On the other hand, I could submit, stress-test, debug, fix and resubmit it without the pressure of "should I switch to the hard instead?" :) It was hard to fight for the top places with the resubmission. Even though the medium problem was much harder than the other two for lyrically as well, she got it right from the first attempt and earned 5 TCO21 points. Congratulations!</div><div><br /></div><div>Here is <a href="https://community.topcoder.com/stat?c=problem_statement&pm=16055&rd=18085">the problem</a> that caused all this mess: you are given an <i>H</i> times <i>W</i> grid (<i>H</i>*<i>W</i><=500), with some of the boundaries between cells being passable, and some being walls. All outside boundaries are walls. Your goal is to remove some more non-outside walls in such a way that the remaining walls split the entire grid into rectangular areas without internal walls. What is the maximum number of such rectangles one can get?<br /><p></p><p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-oIPncXQ8-Fk/X15IIYmK0SI/AAAAAAACw5k/AsdC47GYQbQ5x5cItflmlMfPXvdyAlmugCLcBGAsYHQ/s1095/cf659top5.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="270" data-original-width="1095" height="158" src="https://1.bp.blogspot.com/-oIPncXQ8-Fk/X15IIYmK0SI/AAAAAAACw5k/AsdC47GYQbQ5x5cItflmlMfPXvdyAlmugCLcBGAsYHQ/w640-h158/cf659top5.png" width="640" /></a></div>Codeforces Round 659 then revealed <a href="https://codeforces.com/blog/entry/80422?#comment-669472">the origin of "Polish Mafia" team name</a> (<a href="https://codeforces.com/contest/1383">problems</a>, <a href="https://codeforces.com/contest/1383/standings" target="_blank">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/80562" target="_blank">analysis</a>). I could not solve problem C (neither could I solve problem F, but I did not spend much time on it), and I was <a href="https://codeforces.com/blog/entry/80422?#comment-668119">not alone</a>. That makes the performance of tourist, Benq and Radewoosh who solved all six problems even more impressive, well done! Even they have solved problem C as their last or next-to-last problem, suggesting it was also quite tricky for them.</div><div><br /></div><div>Here is <a href="https://codeforces.com/contest/1383/problem/C">that problem</a>: you are given a string of length up to 10<sup>5</sup>, consisting of the first 20 lowercase English letters. In one step, you can pick any set of characters in this string that are all equal (not necessarily all occurrences of that character), and change all of them to some other character (the same for all replacements in this step). What is the smallest number of steps needed to obtain the other given string of the same length?</div><div><br /></div><div>I would also like to highlight the excellent <a href="https://codeforces.com/blog/entry/80627">investigation by maroonrk</a> on the practical performance of modern flow algorithms :)<br /><p></p><p>Thanks for reading, and check back for more!</p></div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/P9kPMOahHdU" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com2http://petr-mitrichev.blogspot.com/2020/09/an-unexpected-verdict-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-91742570422795549752020-09-13T19:10:00.007+03:002020-09-13T19:10:59.155+03:00An Eggheads week<p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-nCFcNo5z6c4/X15Ce3nd6wI/AAAAAAACw5Q/o-AVoTG4ERkKKB803NrpwFUmRBKCUATSACLcBGAsYHQ/s771/tco20r2btop5.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="145" data-original-width="771" height="120" src="https://1.bp.blogspot.com/-nCFcNo5z6c4/X15Ce3nd6wI/AAAAAAACw5Q/o-AVoTG4ERkKKB803NrpwFUmRBKCUATSACLcBGAsYHQ/w640-h120/tco20r2btop5.png" width="640" /></a></div>The Jul 13 - Jul 19 week was the second TopCoder-only week in a row, with TopCoder Open 2020 Round 2B (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=18074" target="_blank">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=18074&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc" target="_blank">results</a>, top 5 on the left, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=18075&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc" target="_blank">parallel round results</a>, <a href="https://youtu.be/qBhDm7C7Caw" target="_blank">my screencast</a>, <a href="https://www.topcoder.com/2020-tco-round-2b-editorials/" target="_blank">analysis</a>). 203 more contestants advanced to Round 3, and DmitryGrigorev was on the first place thanks to going for easy+hard. Congratulations! Nobody was able to solve all three problems, and the score from easy+medium was only good enough for the 5th place.<p></p><p>Check back for more :)</p><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/UrbZgciOWSI" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com1http://petr-mitrichev.blogspot.com/2020/09/an-eggheads-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-13403426224177700372020-09-13T18:49:00.002+03:002020-09-13T18:49:27.737+03:00A stable bubble week<p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-SCxP0xapBuU/X1x9shBDeCI/AAAAAAACwzM/fFMgbVREz4M2slG1q-ucHX2VShqXcFh7wCLcBGAsYHQ/s783/tco20r2atop5.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="145" data-original-width="783" height="118" src="https://1.bp.blogspot.com/-SCxP0xapBuU/X1x9shBDeCI/AAAAAAACwzM/fFMgbVREz4M2slG1q-ucHX2VShqXcFh7wCLcBGAsYHQ/w640-h118/tco20r2atop5.png" width="640" /></a></div>TopCoder Open 2020 Round 2A was the main event of Jul 6 - Jul 12 week (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=18068" target="_blank">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=18068&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc" target="_blank">results</a>, top 5 on the left, <a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=18069" target="_blank">parallel round results</a>, <a href="https://www.topcoder.com/2020-tco-algorithm-round-2a-editorials/" target="_blank">analysis</a>). Four contestants solved all three problems in the main round, which is even more impressive given that nobody managed to do that in the parallel round, despite that fact that the strongest contestants who qualified directly to Round 4 were competing there. Congratulations to all four, and especially to Kriii on the win!<p></p><p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-BkFgOuKjyTc/X14_SIfYUtI/AAAAAAACw48/5zL-UCXHo_8_vRqi-02TmwH-PlQ6FPg_wCLcBGAsYHQ/s2048/IMG_20200621_102209.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1373" data-original-width="2048" height="430" src="https://1.bp.blogspot.com/-BkFgOuKjyTc/X14_SIfYUtI/AAAAAAACw48/5zL-UCXHo_8_vRqi-02TmwH-PlQ6FPg_wCLcBGAsYHQ/w640-h430/IMG_20200621_102209.jpg" width="640" /></a></div>In <a href="https://petr-mitrichev.blogspot.com/2020/08/a-respects-week.html" target="_blank">my previous summary</a>, I have mentioned <a href="https://codeforces.com/contest/1375/problem/E" target="_blank">a Codeforces problem</a>: you are given an array <i>a</i> with at most 1000 elements. Then we write down all pairs of positions that form an <i>inversion</i>: pairs (<i>u</i>,<i>v</i>) such that <i>u</i><<i>v</i> and <i>a<sub>u</sub></i>><i>a<sub>v</sub></i>, getting a long list of all those pairs. Now we want to treat this list as a sorting program: for every pair in the list, we will swap the elements on the corresponding positions. Our goal is to make this program actually sort our array. We are allowed to put the elements of the list in arbitrary order (but we must have all pairs that form an inversion in the starting array exactly once).<p></p><p>If we were allowed to swap any pair that forms an inversion in the <i>current</i> state of the array, then the bubble sort algorithm would work, as it only swaps adjacent elements that form an inversion. However, we can only use the inversions from the initial array (and must use them all).</p><p>In order to achieve this, we need to find an algorithm that tries to keep most existing inversions unchanged. Let's do the following: first, we find the maximum number. Then, we find the second highest number, and sort them (within their places). Then, we add the third highest number and sort the three numbers within their places, using up all their inversions, and so on. This way, whenever we process a new number, the only thing that happened to the array is that the higher numbers got reordered, so the inversions involving the new number stay unchanged!</p><p>The only remaining step is to learn how to put the new number into its correct place using all its inversions. This is equivalent to putting 1 into the correct place given the array 2 3 4 ... <i>k</i> 1 (<i>k</i>+1) ... <i>n</i>. The following sequence of swaps does the job: swap 2 and 1, then swap 3 and 2 (which is in the original position of 1 now), then swap 4 and 3, and so on until swapping <i>k</i> and <i>k</i>-1.</p><p>Thanks for reading, and check back for more!</p><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/5XQMjRBmt3c" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com1http://petr-mitrichev.blogspot.com/2020/09/a-stable-bubble-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-57992621262943413552020-08-28T18:26:00.002+03:002020-08-28T18:27:51.337+03:00A respects week<p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-1gzsfGCkWnc/X0kiac3UpfI/AAAAAAACwW0/dsSz0BtGOS0aMLNowx1s1o-yW1tosWhtQCLcBGAsYHQ/s1103/cfglobal9top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="271" data-original-width="1103" src="https://1.bp.blogspot.com/-1gzsfGCkWnc/X0kiac3UpfI/AAAAAAACwW0/dsSz0BtGOS0aMLNowx1s1o-yW1tosWhtQCLcBGAsYHQ/s640/cfglobal9top5.png" width="640" /></a></div><br />Codeforces Global Round 9 was the main event of the Jun 29 - Jul 5 week (<a href="https://codeforces.com/contest/1375">problems</a>, <a href="https://codeforces.com/contest/1375/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/79731">analysis</a>). The problemsetters warned us to read all problems before spending too much time on one of them, and yet my story is quite similar to <a href="https://codeforces.com/blog/entry/79620?#comment-656175">Radewoosh's</a>: I've spent 1.5 hours on problem F, and then solved problems G and H immediately after reading their problem statements, but lacked 5 minutes to finish the solution to H (it passed in practice). tourist, on the other hand, just didn't get stuck and got the first place with some margin. Well done!<p></p><p>Let me highlight a (relatively) easier problem this time, <a href="https://codeforces.com/contest/1375/problem/E">problem E</a>: you are given an array <i>a</i> with at most 1000 elements. Then we write down all pairs of positions that form an <i>inversion</i>: pairs (<i>u</i>,<i>v</i>) such that <i>u</i><<i>v</i> and <i>a<sub>u</sub></i>><i>a<sub>v</sub></i>, getting a long list of all those pairs. Now we want to treat this list as a sorting program: for every pair in the list, we will swap the elements on the corresponding positions. Our goal is to make this program actually sort our array. We are allowed to put the elements of the list in arbitrary order (but we must have all pairs that form an inversion in the starting array exactly once). Can you see a way to achieve this?</p><p>Thanks for reading, and check back for more!</p><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/PDMeFsPbt1M" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com1http://petr-mitrichev.blogspot.com/2020/08/a-respects-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-45075657142392153502020-08-26T16:45:00.000+03:002020-08-26T16:45:14.901+03:00A tube week<p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-rSFmqR5DlKw/X0ZmbzFHaXI/AAAAAAACwHg/a4WeyHFTj3Qz3zScjkiIvZH45Q_RVNM4QCLcBGAsYHQ/s2048/IMG_20200524_113417.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1536" data-original-width="2048" src="https://1.bp.blogspot.com/-rSFmqR5DlKw/X0ZmbzFHaXI/AAAAAAACwHg/a4WeyHFTj3Qz3zScjkiIvZH45Q_RVNM4QCLcBGAsYHQ/s640/IMG_20200524_113417.jpg" width="640" /></a></div><br />There were no contests that I'd like to mention during the Jun 22 - Jun 28 week, so let's come back to <a href="https://codeforces.com/contest/1368/problem/F">the Codeforces problem</a> from the previous summary: there are <i>n</i> lamps arranged in a circle (<i>n</i><=1000), and two players are turning them on and off. Initially all lamps are off. The first player starts by turning on any subset of lamps that are off. Let the number of lamps turned on by the first player be <i>k</i>. Then the second player chooses any subset of <i>k</i> consecutive lamps (along the circle), and turns off all lamps in that subset that were on. Then the first player can turn on any subset of lamps that are off again, and so on. The first player can choose to finish the game instead of making their turn. The goal of the first player is to maximize the number of lamps that are on when the game is finished (and they have to finish the game at some point, they can't continue forever), and the second player tries to minimize that number. What is the optimal strategy for the first player?<p></p><p>Let's call a move of the first player followed by a move of the second player one <i>step</i>. Since the second player always turns off at most the same number of lamps that the first player has just turned on, the number of lamps never decreases after a step. We can further classify the steps into two types: the ones that increase the number of lamps that are on, and the ones that keep it unchanged.</p><p>Consider a game that was played optimally by both players, and let's focus on the last increasing step of that game. Suppose the first player has turned <i>k</i> lamps on during their move. If there were <i>k</i> consecutive lamps that were on after that, the second player could have turned them all off, and make the step not increasing. Therefore in order to make an increasing step, the first player needs to keep at least one lamp off among each <i>k</i> consecutive lamps. Therefore the maximum number of lamps that are on after his move is <i>n</i>-ceil(<i>n</i>/<i>k</i>), and then the second player will turn <i>k</i>-1 lamps off in the worst case, so the number of lamps that will be on after this step will be <i>n</i>-ceil(<i>n</i>/<i>k</i>)-<i>k</i>+1.</p><p>The first player can pick the value of <i>k</i> that maximizes <i>n</i>-ceil(<i>n</i>/<i>k</i>)-<i>k</i>+1 and achieve such score in the following way: choose any set of lamps of size <i>n</i>-ceil(<i>n</i>/<i>k</i>) that does not have <i>k</i> consecutive lamps, and keep turning on any <i>k</i> lamps from this set that are off. This will guarantee that each step will be increasing until we reach the score of <i>n</i>-ceil(<i>n</i>/<i>k</i>)-<i>k</i>+1.</p><p>The second player can guarantee that the score never exceeds max(<i>n</i>-ceil(<i>n</i>/<i>k</i>)-<i>k</i>+1) by simply turning off the maximum number of lamps that they can at each turn, which will make sure that whenever a step is increasing and the first player turned on <i>k</i> lamps, the score after this step will not exceed <i>n</i>-ceil(<i>n</i>/<i>k</i>)-<i>k</i>+1. This is not an entirely formal proof, but the remaining details are left to the reader :)</p><p>Thanks for reading, and check back for more! </p><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/bZErJIIJGb0" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com2http://petr-mitrichev.blogspot.com/2020/08/a-tube-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-72956577374395378972020-07-31T16:45:00.001+03:002020-07-31T17:48:41.781+03:00A specific 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/-nzkxnOoLWOE/XyQRh0h3xAI/AAAAAAACvdM/Xy7qY6UP3OIlzxMPp6XNgBENNWIcuBapACLcBGAsYHQ/s1600/cfglobal8top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="274" data-original-width="1103" height="158" src="https://1.bp.blogspot.com/-nzkxnOoLWOE/XyQRh0h3xAI/AAAAAAACvdM/Xy7qY6UP3OIlzxMPp6XNgBENNWIcuBapACLcBGAsYHQ/s640/cfglobal8top5.png" width="640" /></a></div>Codeforces Global Round 8 took place during the Jun 15 - Jun 21 week (<a href="https://codeforces.com/contest/1368">problems</a>, <a href="https://codeforces.com/contest/1368/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/79027">analysis</a>). I got a great start by solving problem F 14 minutes earlier than the second solution to this problem (from Egor), but unfortunately could not solve G in the last hour even though I was quite close. Both ecnerwala and tourist solved their 8th problem in the last 10 minutes, and grabbed the first two places with less than 100 points separating them. Congratulations to both!<br /><br />Here is <a href="https://codeforces.com/contest/1368/problem/F">the problem</a> that I solved so fast: there are <i>n</i> lamps arranged in a circle, and two players are turning them on and off. Initially all lamps are off. The first player starts by turning on any subset of lamps that are off. Let the number of lamps turned on by the first player be <i>k</i>. Then the second player chooses any subset of <i>k</i> consecutive lamps (along the circle), and turns off all lamps in that subset that were on. Then the first player can turn on any subset of lamps that are off again, and so on. The first player can choose to finish the game instead of making their turn. The goal of the first player is to maximize the number of lamps that are on when the game is finished (and they have to finish the game at some point, they can't continue forever), and the second player tries to minimize that number. What is the optimal strategy for the first player?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-1GrQ_RTusfE/XyQXLFqAxzI/AAAAAAACvdY/Y3kpJtlO8eI_9JALGO1zFoK_GMitdrTHgCLcBGAsYHQ/s1600/agc046top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="348" data-original-width="835" height="264" src="https://1.bp.blogspot.com/-1GrQ_RTusfE/XyQXLFqAxzI/AAAAAAACvdY/Y3kpJtlO8eI_9JALGO1zFoK_GMitdrTHgCLcBGAsYHQ/s640/agc046top5.png" width="640" /></a></div>AtCoder Grand Contest 046 followed on Saturday (<a href="https://atcoder.jp/contests/agc046/tasks">problems</a>, <a href="https://atcoder.jp/contests/agc046/standings">results</a>, to 5 on the left, <a href="https://img.atcoder.jp/agc046/editorial.pdf">analysis</a>). tourist would be ahead of everybody else with 5 problems even if he stopped competing an hour before the end, but he has used that hour to solve problem E as well. Congratulations on the commanding victory! I could not solve any of the three harder problems in the last two hours.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-qkBy63uvqN8/XyQcdrY5lxI/AAAAAAACvd8/oDJsdvTZlJYN6vZysbfiCiorOby6CL88gCLcBGAsYHQ/s1600/srm787top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="150" data-original-width="779" height="122" src="https://1.bp.blogspot.com/-qkBy63uvqN8/XyQcdrY5lxI/AAAAAAACvd8/oDJsdvTZlJYN6vZysbfiCiorOby6CL88gCLcBGAsYHQ/s640/srm787top5.png" width="640" /></a></div>TopCoder SRM 787 wrapped up the week on Sunday night (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=17994">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17994&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-787-editorials/">analysis</a>). bqi343 has confirmed his <a href="https://clist.by/standings/tco20-algorithm-stage-3-17680999/">qualification</a> for TCO20 finals, but even with 200 challenge points he could not overtake ksun48 for the first place. Congratulations to both!<br /><br /><a href="https://community.topcoder.com/stat?c=problem_statement&pm=16202&rd=17994">The hard problem</a> in this round was somewhat standard, and could be solved by carefully implementing a few standard tricks. However, one could significantly cut down the implementation time and the chances for making a bug by considering the specifics of this problem, which is also a great skill. From the solutions I saw, I think <a href="https://community.topcoder.com/stat?c=problem_solution&rm=334246&rd=17994&pm=16202&cr=15881985">pashka's</a> demonstrates this skill the most (the actual logic of the solution on top of copy-pasted components starts from the line "<span style="font-family: "courier new" , "courier" , monospace;">for (auto b : br2) {</span>"). No binary search, no tree dynamic programming necessary :)<br /><br />Thanks for reading, and check back for more!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/CsKAMKoLHBc" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com4http://petr-mitrichev.blogspot.com/2020/07/a-specific-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-56783992108742243682020-07-29T19:09:00.001+03:002020-07-30T17:09:19.036+03:00A rescue 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/-65dTb2GhGPc/XyGe31N3iwI/AAAAAAACvJY/SEZQWdbSuUokrLIYvQwl4dY9dHxDwke7gCLcBGAsYHQ/s1600/IMG_20200517_145348.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="1168" data-original-width="1600" height="466" src="https://1.bp.blogspot.com/-65dTb2GhGPc/XyGe31N3iwI/AAAAAAACvJY/SEZQWdbSuUokrLIYvQwl4dY9dHxDwke7gCLcBGAsYHQ/s640/IMG_20200517_145348.jpg" width="640" /></a></div>The Jun 8 - Jun 14 week did not have contests that I want to mention, so let's discuss the question from <a href="https://petr-mitrichev.blogspot.com/2020/07/a-pen-testing-week.html">the previous summary</a>.<br /><br />I have found that the following code solves <a href="https://atcoder.jp/contests/agc045/tasks/agc045_d">an AtCoder problem</a>:<br /><br /><span style="font-family: "courier new" , "courier" , monospace;">for (int n = 1; n <= N; ++n) {</span><br /><span style="font-family: "courier new" , "courier" , monospace;"> for (int a = 1; a <= A && a <= n; ++a) {</span><br /><span style="font-family: "courier new" , "courier" , monospace;"> if (a == n) {</span><br /><span style="font-family: "courier new" , "courier" , monospace;"> w0[n][a] = fact[n];</span><br /><span style="font-family: "courier new" , "courier" , monospace;"> w1[n][a] = fact[n];</span><br /><span style="font-family: "courier new" , "courier" , monospace;"> } else {</span><br /><span style="font-family: "courier new" , "courier" , monospace;"> w0[n][a] = ((n - a) * (int64) w1[n - 1][a] + (a - 1) * (int64) w1[n - 1][a - 1]) % MODULO;</span><br /><span style="font-family: "courier new" , "courier" , monospace;"> w1[n][a] = (w0[n - 1][a - 1] + w0[n][a]) % MODULO;</span><br /><span style="font-family: "courier new" , "courier" , monospace;"> }</span><br /><span style="font-family: "courier new" , "courier" , monospace;"> }</span><br /><span style="font-family: "courier new" , "courier" , monospace;">}</span><br /><div><br /></div>where <span style="font-family: "courier new" , "courier" , monospace;">w0[N][A]</span> would contain the final answer. This solution runs in O(<i>N</i>*<i>A</i>), which is too slow to get the problem accepted since <i>N</i><=10<sup>7</sup> and <i>A</i><=5000. How to make it faster?<br /><br />To <a href="https://codeforces.com/blog/entry/61306">quote TLE</a>, it's Berlekamp-Massey Algorithm to the rescue! The situation here matches the application from that blog post almost exactly. There are two differences, though. The first difference is that our transition has an extra "<span style="font-family: "courier new" , "courier" , monospace;">if (a == n)</span>" branch. However, that branch never triggers when <i>n</i>><i>A</i>, so we can just treat the <i>n</i>=<i>A</i> row as our initial values and imagine we don't have that branch.<br /><br />This is not enough: the answer to the last sample still does not match if we compute <span style="font-family: "courier new" , "courier" , monospace;">w0[A,A]</span>, <span style="font-family: "courier new" , "courier" , monospace;">w0[A+1,A]</span>,..., <span style="font-family: "courier new" , "courier" , monospace;">w0[3*A,A]</span> and apply Berlekamp-Massey to find <span style="font-family: "courier new" , "courier" , monospace;">w0[N][A]</span>. The reason is the following: in our transition function, we multiply by (<i>n</i>-<i>a</i>), while Berlekamp-Massey expects the transition matrix to be independent of <i>n</i>.<br /><br />However, we can notice a peculiar property of our transition: we only multiply by (<i>n</i>-<i>a</i>) when going from (<i>n</i>-1,<i>a</i>) to (<i>n</i>,<i>a</i>). In all other cases, the value of <i>n</i>-<i>a</i> stays constant, and we multiply by something independent of <i>n </i>(we go from either (<i>n</i>-1,<i>a</i>-1) or from (<i>n</i>,<i>a</i>) to (<i>n</i>,<i>a</i>)). Therefore, in aggregate, we will multiply by (<i>n</i>-<i>a</i>)! to achieve state (<i>n</i>,<i>a</i>) starting from a state (<i>x</i>,<i>x</i>). And this in turn means that if we define <span style="font-family: "courier new" , "courier" , monospace;">w2[n][a]=w0[n][a]/fact[n-a]</span>, then the transition function for these values will be independent of <i>n</i>, and we can apply Berlekamp-Massey to the sequence <span style="font-family: "courier new" , "courier" , monospace;"><span style="font-family: "courier new" , "courier" , monospace;">w2[A,A]</span>,<span style="font-family: "courier new" , "courier" , monospace;">w2[A+1,A]</span>,..., <span style="font-family: "courier new" , "courier" , monospace;">w2[3*A,A]</span></span><span style="font-family: inherit;"> to find </span><span style="font-family: "courier new" , "courier" , monospace;">w2[N][A]</span><span style="font-family: inherit;">. Note that we don't need to write down the actual transition function for </span><span style="font-family: "courier new" , "courier" , monospace;">w2</span><span style="font-family: inherit;">, we just need to believe it has the correct form, and we can use the code above to find </span><span style="font-family: "courier new" , "courier" , monospace;">w2</span><span style="font-family: inherit;"> through </span><span style="font-family: "courier new" , "courier" , monospace;">w0</span><span style="font-family: inherit;">, and thus solve our problem in O(<i>N</i><sup>2</sup>*log(<i>N</i>)).</span><br /><span style="font-family: inherit;"><br /></span><span style="font-family: inherit;">Thanks for reading, and check back for more!</span></div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/TscAPBb2GJQ" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com2http://petr-mitrichev.blogspot.com/2020/07/a-rescue-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-88457583664685468512020-07-29T11:25:00.000+03:002020-07-29T18:34:20.112+03:00A pen testing 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/-1F3Qfj7u9ZE/XyEjrazGapI/AAAAAAACvIQ/OaiAIZnvag0nwKKlZWDDoxbHJSXy7jfMwCLcBGAsYHQ/s1600/cf647top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="272" data-original-width="1102" height="156" src="https://1.bp.blogspot.com/-1F3Qfj7u9ZE/XyEjrazGapI/AAAAAAACvIQ/OaiAIZnvag0nwKKlZWDDoxbHJSXy7jfMwCLcBGAsYHQ/s640/cf647top5.png" width="640" /></a></div>Codeforces Round 647 was the first contest of the first week of June (<a href="https://codeforces.com/contest/1361">problems</a>, <a href="https://codeforces.com/contest/1361/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/78355">analysis</a>). This round seemed to have a bit more "Failed System Test" outcomes than a typical Codeforces round (<a href="https://codeforces.com/blog/entry/78276">instructive example</a>), and yet tourist, Um_nik and boboniu did not make mistakes and solved all problems correctly (to be more precise, both tourist and Um_nik resubmitted one of the problems, so they have managed to correct the mistakes they made). Congratulations to all and especially to tourist on the win!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-dd6ZzR59eh8/XyElILBb2BI/AAAAAAACvIc/in6YsU4_aP89aFup_EezUBQfboyU27P2wCLcBGAsYHQ/s1600/gcj20r3top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="395" data-original-width="1572" height="160" src="https://1.bp.blogspot.com/-dd6ZzR59eh8/XyElILBb2BI/AAAAAAACvIc/in6YsU4_aP89aFup_EezUBQfboyU27P2wCLcBGAsYHQ/s640/gcj20r3top5.png" width="640" /></a></div>Google Code Jam 2020 Round 3 selected the 25 finalists, who unfortunately will not travel to Munich, and will instead compete in the online finals (<a href="https://codingcompetitions.withgoogle.com/codejam/round/000000000019ff7e/0000000000377630">problems</a>, <a href="https://codingcompetitions.withgoogle.com/codejam/round/000000000019ff7e">results</a>, top 5 on the left). Besides the significantly easier first problem that was solved by everyone in top 25, the contestants found a lot of different ways to qualify using the other three problems. Gennady.Korotkevich solved all inputs but one and won, continuing his <a href="https://twitter.com/que_tourist/status/1258452821290205184">exceptional GCJ form</a>.<br /><br />I have helped prepare the third problem, <a href="https://codingcompetitions.withgoogle.com/codejam/round/000000000019ff7e/0000000000377630">Pen Testing</a>, that was created by Ian Tullis and which I find quite amazing: you have 15 ballpoint pens having 0, 1, 2, ..., 14 units of ink in them. The pens are given to you in random order and you don't know which pen is which. The only way for you to get information about the pens is to write something with them. In one turn, you pick one pen and try to spend one unit from ink from it, and you get one bit of information doing that: if the pen had at least one unit of ink left before this turn, you succeed in writing with it, and it now has one unit less (possibly 0). If the pen was empty, then you fail in writing with it, and you know that it's definitely empty. You goal is to eventually choose two pens that have at least 15 units of ink <i>remaining</i> in total.<br /><br />Just choosing two pens at random without any writing gives you a 46.(6)% probability of success, and writing seemingly makes things even worse as it reduces the amount of remaining ink, and you only learn the concrete identity of a pen after it has no ink left :) And yet the problem asks you to succeed in 63.6% of all cases. How is it even possible?<br /><br />I have written an extensive analysis for it that you can read by clicking "Analysis" after following the above link. I don't have much to add to it :)<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-5pxfWRX5jKI/XyEtx2LHtoI/AAAAAAACvIs/SQid_C5GeKAXugYncnGUn5SWxalACJlVgCLcBGAsYHQ/s1600/agc045top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="348" data-original-width="813" height="273" src="https://1.bp.blogspot.com/-5pxfWRX5jKI/XyEtx2LHtoI/AAAAAAACvIs/SQid_C5GeKAXugYncnGUn5SWxalACJlVgCLcBGAsYHQ/s640/agc045top5.png" width="640" /></a></div>AtCoder Grand Contest 045 wrapped up the week on Sunday (<a href="https://atcoder.jp/contests/agc045/tasks">problems</a>, <a href="https://atcoder.jp/contests/agc045/standings">results</a>, top 5 on the left, <a href="https://img.atcoder.jp/agc045/editorial.pdf">analysis</a>). Nobody could solve problem E, and only apiad has solved problem F, but he did not have enough time left afterwards for the easier problems and finished in 12th place. Solving the first four problems fast was the way to victory this time, and that's exactly what ksun48 did. Congratulations!<br /><br />I have made most of the steps described in the analysis for <a href="https://atcoder.jp/contests/agc045/tasks/agc045_d">problem D</a>, but not all of them. So I have obtained the following recurrence:<br /><br /><span style="font-family: "courier new" , "courier" , monospace;">for (int n = 1; n <= N; ++n) {</span><br /><span style="font-family: "courier new" , "courier" , monospace;"> for (int a = 1; a <= A && a <= n; ++a) {</span><br /><span style="font-family: "courier new" , "courier" , monospace;"> if (a == n) {</span><br /><span style="font-family: "courier new" , "courier" , monospace;"> w0[n][a] = fact[n];</span><br /><span style="font-family: "courier new" , "courier" , monospace;"> w1[n][a] = fact[n];</span><br /><span style="font-family: "courier new" , "courier" , monospace;"> } else {</span><br /><span style="font-family: "courier new" , "courier" , monospace;"> w0[n][a] = ((n - a) * (int64) w1[n - 1][a] + (a - 1) * (int64) w1[n - 1][a - 1]) % MODULO;</span><br /><span style="font-family: "courier new" , "courier" , monospace;"> w1[n][a] = (w0[n - 1][a - 1] + w0[n][a]) % MODULO;</span><br /><span style="font-family: "courier new" , "courier" , monospace;"> }</span><br /><span style="font-family: "courier new" , "courier" , monospace;"> }</span><br /><span style="font-family: "courier new" , "courier" , monospace;">}</span><br /><div><br /></div>where <span style="font-family: "courier new" , "courier" , monospace;">w0[N][A]</span> would contain the final answer. This solution runs in O(<i>N</i>*<i>A</i>), which is too slow since <i>N</i><=10<sup>7</sup> and <i>A</i><=5000. Can you guess how I got this problem accepted (you don't need to read the problem statement :P)?<br /><br />Thanks for reading, and check back for more!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/yprtAhZnd4o" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com2http://petr-mitrichev.blogspot.com/2020/07/a-pen-testing-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-78386983549573274682020-07-23T19:12:00.001+03:002020-07-25T08:35:18.951+03:00A local 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/-CkUCTYZnD14/Xxm1PNv9zFI/AAAAAAACusI/sX6P3S7QiSwJ3nKrydjbAKbyak3mA-isACLcBGAsYHQ/s1600/kotlin4top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="267" data-original-width="1103" height="154" src="https://1.bp.blogspot.com/-CkUCTYZnD14/Xxm1PNv9zFI/AAAAAAACusI/sX6P3S7QiSwJ3nKrydjbAKbyak3mA-isACLcBGAsYHQ/s640/kotlin4top5.png" width="640" /></a></div>Kotlin Heroes Episode 4 was the main event of the May 25 - May 31 week (<a href="https://codeforces.com/contest/1346">problems</a>, <a href="https://codeforces.com/contest/1346/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/78124">analysis</a>). Only tourist, Golobanov399 and eatmore have managed to solve the hardest problem I, but tourist was done 45 minutes before his competitors and earned a very convincing victory. Well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-LKVoDpy-VqM/Xxm2SUCIc5I/AAAAAAACusY/750mrcKMqqMT-UOGjrPv7kdLoLTTNeUsACLcBGAsYHQ/s1600/IMG_20200517_113246.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/-LKVoDpy-VqM/Xxm2SUCIc5I/AAAAAAACusY/750mrcKMqqMT-UOGjrPv7kdLoLTTNeUsACLcBGAsYHQ/s640/IMG_20200517_113246.jpg" width="640" /></a></div>In <a href="https://petr-mitrichev.blogspot.com/2020/07/an-extract-method-week.html">my previous summary</a>, I have mentioned <a href="https://atcoder.jp/contests/agc044/tasks/agc044_e">an AtCoder problem</a>: there are <i>n</i><=200000 cells arranged in a circle. The <i>i</i>-th cell has two numbers associated with it, <i>a<sub>i</sub></i> and <i>b<sub>i</sub></i> (0<=<i>a<sub>i</sub></i><=10<sup>12</sup>, 0<=<i>b<sub>i</sub></i><=100). We put a token into one of the cells uniformly at random, and our initial score is zero. Then, we repeatedly face the following choice: we either add <i>a<sub>i</sub></i> to our score and end the process (where <i>i</i> is the number of the cell the token is currently in), or we subtract <i>b<sub>i</sub></i> from our score, move the token uniformly at random into one of the two adjacent cells, and continue the process. What is the maximum expected score we can get if we play optimally?<br /><br />Since the only state of the process is the cell the token is currently in, and the only decision we make at every moment is whether to stop or to continue, a strategy is completely described by a set <i>S</i> of cells in which we stop (by taking <i>a<sub>i</sub></i>). How do we compute the expected score if we choose a particular set <i>S</i>?<br /><br />The parts of the circle between consecutive elements of <i>S</i> can be treated completely independently, and we have the following subproblem there: given a segment of length <i>k</i>, we start in a random position and keep moving randomly either to the left or to the right until we leave the segment (because of symmetry we will exit to the left or to the right with probability 50%). What is the expected sum of <i>b<sub>i</sub></i>'s of the cells we go through, where one <i>b<sub>i</sub></i> is added multiple times if its cell is visited multiple times?<br /><br />Because of linearity of expectation, this sum is equal to sum of <i>b<sub>i</sub></i> times the expected number of times the <i>i</i>-th cell is visited. We can denote that expected number of times as <i>f</i>(<i>k</i>, <i>i</i>). Since this number has just two integer parameters, we can implement simulation to check if there is a pattern. I did just that in the beginning of the contest, and the pattern was very clear: <i>f</i>(<i>k</i>, <i>i</i>)=(<i>i</i>+1)*(<i>k</i>-<i>i</i>). There is probably an easy way to deduce that or prove it by induction, but for me the experimental proof was good enough :)<br /><br />Now that we've learned how to compute the expected score given the set <i>S</i>, we can turn our attention to finding the optimal set <i>S</i>. My intuition told me during the round that greedy should work, and indeed it works because of the following lemma: suppose we have a non-empty set <i>S</i> which is locally optimal: neither adding one cell to it, nor removing one cell from it, leads to a set <i>S</i>' with a better expected score. Then this set <i>S</i> is actually globally optimal, and is the answer to the problem.<br /><br />Here is the proof: let's denote the expected score we get if we start from cell <i>i</i> and use the set <i>S</i> as the stopping cells as <i>g</i>(<i>S</i>, <i>i</i>). Let's prove that for any other set <i>S'</i>, <i>g</i>(<i>S'</i>, <i>i</i>)<=<i>g</i>(<i>S</i>, <i>i</i>) by the infinite induction on the number of moves that happen before we stop. If we decide to stop in some cell <i>i</i>, then <i>g</i>(<i>S</i>', <i>i</i>)=<i>a<sub>i</sub></i>, and since <i>S</i> is locally optimal <i>g</i>(<i>S</i>, <i>i</i>)>=<i>a<sub>i</sub></i>, so <i>g</i>(<i>S'</i>, <i>i</i>)<=<i>g</i>(<i>S</i>, <i>i</i>) in this case. If we decide to continue in some cell <i>i</i>, then get we <i>g</i>(<i>S'</i>, <i>i</i>)=-<i>b<sub>i</sub></i>+(<i>g</i>(<i>S'</i>, <i>i</i>-1)+<i>g</i>(<i>S'</i>, <i>i</i>+1))/2, which by induction hypothesis (sorry for being a bit informal here, to make it formal we'd have to introduce a third parameter to <i>g</i>) is <=-<i>b<sub>i</sub></i>+(<i>g</i>(<i>S</i>, <i>i</i>-1)+<i>g</i>(<i>S</i>, <i>i</i>+1))/2, which is in turn <=<i>g</i>(<i>S</i>, <i>i</i>) because S is locally optimal.<br /><br />Therefore all that remains is to find a way to apply local optimizations to the set <i>S</i> in such a way that we converge quickly. We can actually use a very similar argument to guide our way: suppose for some set S' we determine that it's better to remove the cell <i>i</i> from it, in other words it's better to continue if we are in cell <i>i</i>. Then the cell <i>i</i> does not belong to the optimal set S, in other words it is better to continue from the cell <i>i</i> in the optimal solution as well! To see why it's true, let's write down the condition that it's better to remove the cell <i>i</i> from S': <i>a<sub>i</sub></i><-<i>b<sub>i</sub></i>+(<i>g</i>(<i>S''</i>, <i>i</i>-1)+<i>g</i>(<i>S''</i>, <i>i</i>+1))/2 (where <i>S</i>''=<i>S</i>'-{<i>i</i>}). <i>g</i>(<i>S''</i>, <i>i</i>-1)<=<i>g</i>(<i>S</i>, <i>i</i>-1) and <i>g</i>(<i>S''</i>, <i>i</i>+1)<=<i>g</i>(<i>S</i>, <i>i+</i>1), therefore <i>a<sub>i</sub></i><-<i>b<sub>i</sub></i>+(<i>g</i>(<i>S</i>, <i>i</i>-1)+<i>g</i>(<i>S</i>, <i>i</i>+1))/2, which means that <i>i</i> will not belong to <i>S</i> since <i>S</i> is locally optimal.<br /><br />So we can just start with S containing all cells, and keep removing cells while it improves the expected score. In order to avoid traversing the list of cells <i>n</i> times and therefore getting O(<i>n</i><sup>2</sup>) running time, we can use the standard idea of keeping a set of "pending" cells, which would improve the expected score when removed, and update the status of two adjacent non-removed cells when we process the removal of a cell. Another way to do it is to start with a cell that is definitely in <i>S</i> (the one with the highest <i>a<sub>i</sub></i>), and keep going to the right and adding cells to <i>S </i>(which will be represented by a stack), and then repeatedly checking if removing next-to-last cell in <i>S</i> leads to a better expected score. This second approach is very similar to the convex hull algorithms.<br /><br />Thanks for reading, and check back for more!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/aa5U4c_lfGU" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com0http://petr-mitrichev.blogspot.com/2020/07/a-local-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-29672713673859026982020-07-21T08:57:00.001+03:002020-07-21T09:28:22.070+03:00An extract method week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"></div><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-enQy_kWI5Yk/XxaGHr1jrAI/AAAAAAACubw/Efpp3Ez204o0ZakTN5ARHERFOSsjLMzBgCLcBGAsYHQ/s1600/agc044top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="345" data-original-width="822" height="268" src="https://1.bp.blogspot.com/-enQy_kWI5Yk/XxaGHr1jrAI/AAAAAAACubw/Efpp3Ez204o0ZakTN5ARHERFOSsjLMzBgCLcBGAsYHQ/s640/agc044top5.png" width="640" /></a></div>AtCoder Grand Contest 044 was the main event of the May 18 - May 24 week (<a href="https://atcoder.jp/contests/agc044/tasks">problems</a>, <a href="https://atcoder.jp/contests/agc044/standings">results</a>, top 5 on the left, <a href="https://img.atcoder.jp/agc044/editorial.pdf">analysis</a>). I have started by diving into the problem E, implementing what seemed to be a reasonable greedy but repeatedly getting a wrong answer, and my inability to give up on trying reasonable-looking ideas without proof has ruined the whole contest. To add insult to injury, it turned out that the last idea that I wanted to try (also without proof) when the contest ended could actually get the problem accepted :) tourist, on the other hand, came up with a solution to this problem in a normal manner, without trying random ideas, and won the round. Well done!<br /><br />Here is <a href="https://atcoder.jp/contests/agc044/tasks/agc044_e">the problem statement</a>: there are <i>n</i><=200000 cells arranged in a circle. The <i>i</i>-th cell has two numbers associated with it, <i>a<sub>i</sub></i> and <i>b<sub>i</sub></i> (0<=<i>a<sub>i</sub></i><=10<sup>12</sup>, 0<=<i>b<sub>i</sub></i><=100). We put a token into one of the cells uniformly at random, and our initial score is zero. Then, we repeatedly face the following choice: we either add <i>a<sub>i</sub></i> to our score and end the process (where <i>i</i> is the number of the cell the token is currently in), or we subtract <i>b<sub>i</sub></i> from our score, move the token uniformly at random into one of the two adjacent cells, and continue the process. What is the maximum expected score we can get if we play optimally?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-zHCr-dO7WSo/XxaFN47amnI/AAAAAAACubo/1wUaWNzpx7I50aF5gP0bPQHNz9kOTZ7lACLcBGAsYHQ/s1600/IMG_20200415_094028.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/-zHCr-dO7WSo/XxaFN47amnI/AAAAAAACubo/1wUaWNzpx7I50aF5gP0bPQHNz9kOTZ7lACLcBGAsYHQ/s640/IMG_20200415_094028.jpg" width="640" /></a></div>Let me also use this summary to update on <a href="https://petr-mitrichev.blogspot.com/2020/01/a-red-maxflow-week.html">my C++ experiment</a>. For about half a year, I have been using exclusively C++ on all platforms except TopCoder (I kept using Java on TopCoder because <a href="https://codeforces.com/blog/entry/13369">JHelper</a> lacks TopCoder integration). From the only objective measure I could come up with, the experiment doesn't seem to go so well: while on TopCoder I've managed to qualify for the TCO and kept the second place in the overall rating, I've dropped out of the top 10 on Codeforces, my <a href="https://clist.by/standings/atcoder-race-ranking-2020-19846514/">campaign</a> to qualify for AtCoder World Tour Finals 2021 is not in the best shape, and our <a href="http://opencup.ru/index.cgi?data=macros/results&menu=index&head=index&ncup=ock&class=ock&region=main">Open Cup results</a> seem to have taken a turn for the worse in the second half of the season. Of course, all these numbers might well be statistically insignificant if one tries to dig in deeper.<br /><br />Subjectively, I definitely feel that I'm fighting less with the time limits and can focus on implementing the algorithm, however I also feel that my coding speed dropped quite substantially as I have to think more about every line of code I write, and also as C++ support in JetBrains tools is still being improved to the level of Java support (for example, "Extract Method" which I use extensively used to suggest weird parameter names, but it seems to be fixed now). I wonder if it's possible to quantify the coding speed drop based on the screencasts :)<br /><br />I'm still hopeful that the coding speed will improve, and that CLion will have all necessary features soon (or already has them), so I think I will continue the experiment at least until the end of the year. Please share any observations or suggestions that you have about this, and of course check back for the next week's summary!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/9sPqCJQ4FBc" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com3http://petr-mitrichev.blogspot.com/2020/07/an-extract-method-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-74640777173688113332020-07-05T09:59:00.001+03:002020-07-05T09:59:26.854+03:00A Bresenham's 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/-sEUADDpphNM/XwB3hcx4HGI/AAAAAAACrhY/0AW7eoJSro89kpW2ITZcSM4uyG4eFDeEQCLcBGAsYHQ/s1600/cf641top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="270" data-original-width="1100" height="156" src="https://1.bp.blogspot.com/-sEUADDpphNM/XwB3hcx4HGI/AAAAAAACrhY/0AW7eoJSro89kpW2ITZcSM4uyG4eFDeEQCLcBGAsYHQ/s640/cf641top5.png" width="640" /></a></div>The May 11 - May 17 week started with Codeforces Round 641 (<a href="https://codeforces.com/contest/1349">problems</a>, <a href="https://codeforces.com/contest/1349/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/77284">analysis</a>). It was <a href="https://codeforces.com/blog/entry/76895?#comment-620954">quite challenging</a> for <a href="https://codeforces.com/blog/entry/76895?#comment-622501">some contestants</a>, and nobody could solve more than 4 problems out of 7. Um_nik solved his four in just one half of allotted time and won the round, congratulations!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-WCeLzLCrCT8/XwB8C-vvZ7I/AAAAAAACrhk/GoOR0Bzo6UEt8lcF6aH93jiPEYXKxDvigCLcBGAsYHQ/s1600/srm786top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="145" data-original-width="781" height="118" src="https://1.bp.blogspot.com/-WCeLzLCrCT8/XwB8C-vvZ7I/AAAAAAACrhk/GoOR0Bzo6UEt8lcF6aH93jiPEYXKxDvigCLcBGAsYHQ/s640/srm786top5.png" width="640" /></a></div>TopCoder SRM 786 followed on Friday (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=17989">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17989&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-786-editorials/">analysis</a>). bqi343 had a 50-point lead after the coding phase, and increased it to 100 points during the challenge phase. Congratulations on the victory! These 5 qualification points have also made him a huge favorite to qualify to the TCO from <a href="https://clist.by/standings/tco20-algorithm-stage-3-17680999/">the third online stage</a>.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-_FaKK9V87rA/XwCBAIr0NRI/AAAAAAACrhw/5yq6hmZJV7w1V4famuJ6je-x1cFcJfgVACLcBGAsYHQ/s1600/gcj20r2top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="387" data-original-width="1600" height="154" src="https://1.bp.blogspot.com/-_FaKK9V87rA/XwCBAIr0NRI/AAAAAAACrhw/5yq6hmZJV7w1V4famuJ6je-x1cFcJfgVACLcBGAsYHQ/s640/gcj20r2top5.png" width="640" /></a></div>On Saturday Google held Code Jam 2020 Round 2 (<a href="https://codingcompetitions.withgoogle.com/codejam/round/000000000019ffb9/00000000003384ea">problems</a>, <a href="https://codingcompetitions.withgoogle.com/codejam/round/000000000019ffb9">results</a>, top 5 on the left). Placing in the top 1000 was the main goal in this round, but still Benq's jump to the first place with just five minutes remaining in the round was quite impressive, well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-q8SyRDux5uU/XwCBn6CHrUI/AAAAAAACrh4/E9KKl576zLANPU8ZnSmlGS0HTMn78mLmQCLcBGAsYHQ/s1600/oc1920serbiatop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="209" data-original-width="836" height="160" src="https://1.bp.blogspot.com/-q8SyRDux5uU/XwCBn6CHrUI/AAAAAAACrh4/E9KKl576zLANPU8ZnSmlGS0HTMn78mLmQCLcBGAsYHQ/s640/oc1920serbiatop5.png" width="640" /></a></div>Open Cup 2019-20 Grand Prix of Serbia wrapped up the week on Sunday (<a href="http://opencup.ru/index.cgi?data=macros/stage&head=index&menu=index&stg=19&region=main&ncup=ock&class=ock">results</a>, top 5 on the left). Teams Polish Mafia, USA1 and NNSU Almost Retired solved 12 problems each, and the deciding factor was Polish Mafia's significantly fewer incorrect attempts. Congratulations on the win!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-j9JNnA_9sJg/XwCCfS9Hd1I/AAAAAAACriE/BVEjkVi8m1suz0AKGfKL08UlCKqOapT4QCLcBGAsYHQ/s1600/oc1920overalltop10.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="316" data-original-width="1600" height="126" src="https://1.bp.blogspot.com/-j9JNnA_9sJg/XwCCfS9Hd1I/AAAAAAACriE/BVEjkVi8m1suz0AKGfKL08UlCKqOapT4QCLcBGAsYHQ/s640/oc1920overalltop10.png" width="640" /></a></div>It was not announced before the round, but this Grand Prix was the last one of the Open Cup 2019-20 season (<a href="http://opencup.ru/index.cgi?data=macros/results&menu=index&head=index&ncup=ock&class=ock&region=main">overall standings</a>, top 10 on the left). The standings were very close at the top, but in the end we have a new champion. For only the second time since 2013, the champion team's last name list does not include Korotkevich :) Congratulations to the team USA1, and looking forward to even more competition at the top in the coming season!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-MveG3MwbvfM/XwF1hWNlirI/AAAAAAACrmY/fU0OFYssusEd_8oO67FDQ1zx93dqFV7twCLcBGAsYHQ/s1600/IMG_20200325_123649.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/-MveG3MwbvfM/XwF1hWNlirI/AAAAAAACrmY/fU0OFYssusEd_8oO67FDQ1zx93dqFV7twCLcBGAsYHQ/s640/IMG_20200325_123649.jpg" width="640" /></a></div>In <a href="https://petr-mitrichev.blogspot.com/2020/06/a-week-without-paradox.html">my previous summary</a>, I have mentioned an Open Cup problem: a string of 0s and 1s is called <i>balanced</i> if the number of 1s in any two its circular substrings of the same length differs by at most 1. A <i>circular substring</i> of a string <i>s</i> is any string with the length not exceeding the length of <i>s</i> that can be read after we write <i>s</i> on a circle; in other words, it's either a normal substring of <i>s</i>, or a suffix of <i>s</i> concatenated with a prefix of <i>s</i> with total length not exceeding the length of <i>s</i>. You are given a string consisting of 0s, 1s and ?s. How many ways are there to replace each ? with a 0 or a 1 such that the resulting string is balanced? The length of the given string is at most 1024.<br /><br />This setting reminded me of <a href="https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm">Bresenham's line drawing algorithm</a>, so I tried to get balanced strings like this: let's draw a line from point (0,0) to point (<i>x</i>,<i>y</i>), then let's keep walking starting from point (0,0). We walk like this: if we are below the line, then we go up (increase the <i>y</i>-coordinate by 1), and if we are above the line, then we go right (increase the <i>x</i>-coordinate by 1). If we are on the line, then we go up unless the line is horizontal (<i>y</i>=0), in that case we always go right. We will reach the point (<i>x</i>,<i>y</i>) in <i>x</i>+<i>y</i> steps, and let's write down a 0 every time we go right, and a 1 every time we go up.<br /><br />Intuitively, such strings should be balanced, as we're always walking very close to the line and all substrings of the same size should represent almost the same vector. Circular shifts of a balanced string are also balanced, so we need to also consider the circular shifts of the strings we get that way. It's not at all clear if there are other balanced strings, though. Imagine how happy I was when I found out that considering only such strings gets correct answers on all samples, and then was accepted by the judging system!<br /><br />The resulting code is very simple, since the strings we get for different pairs (<i>x</i>,<i>y</i>) are all different, so we just need to find the period of each such string to determine the number of its different circular shifts, and do not need to otherwise check the strings we get for repetitions.<br /><br />This was one of those rare cases where submitting a solution solely based on intuition and without having even a sketch of a proof worked out :)<br /><br />Thanks for reading, and check back for more!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/IIT_0HYvsB8" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com2http://petr-mitrichev.blogspot.com/2020/07/a-bresenhams-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-16780372411158818892020-06-14T17:41:00.002+03:002020-06-14T22:07:36.139+03:00A week without paradox<div dir="ltr" style="text-align: left;" trbidi="on"><div><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-U93mshVO6Oo/XuYwTiJlmwI/AAAAAAACqvU/5lVhFlRRrCsY72NjCj2imRgUUT2t9B7awCK4BGAsYHg/s948/srm785top5.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="177" data-original-width="948" height="120" src="https://1.bp.blogspot.com/-U93mshVO6Oo/XuYwTiJlmwI/AAAAAAACqvU/5lVhFlRRrCsY72NjCj2imRgUUT2t9B7awCK4BGAsYHg/w640-h120/srm785top5.png" width="640" /></a></div>TopCoder SRM 785 took place during the May 4 - May 10 week (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=17965">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17965&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, analysis). <a href="https://community.topcoder.com/stat?c=problem_statement&pm=15903&rd=17965">The hard problem</a> had this feeling of "it's amazing nobody has asked this before", and it turned out that <a href="https://codeforces.com/blog/entry/77112?#comment-618641">somebody did</a> :) mochalka had seen this problem before and was the only contestant to get it accepted, winning the match — even in such situation <a href="https://codeforces.com/blog/entry/77112?#comment-618709">it's important to execute well</a> given the chance, so well done! It turned out that the only bug in my solution was that I was iterating up to bit 29 instead of bit 30 in one place, and it passed in the practice room with that one-byte change. It was disappointing to figure out all tricky details correctly to only fail in that manner :)</div><div><br /></div><div><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-kFkogcglPIg/XuYzZzEJ6MI/AAAAAAACqv0/bd93zh3V7v0p0LN5kd7NgJ0leJ6n7QjQQCK4BGAsYHg/s920/oc1920bytedancetop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="251" data-original-width="920" height="174" src="https://1.bp.blogspot.com/-kFkogcglPIg/XuYzZzEJ6MI/AAAAAAACqv0/bd93zh3V7v0p0LN5kd7NgJ0leJ6n7QjQQCK4BGAsYHg/w640-h174/oc1920bytedancetop5.png" width="640" /></a></div>Open Cup 2019-20 Grand Prix of Bytedance took place on Sunday (<a href="http://opencup.ru/index.cgi?data=macros/stage&head=index&menu=index&stg=18&region=main&ncup=ock&class=ock">results</a>, top 5 on the left). Team japan02 has really aced it this time, finishing 2 problems ahead of the three leaders of the overall standings and winning their second stage this season with a bang. Congratulations!</div><div><br /></div><div>Our solution to problem B was quite unusual, and was based on intuition a lot more than is typically reasonable. The problem went like this: a string of 0s and 1s is called <i>balanced</i> if the number of 1s in any two its circular substrings of the same length differs by at most 1. A <i>circular substring</i> of a string <i>s</i> is any string with the length not exceeding the length of <i>s</i> that can be read after we write <i>s</i> on a circle; in other words, it's either a normal substring of <i>s</i>, or a suffix of <i>s</i> concatenated with a prefix of <i>s</i> with total length not exceeding the length of <i>s</i>. You are given a string consisting of 0s, 1s and ?s. How many ways are there to replace each ? with a 0 or a 1 such that the resulting string is balanced? The length of the given string is at most 1024.</div><div><br /></div><div><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-xDs13wc8om4/XuY2y7hTdcI/AAAAAAACqwQ/OrFYixADJtE1IUEuMtwhnAtMlHhKqA-jACK4BGAsYHg/s3238/IMG_20200316_093314.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="2643" data-original-width="3238" height="522" src="https://1.bp.blogspot.com/-xDs13wc8om4/XuY2y7hTdcI/AAAAAAACqwQ/OrFYixADJtE1IUEuMtwhnAtMlHhKqA-jACK4BGAsYHg/w640-h522/IMG_20200316_093314.jpg" width="640" /></a></div>In <a href="https://petr-mitrichev.blogspot.com/2020/05/a-2021-week.html">my previous summary</a>, I have mentioned another Open Cup problem: we have a string which is initially empty. Then we repeatedly add characters either to the beginning of the string, or to the end of the string, <i>n</i> times (<i>n</i><=1000000). Then, we need to print <i>n</i> numbers: how many period lengths did the string have after each addition? A string <i>s</i> has a period length <i>k</i> if 1<=<i>k</i><=length(<i>s</i>) and for each valid i <i>s<sub>i</sub></i>=<i>s</i><sub><i>i</i>+<i>k</i></sub> (note that under this definition the last repetition of a period may be incomplete). For example, the string <span style="font-family: "courier new" , "courier" , monospace;">ababa</span> has 3 period lengths: 2, 4 and 5.</div><div><br /></div><div>The key observation here is that once a certain length <i>k</i> stops being a period, it will never become one again after we add more characters! This is especially clear from the formal definition above, as we just get more constraints of form <i>s<sub>i</sub></i>=<i>s</i><sub><i>i</i>+<i>k</i></sub> as the number of possible values of <i>i</i> increases. Therefore for each length <i>k</i> it will be a period from step <i>k</i> (each string has its own length as a period length) to some step <i>s<sub>k</sub></i>. </div><div><br /></div><div>We can find each particular <i>s<sub>k</sub></i> using binary search in O(log(<i>n</i>)), using hashes to check if <i>k</i> is a period length in O(1), therefore we can find all <i>s<sub>k</sub></i>'s in O(<i>n</i>*log(<i>n</i>)), and the numbers we need to print can then be computed from those in O(<i>n</i>).</div><div><br /></div><div>It's not particularly important for this problem, but note that we're only doing O(<i>n</i>*log(<i>n</i>)) equality comparisons for the hashes, therefore we're not subject to the birthday paradox, and 32-bit hashes are enough.</div><div><br /></div><div>Thanks for reading, and check back for more!</div></div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/6D8SRPzL2KY" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com6http://petr-mitrichev.blogspot.com/2020/06/a-week-without-paradox.htmltag:blogger.com,1999:blog-1953325079793449971.post-49079406516139676922020-05-03T21:51:00.001+03:002020-05-03T21:51:25.199+03:00A 2021 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/-prCjkPcapSQ/Xq8IpyA_wSI/AAAAAAACnzQ/k4cSenC5SJsZwQkyuKwjkFRMGQAvMWbFgCLcBGAsYHQ/s1600/tco20r1btop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="143" data-original-width="953" height="96" src="https://1.bp.blogspot.com/-prCjkPcapSQ/Xq8IpyA_wSI/AAAAAAACnzQ/k4cSenC5SJsZwQkyuKwjkFRMGQAvMWbFgCLcBGAsYHQ/s640/tco20r1btop5.png" width="640" /></a></div>TopCoder Open 2020 Round 1B was the first round of this week (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=17962">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17962&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17963&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">parallel round results</a>, <a href="https://www.topcoder.com/2020-tco-algorithm-round-1b-editorials/">analysis</a>). This was the last chance to get into Round 2 for those who have not qualified yet, and the problemset was correspondingly even more on the easier side. It turned out that a nonzero score was enough to advance, so contestants were mostly competing against the problems instead of between themselves. In order to get the first place, however, one required a few successful challenges as well. jzd got three and won — congratulations!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-r5oQO7eWWzk/Xq8J83CyeUI/AAAAAAACnzc/P-gdxwmrYiYCole5gEgyFgYL3B5XIHrrQCLcBGAsYHQ/s1600/gcj20r1ctop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="470" data-original-width="1475" height="202" src="https://1.bp.blogspot.com/-r5oQO7eWWzk/Xq8J83CyeUI/AAAAAAACnzc/P-gdxwmrYiYCole5gEgyFgYL3B5XIHrrQCLcBGAsYHQ/s640/gcj20r1ctop5.png" width="640" /></a></div>Google Code Jam Round 1C followed on Saturday (<a href="https://codingcompetitions.withgoogle.com/codejam/round/000000000019fef4/0000000000317409">problems</a>, <a href="https://codingcompetitions.withgoogle.com/codejam/round/000000000019fef4">results</a>, top 5 on the left). Just like in the TCO round, this was the last chance to get into Round 2, but the competition was more intense: one needed to solve at least the first two problems completely to advance, and do it in about one hour. Just half an hour was enough for all three problems for Rafbill and maroon, and Rafbill held to a 4-second edge to claim the win :) Well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-1avSZYTmuIw/Xq8LAR27gcI/AAAAAAACnzo/RbNoTz0c-SQOZbtsCxkNZj5OUTN6Xt0zQCLcBGAsYHQ/s1600/oc1920nanjingtop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="242" data-original-width="1098" height="140" src="https://1.bp.blogspot.com/-1avSZYTmuIw/Xq8LAR27gcI/AAAAAAACnzo/RbNoTz0c-SQOZbtsCxkNZj5OUTN6Xt0zQCLcBGAsYHQ/s640/oc1920nanjingtop5.png" width="640" /></a></div>Finally, Open Cup 2019-20 Grand Prix of Nanjing wrapped up the action (<a href="http://opentrains.snarknews.info/~ejudge/res/res10497">results</a>, top 5 on the left, <a href="https://www.dropbox.com/s/gt14yft414e5qob/Gp%20of%20Nanjing.pdf?dl=0">analysis</a>). Team NNSU Almost Retired claimed their second win of the season and seem to be in great form — congratulations! It looks like they'll need to maintain the form for quite a bit longer, as ICPC 2020 World Finals got <a href="https://codeforces.com/blog/entry/76772">rescheduled to 2021</a>. Team USA1 got 11 problems as well, but an enormous amount of incorrect attempts has ruined their penalty time.<br /><br />Problem B was very easy for some teams, but we got stuck on it for the whole contest, only to come up with a solution right after the end :) It went like this: we have a string which is initially empty. Then we repeatedly add characters either to the beginning of the string, or to the end of the string, <i>n</i> times (<i>n</i><=1000000). Then, we need to print <i>n</i> numbers: how many period lengths did the string have after each addition? A string <i>s</i> has a period length <i>k</i> if 1<=<i>k</i><=length(<i>s</i>) and for each valid i <i>s<sub>i</sub></i>=<i>s</i><sub><i>i</i>+<i>k</i></sub> (note that under this definition the last repetition of a period may be incomplete). For example, the string <span style="font-family: Courier New, Courier, monospace;">ababa</span> has 3 period lengths: 2, 4 and 5. Can you see the trick?<br /><br />Thanks for reading, and check back next week!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/ZL_9-c1Uc9M" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com1http://petr-mitrichev.blogspot.com/2020/05/a-2021-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-55219489509869835782020-05-03T16:44:00.001+03:002020-05-03T16:44:42.257+03:00A Lucas week<div dir="ltr" style="text-align: left;" trbidi="on">Codeforces Round 637 last week was declared unrated after the reference solution for problem E turned out to be incorrect, and the problem seemed to be unsolvable.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-RAYQWHXwIqE/Xq6rzibef1I/AAAAAAACnyM/NLVcZb1eZTcXtt8dPvef6Dr6XXik-6wwwCLcBGAsYHQ/s1600/srm784top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="181" data-original-width="941" height="122" src="https://1.bp.blogspot.com/-RAYQWHXwIqE/Xq6rzibef1I/AAAAAAACnyM/NLVcZb1eZTcXtt8dPvef6Dr6XXik-6wwwCLcBGAsYHQ/s640/srm784top5.png" width="640" /></a></div>Therefore TopCoder SRM 784 was the first round that counted (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=17958">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17958&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://clist.by/standings/tco20-algorithm-stage-3-17680999/">TCO qualification standings</a>, <a href="https://www.topcoder.com/single-round-match-784-editorials/">analysis</a>). The constructive hard problem required one to come up with a pattern, and some people did it much faster than others :) I could not come up with an explicit pattern myself, instead finding a pattern in row and column sums from solutions of small inputs, and finding the actual grid using max flow. This took me about 3 times longer than the fastest solutions to this problem, though, so I was out of contention for the top places. tourist was among the fastest solvers there, and he was also twice faster than me on each of the first two problems. Congratulations on the well-deserved victory!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-ZiR_p3Ji0KU/Xq6vqewa2ZI/AAAAAAACnyY/3QxhrruPXXsf0OkWIqDBzfjP1PxNKcFPwCLcBGAsYHQ/s1600/oc1920moscowtop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="312" data-original-width="1205" height="164" src="https://1.bp.blogspot.com/-ZiR_p3Ji0KU/Xq6vqewa2ZI/AAAAAAACnyY/3QxhrruPXXsf0OkWIqDBzfjP1PxNKcFPwCLcBGAsYHQ/s640/oc1920moscowtop5.png" width="640" /></a></div>Open Cup 2019-20 continued its non-stop return with the Grand Prix of Moscow (<a href="http://rucode.it-edu.mipt.ru/~ejudge/rucodeAB.html">results</a>, top 5 on the left, <a href="https://drive.google.com/file/d/1t6vKxpYMcqxmH8allaReFTrNy0q1onMB/view?usp=sharing">analysis</a>). After the same 3 teams split the first 12 stages between them, we started getting new winners, and team japan02 is already the sixth team to win a stage this season. Congratulations on the superb performance!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-7eSkMZ_P4QI/Xq7KZZdkorI/AAAAAAACny4/MhFT2MeiWXES7SOYTBbJpDQvTf2BYx_RQCLcBGAsYHQ/s1600/IMG_20200316_093316.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/-7eSkMZ_P4QI/Xq7KZZdkorI/AAAAAAACny4/MhFT2MeiWXES7SOYTBbJpDQvTf2BYx_RQCLcBGAsYHQ/s640/IMG_20200316_093316.jpg" width="640" /></a></div>In <a href="https://petr-mitrichev.blogspot.com/2020/04/a-caterpillar-week.html">my previous summary</a>, I have mentioned an <a href="https://codeforces.com/gym/102586/problem/E">Open Cup problem</a>: you are given <i>k</i> (<i>k</i><=200) distinct positive integers <i>a<sub>i</sub></i> (<i>a<sub>i</sub></i><=10<sup>5</sup>). Consider all sequences of length <i>n</i> (<i>n</i><=10<sup>18</sup>) with all elements equal to one of the given integers. Count the number of those sequences with the given sum <i>s</i> (<i>s</i><=10<sup>18</sup>). Is that number odd or even?<br /><br />Since we're asked about the answer modulo 2, a natural idea is to try and discard groups of sequences which have an even count. There are actually multiple ways to do that, but for us the most natural way was to notice that since the order of the numbers matters, we can count the number of different orderings for each multiset of <i>n</i> numbers that add up to <i>s</i>, and discard those multisets for which this number of orderings is even. When our multiset has <i>c<sub>i</sub></i> occurrences of the number <i>a<sub>i</sub></i>, this number of orderings is given by <a href="https://en.wikipedia.org/wiki/Multinomial_theorem#Multinomial_coefficients">the multinomial coefficient</a>: n!/(<i>c</i><sub>1</sub>!*<i>c</i><sub>2</sub>!*...*<i>c</i><sub><i>k</i></sub>!).<br /><br />A quick Google query led us to <a href="https://mathoverflow.net/questions/80169/reference-needed-for-lucas-theorem-for-multinomial-coefficients-modulo-a-prime">this mathoverflow post</a>, which tells that this coefficient is odd if and only if there is no carry when performing the addition <i>c</i><sub>1</sub>+<i>c</i><sub>2</sub>+...+<i>c</i><sub><i>k</i></sub>=<i>n</i> modulo 2. This, in turn, means that for each bit that is set in <i>n</i>, there must be exactly one <i>c<sub>i</sub></i> that has this bit set. Or, in other words, if the binary representation of n is 2<sup><i>b</i><sub>1</sub></sup>+2<sup><i>b</i><sub>2</sub></sup>+...+2<sup><i>b</i><sub>t</sub></sup>, then we need to count the parity of the number of ways to take one of the <i>a<sub>i</sub></i>'s 2<sup><i>b</i><sub>1</sub></sup> times, one of the <i>a<sub>i</sub></i>'s 2<sup><i>b</i><sub>2</sub></sup> times (possibly the same one), and so on, so that the sum of all that is <i>s</i>.<br /><br />I find it beautiful that there is a completely orthogonal argument that leads to exactly the same subproblem, obtained by noticing that the number of non-palindromic sequences is always even. You can find more details in <a href="https://codeforces.com/blog/entry/76213?#comment-607268">this Codeforces comment</a>.<br /><br />Now, how to solve the subproblem? Given that <i>s</i> is up to 10<sup>18</sup>, it still seems to be a pretty tough instance of the knapsack problem. A naive approach would be to implement dynamic programming which counts the [parity of] the number of ways to reach every sum <i>u</i><=<i>s</i> using the first i powers of two 2<sup><i>b</i><sub>1</sub></sup>, 2<sup><i>b</i><sub>2</sub></sup>, ..., 2<sup><i>b</i><sub>i</sub></sup>, but the running time of that would be O(<i>s</i>*<i>k</i>*<i>t</i>), which is enormous.<br /><br />However, we can notice that many states of that dynamic programming are actually useless! Suppose we're processing the powers of two in increasing order, and we have processed all powers of two up to but not including 2<sup><i>b</i><sub>i</sub></sup>. Then everything that we will add later will be divisible by 2<sup><i>b</i><sub>i</sub></sup>. Therefore, only the states that are equal to <i>s</i> modulo 2<sup><i>b</i><sub>i</sub></sup> can contribute to the final answer. On the other hand, our current sum will not exceed <i>m</i>*(1+2+...+2<sup><i>b</i><sub>i</sub>-1</sup>)<<i>m</i>*2<sup><i>b</i><sub>i</sub></sup>, where <i>m</i> is the maximum of <i>a<sub>i</sub></i>. So there are at most <i>m</i> possible sums with the given remainder modulo 2<sup><i>b</i><sub>i</sub></sup>, therefore our new solution runs in time O(<i>m</i>*<i>k</i>*<i>t</i>).<br /><br />Since <i>m</i>=10<sup>5</sup>, <i>k</i>=200 and <i>t</i>=60, this is about one billion operations — somewhat borderline. It was fast enough for us during the contest, but in case it would not be, I was planning to optimize it further taking advantage of the fact that we only care about parity, and therefore can use bitsets to represent our dynamic programming arrays and do operations on them.<br /><br />Thanks for reading, and check back for this week's summary!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/fHXI71Ze7uI" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com0http://petr-mitrichev.blogspot.com/2020/05/a-lucas-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-428928190467974762020-04-26T14:28:00.001+03:002020-04-26T14:28:57.792+03:00A caterpillar 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/-g5-EMu2QAY8/XqVZD3wZC2I/AAAAAAACnjc/v3LN2KhMIsoqAdGsdDB4zUKMVbcHYKURACLcBGAsYHQ/s1600/cf635top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="337" data-original-width="1322" height="162" src="https://1.bp.blogspot.com/-g5-EMu2QAY8/XqVZD3wZC2I/AAAAAAACnjc/v3LN2KhMIsoqAdGsdDB4zUKMVbcHYKURACLcBGAsYHQ/s640/cf635top5.png" width="640" /></a></div>Codeforces Round 635 was the first round of last week (<a href="https://codeforces.com/contest/1336">problems</a>, <a href="https://codeforces.com/contest/1336/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/76099">analysis</a>). Problems A, B, C and E1 were solved by all top competitors, but the next step was less clear. maroonrk went for the hardest problem F, solving it with just two minutes remaining. However, this was not enough to beat boboniu who did not notice the additional difficulty in E2, solving both E1 and E2 together, and then wrapped up their victory with D. Congratulations to both!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-DucQoCvAOBs/XqVZkuoDiSI/AAAAAAACnjo/OnrFgI9Ql9AIQx0yDy-J_P9zWh4QL2PKgCLcBGAsYHQ/s1600/tco20r1atop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="175" data-original-width="920" height="121" src="https://1.bp.blogspot.com/-DucQoCvAOBs/XqVZkuoDiSI/AAAAAAACnjo/OnrFgI9Ql9AIQx0yDy-J_P9zWh4QL2PKgCLcBGAsYHQ/s640/tco20r1atop5.png" width="640" /></a></div>TopCoder Open 2020 Round 1A then started a busy weekend (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=17906">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17906&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17907&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">parallel round results</a>, <a href="https://www.topcoder.com/2020-tco-algorithm-round-1a/">analysis</a>). Most top competitors got a bye into Round 2, therefore the scoreboard looked more yellow this time. Pasqual45's points just from the coding phase would be enough for the first place, but they made sure of the win with 100 more challenge points. Well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-jBjImNyG1WM/XqVaGH6X00I/AAAAAAACnj4/iz_rs9DCLVkTRVtlLCBusbLAmWTk_RwigCLcBGAsYHQ/s1600/oc1920tokyotop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="242" data-original-width="910" height="170" src="https://1.bp.blogspot.com/-jBjImNyG1WM/XqVaGH6X00I/AAAAAAACnj4/iz_rs9DCLVkTRVtlLCBusbLAmWTk_RwigCLcBGAsYHQ/s640/oc1920tokyotop5.png" width="640" /></a></div>Open Cup 2019-20 Grand Prix of Tokyo was next (<a href="https://codeforces.com/gym/102586">problems</a>, <a href="http://opentrains.snarknews.info/~ejudge/res/res10495">results</a>, top 5 on the left, <a href="https://drive.google.com/file/d/10nhABkkiSwjw4JcBn67ytePg1Sc82fG5/view?usp=sharing">analysis</a>). All teams solving 4+ problems got E, F, H and I, but the remaining problems were significantly more difficult. Even though 9 problems were solved by at least one team, the best teams only got 6. Our team was close to 6 problems as well, as our last submission on K was correct algorithmically but had an off-by-one error. Congratulations to teams ext71, Polish Mafia and USA1 on actually getting to 6!<br /><br />Solving <a href="https://codeforces.com/gym/102586/problem/E">problem E</a> involved this wonderful feeling where a relatively natural statement hides a solution with multiple interesting layers that "click" together. You are given <i>k</i> (<i>k</i><=200) distinct positive integers <i>a<sub>i</sub></i> (<i>a<sub>i</sub></i><=10<sup>5</sup>). Consider all sequences of length <i>n</i> (<i>n</i><=10<sup>18</sup>) with all elements equal to one of the given integers. Count the number of those sequences with the given sum <i>s</i> (<i>s</i><=10<sup>18</sup>). Is that number odd or even?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-puaTsdSZRqs/XqVa02cVcYI/AAAAAAACnkA/Z3tuD2VyFSsnVxFAW9Ng3CAXT2WzlzjswCLcBGAsYHQ/s1600/gcj20r1btop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="469" data-original-width="1456" height="206" src="https://1.bp.blogspot.com/-puaTsdSZRqs/XqVa02cVcYI/AAAAAAACnkA/Z3tuD2VyFSsnVxFAW9Ng3CAXT2WzlzjswCLcBGAsYHQ/s640/gcj20r1btop5.png" width="640" /></a></div>And finally, Google Code Jam 2020 Round 1B wrapped up the last week (<a href="https://codingcompetitions.withgoogle.com/codejam/round/000000000019fef2/00000000002d5b62">problems</a>, <a href="https://codingcompetitions.withgoogle.com/codejam/round/000000000019fef2">results</a>, top 5 on the left). xll114514 was the first to finish all problems, but mnbvmar was the fastest of the European competitors who didn't want to wake up at 3am for Round 1A, and had one less incorrect attempt than xll114514. Congratulations on the win!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-K1EK6LugQLk/XqVdXwpKhJI/AAAAAAACnko/J099t1j4ZRwEHhJXXfBFYBblkADLz8BVQCLcBGAsYHQ/s1600/IMG_20200315_153811.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/-K1EK6LugQLk/XqVdXwpKhJI/AAAAAAACnko/J099t1j4ZRwEHhJXXfBFYBblkADLz8BVQCLcBGAsYHQ/s640/IMG_20200315_153811.jpg" width="640" /></a></div>In <a href="https://petr-mitrichev.blogspot.com/2020/04/a-gennady-week.html">my previous summary</a>, I have mentioned two problems. <a href="https://community.topcoder.com/stat?c=problem_statement&pm=14810&rd=17903">The first one</a> came from TopCoder: you are given a directed <a href="https://en.wikipedia.org/wiki/Tournament_(graph_theory)">tournament</a> with <i>n</i><=23 vertices. You are then constructing a "power" of this tournament with <i>n</i><sup><i>k</i></sup> vertices (<i>k</i><=1000), with each vertex described with a <i>k</i>-tuple of vertices of the original tournament. The direction of the edge between two <i>k</i>-tuples is given by the direction of the edge between the vertices that appear in the first position the <i>k</i>-tuples differ. For example, the direction of the edge between (<i>a</i>, <i>b</i>, <i>a</i>, <i>c</i>) and (<i>a</i>, <i>b</i>, <i>d</i>, <i>e</i>) is the same as the direction of the edge between <i>a</i> and <i>d</i> in the original tournament. How many subsets of vertices of this big graph induce a strongly connected subgraph, modulo 998244353?<br /><br />First, let's deal with the <i>k</i>-th power. Consider a set <i>S</i> of vertices of the power graph. Each of those vertices is a <i>k</i>-tuple of vertices of the original graph. Let's consider the first position <i>p</i> in those tuples which has at least two different vertices. For example, if <i>S</i> has vertices (<i>a</i>, <i>b</i>, <i>a</i>, <i>c</i>), (<i>a</i>, <i>b</i>, <i>a</i>, <i>d</i>) and (<i>a</i>, <i>b</i>, <i>b</i>, <i>c</i>), then we're interested in the third position since both <i>a</i> and <i>b</i> appear there, while in the first position we always have <i>a</i>, and in the second position we always have <i>b</i>.<br /><br />Now let's consider the set <i>T</i> of all vertices of the original graph that appear in this position. If <i>S</i> is strongly connected, then <i>T</i> is also strongly connected, because any path can be "projected" to <i>T</i> and still be a valid path due to the construction of the power graph.<br /><br />Now suppose <i>T</i> is strongly connected. It turns out that then <i>S</i> is strongly connected as well, because when there's an edge from <i>a</i> to <i>b</i> in the original graph, there's an edge from any vertex with <i>a</i> in position <i>p</i> to any vertex with <i>b</i> in position <i>p</i>, therefore in order to find a path from any vertex in <i>S</i> to any other vertex in <i>S</i> it suffices to find a path between the corresponding vertices in the <i>p</i>-th position, and then pick any matching vertices for the intermediate stopping points. Note that we rely on the fact that <i>T</i> has at least two vertices here, as we need a cycle in <i>T</i> to build a path between two vertices in <i>S</i> that have the same vertex in the <i>p</i>-th position.<br /><br />We have found that the strong connectivities (is there such a word?) of <i>S</i> and <i>T</i> are equivalent. Therefore if we can solve our problem for <i>k</i>=1, we can solve it for any <i>k:</i> consider a subset <i>T</i> of size <i>m</i>>=2 of the original graph that is strongly connected. How many sets <i>S</i> correspond to <i>T</i> in the <i>p</i>-th position? For each of the <i>m</i> vertices of <i>T</i> we have <i>n</i><sup><i>k</i>-<i>p</i></sup> vertices of the power graph with this vertex in the <i>p</i>-th position, and we need to take any non-empty subset of those, so in total we get (2<sup><i>n</i><sup><i>k</i>-<i>p</i></sup></sup>-1)<sup><i>m</i></sup> subsets.<br /><br />Here comes the more interesting part of the problem: what to do for <i>k</i>=1? More specifically, how to count the number sets of vertices of each size that induce a strongly connected subgraph in a given graph with <i>n</i><=23 vertices?<br /><br />My approach was based on <a href="https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm">the Floyd-Warshall algorithm</a>. We would like to run it on all 2<sup><i>n</i></sup> subsets, which would take O(2<sup><i>n</i></sup>*<i>n</i><sup>3</sup>), which is too slow for <i>n</i>=23. We can replace the inner loop with one bitwise or operation, bringing the running time down to O(2<sup><i>n</i></sup>*<i>n</i><sup>2</sup>) — still too slow.<br /><br />However, we can now merge the iteration over subsets with the Floyd-Warshall algorithm! The outer loop of Floyd-Warshall iterates over intermediate vertices, so if we take a recursive algorithm that iterates over the 2<sup><i>n</i></sup> subsets, we can do one iteration of Floyd-Warshall outer loop as soon as we've decided that a vertex belongs to the subset. Therefore we will need to do at most one iteration of the Floyd-Warshall outer loop at each level of recursion, bringing our running time to O(2<sup><i>n</i></sup>*<i>n</i>+2<sup><i>n-1</i></sup>*<i>n</i>+2<sup><i>n-2</i></sup>*<i>n</i>+...)=O(2<sup><i>n</i></sup>*<i>n</i>)!<br /><br />Here is the relevant part of my contest submission with some comments:<br /><br /><span style="font-family: "courier new" , "courier" , monospace;">// Recursive search: we have decided that from the first</span><br /><span style="font-family: "courier new" , "courier" , monospace;">// "at" vertices we have taken the subset "mask",</span><br /><span style="font-family: "courier new" , "courier" , monospace;">// and the intermediate state of Floyd-Warshall after</span><br /><span style="font-family: "courier new" , "courier" , monospace;">// iterating over them is in "preach".</span><br /><span style="font-family: "courier new" , "courier" , monospace;">private void rec(int at, int mask, int[] preach) {</span><br /><span style="font-family: "courier new" , "courier" , monospace;"> if (at >= n) {</span><br /><span style="font-family: "courier new" , "courier" , monospace;"> </span><span style="font-family: "courier new" , "courier" , monospace;"> </span><span style="font-family: "courier new" , "courier" , monospace;"> // Check if the graph is strongly connected.</span><br /><span style="font-family: "courier new" , "courier" , monospace;"> </span><span style="font-family: "courier new" , "courier" , monospace;"> </span><span style="font-family: "courier new" , "courier" , monospace;"> // "preach" already has the transitive closure for the</span><br /><span style="font-family: "courier new" , "courier" , monospace;"> </span><span style="font-family: "courier new" , "courier" , monospace;"> </span><span style="font-family: "courier new" , "courier" , monospace;"> // chosen subset, so we check if it's complete.</span><br /><span style="font-family: "courier new" , "courier" , monospace;"> int count = 0;</span><br /><span style="font-family: "courier new" , "courier" , monospace;"> for (int i = 0; i < n; ++i) if ((mask & (1 << i)) != 0) {</span><br /><span style="font-family: "courier new" , "courier" , monospace;"> ++count;</span><br /><span style="font-family: "courier new" , "courier" , monospace;"> if ((preach[i] & mask) != mask) {</span><br /><span style="font-family: "courier new" , "courier" , monospace;"> return;</span><br /><span style="font-family: "courier new" , "courier" , monospace;"> }</span><br /><span style="font-family: "courier new" , "courier" , monospace;"> }</span><br /><span style="font-family: "courier new" , "courier" , monospace;"> if (count >= 2) {</span><br /><span style="font-family: "courier new" , "courier" , monospace;"> ++res[count];</span><br /><span style="font-family: "courier new" , "courier" , monospace;"> }</span><br /><span style="font-family: "courier new" , "courier" , monospace;"> return;</span><br /><span style="font-family: "courier new" , "courier" , monospace;"> }</span><br /><span style="font-family: "courier new" , "courier" , monospace;"> // Do not take at-th vertex.</span><br /><span style="font-family: "courier new" , "courier" , monospace;"> rec(at + 1, mask, preach);</span><br /><span style="font-family: "courier new" , "courier" , monospace;"> // Take at-th vertex, meaning that we need to do one more</span><br /><span style="font-family: "courier new" , "courier" , monospace;"> // iteration of Floyd-Warshall outer loop.</span><br /><span style="font-family: "courier new" , "courier" , monospace;"> // To avoid allocating new arrays in Java too often,</span><br /><span style="font-family: "courier new" , "courier" , monospace;"> // I have pre-allocated one array per level of recursion</span><br /><span style="font-family: "courier new" , "courier" , monospace;"> // which I overwrite here.</span><br /><span style="font-family: "courier new" , "courier" , monospace;"> int[] nreach = reach[at + 1];</span><br /><span style="font-family: "courier new" , "courier" , monospace;"> System.arraycopy(preach, 0, nreach, 0, n);</span><br /><span style="font-family: "courier new" , "courier" , monospace;"> for (int i = 0; i < n; ++i) if ((nreach[i] & (1 << at)) != 0) {</span><br /><span style="font-family: "courier new" , "courier" , monospace;"> nreach[i] |= nreach[at];</span><br /><span style="font-family: "courier new" , "courier" , monospace;"> }</span><br /><span style="font-family: "courier new" , "courier" , monospace;"> rec(at + 1, mask | (1 << at), nreach);</span><br /><span style="font-family: "courier new" , "courier" , monospace;">}</span><br /><div><br /></div><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-rHhhGy0P-v4/XqVYFrwn9LI/AAAAAAACnjQ/QvgqlN_APxAKEC7yknicStt19Hx9FxiwACPcBGAsYHg/s1600/IMG_20200426_114339.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="761" data-original-width="704" height="320" src="https://1.bp.blogspot.com/-rHhhGy0P-v4/XqVYFrwn9LI/AAAAAAACnjQ/QvgqlN_APxAKEC7yknicStt19Hx9FxiwACPcBGAsYHg/s320/IMG_20200426_114339.jpg" width="296" /></a></div><a href="https://codeforces.com/contest/1338/problem/D">The second problem</a> was from Codeforces: you are given a tree with <i>n</i><=10<sup>5</sup> vertices. You want to draw <i>n</i> closed curves on the plane, one per vertex, in such a way that two curves intersect if and only if the corresponding vertices are adjacent in the tree. What is the maximum size of a chain of curves that are nested in one another (but do not intersect) in such drawing?<br /><br />The space of possibilities for drawing arbitrary curves on the plane is enormous, so it's not clear how to approach this problem. First, we can notice that the curves for adjacent vertices intersect, and therefore can't be nested in one another. Is that the only restriction? In other words, can we choose the curves in such a way that any two curves either intersect (when the corresponding vertices are adjacent) or are nested (if they're not)? At first I believed it was always possible, then finding the size of the longest chain is just finding the size of the largest independent set in a tree, which can be done with a simple greedy from the leaves. I made a quick submission, which turned out to be incorrect :)<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-bpIPaSwPkKM/XqVYCTf9SkI/AAAAAAACnjM/v0ZbMGA8nDQ7FRZE0VAg89EVStGpJLTagCPcBGAsYHg/s1600/IMG_20200426_114339%257E2.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" data-original-height="1544" data-original-width="1600" height="385" src="https://1.bp.blogspot.com/-bpIPaSwPkKM/XqVYCTf9SkI/AAAAAAACnjM/v0ZbMGA8nDQ7FRZE0VAg89EVStGpJLTagCPcBGAsYHg/s400/IMG_20200426_114339%257E2.jpg" width="400" /></a></div>Then I started to think when does this approach fail. After some doodling on paper, I have found a relatively small counterexample (on the left). Moreover, I have also come up with a description of cases where it does in fact work: they all seemed to be <a href="https://en.wikipedia.org/wiki/Caterpillar_tree">caterpillar trees</a>! After some more doodling, I was able to build the set of curves that achieves the perfect nesting for any caterpillar tree (on the right, the curves corresponding to the main path of the caterpillar are red, and the dotted blue curves corresponding to the legs of the caterpillar could be multiple at each level).<br /><br />Finding the size of the largest independent set in all sub-caterpillars of the given tree is slightly more tricky, but still doable with dynamic programming on the tree. However, is it the correct solution? I did not have a proof, but after so much doodling that didn't provide a counterexample it felt right, so I decided to try with another submission, which worked. You can find the proof in <a href="https://codeforces.com/blog/entry/75913">the editorial</a> :)<br /><br />Thanks for reading, and check back for this week's summary!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/nBqYD-z7Gi4" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com0http://petr-mitrichev.blogspot.com/2020/04/a-caterpillar-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-12145435289506246492020-04-13T16:56:00.000+03:002020-04-13T16:58:09.626+03:00A Gennady 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/-7-DirDUZ_D4/XpRe2rjZZzI/AAAAAAACnTg/o5fBx8pZJ9sVYeFan7sEwxL3uTV213VNwCLcBGAsYHQ/s1600/gcj20r1atop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="359" data-original-width="1375" height="166" src="https://1.bp.blogspot.com/-7-DirDUZ_D4/XpRe2rjZZzI/AAAAAAACnTg/o5fBx8pZJ9sVYeFan7sEwxL3uTV213VNwCLcBGAsYHQ/s640/gcj20r1atop5.png" width="640" /></a></div>Last week saw the first elimination round of Google Code Jam 2020, Round 1A (<a href="https://codingcompetitions.withgoogle.com/codejam/round/000000000019fd74/00000000002b3034">problems</a>, <a href="https://codingcompetitions.withgoogle.com/codejam/round/000000000019fd74">results</a>, top 5 on the left). Gennady.Korotkevich started his title defense with another commanding performance in the middle of the night, wrapping up 10 minutes before everybody else. Well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-1nwmZTQfFiI/XpRfcYRB0tI/AAAAAAACnTo/b1wCDqwmNeUpm2UyC9klArj6D77jaTKqwCLcBGAsYHQ/s1600/srm783top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="143" data-original-width="954" height="94" src="https://1.bp.blogspot.com/-1nwmZTQfFiI/XpRfcYRB0tI/AAAAAAACnTo/b1wCDqwmNeUpm2UyC9klArj6D77jaTKqwCLcBGAsYHQ/s640/srm783top5.png" width="640" /></a></div>TopCoder SRM 783 followed later on Saturday (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=17903">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17903&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://youtu.be/TvIoVreS6LU">my screencast</a>, <a href="https://www.topcoder.com/single-round-match-783-editorials/">analysis</a>). tourist, bqi343 and scott_wu were much faster than other top competitors on the 1000, but Scott's 250 failed to handle perfect squares correctly, and Ben's single challenge was still not enough to catch Gennady. Congratulations on the second victory of the day!<br /><br /><a href="https://community.topcoder.com/stat?c=problem_statement&pm=14810&rd=17903">The hard problem</a> had two almost independent parts: solving the <i>k</i>=1 case, and understanding how to reduce <i>k</i>>1 to <i>k</i>=1. The problem statement was: you are given a directed <a href="https://en.wikipedia.org/wiki/Tournament_(graph_theory)">tournament</a> with <i>n</i><=23 vertices. You are then constructing a "power" of this tournament with <i>n</i><sup><i>k</i></sup> vertices (<i>k</i><=1000), with each vertex described with a <i>k</i>-tuple of vertices of the original tournament. The direction of the edge between two <i>k</i>-tuples is given by the direction of the edge between the vertices that appear in the first position the <i>k</i>-tuples differ. For example, the direction of the edge between (<i>a</i>, <i>b</i>, <i>a</i>, <i>c</i>) and (<i>a</i>, <i>b</i>, <i>d</i>, <i>e</i>) is the same as the direction of the edge between <i>a</i> and <i>d</i> in the original tournament. How many subsets of vertices of this big graph induce a strongly connected subgraph, modulo 998244353?<br /><br />The <i>k</i>=1 part — where the graph with at most 23 vertices is just given to you directly — allowed quite a lot of interesting and different solutions, so I encourage you to try solving at least that part :) I believe my solution did not in fact need the graph to be a tournament, it could handle any directed graph, so you can try solving either version.<br /><br />This was the first time I was recording a screencast while using an external 4K monitor, which brought a couple of challenges: first, it seems that encoding a 4K video was using nearly all resources of my machine, even though I was using the same bitrate as I did for the 1080p video. This meant I had to wait for half a minute every time I ran my solutions, somewhat suboptimal :) Second, the fonts in the arena looked really funny, most likely because I had font scaling enabled in Windows to be able to read text in such resolution. Any suggestions on how to resolve those?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-QyOGyaBTdug/XpRjQShb5WI/AAAAAAACnUE/1M10vtWDf5EknOt8iPwbvCCrsOYI9RUvgCLcBGAsYHQ/s1600/cf633top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="272" data-original-width="1107" height="156" src="https://1.bp.blogspot.com/-QyOGyaBTdug/XpRjQShb5WI/AAAAAAACnUE/1M10vtWDf5EknOt8iPwbvCCrsOYI9RUvgCLcBGAsYHQ/s640/cf633top5.png" width="640" /></a></div>Codeforces Round 633 took place on Sunday (<a href="https://codeforces.com/contest/1338">problems</a>, <a href="https://codeforces.com/contest/1338/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/75913">analysis</a>). My approach turned out to be very similar to <a href="https://petr-mitrichev.blogspot.com/2020/04/a-cheese-week.html">previous week</a>'s Codeforces round, solving four problems at reasonable speed but then giving up too easily on the fifth, instead looking for challenges when there were virtually none available — the only failing solution in my room was hos.lyric's D, and I did not really suspect it to be incorrect. tourist was in a similar spot in the middle of the leading pack after solving four problems, but went on to win the round after solving E. Congratulations on three wins in a row!<br /><br />Radewoosh jumped into the second place with a correct submission on E with 7 minutes remaining, then almost blew it by actually submitting a version without bitsets, and then some version with bitsets but also with too much debug enabled, and finally submitting the correct bitset solution again with just seconds remaining in the round. What was that? :)<br /><br /><a href="https://codeforces.com/contest/1338/problem/D">Problem D</a> was quite nice: you are given a tree with <i>n</i><=10<sup>5</sup> vertices. You want to draw <i>n</i> closed curves on the plane, one per vertex, in such a way that two curves intersect if and only if the corresponding vertices are adjacent in the tree. What is the maximum size of a chain of curves that are nested in one another (but do not intersect) in such drawing?<br /><br />Thanks for reading, and check back next week!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/A0wlJkRZIlY" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com0http://petr-mitrichev.blogspot.com/2020/04/a-gennady-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-72374819076217778142020-04-13T14:59:00.000+03:002020-04-13T14:59:02.149+03:00A cheese 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/-ge2JI4ZRIgQ/XpRNgcg6o9I/AAAAAAACnTM/UIZnKrANaH8WinbGyEZXn6NpRw6RiRMbwCLcBGAsYHQ/s1600/cf631top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="335" data-original-width="1322" height="162" src="https://1.bp.blogspot.com/-ge2JI4ZRIgQ/XpRNgcg6o9I/AAAAAAACnTM/UIZnKrANaH8WinbGyEZXn6NpRw6RiRMbwCLcBGAsYHQ/s640/cf631top5.png" width="640" /></a></div>Codeforces hosted its Round 631 during the Mar 30 - Apr 5 week (<a href="https://codeforces.com/contest/1329">problems</a>, <a href="https://codeforces.com/contest/1329/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/75559">analysis</a>). I had a relatively good start on the first four problems, but could not make progress in the last one and switched to challenging with about 20 minutes remaining, also without success. Um_nik, on the other hand, had an even better start and did not give up so easily on E, earning the ultimate reward of being the only contestant to solve all problems. Great job!<br /><br />When solving <a href="https://codeforces.com/contest/1329/problem/C">problem C</a>, I could not come up with a solution analytically for quite some time, so I've used the adage "so many people got it accepted, the solution must be simple!" and started thinking in terms of what a simple solution might look like. I've came up with the [ultimately] correct greedy very quickly, but could not prove that it works. After some more time, I've decided to just implement and submit it, relying on pretests and the adage to help :)<br /><br />When this approach works, it is satisfying, but I feel that using it might be detrimental in the long run: it greatly reduces the motivation when solving the problems analytically, the opportunity to just start submitting good-looking solutions is too tempting. Or maybe it really is a part of the game?<br /><br />Thanks for reading, and check back for more!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/f0X5vfJ0TAg" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com7http://petr-mitrichev.blogspot.com/2020/04/a-cheese-week.html