tag:blogger.com,1999:blog-19533250797934499712024-02-17T09:48:53.376+01:00Algorithms Weekly by Petr MitrichevPetr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.comBlogger529125tag:blogger.com,1999:blog-1953325079793449971.post-14723449196547795952024-02-15T14:43:00.000+01:002024-02-15T14:43:10.438+01:00A NWERC week<p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgR1Fpae772wF5JJEykQ551NBg5-A62JEdpoRKQupzH7Ttb7mj2fe62FgYJaNQXMlPQhvQlA_H44FeczUIV7Yok8FPgubN4UfHX5blCtJR6sM58SZxrpDCvucXDjOwFfrDOELCQ2KFqqDuldcKzBgX5ss0ebkYYlPe3ovBEnARClFkHdSm40G7cPo-olSc/s1513/ucup2r22top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="544" data-original-width="1513" height="230" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgR1Fpae772wF5JJEykQ551NBg5-A62JEdpoRKQupzH7Ttb7mj2fe62FgYJaNQXMlPQhvQlA_H44FeczUIV7Yok8FPgubN4UfHX5blCtJR6sM58SZxrpDCvucXDjOwFfrDOELCQ2KFqqDuldcKzBgX5ss0ebkYYlPe3ovBEnARClFkHdSm40G7cPo-olSc/w640-h230/ucup2r22top5.png" width="640" /></a></div>The 2nd Universal Cup Stage 22: Hangzhou was the only event of last week (<a href="https://ucup.ac/files/ucup/statements/statements-2-22.pdf">problems</a>, <a href="https://ucup.ac/scoreboard/45">results</a>, top 5 on the left, <a href="https://ucup.ac/files/ucup/tutorials/tutorials-2-22.pdf">analysis</a>). Team USA1 has returned to the winning ways after a short slump in form, already leading on 12 problems but still finishing everything with an hour to spare. Congratulations!<p></p><p>Team "nwerc is bad" from the Univerity of Oxford also reminded that they are <a href="https://codeforces.com/blog/entry/116946">one of the favorites</a> for one of the upcoming World Finals in Luxor by earning an excellent fourth place and being the best ICPC-active team this time. Well done!</p><p>Thanks for reading, and check back next week for more meaningful content :)</p>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com2tag:blogger.com,1999:blog-1953325079793449971.post-52090390071836896052024-02-07T09:50:00.001+01:002024-02-07T09:50:45.016+01:00A Delft week<p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgjB9T226N6CLQ3yJShuYTSwhk0OshiUuaKjET_wsMWdqVEDppu9rtcZsAOnScdRQem3cf7j_p7nU151KhE2ndPmDY-L3VC-VBpkhEuvA7tvxZca4eME1FUFEtxP_qSQFRMUwLwFOrlH-nKD6Cr27QCoYuDO0h6a8XDcjjlg6pVvWIkb3VcBRD0PomLCMw/s1241/ucup2r21top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="292" data-original-width="1241" height="150" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgjB9T226N6CLQ3yJShuYTSwhk0OshiUuaKjET_wsMWdqVEDppu9rtcZsAOnScdRQem3cf7j_p7nU151KhE2ndPmDY-L3VC-VBpkhEuvA7tvxZca4eME1FUFEtxP_qSQFRMUwLwFOrlH-nKD6Cr27QCoYuDO0h6a8XDcjjlg6pVvWIkb3VcBRD0PomLCMw/w640-h150/ucup2r21top5.png" width="640" /></a></div>The 2nd Universal Cup. Stage 21: Delft was the main event of last week (<a href="https://contest.ucup.ac/download.php?type=attachments&id=1511&r=0">problems</a>, <a href="https://contest.ucup.ac/results/QOJ1511">results</a>, top 5 on the left, <a href="https://contest.ucup.ac/download.php?type=attachments&id=1511&r=1">analysis</a>). Team HoMaMaOvO won the round and continued closing the gap in the <a href="https://ucup.ac/rating">overall standings</a>, which is now down to a mere 0.16 points. Winning one more stage (their 9th of the season) would be enough for them to overtake USA1, since it would bring at least 1/4*(3/4)**8*(200-175)~=0.62 points.<p></p><div>As both teams solved everything this time, the key advantage for HoMaMaOvO seems to have come from solving a tricky geometry problem B (and one <a href="https://codeforces.com/blog/entry/125350">can't complain</a> that tricky geometry problems were unexpected) very fast from the first attempt. Well done!</div><div><br /></div><div>Thanks for the (quick) reading, and check back next week.</div>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com0tag:blogger.com,1999:blog-1953325079793449971.post-75854982760294808632024-01-31T09:53:00.001+01:002024-01-31T09:53:42.001+01:00A stable denominator week<p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhlCDXr6JchVudpn1ugf1DLq8FcbQPkzfzrFKYekcAYGaC4DzqssY0KoQuDH0lquaaZIaTj89G3oCWb2hWOnq2RJaaWx94arqi0Dr6r9ZKVvL68RsMUwt_ooIyWsaChRhyeqhvM39tLuM0aeL1dTXzogEUbgfOR2zvegs4fjUI_q3PaVoTnudUwWwuHXpw/s636/srm852top5.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="94" data-original-width="636" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhlCDXr6JchVudpn1ugf1DLq8FcbQPkzfzrFKYekcAYGaC4DzqssY0KoQuDH0lquaaZIaTj89G3oCWb2hWOnq2RJaaWx94arqi0Dr6r9ZKVvL68RsMUwt_ooIyWsaChRhyeqhvM39tLuM0aeL1dTXzogEUbgfOR2zvegs4fjUI_q3PaVoTnudUwWwuHXpw/s16000/srm852top5.png" /></a></div>TopCoder returned last week from another long break with SRM 852 (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=19721">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=19721&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left). The 1000-pointer was about counting <i>k</i>-th roots of a specific permutation, and it took the winner SSRS_ just 3.5 minutes since they reused their <a href="https://yukicoder.me/submissions/770025">submission</a> for a more general problem about counting <i>k</i>-th roots of any permutation. More generally this problem did not present as much of a challenge for the top participants as the 500-pointer, which saw many solutions fail and therefore offered a lot of challenge opportunities. Of the three contestants who managed to solve everything, kotatsugame was behind after the coding phase but managed to recover to the second place thanks to 200 challenge points. Congratulations to all three on the great performance!<p></p><p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjOPTk4DcvQ1A1HJZ_WeYfKf4J0Mav3wXadgKeGYssWZHNOebGPzjLvrXWDQX03GoGkhysm-l5upmYl8aa8UPJC5PS6ypN_Xsfib_5DLO3aiUvGcZfD5bRgKX7rTBuviCuAFrbRKDlIfhcMP-Ov-IYhEHjONJVh701lTBxyK7XYtAnHtBslAacKehoBDp4/s1600/ucup2r20top5.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="562" data-original-width="1600" height="224" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjOPTk4DcvQ1A1HJZ_WeYfKf4J0Mav3wXadgKeGYssWZHNOebGPzjLvrXWDQX03GoGkhysm-l5upmYl8aa8UPJC5PS6ypN_Xsfib_5DLO3aiUvGcZfD5bRgKX7rTBuviCuAFrbRKDlIfhcMP-Ov-IYhEHjONJVh701lTBxyK7XYtAnHtBslAacKehoBDp4/w640-h224/ucup2r20top5.png" width="640" /></a></div>The 2nd Universal Cup. Stage 20: Ōokayama followed, as usual, on Saturday (<a href="https://ucup.ac/files/ucup/statements/statements-2-20.pdf">problems</a>, <a href="https://ucup.ac/scoreboard/43">results</a>, top 5 on the left, <a href="https://ucup.ac/files/ucup/tutorials/tutorials-2-20.pdf">analysis</a>). 16 problems in a round is still a lot even by today's standards, but this still did not stop team HoMaMaOvO from solving all of them with 6 minutes to spare :) Well done! This is their 7th win of the season compared to 9 for USA1, and they are definitely still in contention for the <a href="https://ucup.ac/rating">overall</a> first place.<p></p><p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj5zunFEDzF0tW0nEdwxJetWc0y8h8xGktPtbTwyKViCZax3ke5MY4SkpChhhPwks8qsV35VmsVfozWGIhH0YHVtMu1z7-gF6XPubPeKyYRNAfAuBckBTbUwqRs0C9qslrK5S6qY_QrG5LaomR4eXd9vLi9swiXnKO7qlhcyohty6zJCRit_UUaHHWyq4E/s1102/cf921top5.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="278" data-original-width="1102" height="162" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj5zunFEDzF0tW0nEdwxJetWc0y8h8xGktPtbTwyKViCZax3ke5MY4SkpChhhPwks8qsV35VmsVfozWGIhH0YHVtMu1z7-gF6XPubPeKyYRNAfAuBckBTbUwqRs0C9qslrK5S6qY_QrG5LaomR4eXd9vLi9swiXnKO7qlhcyohty6zJCRit_UUaHHWyq4E/w640-h162/cf921top5.png" width="640" /></a></div>Finally, Codeforces Round 921 wrapped up the competitive week also on Saturday (<a href="https://codeforces.com/contest/1924">problems</a>, <a href="https://codeforces.com/contest/1924/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/125137">analysis</a>). Having dealt with the four easier problems in the first hour, I've decided to focus on <a href="https://codeforces.com/contest/1924/problem/F">problem F</a> since there it seemed that we just need to solve the <i>n</i>=3 case and the rest will easily follow, while <a href="https://codeforces.com/contest/1924/problem/E">problem E</a> gave some generating function vibes :) Unfortunately even the <i>n</i>=3 case in F turned out too hard for me. I have even implemented a brute force that tried different random strategies and it still could not solve <i>n</i>=3. The reason for that was probably the fact that the strategies I tried were non-adaptive: they asked the same questions irrespective of the answers.<div><br /></div><div>Implementing a brute force over adaptive strategies seemed harder, so I've decided to give E another chance. I've realized it feels difficult because the number of choices we have always changes, therefore we are multplying probabilities with different denominators and it's not clear how to do the summation over different trajectories nicely. But then I remembered I already had this feeling in the past, and writing about this in my blog :) So I tried searching for [divide by the sum site:blog.mitrichev.ch], and for some reason this search returned <a href="https://blog.mitrichev.ch/2023/08/a-power-of-two-week.html">what I was looking for</a> on the first page. I've re-read that solution, and remembered the key trick: even if the overall number of choices is different every time, since all choices have the same probability at each step, the relative probability for a particular subset of choices of fixed size will always be the same. In the linked problem it was just 2 options each with probability 50%, while in problem E this time, if we focus on whether we visit a particular pair (<i>x</i>,<i>y</i>) or not, the number of choices affecting this outcome is always <i>x</i>+<i>y</i>, no matter the current state, so we can compute the probability of such visit happening very nicely.</div><div><br /></div><div>There was still some work to do to improve the complexity from O(<i>n</i><sup>2</sup>) to O(<i>n</i>*log<i>n</i>), and luckily I managed to do it before the end of the round. This was of course still not enough to compete with jiangly and others who focused on problem E earlier. Congratulations on the win!<br /><p></p><div>Thanks for reading, and check back next week.</div></div>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com0tag:blogger.com,1999:blog-1953325079793449971.post-11044331420380873692024-01-21T23:04:00.001+01:002024-01-21T23:04:28.209+01:00A Frobenius week<p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhIAF5ZEdvy8nzrMYBCyHEbqG1eEBFR3xQH4UXNvVNfwjsdcAdWgT7LftLLrYiFygmU5_ekhIL9v9Sks5ld-Mn190qy7o1Z52BXvK9-VnrgbQKfC8VpwS4pXW5qziQwqkzvDpgnHo20ir4V2Z02yBNakc0LSCfOyDydpukMWFjc7n3RrQuy9066IcfHh-k/s1845/ucup2r19top5.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="589" data-original-width="1845" height="204" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhIAF5ZEdvy8nzrMYBCyHEbqG1eEBFR3xQH4UXNvVNfwjsdcAdWgT7LftLLrYiFygmU5_ekhIL9v9Sks5ld-Mn190qy7o1Z52BXvK9-VnrgbQKfC8VpwS4pXW5qziQwqkzvDpgnHo20ir4V2Z02yBNakc0LSCfOyDydpukMWFjc7n3RrQuy9066IcfHh-k/w640-h204/ucup2r19top5.png" width="640" /></a></div>The 2nd Universal Cup Stage 19: Estonia was the only event of this week (<a href="https://ucup.ac/files/ucup/statements/statements-2-19.pdf">problems</a>, <a href="https://ucup.ac/scoreboard/42">results</a>, top 5 on the left, <a href="https://ucup.ac/files/ucup/tutorials/tutorials-2-19.pdf">analysis</a>). Team 03 Slimes, who are a distant third in the <a href="https://ucup.ac/rating">overall standings</a>, won their second stage of the season in an impressive fashion, beating the top two teams in the overall standings by two problems. Judging by the +32, some squeezing was involved, potentially of an approach that was not intended to pass — but that is also an important skill in algorthmic competitions, so well done! I am also not sure who actually was on the team this time, as Mingyang Deng is also listed as part of MIT CopyPaste on the same scoreboard.<div><br /></div><div>Possibly rejuvenated by <a href="https://codeforces.com/blog/entry/124905">the news</a> that the 2022 ICPC World Finals seem to be finally happening in April, Harbour.Space P+P+P followed in second place — congratulations as well! (jk, they actually wrote this contest as part of the <a href="https://ocpc.mathos.unios.hr/2023s/contest-info.php">Osijek camp</a> back in September, so they were still practicing towards the original dates).</div><div><br /></div><div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiw59kxJiLpS1FOXKI2RHkmMVBmmGPsXp8hKZWW3z4dr9k_PPRsB6qUll1gJBZk3jxPbJ6vJSCNeXBuqETUMPrsGFk3c1AL4orq-x6uAP5Ny5NlCyNF5U6B00QbRHVSDBF9vjDnWuvQbjvPB41t3yxt7ux-0xzwdp2-E4XC6lP374QNse0Ul-b7rT30pIg/s3914/PXL_20231015_114759883.MP-EDIT.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="2891" data-original-width="3914" height="472" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiw59kxJiLpS1FOXKI2RHkmMVBmmGPsXp8hKZWW3z4dr9k_PPRsB6qUll1gJBZk3jxPbJ6vJSCNeXBuqETUMPrsGFk3c1AL4orq-x6uAP5Ny5NlCyNF5U6B00QbRHVSDBF9vjDnWuvQbjvPB41t3yxt7ux-0xzwdp2-E4XC6lP374QNse0Ul-b7rT30pIg/w640-h472/PXL_20231015_114759883.MP-EDIT.jpg" width="640" /></a></div>Finally, this week an anonymous LGM <a href="https://codeforces.com/blog/entry/124815">published</a> a very nice result that drops a logarithmic factor from matrix exponentiation. Of course, theoretically we already know <a href="https://en.wikipedia.org/wiki/Computational_complexity_of_matrix_multiplication">ways</a> to drop much more from the asymptotic complexity, but all of those are not really beneficial in practice on the time limits prevalent in the algorithmic competitions. This result, however, <a href="https://judge.yosupo.jp/submissions/?problem=pow_of_matrix&order=%2Btime&status=AC">did allow</a> to slash the fastest time to find a power of a 200x200 matrix roughly 3x (compared to the straightforward binary exponentiation method; the judge also has some fast submissions from November 2023 that start with "<span style="font-family: courier;">vector<ll> f=a.poly();</span>", so possibly some other version or precursor of this result?..</div><div><br /></div><div>I guess now it will be a bit harder to separate wrong submissions when preparing problems, on the other hand the squeezing toolkit just got a bump :)</div><div><br /></div><div>Thanks for reading, and check back next week!</div>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com2tag:blogger.com,1999:blog-1953325079793449971.post-25188436414294965802024-01-19T10:25:00.000+01:002024-01-19T10:25:22.492+01:00A HoMaMaOvO week<p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhdxApBenJHaWErYniVv3BDjH51YC6_MH5MQS2l2tR5_htmY3y0H7sD39EQcR8N6zhwbxclmr6ZWMdUK2zj-vHjF_IQjb0kJeHWxZsWFfr2RzJHRDbRhCND3vxscUL0uhGMlqMtCW78ziGtee-unF1IyY3njyWYzzHoA0e2JIZ6pAsIta4iLQfzwdqbQnk/s1205/ucup2r18top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="542" data-original-width="1205" height="288" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhdxApBenJHaWErYniVv3BDjH51YC6_MH5MQS2l2tR5_htmY3y0H7sD39EQcR8N6zhwbxclmr6ZWMdUK2zj-vHjF_IQjb0kJeHWxZsWFfr2RzJHRDbRhCND3vxscUL0uhGMlqMtCW78ziGtee-unF1IyY3njyWYzzHoA0e2JIZ6pAsIta4iLQfzwdqbQnk/w640-h288/ucup2r18top5.png" width="640" /></a></div>The 2nd Universal Cup. Stage 18: Dolgoprudny was the only event of last week (<a href="https://ucup.ac/files/ucup/statements/statements-2-18.pdf">problems</a>, <a href="https://ucup.ac/scoreboard/41">results</a>, top 5 on the left, <a href="https://ucup.ac/files/ucup/tutorials/tutorials-2-18.pdf">analysis</a>). Team Hailiang FLS + RDFZ: Anonymous were the first to 6 problems at 1:58 into the contest, followed by Team HoMaMaOvO at 2:15. The remaining problems were much harder, and the teams were probably faced with tough choices between pursuing multiple problems in parallel and focusing on one problem to get it accepted. Both teams submitted 3 problems in the remaining time, and Anonymous were the first to get one of them accepted, but then HoMaMaOvO overtook them by getting two in the last hour. Congratulations to both teams!<p></p><p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiPPWN_ZsMSGoAm_KTEWRf_Efl_sc6RJZU5rCXZRU1M0wpYVmBEyHWeDNPxoiTaysfwST0jrxSLlrUag0EFjYgl2tu5MC2wdUE9Zc19gdU2W0aBEL0epXxmDoTaVYdai6QXVGIPhM9uw6RszP3dUfDlqsNJNzgDxFr0VwRnPPu3O2VWLyXkbv8-gbeCmi4/s4032/PXL_20231008_121742943.MP.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="3024" data-original-width="4032" height="480" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiPPWN_ZsMSGoAm_KTEWRf_Efl_sc6RJZU5rCXZRU1M0wpYVmBEyHWeDNPxoiTaysfwST0jrxSLlrUag0EFjYgl2tu5MC2wdUE9Zc19gdU2W0aBEL0epXxmDoTaVYdai6QXVGIPhM9uw6RszP3dUfDlqsNJNzgDxFr0VwRnPPu3O2VWLyXkbv8-gbeCmi4/w640-h480/PXL_20231008_121742943.MP.jpg" width="640" /></a></div>In <a href="https://blog.mitrichev.ch/2024/01/a-11-week.html">my previous summary</a>, I have mentioned <a href="https://codeforces.com/contest/1919/problem/D">a Codeforces problem</a>: consider a rooted tree where each node either has a leaf, or has exactly two children. For each node with two children, one of the edges to the children has weight 0, while the other has weight 1. We run a depth-first traversal of this tree starting from the root, and for each leaf we print the sum of weights on the path from the root to this leaf. Now we are given just the printed sequence and not the tree, and need to answer if there exists a tree as described above that could lead to this sequence being printed? For example, 2 1 0 1 1 can be printed, but 1 0 2 1 3 can't. The length of the given sequence is up to 2*10<sup>5</sup>.<p></p><p>The key observation in this problem is to imagine that we are building our tree step by step. Initially, we have only the root, which is also a leaf, so the sequence printed will be just 0. Now we add two children to the root, using edges with weights 0 and 1, and the depth-first search traverses them in some order. Depending on this order, the sequence we get will become either 0 1 or 1 0. We continue by repeatedly taking a leaf and adding two children to it, and the sequence always changes in the following manner: if the number corresponding to this leaf was <i>x</i>, then we insert <i>x</i>+1 into this sequence either directly to the left or directly to the right of it. And we can apply this operation to any number in the sequence, so we just need to check if the sequence we are given can be obtained starting from just the number 0 using this operation repeatedly.</p><p>Now let us look at the process in reverse, in other words we will repeatedly remove numbers that are adjacent to a number smaller by 1 until only 0 is left. What should we remove first? All numbers in this sequence that are adjacent to a number smaller by 1 are candidates. Now consider what happens when we remove number <i>x</i> that was adjacent to <i>x</i>-1: now <i>x</i>-1 becomes adjacent to some other number <i>y</i>. When <i>y</i>=<i>x</i>-2, the number <i>x</i>-1 become a candidate. When <i>y</i>=<i>x</i>, the number <i>y</i> becomes a candidate. In all other cases, no new candidates appear. This means that the new appearing candidates are never bigger than the number being removed.</p><p>Therefore we can safely remove any of the candidates with the highest value: we will never get candidates with even higher value in the future because of the previous argument, therefore those numbers themselves will never be useful to support removal of another number. So we can just keep removing one of the remaining highest values while it is possible, and we either reach a single 0, in which case we have found a solution, or we get stuck when all remaining highest values cannot be removed, in which case there is no solution.</p><p>Thanks for reading, and check back for more!</p>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com0tag:blogger.com,1999:blog-1953325079793449971.post-83107598226270302112024-01-07T20:22:00.001+01:002024-01-08T08:35:01.572+01:00A 1:1 week<p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiKtuqOjVj2iHim9QQ7ncxySiclTvO9Rw3p9m8g9vePrjKPJoDDXiMXXjS_Ees3U3X9TRwZWJ-QntS9iSCXp7UJ94sEXc30u_xv6VJrdUL1awbUuzGTq7MgBYuDaXe5TnT_VcC619e5AF0tOYJQ6gFYYw1SPdrUKfDYr4Awyd9pzKTXsDOkIwu9Zo_UK1A/s1813/ucup2r17top5.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="643" data-original-width="1813" height="226" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiKtuqOjVj2iHim9QQ7ncxySiclTvO9Rw3p9m8g9vePrjKPJoDDXiMXXjS_Ees3U3X9TRwZWJ-QntS9iSCXp7UJ94sEXc30u_xv6VJrdUL1awbUuzGTq7MgBYuDaXe5TnT_VcC619e5AF0tOYJQ6gFYYw1SPdrUKfDYr4Awyd9pzKTXsDOkIwu9Zo_UK1A/w640-h226/ucup2r17top5.png" width="640" /></a></div>For the third consecutive week, the competitive programming scene consisted of a Universal Cup round, and a Codeforces round, both on Saturday. The Universal Cup round was called Stage 17: Jinan (<a href="https://ucup.ac/files/ucup/statements/statements-2-17.pdf">problems</a>, <a href="https://ucup.ac/scoreboard/40">results</a>, top 5 on the left, <a href="https://ucup.ac/files/ucup/tutorials/tutorials-2-17.pdf">analysis</a>). The usual suspects occupied the first two places (well done!), but quite unusually the scores of two teams that participated in the original ICPC regional, both from Peking University according to Google Translate, were enough for 3rd and 4th. I guess we need to pay attention to Peking University at the upcoming World Finals indeed :)<p></p><div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEguaZct69XjrOx5XXQC7A-VUEt0eYhJCokt2ouYicAwEDJeRglYBtTLeqkajDnrt57vNqfPNbkOK1BQu2eK8laaKc9ae3NwGaZAs7ySTYujxcQuX32D6_KvHUtcbvI2o24d1-pgPR_unzbJisVKZvu7Orsw347wqWAbrcxD8nD8vHB8XnMF-oZBPfetPcw/s1108/cfhello2024top5.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="277" data-original-width="1108" height="160" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEguaZct69XjrOx5XXQC7A-VUEt0eYhJCokt2ouYicAwEDJeRglYBtTLeqkajDnrt57vNqfPNbkOK1BQu2eK8laaKc9ae3NwGaZAs7ySTYujxcQuX32D6_KvHUtcbvI2o24d1-pgPR_unzbJisVKZvu7Orsw347wqWAbrcxD8nD8vHB8XnMF-oZBPfetPcw/w640-h160/cfhello2024top5.png" width="640" /></a></div>The Codeforces round was called Hello 2024 (<a href="https://codeforces.com/contest/1919">problems</a>, <a href="https://codeforces.com/contest/1919/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/124220">analysis</a>). I started relatively quickly, and was in 2nd place after solving problem F using the excellent AtCoder library segment tree template that helps focus on defining the monoid in question (search for "Data op" function in <a href="https://codeforces.com/contest/1919/submission/240549860">my solution</a>). This has left me with 3 problems to solve: problem E, where the contour of a quadratic dynamic programming solution was more or less clear after reading the problem, and problems G and H, which looked very interesting to solve but where I did not have any good idea quickly. I've decided to implement E before thinking more about G and H — after all, how long can figuring out the details and implementing a relatively straightforward quadratic dynamic programming take? It turns out, almost two hours :(</div><div><br /></div><div>ecnerwala did not get stuck on problem E, and therefore had plenty of time for the two harder problems, and he needed that time as he solved G with just 7 minutes remaining in the round and claimed the first place. Congratulations!</div><div><br /></div><div>Let me highlight <a href="https://codeforces.com/contest/1919/problem/D">problem D</a> from this round: consider a rooted tree where each node either has a leaf, or has exactly two children. For each node with two children, one of the edges to the children has weight 0, while the other has weight 1. We run a depth-first traversal of this tree starting from the root, and for each leaf we print the sum of weights on the path from the root to this leaf. Now we are given just the printed sequence and not the tree, and need to answer if there exists a tree as described above that could lead to this sequence being printed? For example, 2 1 0 1 1 can be printed, but 1 0 2 1 3 can't. The length of the given sequence is up to 2*10<sup>5</sup>.</div><div><br /></div><div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEglBMYn0v3JiGwaQm4NSSANawlIaxjb7GJzbh5nYirH-TbBC4XczkY6RW7_hRUSSLUzp7mtpmcQPgV6iHxPoQ4YIvC_ajzwHPK0mntvpQ1YYvT3S0FFnBd4N_W14xsV_4VgD6hyphenhyphen5rcQGjnC4WmjBrPrzGAq72tTdrYS5APFlYDGEx8d5aw8yEJn092U6vI/s4032/PXL_20230910_031140469.MP.jpg" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="3024" data-original-width="4032" height="480" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEglBMYn0v3JiGwaQm4NSSANawlIaxjb7GJzbh5nYirH-TbBC4XczkY6RW7_hRUSSLUzp7mtpmcQPgV6iHxPoQ4YIvC_ajzwHPK0mntvpQ1YYvT3S0FFnBd4N_W14xsV_4VgD6hyphenhyphen5rcQGjnC4WmjBrPrzGAq72tTdrYS5APFlYDGEx8d5aw8yEJn092U6vI/w640-h480/PXL_20230910_031140469.MP.jpg" width="640" /></a></div>In <a href="https://blog.mitrichev.ch/2023/12/a-run-twice-week.html">my previous summary</a>, I have mentioned <a href="https://contest.ucup.ac/contest/1465/problem/4829">a Universal Cup problem</a>: your program is executed twice. In the first run, you are given a graph with <i>n</i>=1000 (note that it is not <i>n</i><=1000, but exactly <i>n</i>=1000) vertices, and 2000<=<i>m</i><=5000 edges. It is guaranteed that this graph was generated randomly by adding a uniformly random non-existing edge <i>m</i> times. You can make at most 5 changes to this graph, where one change is adding an edge between two vertices not connected by an edge, or removing an edge. The first run of your program ends there. The graph with your changes applied is then shuffled (randomly permute vertices, edges, and ends of an edge), and is given as input to the second run of your program. The trick is that your program is not told whether it is the first run or the second run, and instead needs to detect it itself. In other words, you need to apply such changes in the first run that you'd be able to detect that the graph was changed from a random one in the second run.</div><div><br /></div><div>As <a href="https://blog.mitrichev.ch/2023/12/a-run-twice-week.html?showComment=1704039259957#c851641109497306387">this comment</a> suggests, there are so many things one can try in this problem. When I solved it earlier today, I've decided to go for the most general approach: let us choose some hash of a graph that is reasonably fast to compute, and that does not change when we shuffle the graph. Now we say we are in the second run if this hash modulo 10000 is equal to 0, and otherwise we just keep trying random edges to add to make this hash modulo 10000 equal to 0. This will require 10000 iterations on average to find, which should be fast enough as each iteration is O(<i>m</i>), and this will incorrectly work on the first run with probability one in 10000, which is tolerable as the problem likely has on the order of 100 testcases.</div><div><br /></div><div>As for the concrete hash function, I've used the (generally incorrect) idea of the hash described in "Problem 2" in <a href="https://rng-58.blogspot.com/2017/02/hashing-and-probability-of-collision.html">this post</a> with 10 iterations, but using the polynomial combination method from "Problem 4" to quickly combine the values of adjacent nodes since it avoids sorting. Most likely any not extremely bad hash would work since the given graphs are random. This was accepted from the first attempt, I did not even have to do any hyperparameter tuning.</div><div><br /></div><div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEho6qlOI99DTycnStQ5gp3YFczEc1yxn1UoMGV5OMX0KAqrqez7NpDbLxNEOa_ZYz4z-zWAIpbonF0LhxWcnLRLceuFFgiptSUxUpndIQOXSRok_SVJgU2wPB18XWJTtdvvGYSDBBYjDlt4OVGeEpzd50-HOHCEoVZN0-OyQMGA0N5uc16OicUzQbZiyNY/s4032/PXL_20230906_141824580.jpg" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="3024" data-original-width="4032" height="480" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEho6qlOI99DTycnStQ5gp3YFczEc1yxn1UoMGV5OMX0KAqrqez7NpDbLxNEOa_ZYz4z-zWAIpbonF0LhxWcnLRLceuFFgiptSUxUpndIQOXSRok_SVJgU2wPB18XWJTtdvvGYSDBBYjDlt4OVGeEpzd50-HOHCEoVZN0-OyQMGA0N5uc16OicUzQbZiyNY/w640-h480/PXL_20230906_141824580.jpg" width="640" /></a></div>Finally, Mike Mirzayanov has <a href="https://codeforces.com/blog/entry/124418">decided</a> to tackle a long-standing Codeforces issue: people using multiple accounts (and maybe also the same account being used by multiple people?). Of course, it <a href="https://codeforces.com/blog/entry/124418?#comment-1104357">escalated</a> rather quickly :) As for me, the social aspect — competing against other people, seeing their progress over the years, learning what type of problems they solve best, talking to them on the forums, and so on — is very important in competitive programming, and it complements the problem solving part very nicely. I think people violating the 1:1 property of the person-to-account mapping do ruin the social aspect, especially if they compete at the highest level (in this case there were two accounts in the top 10 by rating), and therefore I support Mike's decision to act. It is also quite sad that it has come to this at all — competitive programming depends on participants' integrity in a big way (it is very hard to detect if one consults with others during the round, for example), and seeing top-level participants violate one rule that it hard to enforce does not lend confidence that other rules that are hard to enforce are still standing.</div><div><br /></div><div>Thanks for reading, and check back next week!</div>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com0tag:blogger.com,1999:blog-1953325079793449971.post-48405860620404870562023-12-31T16:05:00.001+01:002023-12-31T16:05:07.531+01:00A run twice week<p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjivEWR6OQ6mvnx1p8PiHqLaqBAUraTP86LhVJT9r0IVCX5JWUCKjubRYXWMUxN2eM4ZJJPelaSO1RE8tu_x4E_YvCQ-4BClWu2zMrCSVML-0hT02yZP0f-XFnbW8P4cMrbLQqdTNDQC1l27MQ7zPwxedv2us29jdXgDL8pMc9uwmjnWMjaKnCY_DK3Dck/s1960/ucup2r15top5.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="575" data-original-width="1960" height="188" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjivEWR6OQ6mvnx1p8PiHqLaqBAUraTP86LhVJT9r0IVCX5JWUCKjubRYXWMUxN2eM4ZJJPelaSO1RE8tu_x4E_YvCQ-4BClWu2zMrCSVML-0hT02yZP0f-XFnbW8P4cMrbLQqdTNDQC1l27MQ7zPwxedv2us29jdXgDL8pMc9uwmjnWMjaKnCY_DK3Dck/w640-h188/ucup2r15top5.png" width="640" /></a></div>The 2nd Universal Cup Stage 15: Macau took place last week, but its results were not public when I wrote the last summary (<a href="https://ucup.ac/files/ucup/statements/statements-2-15.pdf">problems</a>, <a href="https://ucup.ac/scoreboard/38">results</a>, top 5 on the left, <a href="https://ucup.ac/files/ucup/tutorials/tutorials-2-15.pdf">analysis</a>). Similar to the previous stages, this seems to have originated as an ICPC regional contest, but this time the top onsite team got quite high place 11 on the Universal Cup scoreboard (still with 9 problems, which seems to be a universal constant) — I guess we need to keep an eye at the Peking University team at one of the upcoming World Finals :) Congratulations to USA1 and HoMaMaOvO, the clear top 2 in <a href="https://ucup.ac/rating?season=2">the overall standings</a> as well, on solving everything!<div><br /></div><div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjl3UIdzxq3pOji-4UrNO7EaEuQiu1xHSC6DvvERB2pYFa7pk2_XPaxyNtigrryikPVJJBxWxf153HJcjqUJ3Gc80qopwdV3o8PYiwMhEznbQOK2QO0PoSoEXfemjcaE-qS6bieZvEluVCAlT0zO9avJIKxbnL8ECyYSMbiQMNP73YICf9-SjkvZGbMq4g/s1944/ucup2r16top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="574" data-original-width="1944" height="188" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjl3UIdzxq3pOji-4UrNO7EaEuQiu1xHSC6DvvERB2pYFa7pk2_XPaxyNtigrryikPVJJBxWxf153HJcjqUJ3Gc80qopwdV3o8PYiwMhEznbQOK2QO0PoSoEXfemjcaE-qS6bieZvEluVCAlT0zO9avJIKxbnL8ECyYSMbiQMNP73YICf9-SjkvZGbMq4g/w640-h188/ucup2r16top5.png" width="640" /></a></div>The 2nd Universal Cup Stage 16: Run Twice followed this Saturday (<a href="https://ucup.ac/files/ucup/statements/statements-2-16.pdf">problems</a>, <a href="https://ucup.ac/scoreboard/39">results</a>, top 5 on the left, <a href="https://ucup.ac/files/ucup/tutorials/tutorials-2-16.pdf">analysis</a>). The round featured 11 problems in the relatively new run-twice format (<a href="https://codeforces.com/blog/entry/123963">announcement</a>), which I think is an awesome idea that extends the boundaries of what an algorithmic contest problem can be. The new format did not bring a new winner, as team HoMaMaOvO solved everything with an hour to go. Well done!</div><div><br /></div><div>I did not participate in this round, but I checked out the problems because the topic was so interesting, and I'd like to highlight <a href="https://contest.ucup.ac/contest/1465/problem/4829">problem F</a>: your program is executed twice. In the first run, you are given a graph with <i>n</i>=1000 (note that it is not <i>n</i><=1000, but exactly <i>n</i>=1000) vertices, and 2000<=<i>m</i><=5000 edges. It is guaranteed that this graph was generated randomly by adding a uniformly random non-existing edge <i>m</i> times. You can make at most 5 changes to this graph, where one change is adding an edge between two vertices not connected by an edge, or removing an edge. The first run of your program ends there. The graph with your changes applied is then shuffled (randomly permute vertices, edges, and ends of an edge), and is given as input to the second run of your program. The trick is that your program is not told whether it is the first run or the second run, and instead needs to detect it itself. In other words, you need to apply such changes in the first run that you'd be able to detect that the graph was changed from a random one in the second run. Do you see a way?<br /><div><div><br /></div><div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhqcUzHOOFU17KcfiftwjEWrzEY_3Qq9MIEs4zmKAm5s0FyFY5aoh1qRMFLCi9tcIFWN8Le2C_mPaorYprPoGk1UQrrEBx4bRi3UczYiiNKf3elkzX-n0cnkboPpS2uGSZdfLjfnNQku9wp0R9fhk4p0FnNeHSp4aQjOHgMM20i4Wav_CZPfRX84Q5nl0U/s4080/PXL_20231203_090149740.MP-EDIT.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1893" data-original-width="4080" height="296" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhqcUzHOOFU17KcfiftwjEWrzEY_3Qq9MIEs4zmKAm5s0FyFY5aoh1qRMFLCi9tcIFWN8Le2C_mPaorYprPoGk1UQrrEBx4bRi3UczYiiNKf3elkzX-n0cnkboPpS2uGSZdfLjfnNQku9wp0R9fhk4p0FnNeHSp4aQjOHgMM20i4Wav_CZPfRX84Q5nl0U/w640-h296/PXL_20231203_090149740.MP-EDIT.jpg" width="640" /></a></div>In continuing another great Open Cup <a href="https://blog.mitrichev.ch/2013/01/prime-contest-on-snarknews.html">tradition</a>, Universal Cup is holding a Prime Contest this and next week. Given the higher amount of Universal Cup rounds, the Prime Contest appears practially infinite with problem numbers going up to 167, and nevertheless 36 out of 39 problems have already been solved, and even more amazingly 26 of those were solved by the same team! There are still 5 days left and 3 problems have not yet been solved, so maybe this is your chance — but remember that those problems are not for the faint-hearted :) You need an Universal Cup login to participate, and I believe you can get one via <a href="https://ucup.ac/register">the registration form</a>.<br /><p></p><p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg9PcuXdKba6R5vLHFbZMSm71_9aYHYKlif7FDv1HDAGC_w6RjHML9oQgv-ckl84J7_j8MeRVH2FBO2dmoq19YNs5k7rq1_V2Fck60IRnu94VLlQbgB4kp5fGiqRq9brAKZY8SUvh2NIg5zuMC0zvOMHozb0MhrilkAU-XgglHfPuMRPaQuXbhdBONFBS8/s1321/cfgoodbye2023top5.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="348" data-original-width="1321" height="168" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg9PcuXdKba6R5vLHFbZMSm71_9aYHYKlif7FDv1HDAGC_w6RjHML9oQgv-ckl84J7_j8MeRVH2FBO2dmoq19YNs5k7rq1_V2Fck60IRnu94VLlQbgB4kp5fGiqRq9brAKZY8SUvh2NIg5zuMC0zvOMHozb0MhrilkAU-XgglHfPuMRPaQuXbhdBONFBS8/w640-h168/cfgoodbye2023top5.png" width="640" /></a></div>Codeforces Good Bye 2023 wrapped up the competitive year (<a href="https://codeforces.com/contest/1916">problems</a>, <a href="https://codeforces.com/contest/1916/standings">results</a>, top 5 on the left). The round was not received well (<a href="https://codeforces.com/blog/entry/124060?#comment-1101375">1</a>, <a href="https://codeforces.com/blog/entry/123930?#comment-1101728">2</a>, <a href="https://codeforces.com/blog/entry/124110">3</a>), but nevertheless congratulations to ksun48 on being the only one to solve everything and therefore getting a clear first place!<p></p><p>Thanks for reading, and check back in 2024.</p></div></div></div>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com1tag:blogger.com,1999:blog-1953325079793449971.post-55439865466797353802023-12-24T14:41:00.003+01:002023-12-25T08:15:38.019+01:00An odd knapsack week<p><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjBLi8ZNLqXqFdG7OGffwfHfwMeUYhsKWzeYQTcPKOD1ZZjefPpauUxh6P1X4M_wlx_-6JHch90DBOtoiB_Fxk-E3Y9ZATsXXWn6QB3cetdBhyQpWFY93ZoLbesArzf7ftrFbue19b7Lpcj3m7UOq7oi3vIPwqtFGU-TXor8b4cicBsEdPWB-J1HBeU7o8/s1324/cfpinely3top5.png" style="clear: left; display: inline; margin-bottom: 1em; margin-right: 1em; text-align: center;"><img border="0" data-original-height="347" data-original-width="1324" height="168" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjBLi8ZNLqXqFdG7OGffwfHfwMeUYhsKWzeYQTcPKOD1ZZjefPpauUxh6P1X4M_wlx_-6JHch90DBOtoiB_Fxk-E3Y9ZATsXXWn6QB3cetdBhyQpWFY93ZoLbesArzf7ftrFbue19b7Lpcj3m7UOq7oi3vIPwqtFGU-TXor8b4cicBsEdPWB-J1HBeU7o8/w640-h168/cfpinely3top5.png" width="640" /></a></p>Pinely Round 3 on Codeforces took place on Saturday (<a href="https://codeforces.com/contest/1909">problems</a>, <a href="https://codeforces.com/contest/1909/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/123584">analysis</a>). Quite a few people got the first 8 problems correctly, some with more than half of the contest time left, but the last two problems proved to be quite tough to crack. Only zh0ukangyang got problem I right, and only maroonrk got problem H right, therefore earning the first two places. Congratulations!<div><br /></div><div>Quite interestingly, this time there was no contestant who successfuly solved H or I after skipping one of the easier problems (so rainboy sadly <a href="https://codeforces.com/submissions/rainboy/contest/1909">scored</a> 0 :(), which goes to show that such strategy looks amazing when it works, but also carries huge risks :)</div><div><br /></div><div>As for my contest, I wasted way too much time on F and G, and therefore did not spend any meaningful amount of time on H and I.</div><div><br /></div><div>In problem F, when trying to generalize my solution from F1 to also solve F2 I got a quadratic-time solution that seemed like it could be sped up by using fast convolution; however, I could not immediately see how, and the number of accepted solutions indicated that there is something simpler there. In the end, I got the worst of both worlds: I did not find the simpler solution, but I also did not pull myself together to write down the quadratic formula explicitly on paper. When I did this after the end of the round, I have quickly <a href="https://codeforces.com/contest/1909/submission/238589866">upsolved</a> it using fast convolution since we were summing up a product of various factorials and inverse factorials of amounts that depend either on <i>u</i>, or <i>v</i>, or on <i>u</i>+<i>v</i> (where <i>u</i> and <i>v</i> are the nested loop variables that yield quadratic running time).</div><div><br /></div><div>In problem G, I wasted about half an hour when my initial solution got TLE, even though its complexity was O(<i>n</i>). It constructed a suffix array instead of using the z-function though, so I guess the lesson learned here is that for practical purposes the O(<i>n</i>) suffix array construction should be treated as O(<i>n</i>log<i>n</i>), as I assume the constraints were so high (n=10<sup>7</sup>) precisely to cut off O(<i>n</i>log<i>n</i>) solutions. In the end I was able to replace the suffix arrays usage with z-function.</div><div><br /></div><div>Having read <a href="https://codeforces.com/blog/entry/123584?#comment-1096463">maroonrk's solution</a> for H (spoilers, do not click if you want to try solving yourself first!), I regretted a lot that I did not have time left to try solving it as the problem was amazing. Here is <a href="https://codeforces.com/contest/1909/problem/H">the problem statement</a>: you are given an array of size 3*10<sup>5</sup>. In one operation, you can take any segment of this array of even length, and swap the 1st and 2nd numbers in that segment, the 3rd and 4th numbers, and so on. You need to sort the array in at most 10<sup>6</sup> operations. You do not need to minimize the number of operations. Can you see a way?</div><div><p></p><p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjDa-NIrfvO-fxcgt_iA3NSFKDrgU6xN88vEImO9ccWlvFzGlbvjhXG7jElMwuhKsflBWr_K1zZ1E2WtrATWTwBN-LN-1lSX6ZDqU1v5d3p7kFzZBg_4t9xV2LYnqzAMKloQsXbPUEBlzMXf3cPL73uOOt_RiaMDFE9GAvdB5XPPPXeATyA8rTDu1GW0Xo/s4032/PXL_20230815_123201151.jpg" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="3024" data-original-width="4032" height="480" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjDa-NIrfvO-fxcgt_iA3NSFKDrgU6xN88vEImO9ccWlvFzGlbvjhXG7jElMwuhKsflBWr_K1zZ1E2WtrATWTwBN-LN-1lSX6ZDqU1v5d3p7kFzZBg_4t9xV2LYnqzAMKloQsXbPUEBlzMXf3cPL73uOOt_RiaMDFE9GAvdB5XPPPXeATyA8rTDu1GW0Xo/w640-h480/PXL_20230815_123201151.jpg" width="640" /></a></div>In <a href="https://blog.mitrichev.ch/2023/12/a-three-step-week.html">my previous summary</a>, I have mentioned <a href="https://atcoder.jp/contests/agc065/tasks/agc065_c">an AtCoder problem</a>: you are given up to 100000 positive integers <i>A<sub>i</sub></i>, each up to 10<sup>9</sup>. Your goal is to split each <i>A<sub>i</sub></i> into two non-negative integer parts <i>A<sub>i</sub></i>=<i>B<sub>i</sub></i>+<i>C<sub>i</sub></i> so that there is no way to choose exactly one of <i>B<sub>i</sub></i> or <i>C<sub>i</sub></i> for each <i>i</i> such that the sum of chosen numbers is equal to exactly half of the sum of all <i>A<sub>i</sub></i> (that sum is guaranteed to be even).<p></p><p>When solving this problem, the first observation I made is that it is in fact hard, likely impossible, to check in a reasonable time if a given split into <i>B<sub>i</sub></i> or <i>C<sub>i</sub></i> satisfies the requirements or not, as it requires solving a pretty large instance of the knapsack problem. This may be the reason that the problem does not require to print a certificate, just a Yes/No answer.</p><p>This naturally leads to the following question: for which splits into <i>B<sub>i</sub></i> or <i>C<sub>i</sub></i> we can reasonably easily prove that achieving exactly half is impossible? To make such proof easier, it makes sense to split all even numbers exactly in half such that <i>B<sub>i</sub></i>=<i>C<sub>i</sub></i>: then we know for sure those numbers' contribution to the sum, and there are fewer possibilities to check. However, if all numbers are even and we do this for all numbers, then it would be possible to achieve exactly half of the total sum (in fact, it would be impossible to achieve anything else :)). But then we can do this even split for all numbers except one, and for one number (say, <i>A</i><sub>1</sub>) we set <i>B</i><sub>1</sub>=0 and <i>C</i><sub>1</sub>=<i>A</i><sub>1</sub>. Then we get exactly half from all other numbers, but if we choose <i>B</i><sub>1</sub> then the sum is slightly less than exactly half of the total, and if we choose <i>C</i><sub>1</sub> it is greater. Therefore we have solved the problem for the case where all <i>A</i><sub><i>i</i></sub> are even (the answer is always Yes).</p><p>What can we do about odd numbers? They cannot be split exactly in half, but we can try to build on the above construction: let us split all odd numbers almost in half, such that <i>B<sub>i</sub></i>+1=<i>C<sub>i</sub></i>, and split one number, the biggest one (assume we reorder the numbers and it is <i>A</i><sub>1</sub>), as <i>B</i><sub>1</sub>=0 and <i>C</i><sub>1</sub>=<i>A</i><sub>1</sub>. Now if the amount of odd numbers is less than <i>A</i><sub>1</sub>, then we still cannot achieve exactly half, because if we choose <i>B</i><sub>1</sub>, even taking <i>C<sub>i</sub></i> from all odd numbers will still leave us short of half of the total, and if we choose <i>C</i><sub>1</sub>, we overshoot. There is a slight complication that happens when <i>A</i><sub>1</sub> is odd, as then we should not count it towards the amount of odd numbers we split almost in half; however, since the total amount of odd numbers is always even (because the sum is even), this does not affect our comparison and we can still compare if <i>A</i><sub>1</sub> is strictly greater than the total amount of odd numbers.</p><p>This criterion was my first submission, however, it got WA. As I did not have any immediate ideas for other situations where achieving exactly half is clearly impossible, I implemented a brute force solution and stress-tested it against this one. The smallest counterexample it produced was: 1, 3, 3, 3. In this case we set all <i>B</i><sub><i>i</i></sub>=0 and <i>C</i><sub><i>i</i></sub>=<i>A</i><sub><i>i</i></sub> and there is no way to achieve the required sum of 5 from some subset of 1, 3, 3, 3. The first idea after seeing this was that divisbility by 3 is somehow a factor; however, quite quickly I realized that we can slightly generalize the construction from the first submission above: we take all odd numbers, sort them, and split them into two parts of odd size. In the part containing the smaller numbers, we set <i>B<sub>i</sub></i>+1=<i>C<sub>i</sub></i>, and in the part containing the bigger numbers, we set <i>B<sub>i</sub></i>+<i>D</i>=<i>C<sub>i</sub></i>, where <i>D</i> is the smallest of those bigger numbers. Now if the size of the part with smaller numbers is less than <i>D</i>, then we always fall short of half of the total if we choose more <i>B<sub>i</sub></i>'s than <i>C<sub>i</sub></i>'s in the part with the bigger odd numbers, and we always overshoot otherwise.</p><p>This solution passed the stress-test against the brute force for small constraints, therefore I submitted it and it got accepted. I did not bother proving it formally since the stress-test was proof enough, but the intuition is somewhat clear: now we say No only if there are at least two odd numbers up to 1, at least four odd numbers up to 3, at least six odd numbers up to 5, and so on until we run out of odd numbers, and the total amount of odd numbers is at least the biggest number. I did not write down all details, but the following method likely works to achieve exactly half in this case: we first go through all even numbers, and then through all odd numbers in decreasing order. If the sum we accumulated so far is bigger than half of total of the numbers processed so far, we take the smaller one of <i>B<sub>i</sub></i> and <i>C<sub>i</sub></i>, otherwise the bigger one. We can now prove by induction that after processing all odd numbers except the <i>x </i>smallest ones, the current sum differs from half of all processed numbers by at most (<i>x</i>+1)/2, which means that in the end it is exactly equal.</p><p>Thanks for reading, and check back next week!</p></div>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com2tag:blogger.com,1999:blog-1953325079793449971.post-75445716177381680542023-12-17T18:26:00.002+01:002023-12-17T18:30:54.473+01:00A three-step week<p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjiJtH3huPM11pC1u64wHm4dC0vwsba3G0utarishdWzDp5ey7van9HF3-Wzb2ZC6SjrHe8jelGQtnNvfXeiatgQDSEk6oK46HIVfgrHQcJfcTNkJB_piJVs-EAmtYc-v2CfKty3oBze5hZ75vs84d_o6UXRDITS0_iYXF169NgPRyY6Cj6HIHYVngfBeg/s1924/ucup2r13top5.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="663" data-original-width="1924" height="220" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjiJtH3huPM11pC1u64wHm4dC0vwsba3G0utarishdWzDp5ey7van9HF3-Wzb2ZC6SjrHe8jelGQtnNvfXeiatgQDSEk6oK46HIVfgrHQcJfcTNkJB_piJVs-EAmtYc-v2CfKty3oBze5hZ75vs84d_o6UXRDITS0_iYXF169NgPRyY6Cj6HIHYVngfBeg/w640-h220/ucup2r13top5.png" width="640" /></a></div>The 2nd Universal Cup Stage 13: Shenyang took place last week, but its results were not public when I wrote the last summary (<a href="https://ucup.ac/files/ucup/statements/statements-2-13.pdf">problems</a>, <a href="https://ucup.ac/scoreboard/36">results</a>, top 5 on the left, <a href="https://ucup.ac/files/ucup/tutorials/tutorials-2-13.pdf">analysis</a>). The first two places in this round coincide with the first two places in the overall Universal Cup standings, and they were also the only teams to solve 12 problems. So I guess one could say this round went exactly as expected :) Congratulations to USA1 and HoMaMaOvO!<p></p><p>This round used the problemset from an ICPC regional contest, and the best team from that contest is only on place 23 in the scoreboard with 9 problems solved, which underscores how the Univesal Cup gathers the best teams in the world.</p><p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhCwXhyEG6Gh5Z5ICH9wOO4jJZlGY8SE4xTz6BHtNaSoo47IVS4K55-MOCG1du8ZPU5rgWtgc_gS6bltGSI8Ee0TvXWhEotUOO6OLMcrJ98SdEdi8445WtGXZiAZTKyvEC6Rky5DJZds02wZij2OsDctCwfP_gK37s_ngxNezDoZWYaMvKEzTmGR-IZ45M/s1856/ucup2r14top5.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="643" data-original-width="1856" height="222" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhCwXhyEG6Gh5Z5ICH9wOO4jJZlGY8SE4xTz6BHtNaSoo47IVS4K55-MOCG1du8ZPU5rgWtgc_gS6bltGSI8Ee0TvXWhEotUOO6OLMcrJ98SdEdi8445WtGXZiAZTKyvEC6Rky5DJZds02wZij2OsDctCwfP_gK37s_ngxNezDoZWYaMvKEzTmGR-IZ45M/w640-h222/ucup2r14top5.png" width="640" /></a></div>The 2nd Universal Cup Stage 14: Southeastern Europe took place this Saturday (<a href="https://ucup.ac/files/ucup/statements/statements-2-14.pdf">problems</a>, <a href="https://ucup.ac/scoreboard/37">results</a>, top 5 on the left, <a href="https://ucup.ac/rating?season=2">overall standings</a>, <a href="https://ucup.ac/files/ucup/tutorials/tutorials-2-14.pdf">analysis</a>). Team HoMaMaOvO got the second place just like last week, but the winner was different: team 03 Slimes got 11 problems solved at just 1:43 into the contest, and therefore had all the time in the world to solve the 12th. Congratulations on the win!<p></p><p>This round has also used the problemset from an ICPC regional contest, but this time the best team from the onsite round placed a bit worse — at place 36, with 9 problems solved.</p><p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjdAwYR2Rtr3y7OIzUHpdqYLoNJXcbq_5z6kC-QIUiISrAkuIpBPw8748eoOAd6rOdxHLPw-D-dHofriGTOghKFkNVtP54aYigRLRssi2N-UMqe7h8I4Hi_kPgHd7T3ZP_v_0WDh9CaOrDqfjlaVDgZvZz9FRoQrX_JnApkhajJjxHmYil3ALr_ku1CTmA/s1002/agc065top5.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="422" data-original-width="1002" height="270" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjdAwYR2Rtr3y7OIzUHpdqYLoNJXcbq_5z6kC-QIUiISrAkuIpBPw8748eoOAd6rOdxHLPw-D-dHofriGTOghKFkNVtP54aYigRLRssi2N-UMqe7h8I4Hi_kPgHd7T3ZP_v_0WDh9CaOrDqfjlaVDgZvZz9FRoQrX_JnApkhajJjxHmYil3ALr_ku1CTmA/w640-h270/agc065top5.png" width="640" /></a></div>Finally, AtCoder Grand Contest 065 wrapped up this week (<a href="https://atcoder.jp/contests/agc065/tasks">problems</a>, <a href="https://atcoder.jp/contests/agc065/standings">results</a>, top 5 on the left, <a href="https://clist.by/standings/atcoder-race-ranking-2023-41247385/">overall standings</a>, <a href="https://atcoder.jp/contests/agc065/editorial">analysis</a>). There was a huge gap in difficulty and in scores between the first four problems and the last two, therefore in this round it could actually be a very good strategy to start with one of the two difficult problems to be able to properly estimate how many easier problems one can squeeze in the remaining time. mulgokizary and newbiedmy executed this strategy successfully to place 3rd and 4th, well done! Of course, it's even better if one can solve the four easier problems and one difficult one, as zhoukangyang and ecnerwala did :) Congratulations to them as well!<div><br /></div><div>The round went quite well for me, in a large part thanks to the fact that I was able to quickly find <a href="https://math.stackexchange.com/questions/555271/k-non-intersecting-diagonals-in-a-polygon">this page</a> for problem D, and <a href="https://cdm.ucalgary.ca/article/view/62279">this paper</a> for problem F. However, while the implementation for D is pretty straightforward with the linked formula, one still needs to make a few more steps on top of the linked paper to get F, and I managed to get stuck in those steps: by the end of the round, my solution returned 125405280 instead of 128792160 for n=10 :(</div><div><br /></div><div>While solving problem C in this round, I followed a quite typical pattern, at least for AtCoder problems: come up with a reasonably simple sufficient but not clearly necessary condition, implement it, submit, get WA, implement a stupid solution and run a stress test, find a case where the solutions differ, come with another, also reasonably simple sufficient but not clearly necessary condition, implement it, run stress test with larger cases, find a bug in the implementation, fix it, pass stress test, submit, get AC :) I think seeing the diffs found by stress test was instrumental for me to discover the correct solution idea. For those who solved this problem during the round or want to upsolve now, were you able to do it without the stress test?</div><div><br /></div><div>Here's <a href="https://atcoder.jp/contests/agc065/tasks/agc065_c">that problem's statement</a>, aptly titled "Avoid Half Sum": you are given up to 100000 positive integers <i>A<sub>i</sub></i>, each up to 10<sup>9</sup>. Your goal is to split each <i>A<sub>i</sub></i> into two non-negative integer parts <i>A<sub>i</sub></i>=<i>B<sub>i</sub></i>+<i>C<sub>i</sub></i> so that there is no way to choose exactly one of <i>B<sub>i</sub></i> or <i>C<sub>i</sub></i> for each <i>i</i> such that the sum of chosen numbers is equal to exactly half of the sum of all <i>A<sub>i</sub></i>.</div><div><p></p><p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgVX-5HReUnAL0ONUH9OBkb9HTyzm8adZpfKCG94ze4efPO-54_SZxHyS0MaQvufGhwN3ILoxqO3KUsdxsRM-QS__qqjwXsr_e827WJlhVsFmj-y-MUTb0IIFJyq4oSIKuJRtDu7_sq8Jbd7CWUPXdvniKqmgCSkcjt35dh3C01tOSd2g4SPsmgiD0I1gk/s1108/atcoder2023top14.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="924" data-original-width="1108" height="534" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgVX-5HReUnAL0ONUH9OBkb9HTyzm8adZpfKCG94ze4efPO-54_SZxHyS0MaQvufGhwN3ILoxqO3KUsdxsRM-QS__qqjwXsr_e827WJlhVsFmj-y-MUTb0IIFJyq4oSIKuJRtDu7_sq8Jbd7CWUPXdvniKqmgCSkcjt35dh3C01tOSd2g4SPsmgiD0I1gk/w640-h534/atcoder2023top14.png" width="640" /></a></div>This round has seemingly concluded (even though a man can hope: maybe one more AGC in 2023 will pop up as a Christmas present? :)) the <a href="https://clist.by/standings/atcoder-race-ranking-2023-41247385/">AtCoder Race Ranking 2023</a> (top 14 on the left). Therefore it seems that I have barely missed qualifying to the World Tour Finals in Japan. Amazingly, the cutoff for the top 12 did not change at all in this round, as Um_nik has kept his final qualifying place while being outside of the top 30 in the round. It means that even the fourth place would have been enough for me to qualify. Not making a wrong attempt on C (or convincing Gennady to skip this round to increase my chances) would have gotten me the fifth place, but to get fourth I really had to solve either E or F. Well, I will try harder next year, and huge congratulations to the 12 finalists!<p></p><p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhYLT6Qf_qlZBukXjJ2rudTFAx9RWKnQu7RbNHghAUEG829VIGkXWuPhScm6HReFP0G4xvwO-2XLYB4hQHqqx7x9k77YQW6zRtUZi0israDh8U1evmJvIZcoodGNMg9WLNUwqqFR9uq9y1wat__FXI6f_zFC9gEZg0W6X0IoIlJoQ34CdwY3lqEQwp2VHk/s2170/PXL_20230814_151804795-EDIT.jpg" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1621" data-original-width="2170" height="478" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhYLT6Qf_qlZBukXjJ2rudTFAx9RWKnQu7RbNHghAUEG829VIGkXWuPhScm6HReFP0G4xvwO-2XLYB4hQHqqx7x9k77YQW6zRtUZi0israDh8U1evmJvIZcoodGNMg9WLNUwqqFR9uq9y1wat__FXI6f_zFC9gEZg0W6X0IoIlJoQ34CdwY3lqEQwp2VHk/w640-h478/PXL_20230814_151804795-EDIT.jpg" width="640" /></a></div>In <a href="https://blog.mitrichev.ch/2023/12/a-17107-week.html">my previous summary</a> I have mentioned <a href="https://www.facebook.com/codingcompetitions/hacker-cup/2023/final-round/problems/E">a Hacker Cup problem</a>: two players are playing a nim-like game, starting with two piles of stones. In one move, a player first chooses one of the remaining non-empty piles, let's say this pile has <i>k</i> stones. Then they can take between <i>A<sub>k</sub></i> and <i>B<sub>k</sub></i> stones from this pile, and they also must create a new pile with <i>C<sub>k</sub></i> stones (1 <= <i>A<sub>k</sub></i> <= <i>B<sub>k</sub></i> <= <i>k</i>, 0 <= <i>C<sub>k</sub></i> < <i>k</i>). Since 1 <= <i>A<sub>k</sub></i> and <i>C<sub>k</sub></i> < <i>k</i>, this game will eventually terminate, and the player unable to make a move loses the game. Your goal is to find for each size (between 1 and <i>n</i>) of the first of the two initial piles the smallest size of the second initial pile that leads to a losing position, and print the sum of those <i>n</i> sizes. <i>n</i> is up to 2 million.<p></p><p>The first step in solving this problem is pretty straightforward. As the games on each pile are independent, we can use <a href="https://en.wikipedia.org/wiki/Sprague%E2%80%93Grundy_theorem">the Sprague-Grundy theorem</a>, therefore we just need to find the nimber for a pile of size <i>k</i> for each <i>k</i>. Denoting this nimber as <i>N<sub>k</sub></i>, from the game rules we get that <i>N<sub>k</sub></i>=mex(<i>N<sub>i</sub></i>⊕<i>N<sub>C<sub>k</sub></sub></i> over all <i>i</i> between <i>k</i>-<i>B<sub>k</sub></i> and <i>k</i>-<i>A<sub>k</sub></i>).</p><p>So we need some data structure that can find mex on a range, with the added twist that all numbers on the range are first xored with some constant. Finding things on a range is typically done with a segment tree, but to find mex even without the xor-constant complexity would require to propagate a lot of information along the tree.</p><p>The key step to progress further in solving this problem is to actually forget about the ranges for now, and focus on the xor-constant part. Suppose we just have a static set of numbers, and need to answer questions: what is the mex of all those numbers xored with a given constant? In this case it is reasonably clear what to do: we need to determine the mex bit-by-bit from the highest bit to the lowest bit. Suppose we want to find the <i>k</i>-th bit having already found out that the answer is equal to <i>r</i> for bits higher than <i>k</i>, in other words we know that the answer is in range [<i>r</i>,<i>r</i>+2<sup><i>k</i>+1</sup>), and need to tell if it is in range [<i>r</i>,<i>r</i>+2<sup><i>k</i></sup>) or [<i>r</i>+2<sup><i>k</i></sup>,<i>r</i>+2<sup><i>k</i>+1</sup>). Because bitwise xor is applied independently to high and low bits, we simply need to know if there is at least one number missing in our set from the range [<i>r</i>⊕<i>s</i>,<i>r</i>⊕<i>s</i>+2<sup><i>k</i></sup>), where <i>s</i> is the bits <i>k</i> and higher from our constant. And finding if a number is missing on a range can be done with a balanced tree or again with a segment tree. Note that even though we forgot about the ranges, the ranges have reappeared: instead of ranges on <i>k</i>, we now have ranges on <i>N<sub>k</sub></i>.</p><p>Now let us reintroduce the ranges on <i>k</i>. First, let us consider only half-ranges: suppose <i>A<sub>k</sub></i>=1 for all k. Then in the above bit-by-bit solution we need to find out if there is at least one number missing from a given range on a suffix of <i>N<sub>k</sub></i>. This can be done by modifying the segment tree approach: let us use a segment tree that, instead of just remembering if a certain number has appeared or not, will remember is rightmost appearance. Then we can find the minimum of those appearances on the needed range, and compare it to <i>k</i>-<i>B<sub>k</sub></i>. In fact, since all ranges of nimbers that we query are aligned with the powers of two, each query will exactly correspond to one of the nodes in the segment tree, and therefore can be done in O(1) (but an update still needs to touch O(log(<i>n</i>)) nodes).</p><p>What to do about the other side of the range on <i>k</i>, in other words when <i>A<sub>k</sub></i>>1? Here comes another relatively standard trick: since we only look at indices up to <i>k</i>-<i>A<sub>k</sub></i>, we could have executed this query when we were processing <i>k</i>'=<i>k</i>-<i>A<sub>k</sub></i>+1, and at that moment this query would be a half-range with only the left boundary, which we can handle using the procedure described above. So we would like to already compute <i>N<sub>k</sub></i> when processing <i>k</i>'=<i>k</i>-<i>A<sub>k</sub></i>+1, however we cannot do that since we might not know <i>N<sub>C<sub>k</sub></sub></i> at that point yet if <i>C<sub>k</sub></i>><i>k</i>-<i>A<sub>k</sub></i>. This naturally points us towards <i>persistent</i> data structures: we can modify our segment tree to be able to not just query what <i>is</i> the minimum on a range, but to also to query what <i>was</i> the minimum on a range at any previous state of the data structure, in particular when <i>k</i>'=<i>k</i>-<i>A<sub>k</sub></i>+1.</p><p>There are several standard ways to do it, one of which is to actually store a tree as a set of immutable nodes with each node pointing to children, and every time we need to change the value in a node we would actually clone the node with the new value instead, together with its path to the root. This way we only create O(log(<i>n</i>)) additional nodes per operation, so the total memory usage is still acceptable at O(<i>n</i>*log(<i>n</i>)), but now since all nodes are immutable we can simply query any old root of the tree to get the minimum on a range at a point in the past.</p><p>I think this problem is educational since it has three steps of "unwrapping the present", as we first solve an easier version of the problem and then gradually add back the full complexity. Each particular step is more or less a well-known trick, but one still needs to find which simplifcation of the problem to tackle first, and for that it is vital for those well-known tricks to really be "in RAM", as well as to have a good intuition about what is not solvable at all, so that one can explore many directions and find the correct three-step path. If one has to think for half an hour to solve each particular step, there is really no chance to find the correct sequence of three steps in time, as there will necessarily be other promising directions that won't lead anywhere but waste a lot of solving time.</p><p>Thanks for reading, and check back next week!</p></div>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com0tag:blogger.com,1999:blog-1953325079793449971.post-42581990678784647162023-12-10T17:33:00.001+01:002023-12-10T17:33:58.265+01:00A 17107 week<p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiS6H7Cyb2YI2vi5R2duRh-f31aWaZ0vW3BObySg62HRvDtkp_warR1po2ony89NZ9tTq3gTA7VJruugGCDmGehHGLC0xndACxVLICAXB4ifPA0YC5Mv1mtcuMS2KvzIOwJNkRYyW8PqMolaX4GM_eWiCI_7zqb-bzfJfTWSA6tyUrme3w-7Yd90hpM7OI/s954/srm851top5.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="145" data-original-width="954" height="97" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiS6H7Cyb2YI2vi5R2duRh-f31aWaZ0vW3BObySg62HRvDtkp_warR1po2ony89NZ9tTq3gTA7VJruugGCDmGehHGLC0xndACxVLICAXB4ifPA0YC5Mv1mtcuMS2KvzIOwJNkRYyW8PqMolaX4GM_eWiCI_7zqb-bzfJfTWSA6tyUrme3w-7Yd90hpM7OI/w640-h97/srm851top5.png" width="640" /></a></div>TopCoder SRM 851 was their first round after a long while (<a href="https://community.topcoder.com/stat?c=round_overview&rd=19718">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=19718&dn=1&sq=Round_Statistics_Data&sc=10&sd=desc">results</a>, top 5 on the left). Only three contestants got the 1000 right. Out of those, snuke had a small lead after the coding phase despite a resubmit on the 1000, and he managed to extend the lead with an active challenge phase (+2-2). Well done!<p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiXy-hWDbjGSM1w6XChXu5H3bNPWZ3sqAXzrPuMDj6B25L3oDgrIW2Gj8H-ljDqXVMXM8_cWaF6O7VAeS8nsyzk5AQCH9oVX9wywwH7zakh0PApw-hYPPygNLhIUFGbbgynzIhEz137LGFXnwcaifE8FWcb2ypavtdcCF89Uaf5HWwChMN78tJ2vJ0lPx4/s1369/fbhc2023top5.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="281" data-original-width="1369" height="132" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiXy-hWDbjGSM1w6XChXu5H3bNPWZ3sqAXzrPuMDj6B25L3oDgrIW2Gj8H-ljDqXVMXM8_cWaF6O7VAeS8nsyzk5AQCH9oVX9wywwH7zakh0PApw-hYPPygNLhIUFGbbgynzIhEz137LGFXnwcaifE8FWcb2ypavtdcCF89Uaf5HWwChMN78tJ2vJ0lPx4/w640-h132/fbhc2023top5.png" width="640" /></a></div>Meta Hacker Cup 2023 Final Round was the last but also the most important event of the week (<a href="https://www.facebook.com/codingcompetitions/hacker-cup/2023/final-round/problems/A2">problems</a>, <a href="https://www.facebook.com/codingcompetitions/hacker-cup/2023/final-round/scoreboard">results</a>, top 5 on the left, <a href="https://www.facebook.com/codingcompetitions/hacker-cup/2023/final-round/solutions">analysis</a>). The scoreboard was quite exciting to watch during the round, as different people went for completely different orders of tackling the problems (and also for <a href="https://codeforces.com/blog/entry/123134?#comment-1092217">creative ways</a> to avoid thinking too much about cacti!). The order did not matter in the end as only Gennady managed to solve all problems, which was actually necessary for him to claim the first place from Benq who had a better penalty time. Congratulations Gennady on winning <a href="https://cphof.org/profile/fhc:2363294937300653">the 5th Hacker Cup title</a>!<p></p><p>As I saw the point values for the problems, the optimal strategy seemed obvious: <a href="https://www.facebook.com/codingcompetitions/hacker-cup/2023/final-round/problems/A2">problem A</a> with its 19 total points effectively has weight 2 for the penalty purposes, so assuming the 19 points accurately reflect its difficulty, it is much better to solve it in the beginning. Combine this with the fact that it was a constructive problem, the type I typically enjoy solving, and you can guess what I did for the first 2 hours of the 4-hour round :) I think the main reason it took so long was that I was constantly quite close to a working solution, and therefore it always seemed that I need just one more small trick, so I went for small tricks instead of rethinking the approach. I ended up accumulating a lot of those small tricks: in addition to <i>k</i>->2<i>k</i> and <i>k</i>->2<i>k</i>+1 steps that everyone likely used, my solution also used <i>k</i>->4<i>k</i>-1, <i>k</i>->8<i>k</i>-1, ... (therefore using the <i>A</i>=<i>A</i>-1 primitive that the official analysis dismissed so easily :), and also <i>k</i>->3<i>k</i> and <i>k</i>->3<i>k</i>+2; to accommodate such a wide variety of possible steps, I chose the cells to include into the labyrinth outside of the main path dynamically based on the type of the next primitive I needed.</p><p>Even though spending 2 hours on this problem ruined my (mostly theoretical anyway) chances for a good result, I am still grateful to the organizers for not setting the tightest possible constraints and therefore allowing alternative approaches like mine.</p><p>One of the problems that I could not crack in the remaining time even though I was very close, and that I think is quite educational despite having a very ugly statement, is <a href="https://www.facebook.com/codingcompetitions/hacker-cup/2023/final-round/problems/E">Problem E</a>: two players are playing a nim-like game, starting with two piles of stones. In one move, a player first chooses one of the remaining non-empty piles, let's say this pile has <i>k</i> stones. Then they can take between <i>A<sub>k</sub></i> and <i>B<sub>k</sub></i> stones from this pile, and they also must create a new pile with <i>C<sub>k</sub></i> stones (1 <= <i>A<sub>k</sub></i> <= <i>B<sub>k</sub></i> <= <i>k</i>, 0 <= <i>C<sub>k</sub></i> < <i>k</i>). Since 1 <= <i>A<sub>k</sub></i> and <i>C<sub>k</sub></i> < <i>k</i>, this game will eventually terminate, and the player unable to make a move loses the game. Your goal is to find for each size (between 1 and <i>n</i>) of the first of the two initial piles the smallest size of the second initial pile that leads to a losing position, and print the sum of those <i>n</i> sizes. <i>n</i> is up to 2 million.</p><p>Thanks for reading, and check back next week for the results of the most important round of December, <a href="https://atcoder.jp/contests/agc065">the last AGC</a> of the year! Thanks to Um_nik now I know that 12 people (up from 8) <a href="https://clist.by/standings/atcoder-race-ranking-2023-41247385/">qualify to the WTF</a>, which means that even the second place will probably do ;)</p>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com1tag:blogger.com,1999:blog-1953325079793449971.post-5119617114278938372023-09-23T19:51:00.001+02:002023-09-23T19:51:41.137+02:00A MEX week<p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEggHvDuX6Uywl1guAeqdqQzMaPffcOZ7hnif4NAcoDw28Mw9eAvokN1GTU537hWBFSFoxOqHUANIOTJrgbwddQUXgf50pz_yfrAWs_Fu2RfEDBO8id9vt7a7oUlkBrmaQVQyE_NVwYhuJRGlUGllG-UMTTEriVHMuzyfqWN5yVT3lcZ4CiTA6gT_s3qboc/s1322/cfton6top5.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="344" data-original-width="1322" height="166" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEggHvDuX6Uywl1guAeqdqQzMaPffcOZ7hnif4NAcoDw28Mw9eAvokN1GTU537hWBFSFoxOqHUANIOTJrgbwddQUXgf50pz_yfrAWs_Fu2RfEDBO8id9vt7a7oUlkBrmaQVQyE_NVwYhuJRGlUGllG-UMTTEriVHMuzyfqWN5yVT3lcZ4CiTA6gT_s3qboc/w640-h166/cfton6top5.png" width="640" /></a></div>Codeforces CodeTON Round 6 was the main event of the last two weeks (<a href="https://codeforces.com/contest/1870">problems</a>, <a href="https://codeforces.com/contest/1870/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/120524">analysis</a>, <a href="https://codeforces.com/blog/entry/120458">discussion</a>). orzdevinwang solved 8 problems while everybody else got at most 7 and I barely got 6, and earned a well-deserved first place. Congratulations!<div><br /></div><div>While I could more or less keep up with the leaders on the first 4 easier problems, I was not able to solve E at all and spent a lot of time implementing, speeding up and debugging F, even though the algorithmic solution was clear to me reasonably quickly. On the other hand, I could solve G in 22 minutes, which seems to be the fastest among the top scorers, but it was already too late to catch up :) I guess that's one more lesson to read all problems, at least when one is stuck trying to solve the next problem by difficulty.</div><div><br /></div><div>Here is <a href="https://codeforces.com/contest/1870/problem/F">problem F</a> that has caused me so much implementation pain: we write down all integers between 1 and <i>n</i> as strings in base <i>k</i> (assuming we have characters for all digits between 0 and <i>k</i>-1). Now we sort those strings lexicographically, for example the first few would typically be 1, 10 (=<i>k</i>), 100 (=<i>k</i><sup>2</sup>), ... How many numbers are in the same position in this sorted order as in the order where we just sort by number? <i>n</i> and <i>k</i> are up to 10<sup>18</sup>, and you have to solve 1000 testcases in 3 seconds.</div><div><p></p><p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhj4ueArLN6hqITOE4AZoCBI8_VpCAkJC_0ZLeQ1Q8KZClXWl8tylRfxrKpA8HFx8PumTbSswRC281Ea2FRQ3ifEZWMnL-bYE6PMbM394Z_FJuuf6eYjomAY69uuj3pYtY3wIeSXI55KxXTA9r4Ffwug3DFvNhrUsLd-nk_ZHQYJgv5MH2HTxufcO_qCQo/s4032/PXL_20230409_152256094.jpg" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="2716" data-original-width="4032" height="432" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhj4ueArLN6hqITOE4AZoCBI8_VpCAkJC_0ZLeQ1Q8KZClXWl8tylRfxrKpA8HFx8PumTbSswRC281Ea2FRQ3ifEZWMnL-bYE6PMbM394Z_FJuuf6eYjomAY69uuj3pYtY3wIeSXI55KxXTA9r4Ffwug3DFvNhrUsLd-nk_ZHQYJgv5MH2HTxufcO_qCQo/w640-h432/PXL_20230409_152256094.jpg" width="640" /></a></div>In <a href="https://blog.mitrichev.ch/2023/09/a-dual-week.html">my previous summary</a>, I've highlighted <a href="https://atcoder.jp/contests/wtf22-day2/tasks/wtf22_day2_a">one of the AWTF problems</a>: <i>n</i> people are standing in a row, each with either a red or a blue hat on. Each person can see the hat colors of the people in front of them (with smaller position numbers), but not their own hat color or the hat colors of the people behind them. Each person also knows the total number of red and blue hats. Then, the following process happens in rounds: in one round, every person who can already deduce their hat color, declare that they have done so (they do not declare the color itself). If multiple people can deduce it in the same round, they declare it simultaneously without hearing each other first. In the next round, on the other hand, people can already use the information of who has declared in the previous round to potentally make additional deductions themselves. Which people will eventually declare, and which will still be in the dark about their hat color even after an large number of rounds?<p></p></div><div>The key step in such problems about logic is to figure out the correct formalization. What exactly does it mean to be able to deduce one's hat color using the information of who has declared in prevoius rounds? Or in other words, we can start by finding a solution that runs with any time complexity, but that is correct. When I was solving this problem, I've only thought and implemented such solution for a stress test after my approach did not pass the samples, which in hindsight was way too late.</div><div><br /></div><div>Here is the formalization: there are C(<i>n</i>,<i>r</i>) possible sequences of hat colors, where <i>r</i> is the globally known number of red hats. After the <i>i</i>-th round, from the point of view of the first person who does not see any hats, some of those sequences are still possible, and some are not (in other words, if the hats did in fact correspond to this sequence, would everybody say what they have said?). This set of possible sequences <i>S<sub>i</sub></i> also clearly defines what all other people are thinking: for each person, the set of possible sequences that is possible from their point of view is equal to the intersection of <i>S<sub>i</sub></i> with the set of sequences that have the correct hat colors for those hats that they see. This sounds trivial when spelled out, but it was actually not that easy to state it for me during the round.</div><div><br /></div><div>Now, what will each person do during the <i>i</i>-th round? They will look at the set of sequences that are still possible from their point of view (given by the intersection mentioned above), and check if their hat color is the same in all of them. If yes, they will declare, otherwise they won't.</div><div><br /></div><div>How to compute <i>S<sub>i</sub></i> given <i>S</i><sub><i>i</i>-1</sub> and the declarations? We need to check the declarations that would have happened for each sequence in <i>S</i><sub><i>i</i>-1</sub> (assuming each person sees some prefix of that sequence), and remove those sequences where this set of declarations does not match one for the real sequence of hats. Once again, this looks very simple, almost trivial, but it was actually far from easy to state concisely.</div><div><br /></div><div>This is how far I've got during the round: I've implemented a slow solution based on the above, and was trying to find some fast heuristic solution that would match it on random inputs. It turns out that this did not lead to a correct solution. Instead, one simply had to speed up the slow solution!</div><div><br /></div><div>One had to notice that after each step, the set <i>S<sub>i </sub></i>can be described by the lists of possible amounts of red hats in each of the prefixes of the sequence. For example, suppose there are 4 red and 3 blue hats in total. The initial set <i>S</i><sub>0<i> </i></sub>can then be described as: empty prefix has 0 red hats; the prefix of length 1 has 0 or 1 red hats; 2 has 0, 1, 2; 3 has 0, 1, 2, 3; 4 has 1, 2, 3, 4; 5 has 2, 3, 4; 6 has 3, 4; and the whole sequence has 4. Every sequence that has 4 red and 3 blue hats satisfies those constraints, and every sequence that satisfies those constraints has 4 red and 3 blue hats.</div><div><br /></div><div>Then suppose during the first round only the last two people have declared that they know the color of their hats. It turns out that the resulting set <i>S<sub>1 </sub></i>can then be described as: empty prefix has 0 red; 1 has 0, 1; 2 has 0, 1, 2; 3 has 1, 2, 3; 4 has 2, 3; 5 has 2, 4; 6 has 3, 4; 7 has 4.</div><div><br /></div><div>More generally, if we describe the prefix of length <i>i</i> having <i>j</i> red hats as (<i>i</i>,<i>j</i>), then the (<i>i</i>+1)-th person will declare if exactly one of (<i>i</i>+1,<i>j</i>) and (<i>i</i>+1,<i>j</i>+1) is still possible, and not declare if both are possible. This criterion allows us to compute the declarations that actually happen, and the same criterion then allows us to eliminate states which contradict those declarations. However, we also need to pay attention to also eliminate states that do not have a possible predecessor (if both (<i>i</i>-1,<i>j</i>-1) and (<i>i</i>-1,<i>j</i>) are eliminated, then (<i>i</i>,<i>j</i>) should be eliminated as well), or a possible successor (if both (<i>i</i>+1,<i>j</i>) and (<i>i</i>+1,<i>j</i>+1) are eliminated, then (<i>i</i>,<i>j</i>) should be eliminated as well). This criterion is also the basis of the inductive proof that <i>S<sub>i</sub></i> can always be represented in the above form.</div><div><br /></div><div>Therefore we can maintain the set of states (<i>i</i>,<i>j</i>) that are still possible after each round, and stop when this set of states stops changing.</div><div><br /></div><div>Thanks for reading, and check back next week!</div>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com0tag:blogger.com,1999:blog-1953325079793449971.post-67701255902123985762023-09-10T21:25:00.001+02:002023-09-10T21:25:33.495+02:00A dual week<p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiXyhVeYxAOsn6WcjeCz9SI-9HUMU9Ln4u5NrQssidrEfVzMm0Rj9Hlib44I_CPn-dTweZoEKorOkuDqRP9-bbMuUPSKha4Pl69pAyhy-pHfK2X3mnfFm3CCQ8AuLn6ru5N__SDyyYzLxUfzon93ytdWtQ5SeC_KbVnwrj-KGX1KmfTE-x_qJoBEwBsOuk/s768/404061544333293c1c25d46185ca7e888e71e008.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="432" data-original-width="768" height="360" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiXyhVeYxAOsn6WcjeCz9SI-9HUMU9Ln4u5NrQssidrEfVzMm0Rj9Hlib44I_CPn-dTweZoEKorOkuDqRP9-bbMuUPSKha4Pl69pAyhy-pHfK2X3mnfFm3CCQ8AuLn6ru5N__SDyyYzLxUfzon93ytdWtQ5SeC_KbVnwrj-KGX1KmfTE-x_qJoBEwBsOuk/w640-h360/404061544333293c1c25d46185ca7e888e71e008.png" width="640" /></a></div>I have previously posted all the links to the AWTF onsite contests (<a href="https://blog.mitrichev.ch/2023/09/atfw22-day-1.html">day 1</a>, <a href="https://blog.mitrichev.ch/2023/09/awtf22-day-2.html">day 2</a>, <a href="https://codeforces.com/blog/entry/120126?#comment-1066734">thanks</a> jonathanirvings for the screenshot!), so let us talk about the problems now. I have only solved a few of them, for the remaining ones I have either got the solution from other competitors or read the editorial.<div><br /></div><div>On the first day, the easiest <a href="https://atcoder.jp/contests/wtf22-day1/tasks/wtf22_day1_a">problem A</a> "Save the monsters", similar to many game problems, required one to consider possible good strategies for both players until you find two that achieve the same score, thus proving that it is the answer. I have made a bug in my initial submit and therefore assumed that I had a logical issue and the approach does not work, but instead it was just a coding mistake.</div><div><br /></div><div>The key to solving <a href="https://atcoder.jp/contests/wtf22-day1/tasks/wtf22_day1_b">problem B</a> "Non-Overlapping Swaps" was the idea that if we swap elements in positions 1 and 2, then this swap most likely does not contradict the swaps before and after, so we can use this to divide the entire process into two recursive parts with this swap in the middle. There were still details to figure out as "most likely" does not mean "for sure". This idea did not occur to me unfortunately. I did examine swapping the first two positions as the first move and then doing two independent processes for the two resulting cycles, but it was not clear how to transition from one to the other, and in fact I have found a small counterexample when doing such first move leads to inability to finish in time. I did examine other promising ideas, for example I've noticed that if we have overlapping swaps with a common end, we can always replace them with non-overlapping ones with the same effect, for example swapping positions (a,c) then (b,c) with a<b<c is equivalent to first swapping (b,c) then (a,b). Therefore I was trying to construct some kind of iterative process that gradually removes overlaps.</div><div><br /></div><div>I've spent most of the time on <a href="https://atcoder.jp/contests/wtf22-day1/tasks/wtf22_day1_c">problem C</a> "Shrink the Tree". While I could make progress by finding a canonical representation for a tree, I did not have the key idea from the editorial that we should then switch to looking at the problem from the other side: thinking what are the obvious criteria for us to be able to collapse a given forest, and when are they not enough, potentially using a stress test to come up with new criteria. The approach of moving from two sides is similar to problem A, and will actually appear many more times in this problemset. One could also say that thinking from the other side makes an implicit assumption that the problem is beautiful: that the real criteria will be easy to state. Otherwise trying to conjure them up from the air would be much less promising than the "minimal representation for a forest" approach.</div><div><br /></div><div>Solving <a href="https://atcoder.jp/contests/wtf22-day1/tasks/wtf22_day1_d">problem D</a> "Welcome to Tokyo!" required doing three things in sequence: applying the trick from Aliens, then looking at the dual problem for a linear program, and finally noticing that solving many instances of that problem with a varying parameter can be done efficiently. My issue was that after applying the trick from Aliens, which I of course considered, we seem to have made the problem more difficult than it was originally, as because of a different party cost we'd have to redo things from scratch every time, and therefore be at least quadratic. Therefore I have discarded this direction as a dead end.</div><div><br /></div><div>Finally (for day 1), solving <a href="https://atcoder.jp/contests/wtf22-day1/tasks/wtf22_day1_e">problem E</a> "Sort A[i]-i" required noticing some tricky combinatorial identities. I have not spent much time on this problem because I expected the solution to involve heavy manipulations with generating functions, which I am not very good at. It turns out the generating functions were actually only needed to prove the identities, and therefore could probably be avoided completely. To be honest, I am not sure how feasible it was to find those identities in another way, maybe hos_lyric can share the solving process?</div><div><br /></div><div>I'd like to give the readers a week to think about second day's <a href="https://atcoder.jp/contests/wtf22-day2/tasks/wtf22_day2_a">problem A</a> "Hat Puzzle", so I will just share the statement for now: <i>n</i> people are standing in a row, each with either a red or a blue hat on. Each person can see the hat colors of the people in front of them (with smaller position numbers), but not their own hat color or the hat colors of the people behind them. Each person also knows the total number of red and blue hats. Then, the following process happens in rounds: in one round, every person who can already deduce their hat color, declare that they have done so (they do not declare the color itself). If multiple people can deduce it in the same round, they declare it simultaneously without hearing each other first. In the next round, on the other hand, people can already use the information of who has declared in the previous round to potentally make additional deductions themselves. Which people will eventually declare, and which will still be in the dark about their hat color even after an large number of rounds?</div><div><br /></div><div>Solving <a href="https://atcoder.jp/contests/wtf22-day2/tasks/wtf22_day2_b">problem B</a> "The Greatest Two" was once again reliant on "assume the problem is beautiful" or "come up with a bound and then assume/prove it is tight" approach: the key trick was to say that for every number we have a range of possible positions, and that those ranges were more or less independent. Simplifying the problem like this makes the solution a straightforward, if a bit tricky, implementation (it took me ~1.5 hours to implement after having this idea I think), but it was not at all obvious to me that this framework is correct at all, even though it can be proven by induction after the fact, so I just took a leap of faith.</div><div><br /></div><div>Similarly, the solution for <a href="https://atcoder.jp/contests/wtf22-day2/tasks/wtf22_day2_c">problem C</a> "Jewel Pairs" seemed to involve two steps where one comes up with a reasonably simple bound and assumes/proves it: first the description of the matching criteria (from the words "Focusing on the form of the mincut" in <a href="https://atcoder.jp/contests/wtf22-day2/editorial/7110">the editorial</a>; those words also mean that it might be able to deduce this form analytically instead of going "from the other side", but I did not try doing so myself as I was focusing on other problems), and then the criteria for dealing with the colors 2<i>f</i>(<i>c</i>)<=<i>A</i>-<i>B</i>.</div><div><br /></div><div>The key to solving <a href="https://atcoder.jp/contests/wtf22-day2/tasks/wtf22_day2_d">problem D</a> "Cat Jumps" was finding a way to decompose the overall construction into building blocks that can be combined arbitrarily, so that we can use dynamic programming (or just multiplication) to compute the answer. This is a common theme in many counting problems, but even after reading the editorial I had no idea how to actually come up with the decomposition in this problem. It does not look that we can go from the other side in this case ("What could we reasonably compute with DP for the given constraints?"), and the decomposition itself is too complex to just appear out of nowhere. I did not think much about this problem during the round.</div><div><br /></div><div>Finally, <a href="https://atcoder.jp/contests/wtf22-day2/tasks/wtf22_day2_e">problem E</a> "Adjacent Xor Game" was once again solved from the other side: one had to hypothesize or prove that all that matters in the end is how many times each bit is flipped (where going from <i>y</i><sub>1</sub> to <i>y</i><sub>2</sub> such that <i>y</i><sub>1</sub>^<i>y</i><sub>2</sub>=<i>x</i> we count all times a bit is flipped as we count <i>y</i><sub>1</sub>, <i>y</i><sub>1</sub>+1, ..., <i>y</i><sub>2</sub>, not just whether <i>y</i><sub>1</sub> and <i>y</i><sub>2</sub> have a difference in a given bit), and we can just get a bound on the answer independently for each bit, and then take a maximum of those bounds. I have spent time building a more direct solution instead (given the lower bound on <i>y</i><sub>1</sub>, how do we find the smallest <i>y</i><sub>2</sub> for a given <i>x</i>?), figured out a rule for that with 4 cases, but this road did not seem to lead anywhere. Maybe had I considered replacing going from <i>y</i><sub>1</sub> to <i>y</i><sub>2</sub> in one go with processing <i>y</i><sub>1</sub>, <i>y</i><sub>1</sub>+1, ..., <i>y</i><sub>2</sub> step-by-step, I would have come up with the criteria, but this idea never occurred to me.</div><div><br /></div><div>Overall, the problems were beautiful and interesting to solve, even if I was feeling quite stuck for long periods of time :) The biggest common theme seems to be that in 5 out of 10 problems (1A, 1C, 2B, 2C, 2E, and maybe also 1D as linear programming duality is the same idea), one had to stop thinking "how can we optimize/improve what we already can" and go from the other side, "what would be the reasonable bounds/criteria when we clearly can't", and then either proving those are tight, or just assuming it. This could be seen as basing the solution on the fact that the problem is beautiful, or at the very least on the fact that it is solvalbe for the given constraints. So one takeaway is that I should try this solving approach more often.</div><div><br /></div><div>I'm sorry for a long brain dump, feel free to tell me that what I'm writing makes no sense at all :)</div><div><p></p><p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiWJXR7aqHGRSHJ8MaelDucgjeqnrD5ClLXH7XOFebuOySERqJGdyiaTX-AGd0Ur_Jba4cdq6xqs-iBntXnX2Z6XtElFOdEjGoqa30aoFnxWZBh4mH00_p1WignP5paHvYzEX8DTv0w51dS9M-7yVuaDxxXqBESjOebAHwGbqkXSEbnvmt3eXjsVYiYTSQ/s1057/ucup2r2top5.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="234" data-original-width="1057" height="142" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiWJXR7aqHGRSHJ8MaelDucgjeqnrD5ClLXH7XOFebuOySERqJGdyiaTX-AGd0Ur_Jba4cdq6xqs-iBntXnX2Z6XtElFOdEjGoqa30aoFnxWZBh4mH00_p1WignP5paHvYzEX8DTv0w51dS9M-7yVuaDxxXqBESjOebAHwGbqkXSEbnvmt3eXjsVYiYTSQ/w640-h142/ucup2r2top5.png" width="640" /></a></div>The 2nd Universal Cup Stage 2: SPb also took place over the weekend (<a href="https://qoj.ac/contest/1356">problems</a>, <a href="https://qoj.ac/results/QOJ1356">results</a>, top 5 on the left). This season follows the highly successful <a href="https://ucup.ac/rating?season=1">debut season</a> of the Universal Cup, which has more or less taken Open Cup's space as the main team competition outside of the ICPC system. As I understand, <a href="https://qoj.ac/results/QOJ1339">Stage 1</a> of the 2nd Universal Cup was declared unrated because of the server problems, so this was the actual first stage.<p></p><p>On the surface, it might have seemed that making last season's winner USA1 even stronger would be impossible, but they have found a way, demolishing the field in just over three hours with Gennady on the team. Well done!</p><p>It would be nice to gather Petr Team again to participate, but given that the number of stages in a year is ~2x that of the Open Cup, with a stage is happening almost every weekend, the time commitment required to feel a real part of the proceedings would be way too big. We should try to do a one-off round some time, though :)</p><p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjlV7sDe06zFiotEhXtXVzgdMtzpxMgunOKYB5wyotO_hTXu9dboSgVcT1DZDhJcmyBMXSFKAl-uK0z19uTa6MKmhcGpyxA_5VD4V0s_TzxyDVPmHXf6TMOcgKON7QfUX3dEVtJQsGXzcoQiq7hgaEqugGf_Xcnvu0LeOO_1U9m6UDhsh1_7UVl6yS0ox8/s1323/cf896top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="346" data-original-width="1323" height="168" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjlV7sDe06zFiotEhXtXVzgdMtzpxMgunOKYB5wyotO_hTXu9dboSgVcT1DZDhJcmyBMXSFKAl-uK0z19uTa6MKmhcGpyxA_5VD4V0s_TzxyDVPmHXf6TMOcgKON7QfUX3dEVtJQsGXzcoQiq7hgaEqugGf_Xcnvu0LeOO_1U9m6UDhsh1_7UVl6yS0ox8/w640-h168/cf896top5.png" width="640" /></a></div>Codeforces Round 896 wrapped up the week (<a href="https://codeforces.com/contest/1868">problems</a>, <a href="https://codeforces.com/contest/1868/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/116642">analysis</a>, <a href="https://codeforces.com/blog/entry/119859">discussion</a>). Quite fittingly, the first two places in the round went to the problemsetter (<a href="https://codeforces.com/blog/entry/119859?#comment-1067223">well, well</a>) and the winner of AWTF. Congratulations to both!<p></p><p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhAPzdEZ-WYqQPD7bncW0-hojRuK9h59emKbsukbRaZ3xRZD1b4Ni81ZYEk6udVMwj7BrQIo2YuDl6vHI48-bVyvzVk5V7Jjej1arQT-lVg__1f6Pv2ZKyC-hyNGIf12-Cmt8u-4Qka9R3yr6mcQdNyAlslHOYpy-vyn-C59NHN3sNUJlHEXgUlqqmVdko/s3453/PXL_20230429_145304291.MP%20(1).jpg" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1965" data-original-width="3453" height="364" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhAPzdEZ-WYqQPD7bncW0-hojRuK9h59emKbsukbRaZ3xRZD1b4Ni81ZYEk6udVMwj7BrQIo2YuDl6vHI48-bVyvzVk5V7Jjej1arQT-lVg__1f6Pv2ZKyC-hyNGIf12-Cmt8u-4Qka9R3yr6mcQdNyAlslHOYpy-vyn-C59NHN3sNUJlHEXgUlqqmVdko/w640-h364/PXL_20230429_145304291.MP%20(1).jpg" width="640" /></a></div>In <a href="https://blog.mitrichev.ch/2023/09/a-yoneda-week.html">the last week's summary</a>, I have mentioned <a href="https://codeforces.com/contest/1863/problem/F">a Codeforces problem</a>: you are given an array of at most 10000 integers, each between 0 and 2<sup>60</sup>. In one operation, you split the array in the middle into two parts, compute the bitwise xor of each part, and discard the part where the bitwise xor is smaller. In case they are equal, you may discard either part. After doing this operation several times, you have just one number remaining. Which positions in the initial array could this number correspond to?</div><div><br /></div><div>The first observation, which taking bitwise xors of two parts points to, is to notice that the bitwise xor of the bitwise xors of the two parts is equal to the bitwise xor of the entire array. Therefore if the bitwise xor of the first part is <i>x</i>, and the bitwise xor of the entire array is <i>s</i>, then the bitwise xor of the other part can simply be found as <i>s</i>^<i>x</i>. And when comparing <i>x</i> and <i>s</i>^<i>x</i>, they will differ in those bits where <i>s</i> has a 1 bit, therefore we need to look at the highest 1 bit of <i>s</i>, and we will always choose such part that <i>x</i> has a 1 bit in that position. This condition is both necessary and sufficient: any part which has a 1 bit in that position will be chosen.</div><div><br /></div><div>The fact that only the highest 1 bit matters allows to speed up the straightforward dynamic programming from O(<i>n</i><sup>3</sup>) to O(<i>n</i><sup>2</sup>), because we can handle multiple transitions at the same time. The dynamic programming will compute for each of the O(<i>n</i><sup>2</sup>) subsegments whether we can reach it. For O(<i>n</i><sup>3</sup>) complexity, for every reachable state we can simply iterate over all ways to move the left boundary while keeping the right boundary constant, or vice versa, and check if a move is possible (by comparing <i>x</i> and <i>s</i>^<i>x</i>).</div><div><br /></div><div>However, we can notice that doing the transitions that try moving from (<i>l</i>,<i>r</i>) to (<i>l</i>,<i>r-2</i>), (<i>l</i>,<i>r-3</i>), ... and the transitions that try moving from (<i>l</i>,<i>r-1</i>) to (<i>l</i>,<i>r-2</i>), (<i>l</i>,<i>r-3</i>), ... have many things in common. In fact, if (<i>l</i>,<i>r</i>) and (<i>l</i>,<i>r-1</i>) have the same highest 1 bit in their bitwise xor, then those transitions are either possible or not possible at the same time.</div><div><br /></div><div>This hints at what should we be computing in the O(<i>n</i><sup>2</sup>) dynamic programming: for every segment (<i>l</i>,<i>r</i>) we will compute the set of possible highest 1 bits (represented as a bitmask) of all reachable containing segments with the same left boundary (<i>l</i>,<i>r</i><sub>1</sub>) where <i>r</i><sub>1</sub>><i>r</i>, and the same for the containing segments with the same right boundary. To compute this number for (<i>l</i>,<i>r</i>) we can take the same number for (<i>l</i>,<i>r+1</i>) and update it with the highest 1 bit of the bitwise xor of the segment (<i>l</i>,<i>r+1</i>), if it is reachable. And knowing this bitmask allows to check if this segment is reachable by simply testing if this bitmask has a non-zero bitwise and with the bitwise xor of this segment.</div><div><br /></div><div>Another way of putting the same idea is to say that we're introducing intermediate states into our dynamic programming to aid reuse: instead of going from a reachable segment to its prefix or suffix directly, we now first go from a reachable segment to a (segment, highest 1 bit, decision whether we will change left or right boundary) tuple, which allows to add transitions between those tuples, and transitions from those tuples back to segments, in such a way that we have O(1) transitions per tuple instead of having O(n) transitions per segment. This would mean going from O(<i>n</i><sup>2</sup>) states and O(<i>n</i><sup>3</sup>) transitions to O(<i>n</i><sup>2</sup>*#bits) states and O(<i>n</i><sup>2</sup>*#bits) transitions, but then using bitmasks helps get rid of the #bits factor.</div><div><br /></div><div>Thanks for reading, and check back next week!</div>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com0tag:blogger.com,1999:blog-1953325079793449971.post-61793370994158329042023-09-09T17:05:00.002+02:002023-09-09T17:05:40.639+02:00AWTF22 day 2<p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiYMi6tfLDTm_HtVj2RhmUzAEhHEG-U_mnelEAwsfXflA69u07MrswxU65xzrW4tOUf9h1rZF2qlSc3y5WE_C3gBwiulQb2lUiHBu6zJSGps1d0jI15OMvGHEbJlPTEZFQaWubzhxem4Ff_3CSo-l5paMfpM9W2WyBux4u10gaEj35mR-KvNDX5CO1PEy4/s819/wtf22day2top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="352" data-original-width="819" height="276" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiYMi6tfLDTm_HtVj2RhmUzAEhHEG-U_mnelEAwsfXflA69u07MrswxU65xzrW4tOUf9h1rZF2qlSc3y5WE_C3gBwiulQb2lUiHBu6zJSGps1d0jI15OMvGHEbJlPTEZFQaWubzhxem4Ff_3CSo-l5paMfpM9W2WyBux4u10gaEj35mR-KvNDX5CO1PEy4/w640-h276/wtf22day2top5.png" width="640" /></a></div>AtCoder WTF22 onsite round wrapped up today with the second contest (<a href="https://atcoder.jp/contests/wtf22-day2/tasks">problems</a>, <a href="https://atcoder.jp/contests/wtf22-day2/standings">combined results</a>, top 5 on the left, <a href="https://atcoder.jp/contests/wtf22-day2-open/standings">mirror results</a>, <a href="https://atcoder.jp/contests/wtf22-day2/editorial">analysis</a>, <a href="https://youtu.be/b55sFRsz3ow">day 1 livestream</a>, <a href="https://youtu.be/-5MS6cuiorM">day 2 livestream</a>). Once again I have managed to solve only one problem in 5 hours, but at least this time it was worth more points, and it was more satisfying as I have actually gradually approached the correct solution instead of just pulling it out of thin air. Overall, I remained in the 15th place that I had after the first round, and this is also the place I have when ordered by rating. I guess everything went as expected after all :) Qualifying next time would require crawling back into the top 8, though, and that will be a big challenge (<a href="https://clist.by/standings/atcoder-race-ranking-2023-41247385/">current standings</a>).<p></p><p>The overall top 3 solved non-intersecting sets of problems today, and it worked out the best for jiangly who combined the first place on day 2 with the second place on day 1 to win the event. Huge congratulations to him, ksun48 and tourist!</p><p>In a search for external factors that prevented myself from doing better, I've noticed that advancing to the finals from the 2021 season was the most correlated with the final results: the 2021 finalists got places 1,2,3,4,6,7,8 and 14. Maybe the problems for the finals were mostly prepared at the same time as the problems for the AGCs from 2021, and therefore require similar solving approaches? Unfortunately I have advanced in all other years, but not in 2021, hence the poor performance ;) Well done peti1234 for bucking the trend and winning the 5th place!</p><p>Huge thanks to the AtCoder organizing team for the amazing event, and to the problemsetters and testers for the problems! I have also enjoyed the social part immensely, meeting some old friends and getting to know new ones. I hope to meet you all again at some other competition in the future!</p><p>Thanks for reading, and check back tomorrow for this week's summary where I will also choose some AWTF problems to highlight.</p>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com1tag:blogger.com,1999:blog-1953325079793449971.post-56735948096720270742023-09-08T14:19:00.002+02:002023-09-09T17:08:56.585+02:00AWTF22 day 1<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiOWcW-bwNZQw9niAQT6N6qgHMr1drq0zhSfqsTAaa_7tUWtlu4K_WdtfFGrY_f0cIBBUtHX8_SrFXwULKaa5A48Bm1-_ow7hDxnsuJAdhDzbEgctBtlmTyI-TxnrFOXB_1dPDrhceWOjO5qETSw3QQDEm4pypmxaKoSQk6M7RwonHJPkV8txJxlX1geOo/s821/wtf22day1top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="355" data-original-width="821" height="276" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiOWcW-bwNZQw9niAQT6N6qgHMr1drq0zhSfqsTAaa_7tUWtlu4K_WdtfFGrY_f0cIBBUtHX8_SrFXwULKaa5A48Bm1-_ow7hDxnsuJAdhDzbEgctBtlmTyI-TxnrFOXB_1dPDrhceWOjO5qETSw3QQDEm4pypmxaKoSQk6M7RwonHJPkV8txJxlX1geOo/w640-h276/wtf22day1top5.png" width="640" /></a></div>AtCoder WTF22 onsite day 1 just finished (<a href="https://atcoder.jp/contests/wtf22-day1/tasks">problems</a>, <a href="https://atcoder.jp/contests/wtf22-day1/standings">results</a>, top5 on the left, <a href="https://atcoder.jp/contests/wtf22-day1-open/standings">mirror results</a>, <a href="https://atcoder.jp/contests/wtf22-day1/editorial">analysis</a>). I was actually able to get a problem accepted after two hours have passed, with the caveat that this was the only problem I got accepted :) I probably spent about an hour on B and about three hours on C, with no success. In C, I passed all samples except the last one. It turns out that I did have the correct "minimal representation" for a tree at the end, but then I tried to merge them to obtain a minimal representation for a forest in the same format, but it turns out that this was not possible at all: when merging trees B->W<-B (W is root) and W->B (B is root), the minimal representation is just B, but if we later merge it with a tree W->B<-W (B is root), we get a non-empty representation, while if we choose B->W<-B for the result of the first merge, then we can cancel everything out on the second merge. This counterexample stems from the correct solution idea, which tells that one of the conditions for being able to cancel everything is having at least two roots of different colors; hence any approach that merges the representations of trees has to be able to tell if we have seen two roots of different colors. I feel that this was pretty hard to come up with without actually coming up with the trick from the editorial directly.<div><br /></div><div>Congratulations to everyone who was able to solve two problems in this round, and especially to ksun48 on the total domination and to hos_lyric for solving E!</div><div><br /></div><div>Given that tomorrow's round has a 1000-pointer as the first problem, I might have to be content with the points I already have. But I will do my best ;)</div>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com0tag:blogger.com,1999:blog-1953325079793449971.post-79976400305644633642023-09-06T15:38:00.001+02:002023-09-06T15:38:43.365+02:00AWTF22 taifun<p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhH72W7C4vCw5YpRtWUQJJAjFCjxOBPruvikOkqhCU4xciImKwFn6I1C3kL7gPVVy_56x8X-hrmfcdWIehjSoZO0HOgDjRqZtPViwVC3XT7iglpFCV3LB4RqaV9ZrunS65bw2-xZdwQyvFjH0hbUpU_-DkNg6mOz8DqR4ZiU42hyiPYuh1qOtnmRMtVh8Y/s2340/Screenshot_20230906-181817.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="2340" data-original-width="1080" height="640" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhH72W7C4vCw5YpRtWUQJJAjFCjxOBPruvikOkqhCU4xciImKwFn6I1C3kL7gPVVy_56x8X-hrmfcdWIehjSoZO0HOgDjRqZtPViwVC3XT7iglpFCV3LB4RqaV9ZrunS65bw2-xZdwQyvFjH0hbUpU_-DkNg6mOz8DqR4ZiU42hyiPYuh1qOtnmRMtVh8Y/w296-h640/Screenshot_20230906-181817.jpg" width="296" /></a></div>One thing that greeted me on arrival to Tokyo was an unusual notification in Google Maps (see on the left). It looked somewhat scary, but then I remembered the amount of dangerous weather notifications that I get in Zurich that typically do not mean anything too unusual, and relaxed a bit. Imagine how much more relaxed I became when this note greeted me in my hotel room (see on the bottom-right).<p></p><p>So, maybe people with experience of Tokyo winds can share: how bad can it be?</p><p>In general, my approach to this trip is to avoid jetlag by living more or less on Swiss time. The contests start at 6:00 Zurich time, which is definitely early, but not outrageously so. Given that I'm here for just 4 days, it seems logical to not bother shifting the schedule by much, and to sleep 20:00-5:00 Swiss time (=3:00-12:00 here).</p><p>One of the benefits is that I get to do sightseeing in the evening, when it is much more pleasant outside, and there are less people everywhere. The flip side of this coin is that many places will be closed at night.</p><p>One particularly important challenge is getting food. Lunch happens during dinner time here, so it is not really an issue. I will be late for the hotel breakfast, but it will already be lunchtime, which means that I can get some lunch food in one of the cafes near the Shinjuku station (not sure if the lunch in the hotel restaurants will be quick enough to be in time for the contests). However, what to do about dinner? Any suggestions about where to eat in Tokyo at 1am? Bonus points if your suggestion comes in the next 2 hours ;)</p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiK_C8qvl5U5ttsS37km7t0Lb_fIbp7hhBfSV4Cel1g8maQTgG2QemAoKJmKUmMEC8zrrnO9wa4Ksyb4osZT2NiuVYcxwXtRqzTssaKRNEte6jqH2JM4fFEcxKpPrRQPJesbg9_cEhJHIzuC3q_m5oAc8y9TpL_oo-zhn1WbknDKBPhf7rOfcvIjZYAgdQ/s4032/PXL_20230906_070301564.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" data-original-height="4032" data-original-width="3024" height="640" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiK_C8qvl5U5ttsS37km7t0Lb_fIbp7hhBfSV4Cel1g8maQTgG2QemAoKJmKUmMEC8zrrnO9wa4Ksyb4osZT2NiuVYcxwXtRqzTssaKRNEte6jqH2JM4fFEcxKpPrRQPJesbg9_cEhJHIzuC3q_m5oAc8y9TpL_oo-zhn1WbknDKBPhf7rOfcvIjZYAgdQ/w480-h640/PXL_20230906_070301564.jpg" width="480" /></a></div><br /><p><br /></p>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com2tag:blogger.com,1999:blog-1953325079793449971.post-46291282167117057282023-09-06T08:41:00.001+02:002023-09-06T08:41:02.556+02:00AWTF22 arrival<p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh2onkvHA91OgAhD0YM1ys8SujGKFDh_h_6wgud-pWSFpMM2D7xwBwNqDSDVWF56vvxrU4ihXBcyNLf-uu6lNg11lWpWXrIWMypgooMIChy2XMHlDJLCCItQGeY57l9KaLQxcXKvuljQpJmbohTC_04Ufh2asFqTrJtlR42EYv36MWqm9wjspLUy8eGMeI/s4032/PXL_20230906_041429965.MP.jpg" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="3024" data-original-width="4032" height="300" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh2onkvHA91OgAhD0YM1ys8SujGKFDh_h_6wgud-pWSFpMM2D7xwBwNqDSDVWF56vvxrU4ihXBcyNLf-uu6lNg11lWpWXrIWMypgooMIChy2XMHlDJLCCItQGeY57l9KaLQxcXKvuljQpJmbohTC_04Ufh2asFqTrJtlR42EYv36MWqm9wjspLUy8eGMeI/w400-h300/PXL_20230906_041429965.MP.jpg" width="400" /></a></div>So, an onsite event unfortunately means a couple of long flights :) Can you guess which of the two photos is the Zurich airport, and which is the Tokyo airport?<div><br /></div><div>Surprisingly, there were no signs announcing the AtCoder WTF at the airport — how could the airport forget to greet the participants? ;) Having encountered the Japanese reality both in a good way (the immigration was well-organized, and apparently there's even a way to fill all forms online in advance) and in a not-so-good way (apparently the tickets for some, but not all, trains can only be bought in cash, so I had to wait for the next train because there was no time to run to an ATM), I have almost arrived at the competition hotel. <br /><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgh2YIGMPVixKcMiRLnVlbuWuxg349XMhkMKpsz_YqUx0k7_kM6M9XyqMK_U6x2WP--rtjVo6g2fND8MkT_lp0sTX13jJTRwTfvZPl83hjVf9mQ4tsvSzpRMjAD0GAc2vLUgc0ZFcLFrzPuV289qDq2jzT1MF4zA2ZauE8ff0xmxGYj4MpumeAZlIta1nQ/s4032/PXL_20230905_080635538.jpg" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" data-original-height="3024" data-original-width="4032" height="300" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgh2YIGMPVixKcMiRLnVlbuWuxg349XMhkMKpsz_YqUx0k7_kM6M9XyqMK_U6x2WP--rtjVo6g2fND8MkT_lp0sTX13jJTRwTfvZPl83hjVf9mQ4tsvSzpRMjAD0GAc2vLUgc0ZFcLFrzPuV289qDq2jzT1MF4zA2ZauE8ff0xmxGYj4MpumeAZlIta1nQ/w400-h300/PXL_20230905_080635538.jpg" width="400" /></a></div>The competition itself takes place on Friday and Saturday, with two five-hour rounds currently scheduled. I do not know if those are just placeholders, but if not, that is quite a challenge for an individual event. I have a feeling that recently I do not get any problems accepted after the 2 hour mark in contests that last longer than 2 hours, so I will have to do very well in the first 2 hours of each day :)<p></p></div><div>There is probably a way to use Codeforces API to get a more grounded assessment of that feeling. Or maybe there is an existing tool that can help answer the questions like "what would my place be in Round X if it was over after 2 hours"?</div><div><br /></div><div>Thanks for reading, and check back soon for more AWTF updates. And I'm sorry for the low fraction of the actual algorithmic content this week :)</div>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com0tag:blogger.com,1999:blog-1953325079793449971.post-45626259080673232862023-09-03T19:33:00.001+02:002023-09-23T23:58:06.973+02:00A Yoneda week<p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgzmm0zRqVWQwmUEGLiW_4knh7ygFcQWrY21OYWW53DAj-i2PSoYG8oJrPoWAfMHcOqMB60E9sHUgD-BaeZ1AXHOUjz5Cp8mg_MEoTTQGqCPh0GNpM63IDcEANkWB3OyHqvDa1ZxZxnxit09XERwdNmO8XdBOakS2K_FeNXyX6QradvyNMoc8--LD-Shmk/s1183/ioi23top5.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="203" data-original-width="1183" height="110" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgzmm0zRqVWQwmUEGLiW_4knh7ygFcQWrY21OYWW53DAj-i2PSoYG8oJrPoWAfMHcOqMB60E9sHUgD-BaeZ1AXHOUjz5Cp8mg_MEoTTQGqCPh0GNpM63IDcEANkWB3OyHqvDa1ZxZxnxit09XERwdNmO8XdBOakS2K_FeNXyX6QradvyNMoc8--LD-Shmk/w640-h110/ioi23top5.png" width="640" /></a></div>The 35th International Olympiad in Informatics in Szeged, Hungary was the main event of this week (<a href="https://ioi2023.hu/tasks/">problems</a>, <a href="https://stats.ioinformatics.org/results/2023">results</a>, top 5 on the left, <a href="https://youtu.be/wbuU_mSOdiE">day 1 broadcast</a>, <a href="https://youtu.be/CqnCzSArftg">day 2 broadcast</a>). <span style="white-space: normal;">Tingqiang Xu and </span>Siyuan Cheng were miles ahead of everybody else (who still did <a href="https://codeforces.com/blog/entry/119951?#comment-1064430">great</a> :)), and only 1 point ended up deciding the overall winner. Congratulations to them but also to all medalists! My inevitable slide in the <a href="https://stats.ioinformatics.org/halloffame/">Hall of Fame</a> continued, seemingly by just 1 place though.<p></p><div>According to <a href="https://ioi2023.hu/tasks/">the problem page</a>, three out of six problems were created by the amazing team of <a href="https://cphof.org/profile/topcoder:square1001">square1001</a> and <a href="https://cphof.org/profile/topcoder:E869120">E869120</a>. Creating just one IOI-quality problem is an amazing achievement requiring great ideas and weeks (if not months) of work, so it is hard for me to even imagine creating three in the same year. Well done!</div><div><br /></div><div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgx93pw57nTIFILNQ8dsd2gLkeYWW8T6OYf89CAW9D602y_zQO98ssU8uipEmq0jN9htKFThhpsCe0WVP_nQUrigPodXeXM4AaJafP8apPvRZXZzsprkYIpJGnp0p4cvH8TpPP_4d4Iog6wfF5OitjhO6p1dxBOiqgHLkRA6OPH4nR8mGrjza5BnWY5Akw/s1319/cfpinely2top5.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="344" data-original-width="1319" height="166" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgx93pw57nTIFILNQ8dsd2gLkeYWW8T6OYf89CAW9D602y_zQO98ssU8uipEmq0jN9htKFThhpsCe0WVP_nQUrigPodXeXM4AaJafP8apPvRZXZzsprkYIpJGnp0p4cvH8TpPP_4d4Iog6wfF5OitjhO6p1dxBOiqgHLkRA6OPH4nR8mGrjza5BnWY5Akw/w640-h166/cfpinely2top5.png" width="640" /></a></div>Codeforces ran Pinely Round 2 just a few hours after the first IOI day was over (<a href="https://codeforces.com/contest/1863">problems</a>, <a href="https://codeforces.com/contest/1863/standings">results</a>, top 5 on the left, <a href="https://youtu.be/Vt8LoTmA9Ow">my screencast</a>, <a href="https://codeforces.com/blog/entry/119770">discussion</a>, <a href="https://codeforces.com/blog/entry/119902">analysis</a>). I wonder who is the highest-placed participant who took part in both :) Among the participants well past their IOI days, tourist got his first place using just under an hour out of the three hours available. It could all change at the end of the round, as both last problems were not completely unsolvable and saw a lot of last-minute submissions, but nobody was able to get all details exactly right. Congratulations to tourist!</div><div><br /></div><div><a href="https://codeforces.com/contest/1863/problem/F">Problem F</a> did not require one to come up with complicated ideas, but instead required some accuracy "unwrapping the present" to arrive at the solution, and it was nice that the solution turned out quite easy to implement: you are given an array of at most 10000 integers, each between 0 and 2<sup>60</sup>. In one operation, you split the array in the middle into two parts, compute the bitwise xor of each part, and discard the part where the bitwise xor is smaller. In case they are equal, you may discard either part. After doing this operation several times, you have just one number remaining. Which positions in the initial array could this number correspond to?</div><div><br /></div><div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhbDen_JRXRnJrLBoZEa0vsXQ7thYT-DCDSY2MP0ACDfYUMCnupWVNgJyr5Fs7ShCSZZmlpeK1mZen3Zdab3y1G1vBbEKKmoWjuNPOToQBhAsBTd0wxZJjIl7Dgt82YBUeV5_RHvRuCr6IITcG8gOVqSC8wvcKSnm2Nf9kbMix7NOK6TWdHppJZ5pyZVHk/s4032/PXL_20230501_105631943-EDIT.jpg" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="2425" data-original-width="4032" height="384" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhbDen_JRXRnJrLBoZEa0vsXQ7thYT-DCDSY2MP0ACDfYUMCnupWVNgJyr5Fs7ShCSZZmlpeK1mZen3Zdab3y1G1vBbEKKmoWjuNPOToQBhAsBTd0wxZJjIl7Dgt82YBUeV5_RHvRuCr6IITcG8gOVqSC8wvcKSnm2Nf9kbMix7NOK6TWdHppJZ5pyZVHk/w640-h384/PXL_20230501_105631943-EDIT.jpg" width="640" /></a></div>You might have noticed that the address of this blog has changed to <a href="https://blog.mitrichev.ch/">https://blog.mitrichev.ch/</a>. I am going to use this address going forward, even though the old address will keep redirecting to the new one for the foreseeable future. So, welcome to the new home!</div><div><br /></div><div>It is also a good opportunity to write about my online presence in general. I do not have accounts in the common social networks, such as Facebook, Twitter/X, LinkedIn, TikTok, Instagram, etc. Of the social network-like things I mainly have <a href="https://blog.mitrichev.ch">this blog</a>, <a href="https://www.youtube.com/@petrmitrichev">my Youtube channel</a>, and <a href="https://codeforces.com/profile/Petr">my Codeforces account</a>.</div><div><br /></div><div>Thanks for reading, and check back soon! I will try to post updates about <a href="https://codeforces.com/blog/entry/117533">the AWTF</a> during the week.</div>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com0tag:blogger.com,1999:blog-1953325079793449971.post-24352057160049415742023-08-27T12:15:00.000+02:002023-08-27T12:15:17.424+02:00An onsite week<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgwRYTCJfjrY2ExILhLUup0sVOXCa4E9p0iZyqePdaUMnzlAloFTgkL2cdAbPM7ocqMbMzywpqiEU0ShXH4iUuxscM-JrY9fCq4uCycoJeIJ-gPpOyAKRWu6fJJhv3IllFbT_6MVDbUOyeWydTp0dA-8TstT9zD5v5otwktBcnK_yg6zqOqv6ayeL3u8Ak/s1102/cfharbor2023top5.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="282" data-original-width="1102" height="164" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgwRYTCJfjrY2ExILhLUup0sVOXCa4E9p0iZyqePdaUMnzlAloFTgkL2cdAbPM7ocqMbMzywpqiEU0ShXH4iUuxscM-JrY9fCq4uCycoJeIJ-gPpOyAKRWu6fJJhv3IllFbT_6MVDbUOyeWydTp0dA-8TstT9zD5v5otwktBcnK_yg6zqOqv6ayeL3u8Ak/w640-h164/cfharbor2023top5.png" width="640" /></a></div>Harbour.Space Scholarship Contest 2023-2024 on Codeforces was the main event of the week (<a href="https://codeforces.com/contest/1864">problems</a>, <a href="https://codeforces.com/contest/1864/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/119512">discussion</a>, <a href="https://codeforces.com/blog/entry/119772">analysis</a>). Radewoosh solved the first eight problems 20 minutes faster than everybody else, and therefore had all but guaranteed himself first place by the middle of the contest. Still, he kept his focus and managed to get problem I accepted as well with just 3 minutes to go. Huge congratulations!<div><br /></div><div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj2aVzMD0xc4HqYb9R4tYbuFabwpF14pQ8BgQZgJPclcacCGy5kXZ9esdB-_Z245WNldtLKRLuN62IjqVXLt_xj4H_lQHg69CCpNqwbUbE72lC4Jbrehyuyu1zSjncfCyC0DePbDWJy07ynNmnrF7AEqW5L6EyG69PCiNDPmfEKaWwj1dyFGe0vxtPpeZU/s4032/PXL_20230501_202248747.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="3024" data-original-width="4032" height="480" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj2aVzMD0xc4HqYb9R4tYbuFabwpF14pQ8BgQZgJPclcacCGy5kXZ9esdB-_Z245WNldtLKRLuN62IjqVXLt_xj4H_lQHg69CCpNqwbUbE72lC4Jbrehyuyu1zSjncfCyC0DePbDWJy07ynNmnrF7AEqW5L6EyG69PCiNDPmfEKaWwj1dyFGe0vxtPpeZU/w640-h480/PXL_20230501_202248747.jpg" width="640" /></a></div>I skipped this round and therefore cannot tell you much about its problems. Therefore, I'd like to use this post to talk about the upcoming onsite event that you might not be aware of :) I'm not referring to the IOI, which takes place next week in Szeged, Hungary, since I expect everybody interested in it to know where to find more information. Instead, I'd like to talk about the AtCoder WTF that <a href="https://codeforces.com/blog/entry/117533">takes place</a> on September 8-9 in Tokyo, Japan.</div><div><br /></div><div>When AtCoder <a href="https://codeforces.com/blog/entry/56623">announced</a> its own onsite competition, the World Tour Finals, back in 2017, the world of onsite algorithmic competitions was quite packed. They have managed to <a href="https://petr-mitrichev.blogspot.com/2019/02/a-wtf-week.html">host</a> one edition of the WTF before the pandemic hit. All onsite competitions were <a href="https://cphof.org/contests">cancelled or moved online</a> during the pandemic, but instead of returning after global travel became relevant again, most were cancelled completely: Google Code Jam, TopCoder Open, likely Meta Hacker Cup. There were a few more Russia-based onsite competitions that are of course no longer a thing. ACM ICPC and high school olympiads such as the IOI are back in the onsite mode, but they have age upper bounds for participation.</div><div><br /></div><div>AtCoder did not move the WTF online, instead they kept running <a href="https://clist.by/standings/?search=race+ranking&resource=93">the yearly qualification cycle</a>, promising to invite the top 8 from each year to the onsite round in Japan when it becomes possible again. This is finally happening in two weeks! <a href="https://clist.by/accounts/?contest=33151256&contest=19844250&contest=19846514&contest=26421821&advanced=true">18 finalists</a> out of the maximum of 32 from the four qualification cycles will compete on the same problems over two competition days. This approach lies in contrast to the ACM ICPC approach where the finals for the 2022 and 2023 seasons are happening together in Egypt but the actual competitions will be kept separate. Which one do you think makes more sense?</div><div><br /></div><div>I am really excited both for the competition (where to be honest I no longer stand a chance), and for the onsite event atmosphere. As an added twist, AtCoder <a href="https://codeforces.com/blog/entry/112915">have announced</a> the online participation option for the future WTFs; I can't predict how this will work out, but when TopCoder did the same for TCO22, so few people decided to come onsite that they decided to cancel the onsite event altogether. Therefore this might be the last onsite event without the age upper bound ever :)</div><div><div><div><br /></div><div>Thanks for reading, and check back next week!</div></div></div>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com2tag:blogger.com,1999:blog-1953325079793449971.post-13708177079028872582023-08-20T21:30:00.003+02:002023-08-20T21:30:56.350+02:00An arborescence week<p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiKRpMPLvdLPnH_frxEbGcyaB1OEpRhGUjoBoV04UD3qP1sR05H-iH-sXLP9TytqE89_CFQnUJT1jrSewk7IwoDNyQz7OTSydmuwLpa_CGJYrVCEbLcEKRvtkyDd9Sj-T9nfnYUr3Md79Xz1vzWAlnIwAtDph4HQkCDIYyAik8l4Y2BuJeFDDPz7YL8ig8/s3349/PXL_20230503_081327957-EDIT.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1912" data-original-width="3349" height="366" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiKRpMPLvdLPnH_frxEbGcyaB1OEpRhGUjoBoV04UD3qP1sR05H-iH-sXLP9TytqE89_CFQnUJT1jrSewk7IwoDNyQz7OTSydmuwLpa_CGJYrVCEbLcEKRvtkyDd9Sj-T9nfnYUr3Md79Xz1vzWAlnIwAtDph4HQkCDIYyAik8l4Y2BuJeFDDPz7YL8ig8/w640-h366/PXL_20230503_081327957-EDIT.jpg" width="640" /></a></div>There was no contest that I'd like to mention this week, so let us come back to the <a href="https://atcoder.jp/contests/agc064/tasks/agc064_b">AtCoder problem</a> from the <a href="https://petr-mitrichev.blogspot.com/2023/08/an-apiad-week.html">previous summary</a>: you are given a connected graph where each edge is either red or blue, and each vertex is also either red or blue. You need to find a spanning tree in this graph such that for each vertex it has at least one adjacent edge of the same color as the vertex, or report that there isn't any.<p></p><p>The first step is to notice that all edges are of three types: type 2 are the edges where both ends have the same color as the edge, type 1 are the edges where one end has the same color as the edge, and type 0 are the edges where no end has the same color as the edge. We will also direct the type 1 edges from the vertex of the correct color to the vertex of the wrong color.</p><p>Clearly type 2 edges are the most useful for reaching our goal. In fact, if every vertex has at least one type 2 edge adjacent to it, then we can simply find the spanning forest among the type 2 edges. If it is a spanning tree, then we have solved the problem. If it is not connected, since we have already satisfied the color constraints, we can augment the forest to a tree using the remaining edges in any way.</p><p>What if there are some vertices that do not have type 2 edges adjacent to them? If there is a vertex with no outgoing type 1 edges, or in other words a vertex where all adjacent edges have the wrong color, then there is clearly no solution. So we only have to consider the case where some vertices have type 2 edges adjacent to them, and all remaining vertices have at least 1 outgoing type 1 edge. We will call the vertices with type 2 edges adjacent to them type 2 vertices, and the ones without them type 1 vertices.</p><p>The key remaining observation is that we cannot solve the problem using only type 1 edges. Each type 1 edge satisfies the color constraint for 1 vertex, but overall we have <i>n</i> vertices but only <i>n</i>-1 edges. So a logical idea is to start with the spanning forest of the type 2 edges that will cover all type 2 vertices, and then repeatedly try to find a type 1 edge that goes from a yet uncovered vertex to an already covered vertex (building something similar to an arborescence). If we manage to cover all vertices this way, then we can once again augment the resulting forest to a tree using the remaining edges. If we get stuck at some point, then there is no solution.</p><p>But why is this correct? We have proven that we need at least one type 2 edge, but why is it always correct to take ~all of them? This is a very typical situation for problems involving the spanning trees, as they all usually end up relying on some kind of greedy argument, so one could just bet on intuition here in my opinion. Still, here is the formal proof: consider the situation where our solution gets stuck. At this moment, the set <i>S</i> of uncoverted vertices contains only type 1 vertices, and there is no type 1 edge going from this set to the set of covered vertices. But then how could <i>S</i> be covered in any other solution? Since we have at most |<i>S</i>|-1 edges within <i>S</i>, and only edges within <i>S</i> can cover its vertices, one of them will have to remain uncovered in any tree.</p><p>Thanks for reading, and check back next week!</p>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com0tag:blogger.com,1999:blog-1953325079793449971.post-14898391130596187622023-08-13T21:03:00.001+02:002023-08-13T21:03:12.736+02:00An apiad week<p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgtAAsuZ1D3dPD0iAtmZBPYDEs1H9TofrjOZ1V4yJ9iWdmGhzqY00MY9GAOQGnwjsOHQxcmplKY3HLfrdC-Ckv5D7oA5bPgr0epIq-NVMhcqK-nbj1gvM8IkZpRxduxbZbLWVZrAkFEFOoVX_PDpJs6o_9aEdG6LFhtbDLrgH7iqoUg4hbkdx9Hq010a3Y/s786/agc064top5.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="357" data-original-width="786" height="290" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgtAAsuZ1D3dPD0iAtmZBPYDEs1H9TofrjOZ1V4yJ9iWdmGhzqY00MY9GAOQGnwjsOHQxcmplKY3HLfrdC-Ckv5D7oA5bPgr0epIq-NVMhcqK-nbj1gvM8IkZpRxduxbZbLWVZrAkFEFOoVX_PDpJs6o_9aEdG6LFhtbDLrgH7iqoUg4hbkdx9Hq010a3Y/w640-h290/agc064top5.png" width="640" /></a></div>AtCoder Grand Contest 064 was the main event of the week (<a href="https://atcoder.jp/contests/agc064/tasks">problems</a>, <a href="https://atcoder.jp/contests/agc064/standings">results</a>, top 5 on the left, <a href="https://atcoder.jp/contests/agc064/editorial">analysis</a>, <a href="https://youtu.be/QhBTJqK-y8U">my screencast</a>, <a href="https://clist.by/standings/atcoder-race-ranking-2023-41247385/">race standings</a>). apiad's usual strategy worked spectacularly well this time, as after spending two hours on E he was able to solve just enough easier problems to win the round, while those who started with the four easier problems did not have two hours remaining for E and could not figure out all details. Congratulatons on the victory!<p></p><p>I was one of those starting with the four easier problems. Somewhat unexpectedly, I did not get stuck in them and did actually have a bit more than an hour remaining for E, and made some significant progress on paper: I realized that if the sum of all <i>a<sub>i</sub></i> is zero, and the sum of all <i>b<sub>j</sub></i> is zero, and we can place the <i>n</i><sup>2</sup> negated sums -(<i>a<sub>i</sub></i>+<i>b<sub>j</sub></i>) in the matrix in such a way that every column and row has exactly one of each <i>a<sub>i</sub></i> and <i>b<sub>j</sub></i>, then the sum of the 2<i>n</i>-1 cells in a cross, which is the sum of the row plus the sum of the column minus the middle cell, will be exactly <i>a<sub>i</sub></i>+<i>b<sub>j</sub></i>. I've then realized that if the sum of all <i>a<sub>i</sub></i> plus the sum of all <i>b<sub>j</sub></i> is divisible by 2<i>n</i>-1, then we can get both of those sums equal to zero with some constant shifts. Finally, I've correctly hypothesized that in case it's not divisible by 2<i>n</i>-1, then we can only achieve score <i>n</i><sup>2</sup>-1, and figured out how to do so with some more constant shifts for the first row and the first column.</p><p>Therefore the only remaining step was to place the <i>n</i><sup>2</sup> negated sums -(<i>a<sub>i</sub></i>+<i>b<sub>j</sub></i>) in the matrix in such a way that every column and row has exactly one of each <i>a<sub>i</sub></i> and <i>b<sub>j</sub></i>. This does not depend on the values of <i>a</i> and <i>b</i>, so this simply needs to be done once for every <i>n</i>. It seemed quite doable as it felt like a more advanced derangement, and derangements are quite dense. I've tried some random placements and noticed that I can find such a placement for odd <i>n</i>, but not for even <i>n</i>. And this is pretty much how far I've got in an hour :)</p><p>Judging from <a href="https://atcoder.jp/contests/agc064/editorial/6983">the editorial</a> (which I do not understand), it seems that for even <i>n</i> we need to use more degrees of freedom, therefore while I enjoyed coming up with my approach, I needed another huge step to finish the solution, and therefore needed at least another hour.</p><p>I found <a href="https://atcoder.jp/contests/agc064/tasks/agc064_b">problem B</a> to be a cute test of how well one understands the spanning tree mechanics (it is amazing how many nice problems can be derived from a relatively simple concept of a spanning tree, and the fact that it can be found greedily!): you are given a connected graph where each edge is either red or blue, and each vertex is also either red or blue. You need to find a spanning tree in this graph such that for each vertex it has at least one adjacent edge of the same color as the vertex, or report that there isn't any. Can you see a way to do it?</p><p>Thanks for reading, and check back next week!</p>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com4tag:blogger.com,1999:blog-1953325079793449971.post-63856348629369886422023-08-04T13:55:00.001+02:002023-08-04T13:55:35.692+02:00A power of two week<p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhNpPL9VSrjJ1xz8y-Q1P9ZWSC8KtS_VI2rGuC4q3bw51XEhndaPttb2TDgRoucu1RsjLJGlFA7-2MPGzGpv7k5tFwPAU0PhL9VU4C4Igu7EksIpSOdGS_tsw9Knq3KeURXDB6sSlbO4Gx4kVhHoziDP4fPbynnsg66wwYiOBtgIGdmFs0eKZB-h9vtzss/s4032/PXL_20230505_151356985.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="3024" data-original-width="4032" height="480" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhNpPL9VSrjJ1xz8y-Q1P9ZWSC8KtS_VI2rGuC4q3bw51XEhndaPttb2TDgRoucu1RsjLJGlFA7-2MPGzGpv7k5tFwPAU0PhL9VU4C4Igu7EksIpSOdGS_tsw9Knq3KeURXDB6sSlbO4Gx4kVhHoziDP4fPbynnsg66wwYiOBtgIGdmFs0eKZB-h9vtzss/w640-h480/PXL_20230505_151356985.jpg" width="640" /></a></div>There were no contests that I'd like to mention this week, but we still have two cool problems C from <a href="https://petr-mitrichev.blogspot.com/2023/07/a-sokoban-week.html">the previous summary</a> to discuss. First, let us talk about <a href="https://codeforces.com/contest/1854/problem/C">a Codeforces problem</a>: you have a set <i>S</i> of integers between 1 and <i>M</i> (<i>M</i><=500). In one operation, you pick an element of the set uniformly at random, and increment it by 1. If the incremented element coincides with another element of the set, we keep only one copy, so the size of the set decreases by 1. If the incremented element exceeds <i>M</i>, we discard it, so the size of the set also decreases by 1 in that case. We are given the starting set <i>S</i>, and need to find the expected number of steps before it becomes empty.<p></p><p>When I was thinking about this problem, I have convinced myself that any solution will need to keep track of the number of elements in the set <i>S</i> as we divide the probabilities by that number on each step, and unlike multiplication, division does not lend itself to some nice linearity of expectation arguments. Well, it turns out it does :)</p><p>Consider two adjacent numbers from the initial set <i>S</i>. How do they move? Well, either the lower number increases by 1, in which case it might actually merge with the higher number, or the higher number increases by 1, in which case it might disappear if it exceeds <i>M</i>, and then the lower number will also disappear after a few more steps. What is the expected number of steps that the lower number makes? Here comes the stunning observation: we do not actually need to know anything about the rest of the set <i>S</i> to compute this expected number of steps! No matter what happens to the rest of the set, every time one of those two numbers moves, it will be the lower number with probability 50%, and the higher number with probability 50%. So we can implement a relatively standard dynamic programming to compute the expectation.</p><p>And then, as you have probably guessed by this point, thanks to the linearity of expectation the answer to the problem can be computed as the sum of those expected numbers of steps over all pairs of adjacent numbers in the input, plus the expected number of steps for the highest number (which is just <i>M</i>+1 minus that number).</p><p>The really unexpected aspect of this solution for me is that we end up only ever dividing by 2, even though on the surface it looks like we need to divide by numbers up to |<i>S</i>|. Having learned this from the editorial, I immediately remembered one thing that I considered doing during the contest: can we try to reconstruct the answers to the sample cases in the fraction form from the values modulo 1000000007 that are given in the problem statement (750000009, 300277731 and 695648216)? Knowing the solution, I realized that those fractions would have a power of two in the denominator, and that might have been just the clue I needed to solve this problem.</p><p>I've <a href="https://colab.research.google.com/drive/1gjt2fUN7Ka9mGVxwc-CfWWNBGA7Ns1eu?usp=sharing">tried doing this</a> now, and it turns out this reconstruction is not so easy. Just trying to find a fraction with the smallest numerator and denominator yields:</p><p><span style="font-family: courier;">750000009 = 15/4<br />300277731 = 26062/39247<br />695648216 = 35459/32906</span></p><p>Which is clearly incorrect for the last two cases, as the answer cannot be less than 1 or so close to 1. Adding some reasonable boundaries on the value of the fraction (it must be between 10 and 50 for the last two cases), we get:</p><p><span style="font-family: courier;">750000009 = 15/4 = 3.75<br />300277731 = 133137/8642 = 15.40580884054617<br />695648216 = 133345/10938 = 12.19098555494606</span></p><p>Which actually looks plausible, but is still incorrect as we know from the above. However, we know from the problem statement that the denominator cannot have prime factors greater than |<i>S</i>|, which in our case is 5. Adding that constraint produces:</p><p><span style="font-family: courier;">750000009 = 15/4 = 3.75<br />300277731 = 1241063/65536 = 18.937118530273438<br />695648216 = 582323/32768 = 17.771087646484375</span></p><p>Which looks even more plausible, to the point that it might be correct (I did not check), and in any case might have delivered the key hint about only ever dividing by 2.</p><p>Now, some questions to the reader :) Do you routinely try to convert the sample answers from the "modulo prime" form to the fraction form? Did it ever help you solve a problem? Do you have some tricks on how to do this more reliably? If the problemsetters are reading this, did you consider this trick when choosing the samples for this problem?</p><p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhl5u7f-pqNUmagqepC_tc63hnyU30ZxsoM5Afrjs4wGgxQUU5jL9zj3PiwaOU93jE0X4OayrxlD2x7bqrInAg2wzk-u9kusyZhrW9SHCWtHCKGUpozDi1BM45iKZbE3vd4gQXeLyDHoR0XPjHDivK-WJWcP1oZvgdElWb_3kOFzmM9A_T5EZ53NYeuLFY/s4032/PXL_20230506_102429309.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="4032" data-original-width="3024" height="640" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhl5u7f-pqNUmagqepC_tc63hnyU30ZxsoM5Afrjs4wGgxQUU5jL9zj3PiwaOU93jE0X4OayrxlD2x7bqrInAg2wzk-u9kusyZhrW9SHCWtHCKGUpozDi1BM45iKZbE3vd4gQXeLyDHoR0XPjHDivK-WJWcP1oZvgdElWb_3kOFzmM9A_T5EZ53NYeuLFY/w480-h640/PXL_20230506_102429309.jpg" width="480" /></a></div>Now, on to <a href="https://atcoder.jp/contests/agc063/tasks/agc063_c">an AtCoder problem</a>: you are given <i>N</i><=1000 pairs of integers (<i>A<sub>i</sub></i>,<i>B<sub>i</sub></i>), each integer between 0 and 10<sup>9</sup>. In one operation, you choose two integers <i>x</i><<i>y</i> between 0 and 10<sup>18</sup>, and replace each <i>A<sub>i</sub></i> with (<i>A<sub>i</sub></i>+<i>x</i>) mod <i>y</i> (note that you apply the same <i>x</i> and <i>y</i> to all <i>A<sub>i</sub></i>). You need to make it so that <i>A<sub>i</sub></i>=<i>B<sub>i</sub></i> for all i after at most <i>N</i> operations, or report that it is impossible.<p></p><p>During the round, I guessed correctly that this is almost always possible, except for the cases like <i>A<sub>1</sub></i>=<i>A<sub>2</sub></i>, but B<i><sub>1</sub></i><span style="background-color: white; color: #202124; font-family: "Google Sans", arial, sans-serif; font-size: 16px;">≠</span><i>B<sub>2</sub></i>. However, I could not find a nice way to reorder the numbers. I was thinking mostly about operations where <i>y</i> is bigger than the biggest number, to have at least some control over what is happening. In that case, by choosing the appropriate <i>x</i>, we can split the numbers into two parts and interleave those parts, but that does not give us enough control to achieve an arbitrary ordering.</p><p>One other thing that came to mind when thinking about this interleaving operation is that it can only make the numbers closer to each other, but not pull them apart. However, when no interleaving actually happens, in other words when we just do a cyclic shift of the numbers, then we are not reordering, but we can pull the two halves apart as much as we'd like.</p><p>This is how far I've got during the round, and it turns out that this is the right direction, but I missed one final trick. Here is a working plan: in the first <i>N</i>-1 operations, we do <i>N</i>-1 cyclic shifts, which allows us to create almost arbitrary gaps between pairs of adjacent numbers, but still keeps the cyclic order intact. And then in the <i>N</i>-th operation we do a massive reodering and everything falls into place.</p><p>Knowing the plan, it is relatively easy to figure out the details. Assuming the last operation uses <i>x</i>=0 and some <i>y</i>=<i>Y</i> that is bigger than all <i>B<sub>i</sub></i>, we just need to make <i>A<sub>i</sub></i>=<i>Y</i>*<i>k<sub>i</sub></i>+<i>B<sub>i</sub></i>. And now we can choose <i>k<sub>i </sub></i>in such a way that the cyclic order of those <i>A<sub>i</sub></i> coincides with the initial cyclic order of <i>A<sub>i</sub></i>, moreover we can choose any particular cyclic shift of this cyclic order, which then makes planning the first <i>N</i>-1 operations easy. You can find more details in <a href="https://atcoder.jp/contests/agc063/editorial/6884">the editorial</a>.</p><p>However, it is still unclear to me how I could have arrived at this final trick without just "seeing" it out of nowhere. Even though the operation used in this problem is simple, the space of ways to use it is endless, and it was hard for me to somehow narrow down the search. For many problems, it is more or less clear where the difficulty lies and that you must use a certain resource optimally to arrive at the solution, and this helps cut less promising directions quickly when trying to solve the problem. However, in problems like this one, one cannot be sure that the direction is correct until they see a full solution.</p><p>To the 174 people who solved this problem during the round: how did you arrive at the solution? Is there some intermediate reasoning step that makes the last leap of faith smaller, or is it just small enough for you as it is?</p><p>Thanks for reading, and check back next week!</p>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com2tag:blogger.com,1999:blog-1953325079793449971.post-39809735568120101742023-07-30T17:38:00.004+02:002023-07-31T09:38:13.895+02:00A Sokoban week<p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiZyzeD43Hc6uw6B-JJekwpVfnpkgqA3bbLfQlQyzVWj2UvHN3pIouJjAzFWCDexlgMXS-vlnuYS6oJ7qVO_--pkxaFCyZF5IFiZ30st5s8sVeHcCtfR37rheRnINZzlA-nHtULfHIUSFi93XPirqj86B7nN3aYy2I_z06dSKGUxbt-ZFjmsBoVX8jkkk8/s1320/cf889top5.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="345" data-original-width="1320" height="168" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiZyzeD43Hc6uw6B-JJekwpVfnpkgqA3bbLfQlQyzVWj2UvHN3pIouJjAzFWCDexlgMXS-vlnuYS6oJ7qVO_--pkxaFCyZF5IFiZ30st5s8sVeHcCtfR37rheRnINZzlA-nHtULfHIUSFi93XPirqj86B7nN3aYy2I_z06dSKGUxbt-ZFjmsBoVX8jkkk8/w640-h168/cf889top5.png" width="640" /></a></div>Codeforces Round 889 opened the competitive programming weekend (<a href="https://codeforces.com/contest/1854">problems</a>, <a href="https://codeforces.com/contest/1854/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/118540">analysis</a>). Radewoosh was the fastest to solve the first six problems, and even though the last one did not budge, it was enough for the first place. He was also <a href="https://codeforces.com/blog/entry/118631?#comment-1053004">able to hack</a> his own, tourist's and one of the reference solutions for D after the round, further demonstrating his great understanding of the problems. Congratulations!<p></p><p>I liked the problemset a lot, because it felt like a problemset that I could have come up with myself :) The solutions for the harder problems involved a fair bit of experimentation, and more generally I did not get the (quite regular these days...) feeling of "how on Earth could one think of this setting for a problem or this solution idea", both the problem settings and the solution ideas seemed pretty approachable. Kudos to TheScrasse and dario2994!</p><p>I ended up in place 42 instead of place 10 because of an off-by-one error in B: I <a href="https://codeforces.com/contest/1854/submission/216247914">used</a> <span style="font-family: courier;">bitset<200001></span> instead of <span style="font-family: courier;">bitset<200002></span>. I'm actually curious why this out-of-bounds access (querying element <span style="font-family: courier;">200001</span><span style="font-family: inherit;"> </span>of <span style="font-family: courier;">bitset<200001></span><span style="font-family: inherit;">) causes a runtime error. Doesn't the implementation use an integer number of bytes, and therefore the actual number of bits has to be at least </span>200008?</p><p>The reason I could not go higher was my inability to solve problem C, which caused me to focus on <a href="https://codeforces.com/contest/1854/problem/F">problem F</a> which I could actually solve and was trying to code. I've implemented a bruteforce, and printed all points for which the distance differed from the one obtainable from the obvious bounds (has to have the same parity and the sum of coordinates less than the sum of all jumps). For example, <a href="https://docs.google.com/document/d/1aozMdxEgxz51FuCkMDEJNShv4qhNQKUp7xZENdIBma0/edit?usp=sharing">here is the list of points</a> I got which have distance 12 but just according to parity and the sum of coordinates would have had a smaller distance:</p><p>Looking at the list of points, I've noticed a pattern: the points can be split into groups where some coordinates are fixed small ones (for example the group starting with <span style="font-family: courier;">2 2</span> ...), and the remaining coordinates take all possible combinations with a given sum or within a given range of sums. This makes sense, as essentially we're saying that achieving a certain combination of small coordinates potentially wastes some of the small moves and may also take away some flexibility from the remaining coordinates because the small moves are not available there. And it seems that the largest "small" coordinate to take into account is 6, based on the point <span style="font-family: courier;">1 6 6 51</span>.</p><p>So what I tried to do during the round is to find the smallest and largest sum of remaining coordinates for each possible set of small coordinates for the first 15 moves, assume that all possible combinations of large coordinates between those bounds are valid, and further assume that the bounds just move by (s+1)+(s+2)+(s+3)+(s+4) when going from s moves to s+4 moves. It seemed logical to assume the same structure between s and s+4 because of how the parities of s*(s+1)/2 change. I could not finish coding the part that counted the actual answer to the problem (taking the given parallelepiped into account).</p><p>When I did finish coding it after the contest, it turned out that there were also two flaws in the above hypotheses. First, not all combinations of large coordinates with the sum between the smallest and the largest sum are valid. It turns out that for each particular sum, either all combinations with this sum are valid, or all are not, and the invalid sums are always close to the boundaries. It makes sense in retrospect since if we have spent, say, 1 and 2 on the small coordinates, then there is no way to achieve the sum of all others minus 1 or minus 2 with the rest, but we can achieve minus 0 and minus 3. It also turns out that the lower and upper bounds do not shift by the same amount when going from s to s+4, instead the lower bound moves slower, because the segment expands. This also makes perfect sense in retrospect, as s*(s+1)/2 grows non-linearly. Overall, finishing the code, then finding and fixing those two flaws took me about an hour after the contest. So I was not that close to getting it accepted during the round, but at least I was moving in the right direction :)</p><p>Here is <a href="https://codeforces.com/contest/1854/problem/C">problem C</a>, which I had no idea how to even approach during the round, but which has the most beautiful solution: you have a set <i>S</i> of integers between 1 and <i>M</i> (<i>M</i><=500). In one operation, you pick an element of the set uniformly at random, and increment it by 1. If the incremented element coincides with another element of the set, we keep only one copy, so the size of the set decreases by 1. If the incremented element exceeds <i>M</i>, we discard it, so the size of the set also decreases by 1 in that case. We are given the starting set <i>S</i>, and need to find the expected number of steps before it becomes empty.</p><p>Wow, this may be the longest I have ever written about one contest, and I haven't even started talking about problem E which stirred <a href="https://codeforces.com/blog/entry/118631?#comment-1053106">some</a> <a href="https://codeforces.com/blog/entry/118631?#comment-1053112">controversy</a>. As I said before, I quite liked the round :)</p><p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhndpBnOcwmih13OtlbHzYBBCuCXULBTQ-BW-L4o4ZI-6i1M_seZ31NQj2pBorLKNgfjJjMQHRaoFUYFJ-sRbbiLHSqaSnbu9jE6B4dLRD3kQcSIdMqIev09k8oO8gPqEAbwjOkGoj9qv99SRvMWNKszTfS9sGvX2D90DLpNUj6e6yaMAV8Vn9hAkJOTpU/s834/agc063top5.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="351" data-original-width="834" height="270" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhndpBnOcwmih13OtlbHzYBBCuCXULBTQ-BW-L4o4ZI-6i1M_seZ31NQj2pBorLKNgfjJjMQHRaoFUYFJ-sRbbiLHSqaSnbu9jE6B4dLRD3kQcSIdMqIev09k8oO8gPqEAbwjOkGoj9qv99SRvMWNKszTfS9sGvX2D90DLpNUj6e6yaMAV8Vn9hAkJOTpU/w640-h270/agc063top5.png" width="640" /></a></div>AtCoder Grand Contest 063 wrapped up the week on Sunday (<a href="https://atcoder.jp/contests/agc063/tasks">problems</a>, <a href="https://atcoder.jp/contests/agc063/standings">results</a>, top 5 on the left, <a href="https://atcoder.jp/contests/agc063/editorial">analysis</a>). Huge congratulations to zhoukangyang for solving five problems — so far I cannot imagine how this is possible :)<div><br /></div><div>I've earned a respectable 345th place by solving two problems, and even that was not easy — I was stuck with a wrong (and more difficult to implement) approach in B for quite some time. I had no idea how to solve C after thinking about it for a long time, and I could not solve E or F after thinking about them for a bit. I solved D relatively quickly, but spent more than an hour implementing it. I had the solution for ready about 20 minutes before the end, but could not find all bugs in time.</div><div><br /></div><div>Well, let's hope the bad results will all be spent during the regular AGCs and I will get to shine at the World Tour Finals in Tokyo in September :)</div><div><br /></div><div>In following this post's tradition, here is <a href="https://atcoder.jp/contests/agc063/tasks/agc063_c">problem C</a> that I had no idea how to solve during the round: you are given <i>N</i><=1000 pairs of integers (<i>A<sub>i</sub></i>,<i>B<sub>i</sub></i>), each integer between 0 and 10<sup>9</sup>. In one operation, you choose two integers <i>x</i><<i>y</i> between 0 and 10<sup>18</sup>, and replace each <i>A<sub>i</sub></i> with (<i>A<sub>i</sub></i>+<i>x</i>) mod <i>y</i> (note that you apply the same <i>x</i> and <i>y</i> to all <i>A<sub>i</sub></i>). You need to make it so that <i>A<sub>i</sub></i>=<i>B<sub>i</sub></i> for all i after at most <i>N</i> operations, or report that it is impossible. </div><div><p></p><p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjzKkOcQ6a9ElEUtu6tznHBEZVnh9ITJT1lkgR7u2NdWjvdjxBzS7QD4OIUBx7xMCkNTgmQfdKqL9XfxO5s3scJszrfV1HYt7LdigV3CC_SSbaqXiZgAb20Ooc9WVobYjnScuB1YKyuwXBwEFKJvAmnb7H4feFoBYCnQNWFkTvwmC0flcynn0niUsGjiJg/s4032/PXL_20230513_160333901.jpg" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="3024" data-original-width="4032" height="480" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjzKkOcQ6a9ElEUtu6tznHBEZVnh9ITJT1lkgR7u2NdWjvdjxBzS7QD4OIUBx7xMCkNTgmQfdKqL9XfxO5s3scJszrfV1HYt7LdigV3CC_SSbaqXiZgAb20Ooc9WVobYjnScuB1YKyuwXBwEFKJvAmnb7H4feFoBYCnQNWFkTvwmC0flcynn0niUsGjiJg/w640-h480/PXL_20230513_160333901.jpg" width="640" /></a></div>In <a href="https://petr-mitrichev.blogspot.com/2023/07/an-egoi-week.html">my previous summary</a>, I have mentioned <a href="https://egoi23.se/assets/tasks/day1/findthebox.pdf">an EGOI problem</a>: you are given a HxW grid (H,W <= 50), where some unknown cell of the grid contains an obstacle: a box that cannot be moved. You can send a robot onto the grid in order to determine the location of the box. In one visit, you give the robot a program consisting of characters <span style="font-family: courier;"><</span>, <span style="font-family: courier;">></span>, <span style="font-family: courier;">^</span> and <span style="font-family: courier;">v</span>. The robot starts the visit at the cell (0,0), and then executes your program (> corresponds to moving one cell right, and so on). If a certain move is not possible, either because it would cause the robot to move outside the grid, or because the robot would end up in the cell with the obstacle, the corresponding command is ignored and the execution of the rest of the program continues. You do not observe the robot's movements; instead, you only receive the final coordinates of the robot after executing all commands from the program given for the visit. In the next visit, the robot will start from the cell (0,0) again. To get the full score in this problem, you have to determine the location of the box in just 2 visits. Bonus points (not really) if the total number of commands used throughout all visits is H*W+O(H+W).<p></p><p>When I was thinking about this problem, the key idea to deal with the unknown location of the box was to find such a sequence of moves so that if we have already found the box, then we would stay in the same place, and if not, we would continue looking for it. For example, suppose the box is directly to the left of the robot, and the grid boundary is reasonably far away. Then after performing the sequence of moves <span style="font-family: courier;">v<^</span><span style="font-family: courier;">></span><span style="font-family: courier;">^</span> the robot returns to the same place, since the <span style="font-family: courier;">^</span><span style="font-family: inherit;"> m</span>ove in the middle is blocked by the box. However, if there is no box next to the robot, performing this sequence would result in the robot moving one cell up. We can construct similar sequences for moving one cell down, to the left and to the right, while keeping the property that if the box is directly to the left of the robot, the robot stays in place.</p><p>This allows us to go looking for the box, and if we approach it from the right, then we will stay next to it forever, which allows to determine the location of the box from the final location of the robot by just subtracting 1 from the column.</p><p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh6SoWI7ujGfOV4CPK8O2_7-exUXe6HG1sEiAMNat3UuN7h-UlugcnvtFu65ga62wFwmnLrntAWFPYVK2FQAJb5OJlT3wYSGPO14kYBGSQZZGfrCO1pWdSW6VmxKGnnCBAaIjYPZN-2TLX4XjTd4gd6QFmCcaOSdcd8UtrR4TofPsTY7Toz0wGu_nzVbWU/s2957/PXL_20230729_101344069~2.jpg" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" data-original-height="1311" data-original-width="2957" height="178" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh6SoWI7ujGfOV4CPK8O2_7-exUXe6HG1sEiAMNat3UuN7h-UlugcnvtFu65ga62wFwmnLrntAWFPYVK2FQAJb5OJlT3wYSGPO14kYBGSQZZGfrCO1pWdSW6VmxKGnnCBAaIjYPZN-2TLX4XjTd4gd6QFmCcaOSdcd8UtrR4TofPsTY7Toz0wGu_nzVbWU/w400-h178/PXL_20230729_101344069~2.jpg" width="400" /></a></div>If we know that the box is not on the boundary of the grid, then we can actually determine its location in just one visit: first we go right W-1 times, then move down once, so that we are in the cell (1,W-1). If the box is in the cell (1,W-2), then we are already directly to the right of it, as we need for the above approach. So from this point on we move only using the special sequences mentioned above, to avoid losing the box if we have already found it. First we use the "down" sequence H-3 times, so that if the box is in the column W-2, we find it and stick to it. Then we use the "left" sequence once, then the "up" sequence H-3 times, then the "left" sequence once, and so on.<p></p><p>How do we deal with the boundary? Since the boundary has not so many cells, my approach was to try different ways of going through those cells, and to see if the final location will tell us enough information if one of those cells contained an obstacle. After a couple of experiments, the following approach bore fruit: during the first visit, we go right W-1 times, then down H-1 times, then left W-2 times.</p><p>If there was an obstacle in row 0, we hit it when going right, so we went right at most W-2 times, and therefore we end up in the cell (H-1,0). If there was an obstacle in cell (R,W-1) for any R>0, we hit it when going down, so we end up in the cell (R-1,1). If there was an obstacle in cell (H-1,C) for any 0<C<W-1, we hit it when going left, so we end up in the cell (H-1,C+1). Finally, if we did not hit any obstacles we end up in the cell (H-1,1).</p><p>It means that if the obstacle was on the right or bottom boundary, we already know its location, if it's on the top boundary, we know it's there but don't know the exact location, and if it's on the left boundary or inside the grid, we still do not know anything. Dealing with the top boundary is easy: during the second visit we just go right W-1 times and see where we stop.</p><p>Now we just need to deal with the case where the obstacle is inside the grid or on the left boundary. We have described the approach for the obstacle inside the grid above, but one can notice that it also works for the left boundary if we end up walking through column 1 using the "down" sequences. This happens automatically if W is even, and if W is odd, we can change the direction once to achieve this, for example we can start from (H-2,W-1) instead of (1,W-1) in the very beginning. Therefore we can find the box during the second visit in this case as well.</p><p>This solution uses about 5*H*W moves, because our sequences for "down" and "up" have 5 moves each. However, one can process the "down" and "up" moves in batches: to move up many times, one can do <span style="font-family: courier;">v<^^^...^^^</span><span style="font-family: courier;">></span><span style="font-family: courier;">^</span>, which brings the number of moves per cell of the grid to 1, notwithstanding a linear number of additional moves: H*W+O(H+W) (the number of moves during the first visit is linear, so it does not change anything). I like it because it's asymptotically optimal: it is not hard to prove that we must try to enter each cell except maybe one at least once, so we need at least H*W-2 moves in any solution.</p><p>A few days later, I've noticed a different way to look at my solution: if we forget about the boundaries of the grid for a second and assume it is infinite (but the box is still within the given rectangle), then under certain assumptions the problem is equivalent to the following: the box is actually movable (like in the Sokoban game), and we need to bring it to a concrete location no matter where it starts. To see this eqivalence, we can say that every time we try to move towards the box and can't, we can shift the coordinate system by 1 instead, which means that the immovable box has effectively moved :) And I think the solution is much easier to find in this equivalent formulation.</p><p>Note that <a href="https://egoi23.se/assets/solutions/day1/findthebox.pdf">the author's solution</a> is completely different: it needs to divide the grid into two halves! However, it also has the property of using only H*W+O(H+W) moves in total. Did you end up using an approach that differs from both?</p><p>Thanks for reading, and check back next week!</p></div>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com0tag:blogger.com,1999:blog-1953325079793449971.post-57862577156609516462023-07-23T20:46:00.000+02:002023-07-23T20:46:23.004+02:00An EGOI week<p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh3AMa5v2CQImDlLmkq1epARTUN_gPxtWfiszVwnA3dVQbtQ6VOTHfWoxQyFmLbEfe5rUzy6toQYtz2n9jb88y-FFSkJkvh2gGYv8VkE28h3aCt9nt7I1aVx2q4BuVCEVr42QA82TSVoK8WLTIpA8MCRVk1ZAQmqJqpXOBYbSAO3wJWoiURBuj0SFlLjVc/s1177/egoi23top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="330" data-original-width="1177" height="181" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh3AMa5v2CQImDlLmkq1epARTUN_gPxtWfiszVwnA3dVQbtQ6VOTHfWoxQyFmLbEfe5rUzy6toQYtz2n9jb88y-FFSkJkvh2gGYv8VkE28h3aCt9nt7I1aVx2q4BuVCEVr42QA82TSVoK8WLTIpA8MCRVk1ZAQmqJqpXOBYbSAO3wJWoiURBuj0SFlLjVc/w640-h181/egoi23top5.png" width="640" /></a></div>EGOI 2023 in Lund, Sweden was the main event of the week (<a href="https://egoi23.se/competition/tasks">problems</a>, <a href="https://egoi23.se/scoreboard/">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/118430">discussions</a>). Congratulations to all participants and especially to the medalists!<p></p><p>This was the third overall and the second onsite edition of the <a href="https://egoi23.se/about/">European Girls' Olympiad in Informatics</a>, and I'm very happy to support this great event. I was onsite as a problem author, but my problem did not end up being used for the competition, therefore my contribution this time was not very significant. Still, being there and feeling the awesome onsite programming contest atmosphere again finally gave me enough motivation to restart this blog :) I was also very impressed with Lund, even though we mostly explored its playgrounds.</p><p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhrvcIx5LIJz_rzmkhtADpmFh0wCs9OPk00LOYiV-jQqHknW3vnhr058uf38E50ZZHaiO3rq93Fghxzt4c-tq6kutmgbAeDYdOqLzb0YjU69yU33UeVmD_-kc0dpBHusrxqDfLP0Ynj05cAy9tdaqYNysuAV2XDBjMJgIgN6f3jH2u4KOBxOb4n5OTA6W4/s715/egoi23robotpic.png" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" data-original-height="596" data-original-width="715" height="267" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhrvcIx5LIJz_rzmkhtADpmFh0wCs9OPk00LOYiV-jQqHknW3vnhr058uf38E50ZZHaiO3rq93Fghxzt4c-tq6kutmgbAeDYdOqLzb0YjU69yU33UeVmD_-kc0dpBHusrxqDfLP0Ynj05cAy9tdaqYNysuAV2XDBjMJgIgN6f3jH2u4KOBxOb4n5OTA6W4/s320/egoi23robotpic.png" width="320" /></a></div>Of the problems that did make it to the problemset, I'd like to highlight <a href="https://egoi23.se/assets/tasks/day1/findthebox.pdf">problem C</a> from the first day: you are given a HxW grid (H,W <= 50), where some unknown cell of the grid contains an obstacle: a box that cannot be moved. You can send a robot onto the grid in order to determine the location of the box. In one visit, you give the robot a program consisting of characters <span style="font-family: courier;"><</span>, <span style="font-family: courier;">></span>, <span style="font-family: courier;">^</span> and <span style="font-family: courier;">v</span>. The robot starts the visit at the cell (0,0), and then executes your program (> corresponds to moving one cell right, and so on). If a certain move is not possible, either because it would cause the robot to move outside the grid, or because the robot would end up in the cell with the obstacle, the corresponding command is ignored and the execution of the rest of the program continues. You do not observe the robot's movements; instead, you only receive the final coordinates of the robot after executing all commands from the program given for the visit. In the next visit, the robot will start from the cell (0,0) again. To get the full score in this problem, you have to determine the location of the box in just 2 visits. Can you see how to do it? Bonus points (not really) if the total number of commands used throughout all visits is H*W+O(H+W).<p></p><p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhzsr_gdqh8OVIUHZAjX5Tm-ax0EaAtYpjhBQKy-5Y-GWA-insjWbkkdsuzb45kEBytWZdL1NsEVUGVjoA1W9Y5LEjF10Q3tcjZFY40B3wRQVHW1ed9nLE5SeqfUNA6eCU7s2aBFy7b4mpN7JOA7x7NBXGUakcVyeyzGPEFT1dPidcBABzMfTg2ae5tuBs/s1317/cf887top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="346" data-original-width="1317" height="168" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhzsr_gdqh8OVIUHZAjX5Tm-ax0EaAtYpjhBQKy-5Y-GWA-insjWbkkdsuzb45kEBytWZdL1NsEVUGVjoA1W9Y5LEjF10Q3tcjZFY40B3wRQVHW1ed9nLE5SeqfUNA6eCU7s2aBFy7b4mpN7JOA7x7NBXGUakcVyeyzGPEFT1dPidcBABzMfTg2ae5tuBs/w640-h168/cf887top5.png" width="640" /></a></div>Codeforces Round 887 wrapped up the week (<a href="https://codeforces.com/blog/entry/116916">problems</a>, <a href="https://codeforces.com/contest/1852/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/116940">analysis</a>). Even rainboy <a href="https://codeforces.com/submissions/rainboy/contest/1852">was not able</a> to solve the last problem, but the remaining five provided enough of a challenge even for the top participants. Rebelz was a bit faster but made one wrong submission on E, which proved decisive as it dropped them two points behind jiangly. Congratulations to both on the great performance!<p></p><p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjKY-EmwudZY8CMQt4TI8aEfNX-1VTABFxUN-VevI0CEBW7XbqRNW3FqlnhbDLBSLz5zJxsTy5sreyTKw4UGh3ZMkx6G97KR5KFqgWSYv56WrpH3UmbyIzzC3Mena_SdRG67BEysPt4WYlTB1wcG8xsUSyaNkzHvBnmEZT2om5VfFUnz8iD8Jv2P-6OHAE/s3705/PXL_20230718_172243427-EDIT.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="2829" data-original-width="3705" height="488" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjKY-EmwudZY8CMQt4TI8aEfNX-1VTABFxUN-VevI0CEBW7XbqRNW3FqlnhbDLBSLz5zJxsTy5sreyTKw4UGh3ZMkx6G97KR5KFqgWSYv56WrpH3UmbyIzzC3Mena_SdRG67BEysPt4WYlTB1wcG8xsUSyaNkzHvBnmEZT2om5VfFUnz8iD8Jv2P-6OHAE/w640-h488/PXL_20230718_172243427-EDIT.jpg" width="640" /></a></div>As this blog has been dormant for quite some time, it is a good time to ask: what do you think about the format? Do you have suggestions on what I should remove, add, or do more often? Of course, I don't promise to follow the suggestions, but I will consider :)<p></p><p>Thanks for reading, and check back next week!</p>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com2tag:blogger.com,1999:blog-1953325079793449971.post-90578471904994688422022-02-20T20:55:00.003+01:002022-02-21T10:08:36.902+01:00A Berlekamp-Massey week<p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/a/AVvXsEhKgDYszpx-ln4EVKB4qYifGq0ikpHD5Iw2RYbECDLmpwgoaPaEMtV_1ubhLa5YK-8EJjPXWpN40ET04dspnR2HkkGhAiTR2z2miAx95M6tfAydys2W6jBa7B1zXyzHHxsXrXa6cZiNSFOn-mvQ27VFrmMM5PsY2ipRnAX18IEVgSUN2pevyStq4a7B=s633" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="98" data-original-width="633" src="https://blogger.googleusercontent.com/img/a/AVvXsEhKgDYszpx-ln4EVKB4qYifGq0ikpHD5Iw2RYbECDLmpwgoaPaEMtV_1ubhLa5YK-8EJjPXWpN40ET04dspnR2HkkGhAiTR2z2miAx95M6tfAydys2W6jBa7B1zXyzHHxsXrXa6cZiNSFOn-mvQ27VFrmMM5PsY2ipRnAX18IEVgSUN2pevyStq4a7B=s16000" /></a></div>TopCoder SRM 824 was the first event of this week (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=19053">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=19053&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://youtu.be/G0oaopqeclQ">my screencast</a>, <a href="https://clist.by/standings/tco22-algorithm-stage-3-28608402/">TCO race standings</a>). I had some kind of blackout and could not solve the medium, which in retrospect was quite standard. However, the hard was also quite standard and straightforward for me, while many others failed to get all details correctly, so the end result was not so bad. Still, I could not really compete with <a href="https://cphof.org/profile/topcoder:Um_nik">Um_nik</a> and <a href="https://cphof.org/profile/icpc:Yahor%20Dubovik">mhq</a> who solved all three problems. Well done!<p></p><p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/a/AVvXsEh_0-OnIKUMQxNW0g_ood27hzob97iWV6Sj_SNTil_s1ok7FCX7Lz-vaOFfibFVcyfoMzs_zh6A-Hx71xwyjVAn_a9bbY0iCazRlw3F3EDXANamJVDxO5BR8Q6FVX_pipxbTDrsu0KPY_RLpLm21wITke60rSZ4H7-aC8xUP_3VZl6On_k0IOIAGeo-=s1050" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="241" data-original-width="1050" height="146" src="https://blogger.googleusercontent.com/img/a/AVvXsEh_0-OnIKUMQxNW0g_ood27hzob97iWV6Sj_SNTil_s1ok7FCX7Lz-vaOFfibFVcyfoMzs_zh6A-Hx71xwyjVAn_a9bbY0iCazRlw3F3EDXANamJVDxO5BR8Q6FVX_pipxbTDrsu0KPY_RLpLm21wITke60rSZ4H7-aC8xUP_3VZl6On_k0IOIAGeo-=w640-h146" width="640" /></a></div>Open Cup has returned from its winter break with the Grand Prix of Kyoto on Sunday (<a href="http://opentrains.snarknews.info/~ejudge/res/res10570">results</a>, top 5 on the left). Team USA1 continued their domination of this Open Cup season, finishing all problems a good hour before any other team, and with just one incorrect attempt to boot. Very impressive!<div><br /></div><div>Our team struggled quite a bit with the two mathy problems H and M, until Google and OEIS came to the rescue. In problem M, I found the <a href="https://oeis.org/A220094">answers to a simplified problem</a> in OEIS, noticed a linear recurrence as one of the methods to compute it, and then hypothesized that the answers to the full problem can also be determined using a linear recurrence :) And in problem H, I had to do <a href="https://codeforces.com/blog/entry/100143?#comment-888479">a quick dive</a> into some mathematical concepts that were new to me.</div><div><br /></div><div>I have found problem J the most beautiful in this round: you are given a string of length <i>n</i> (<i>n</i><=200000) with characters <span style="font-family: courier;">+</span>, <span style="font-family: courier;">-</span> and <span style="font-family: courier;">?</span>, and two numbers <i>a</i> and <i>b</i>. You can replace each <span style="font-family: courier;">?</span> character with either <span style="font-family: courier;">+</span> or <span style="font-family: courier;">-</span>. Then you need to find a <i>balanced</i> substring of the string, which means a substring of length <i>a</i>+<i>b</i> that has exactly <i>a</i> <span style="font-family: courier;">+</span> characters and <i>b</i> <span style="font-family: courier;">-</span> characters, in any order, and remove it from the string (the parts before and after the substring being removed become adjacent to each other). Then you need to find a balanced substring in the remaining string, and remove it from the string, and so on. You goal is to replace the <span style="font-family: courier;">?</span> characters in such a way that the number of times you can remove a balanced substring is maximum possible (this number of times will never exceed <i>n</i>/(<i>a</i>+<i>b</i>) since we would run out of characters). How to find this maximum number of times?</div><div><p></p><p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/a/AVvXsEgq-NjN_3-Ud-T5Es94eQd6Zl8LCrSfbLoJhzjFwISuJooVsvY6fCLOHW4NDvGBSI8DcZVPsNFdFjzawDhCl-p2A9l79ugV7crS68Q06OSzSJGYgGGa-48jnVWXPKRywL1XkymG3Sl_yiRZ0cCZ3ToIR_RtWnJGDreZV0wAVgpDRAIJPFxHelaBIT1e=s4032" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="3024" data-original-width="4032" height="480" src="https://blogger.googleusercontent.com/img/a/AVvXsEgq-NjN_3-Ud-T5Es94eQd6Zl8LCrSfbLoJhzjFwISuJooVsvY6fCLOHW4NDvGBSI8DcZVPsNFdFjzawDhCl-p2A9l79ugV7crS68Q06OSzSJGYgGGa-48jnVWXPKRywL1XkymG3Sl_yiRZ0cCZ3ToIR_RtWnJGDreZV0wAVgpDRAIJPFxHelaBIT1e=w640-h480" width="640" /></a></div>In <a href="https://petr-mitrichev.blogspot.com/2022/02/a-global-week.html">my previous summary</a>, I have mentioned <a href="https://codeforces.com/contest/1637/problem/G">a Codeforces problem</a>: you are given a single integer <i>n</i>. You start with a sequence of numbers 1, 2, 3, ..., <i>n</i>. In one step, you can take any two numbers <i>x</i> and <i>y</i>, and replace them with <i>x</i>+<i>y</i> and |<i>x</i>-<i>y</i>|. Your goal is to make all numbers equal, and you also need to make those equal final numbers as small as possible, and you need to do all this in at most 20<i>n</i> steps.<p></p><p>I was not sure how to even approach this problem, so I started by implementing a brute force solution that found me the answers for all values of <i>n</i> up to 15. The brute force returns that for <i>n</i>=3,4 we can make all numbers equal to 4, for <i>n</i>=5,6,7,8 we can make all numbers equal to 8, and for <i>n</i>=9,10,11,12,13,14,15 we can make all numbers equal to 16. This naturally suggests that we need to target the smallest power of two that is at least <i>n</i>. I did not prove this fact during the contest, but there exists <a href="https://codeforces.com/blog/entry/99776?#comment-886289">a very simple proof</a>.</p><p>Apart from this observation, looking at the way the brute force achieved the goal helped me learn a couple of tricks that are useful for the solution. First of all, when we have a 0, then we can double any number: (0,<i>x</i>)->(<i>x</i>,<i>x</i>)->(0,2<i>x</i>). Second, the solution often makes many smaller powers of two, and then makes them all equal using this trick.</p><p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/a/AVvXsEjFVPWOW7EtmIrvs0IQ3NMcLrgEHc5lbwu8n5HeWbVSuniXQa5UT5bIWnrZ86-_NmiPGxVfqPI3_pPQXbnHPyYGyFjBKdWtyE6GnqbJdXh5BW7Mf80XSq5tlNypYGpVEf8RcD9sGHBS6EU-zXFrgRnTijQ-Uf1dbV3sg1N__8DmSdMJPSSi51-HGbWr=s2353" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" data-original-height="780" data-original-width="2353" height="133" src="https://blogger.googleusercontent.com/img/a/AVvXsEjFVPWOW7EtmIrvs0IQ3NMcLrgEHc5lbwu8n5HeWbVSuniXQa5UT5bIWnrZ86-_NmiPGxVfqPI3_pPQXbnHPyYGyFjBKdWtyE6GnqbJdXh5BW7Mf80XSq5tlNypYGpVEf8RcD9sGHBS6EU-zXFrgRnTijQ-Uf1dbV3sg1N__8DmSdMJPSSi51-HGbWr=w400-h133" width="400" /></a></div>So now we need to convert all numbers into powers of two, not necessarily equal ones. Suppose 2<sup><i>k</i></sup> is the smallest power of two bigger than <i>n</i> (we assume <i>n</i> is not a power of two, as for that case we can just use the solution for <i>n</i>-1 without touching the number <i>n</i> at all). We can apply the operation to <i>n</i> and 2<sup><i>k</i></sup>-<i>n</i>, <i>n</i>-1 and 2<sup><i>k</i></sup>-(<i>n</i>-1), and so on, 2<sup><i>k-1</i></sup>+1 and 2<sup><i>k-1</i></sup>-1. This way, we will get many copies of 2<sup><i>k </i></sup>as sums, and from the differences we will get numbers 2<i>n</i>-2<sup><i>k</i></sup>, 2<i>n</i>-2<sup><i>k</i></sup>-2, ..., 6, 4, 2. And we also have the remaining numbers which we did not touch, those are 2<sup><i>k-1</i></sup> and 1, 2, ..., 2<sup><i>k</i></sup>-<i>n</i>-1. 2<sup><i>k </i></sup>and 2<sup><i>k-1</i></sup> are already powers of two so we don't need to do anything. And for the two chains 1, 2, ..., 2<sup><i>k</i></sup>-<i>n</i>-1 and 2, 4, 6, ..., 2<i>n</i>-2<sup><i>k</i></sup>-2, 2<i>n</i>-2<sup><i>k</i></sup> we can just apply the same algorithm recursively: directly for the first chain, and doing a recursive call for 1, 2, 3, ..., <i>n</i>-2<sup><i>k</i>-1</sup> and multiplying all results by two for the second chain.<p></p><p>This way we will convert all numbers into powers of two not exceeding 2<sup><i>k</i></sup>. It turns out that for <i>n</i>>=3 at least two of those powers will be equal and less than 2<sup><i>k</i></sup>, which allows us to use the (<i>x</i>,<i>x</i>)->(0,2<i>x</i>) step to get a zero, and then use this zero to keep multiplying all numbers by two until we have only one zero and many 2<sup><i>k</i></sup>, and finally use the (0,<i>x</i>)->(<i>x</i>,<i>x</i>) step to get rid of the zero.</p><p>Thanks for reading, and check back next week!</p></div>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com0tag:blogger.com,1999:blog-1953325079793449971.post-50623236412070955512022-02-13T18:30:00.002+01:002022-02-20T17:37:51.152+01:00A global week<p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/a/AVvXsEgT0J4KuBLQe1MOpwMW68z4mIpaMBO9hW08wZsHfrsN-m8uIKWRDVLlaruH5ts_-D5kqQO4HfLVI4S_gvf7U7Ywk5giBrSzUAjfI46PWvtwgndyBfARiISy_oBunuz_TweW--T8kpn4uGKroHKEnR4uQqI2pOI0Y-pkVQkJ9jzNRS5Ec2IPQtskuIHW=s1101" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="281" data-original-width="1101" height="164" src="https://blogger.googleusercontent.com/img/a/AVvXsEgT0J4KuBLQe1MOpwMW68z4mIpaMBO9hW08wZsHfrsN-m8uIKWRDVLlaruH5ts_-D5kqQO4HfLVI4S_gvf7U7Ywk5giBrSzUAjfI46PWvtwgndyBfARiISy_oBunuz_TweW--T8kpn4uGKroHKEnR4uQqI2pOI0Y-pkVQkJ9jzNRS5Ec2IPQtskuIHW=w640-h164" width="640" /></a></div>Codeforces Global Round 19 was the only round of this week (<a href="https://codeforces.com/contest/1637">problems</a>, <a href="https://codeforces.com/contest/1637/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/99883">analysis</a>). <a href="https://cphof.org/profile/topcoder:tourist">tourist</a> and <a href="https://cphof.org/profile/topcoder:Um_nik">Um_nik</a> were pretty close, but Um_nik's two wrong attempts on E have set him back both in terms of points and in terms of contest time, so tourist came out on top. Congratulations!<p></p><p>Also well done to <a href="https://cphof.org/profile/codeforces:Maksim1744">Maksim1744</a> for being the only other contestant to solve all problems. I have solved problem G at roughly the same time as him, but have more or less given up on solving H in the remaining time, while he persevered and was rewarded with the third place.</p><p>I think <a href="https://codeforces.com/contest/1637/problem/F">problem F</a>, while a bit standard, was quite educational, so I encourage you to check it out as a good practice opportnity. However, since the last problem I described in this blog was also of this kind, let me instead focus on the very original <a href="https://codeforces.com/contest/1637/problem/G">problem G</a>: you are given a single integer <i>n</i>. You start with a sequence of numbers 1, 2, 3, ..., <i>n</i>. In one step, you can take any two numbers <i>x</i> and <i>y</i>, and replace them with <i>x</i>+<i>y</i> and |<i>x</i>-<i>y</i>|. Your goal is to make all numbers equal, and you also need to make those equal final numbers as small as possible, and you need to do all this in at most 20<i>n</i> steps. Can you see a way? At least for me, it was quite helpful to experiment on a computer instead of just solving on paper.</p><p>Thanks for reading, and check back next week!</p>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com2