tag:blogger.com,1999:blog-19533250797934499712024-07-19T09:45:21.329+02:00Algorithms Weekly by Petr MitrichevPetr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.comBlogger540125tag:blogger.com,1999:blog-1953325079793449971.post-14704873828617689742024-07-14T14:06:00.000+02:002024-07-14T14:06:02.043+02:00An ecnerwala week<p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiA7c0hawy4XEcqOPYwdMusrzrCAT6PPXJRZ8p6EZdQhyphenhyphen8gbV71Ssv08LJW2osaqvEVvBHqnvxlVrpdXus2jqH7dLgWup_KcqQ1n1d3Krt_aLqi2vcJihj75LoA-cZYRHZxKDJdWDk_qf0iJP5Euy1QBYPHg0dJh1mmUTLwTk6QO28O62PCJ5S0YJ-UK7g/s4080/PXL_20240220_113500134-EDIT.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="2341" data-original-width="4080" height="368" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiA7c0hawy4XEcqOPYwdMusrzrCAT6PPXJRZ8p6EZdQhyphenhyphen8gbV71Ssv08LJW2osaqvEVvBHqnvxlVrpdXus2jqH7dLgWup_KcqQ1n1d3Krt_aLqi2vcJihj75LoA-cZYRHZxKDJdWDk_qf0iJP5Euy1QBYPHg0dJh1mmUTLwTk6QO28O62PCJ5S0YJ-UK7g/w640-h368/PXL_20240220_113500134-EDIT.jpg" width="640" /></a></div>AWTF24 was the main event of this week. I have mentioned its results in the <a href="https://blog.mitrichev.ch/2024/07/awtf24-contest.html">previous post</a>, so I want to use this one to discuss its problems briefly.<p></p><p>Problems A and B both had short solutions and were quick to implement, but required one to come up with a beautiful idea somehow. When Riku was explaining their solutions during the broadcast, I was amazed but could not understand how to come up with them :) One way to do it, at least for problem A, was to actually start by assuming the problem is beautiful, and to try coming up with some beautiful lower or upper bound for the answer, which can turn out to be the answer.</p><p>To test if you can walk this path, here is the <a href="https://atcoder.jp/contests/awtf2024-open/tasks/awtf2024_a">problem statement</a>: you are given <i>n</i><=250000 slimes on a number line, each with weight 1. You need to choose <i>k</i> of them, all others will be removed. Then, they will start moving: at each moment in time, every slime moves with velocity <i>r</i>-<i>l</i>, where <i>r</i> is the total weight of all slimes to the right of it, and <i>l</i> is the total weight of all slimes to the left of it. When <i>r</i>-<i>l</i> is positive, it moves to the right, and when it is negative, it moves to the left. Since this rule pushes the slimes towards each other, sometimes they will meet. When two or more slimes meet, they merge into one slime with weight equal to their total weight, which continues to move according to the above rule. Eventually, all slimes will merge into one stationary slime, suppose this happens at time <i>t</i>. What is the maximum value of <i>t</i>, given that you can choose the <i>k</i> slimes to use freely?</p><p>Problem D turned out to be equivalent to an <a href="https://codeforces.com/contest/1637/problem/H">old Codeforces problem</a> applied to the inverse permutation. Most of this week's finalists have participated in that round or upsolved it, so it was not too unfair. The top two contestants ecnerwala and zhoukangyang did solve the Codeforces problem back in 2022, but did not remember it, and implemented the solution to D from scratch (even though of course having solved the old problem might have helped come up with the correct idea here). ksun48 and heno239 in places 3 and 4 did copy-paste their code from 2022.</p><p>Problems C and E involved a bit more code and effort to figure out all details, but one could make gradual progress towards a solution when solving them, instead of having to pull a beautiful idea out of thin air. Were I actually participating in this round, I would most likely spend the most time on, and maybe even solve those two problems.</p><p>Overall, this was a very nice round, and I'm looking forward to more AGCs in 2024 to try my hand at more amazing problems!</p><p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjnEfTzbZB_FN3tXDqXDrhL4juOearL80B27HBgNsIcsGYBjBMDP7ZP8yDNIPOYXGXOqP5E1ZrYfH1SbG_vwmhyphenhyphen5nNLNOPiXuj0ZREZ8Snd4qv0IvjsG9UzrPNsc125YeIcIMJTaavipdBxJkKjJDfhr9Mkhbsctr2dcTtv0nctuwm0ajSuHKv_pw6HEuE/s1268/ucup3r4top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="233" data-original-width="1268" height="118" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjnEfTzbZB_FN3tXDqXDrhL4juOearL80B27HBgNsIcsGYBjBMDP7ZP8yDNIPOYXGXOqP5E1ZrYfH1SbG_vwmhyphenhyphen5nNLNOPiXuj0ZREZ8Snd4qv0IvjsG9UzrPNsc125YeIcIMJTaavipdBxJkKjJDfhr9Mkhbsctr2dcTtv0nctuwm0ajSuHKv_pw6HEuE/w640-h118/ucup3r4top5.png" width="640" /></a></div>On the next day after the AWTF, the 3rd Universal Cup Stage 4: Hongō took place (<a href="https://contest.ucup.ac/contest/1738">problems</a>, <a href="https://contest.ucup.ac/results/QOJ1738">results</a>, top 5 on the left). 8 out of 9 participants from the first three teams (congrats!), which coincidentally are also the first three teams in the <a href="https://ucup.ac/rating">season ranking</a>, were in Tokyo, so Riku and Makoto have organized an onsite version of this stage at the AtCoder office. Solving a 5-hour contest with your team in person instead of online is already much more fun, but having other teams in the room and discussing the problems with them right after the round is even better. I guess I'm still yearning for the Open Cup days :)<p></p><p>I was solving this round together with <a href="https://cphof.org/profile/topcoder:Endagorion">Mikhail</a> and <a href="https://cphof.org/profile/topcoder:rng_58">Makoto</a>. Thanks a lot Makoto for briefly coming out of <a href="https://codeforces.com/blog/entry/86174">retirement</a> to participate, it was great fun solving this round together, and I can confirm that you're still very strong! Maybe we can have another go next year.</p><p><a href="https://contest.ucup.ac/contest/1738/problem/9126">Problem N</a> was not very difficult (I spent at least half an hour without any success, explained the problem to Makoto and he solved it almost immediately), but still enjoyable: you are given a string of length <i>n</i><=500000. We choose one its arbitrary non-empty substring and erase it from this string, in other words we concatenate a prefix and a suffix of this string with total length less than <i>n</i>. There are <i>n</i>*(<i>n</i>+1)/2 ways to do it, but some of them may lead to equal strings. How many distinct strings can we get?</p><p>Thanks for reading, and check back next week.</p>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com1tag:blogger.com,1999:blog-1953325079793449971.post-30604623514147549652024-07-13T17:55:00.000+02:002024-07-13T17:55:43.545+02:00AWTF24 contest<p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjqowRMYE5NoqhaPse-v0NSrrvoR7HPGExbfqWPMZ1RSPSn6ajbn5CZ4FLp_moC7P-PwUs22rMXNPYNY3jdpwCNeq5_8B5k7ZAFLF58j7eT2fnU4kEk9eCHE9RtQ-iABffkW3oCFM4VvpWyIjv_aPMdq1NVN5dg31Sz975_nxoeMOu2HpZChu0MnOiWiEk/s778/awtf24top5.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="360" data-original-width="778" height="296" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjqowRMYE5NoqhaPse-v0NSrrvoR7HPGExbfqWPMZ1RSPSn6ajbn5CZ4FLp_moC7P-PwUs22rMXNPYNY3jdpwCNeq5_8B5k7ZAFLF58j7eT2fnU4kEk9eCHE9RtQ-iABffkW3oCFM4VvpWyIjv_aPMdq1NVN5dg31Sz975_nxoeMOu2HpZChu0MnOiWiEk/w640-h296/awtf24top5.png" width="640" /></a></div>AtCoder World Tour Finals 2024 took place today (<a href="https://atcoder.jp/contests/awtf2024-open/tasks">problems</a>, <a href="https://atcoder.jp/contests/awtf2024/standings">results</a>, top 5 on the left, <a href="https://youtu.be/uajgh54TRu8">broadcast recording</a>, <a href="https://atcoder.jp/contests/awtf2024-open/editorial">analysis</a>). This was my first 5-hour commentating experience, and I enjoyed it a lot! How did it look from your side? Please share your improvement suggestions, just for the <i>remote</i> chance that I do not qualify again :)<p></p><div>This time the contestants had an opportunity to share their thoughts on stream (similar to the "confession booth" concept from some chess tournaments recently), and while not everybody used it, it was great fun and great insight to listen to those who did (<a href="https://youtu.be/uajgh54TRu8?t=13771">for example</a>; did somebody maybe gather all timestamps?). I hope this practice gets expanded and improved at future contests!</div><div><br /></div><div>ecnerwala also tried to share his thoughts before the contest even started, but unfortunately the stream had not started as well at that point and therefore his words were not recorded. Nevertheless, maybe this helped him get into the right mood and solve problem E quickly, which was key to his win. Congratulations to him and to zhoukangyang and ksun48 who also won prizes!</div><div><br /></div><div>Thanks for reading, and check back tomorrow for this week's summary.</div>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com1tag:blogger.com,1999:blog-1953325079793449971.post-50804034112864096472024-07-11T18:15:00.002+02:002024-07-12T07:58:38.618+02:00AWTF24 pre-contest<p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj_ctCrAqOGBHAp6WYymytGxdBs6y_72CW8GnX8jiVdOVuRwviKocDGcRqChKLsslQFQQAs1jnqe3ViMvUTh28RcqeUpECXkU2_Njerc8oAftMjL889bnEC6pApYpqBXYo-o23L08Ff6ab6hvUtc1mrAPbJsM-IR6daZsoxi6dgjiR1XaMbRkfNAwW3iOk/s4080/PXL_20240710_044413505-EDIT.jpg" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="2249" data-original-width="4080" height="352" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj_ctCrAqOGBHAp6WYymytGxdBs6y_72CW8GnX8jiVdOVuRwviKocDGcRqChKLsslQFQQAs1jnqe3ViMvUTh28RcqeUpECXkU2_Njerc8oAftMjL889bnEC6pApYpqBXYo-o23L08Ff6ab6hvUtc1mrAPbJsM-IR6daZsoxi6dgjiR1XaMbRkfNAwW3iOk/w640-h352/PXL_20240710_044413505-EDIT.jpg" width="640" /></a></div>On Wednesday, the contestants were gathering in the hotel. The contestants from Europe and America hat some very long flights behind them, so there was not much appetite for activities. Therefore we played some board games in the hotel lobby in between short excursions to get some Japanese food. We did not actually meet most of the contestants from Asia — maybe the reason was that they actually had more energy for exploring Tokyo and did not hang around in the hotel :)<p></p><div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjp8bnA-em2l-wwcdu-diywrEhFk31Sn49KHH1dFLJmZtKPkSexKIn_Emzmcen2Cy9DHEAt1NbT58KyYauqlctAgYicUp-UgEMG02LoURoHbFgIGpjkrHvvbF5JBGMZLIAVcRp8lbgCV_P_NVXJqyIbjhyphenhyphenzguCrYmP_ewp5OY1hi3PuJ5AB8n-6dX5dyh8/s3452/pxl_20240710_120544108~2.jpg" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" data-original-height="3452" data-original-width="3001" height="400" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjp8bnA-em2l-wwcdu-diywrEhFk31Sn49KHH1dFLJmZtKPkSexKIn_Emzmcen2Cy9DHEAt1NbT58KyYauqlctAgYicUp-UgEMG02LoURoHbFgIGpjkrHvvbF5JBGMZLIAVcRp8lbgCV_P_NVXJqyIbjhyphenhyphenzguCrYmP_ewp5OY1hi3PuJ5AB8n-6dX5dyh8/w348-h400/pxl_20240710_120544108~2.jpg" width="348" /></a></div>The games of choice (well, those were the only ones I brought so there was not <i>that</i> much choice...) were Cascadia and (<a href="https://hanabi.github.io/level-1">Level 1 H-Group</a>) Hanabi. It turns out that the synergies of the H-Group conventions are not so obvious at level 1, so probably next time we introduce somebody to them we should start at least with level 3.</div><div><br /></div><div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgo2bayHBtRlY5QyEJAfZklPv5nh9XxgR-PLE5Fj4m3Wy68sGlHNWwA-8NXJCRF_Y7EFiEPyEINWmLIBvbEnql9Wmtag9LAZyMXz2e7Zl9BX_XzJrF5Zf6gf6d0uIZL1zb7RUj26kgrH0MO6J0hPpHVgxhPr9AVOVklJp2Qeug1Gh-15rIHwgnE763eABg/s1824/tshirts-frame.jpg" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1824" data-original-width="1376" height="400" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgo2bayHBtRlY5QyEJAfZklPv5nh9XxgR-PLE5Fj4m3Wy68sGlHNWwA-8NXJCRF_Y7EFiEPyEINWmLIBvbEnql9Wmtag9LAZyMXz2e7Zl9BX_XzJrF5Zf6gf6d0uIZL1zb7RUj26kgrH0MO6J0hPpHVgxhPr9AVOVklJp2Qeug1Gh-15rIHwgnE763eABg/w301-h400/tshirts-frame.jpg" width="301" /></a></div>We also got to witness the AtCoder admins printing the logos on the official t-shirts, as it turned out that the shop where one can print arbitrary content on a t-shirt in a self-service manner happened to be on the lower floors of the hotel building. Even though this is not much different from a normal printer, seeing how one can slightly adjust the image and then get an actual t-shirt with this image in a couple of minutes was quite impressive.</div><div><br /></div><div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiq1ubc00s9rYA8FTT-kHY_88eWHRE9R7YD3-eD-yzCzx6urpsdpmn3C6hyphenhyphenVY78y1BDkq6tXHaeqA3WXrfB2CK1qJatmYMj8Bn4VOl-s2mjlmVBr2CaDqbEZcMAH9bi2fuXxCrYxEzPSEUsgwudljjlvDsfYFWb2yN1GaLaczjpjPPz2QYSwZ2KPTTz_Nk/s4080/PXL_20240711_051024115-EDIT.jpg" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" data-original-height="3072" data-original-width="4080" height="482" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiq1ubc00s9rYA8FTT-kHY_88eWHRE9R7YD3-eD-yzCzx6urpsdpmn3C6hyphenhyphenVY78y1BDkq6tXHaeqA3WXrfB2CK1qJatmYMj8Bn4VOl-s2mjlmVBr2CaDqbEZcMAH9bi2fuXxCrYxEzPSEUsgwudljjlvDsfYFWb2yN1GaLaczjpjPPz2QYSwZ2KPTTz_Nk/w640-h482/PXL_20240711_051024115-EDIT.jpg" width="640" /></a></div>Today was a free day for the contestants, who have ventured a bit more into the city having rested from their travels. It was still funny with the timezone differences and jetlag, as the same meal was breakfast for me, lunch for the locals, and dinner for the contestants from America. Some contestants warmed up their problem solving capabilities by doing escape rooms, while others opted for actually solving old competitive programming problems for some last-ditch practice.</div><div><br /></div><div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiTx4P_uhejEhSQ0KcZ99n_Y5wTG-qAieJs9RVtjCwNv02xLOHSMSw802ZK2hgEcAqKwl5D8R2ogS1InUX3Zga6NPgF7ooRq_K8SeeCWSwCrBRk5dq2QsUZjzQxKJ8BYCbtedB3pOTm0dRdeEoz4CDRZbTC_5lYuOrZtDYRFEKKVmxdne-Au_Uz2hGubtk/s3912/PXL_20240709_154456749-EDIT.jpg" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="2861" data-original-width="3912" height="468" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiTx4P_uhejEhSQ0KcZ99n_Y5wTG-qAieJs9RVtjCwNv02xLOHSMSw802ZK2hgEcAqKwl5D8R2ogS1InUX3Zga6NPgF7ooRq_K8SeeCWSwCrBRk5dq2QsUZjzQxKJ8BYCbtedB3pOTm0dRdeEoz4CDRZbTC_5lYuOrZtDYRFEKKVmxdne-Au_Uz2hGubtk/w640-h468/PXL_20240709_154456749-EDIT.jpg" width="640" /></a></div>Tomorrow is the big day! The overall setup is similar to the <a href="https://blog.mitrichev.ch/2023/09/awtf22-day-2.html">last year</a>, but with just one contest: 5 problems for 5 hours, the penalty time is computed as the time of the last successful submission (<i>not</i> the usual ICPC sum) plus 5 minutes for each incorrect submission. You can find more details in <a href="https://codeforces.com/blog/entry/131411">Riku's post</a>. And of course tune in to see my and Riku's commentary on the <a href="https://www.youtube.com/watch?v=uajgh54TRu8">live broadcast</a> which will start at the same time as the contest, <a href="https://www.timeanddate.com/worldclock/fixedtime.html?iso=20240712T1230&p1=248">12:30 Tokyo time</a>, and last for 5 hours.</div><div><br /></div><div>All 12 finalists are very strong, so it is hard to predict who will come out on top. zhoukangyang won 4 out of the last 6 AGCs, tourist has a lot of experience winning those contests, and jiangly has won the AWTF last year — I guess we can keep an eye for those three, but anything can happen really.</div><div><br /></div><div>Thanks for reading, and tune in tomorrow!</div><div><br /></div><div>UPD: the <a href="https://www.youtube.com/watch?v=uajgh54TRu8">live broadcast</a> link has been updated.</div>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com1tag:blogger.com,1999:blog-1953325079793449971.post-43643434098091595572024-07-09T16:06:00.005+02:002024-07-19T09:44:50.798+02:00A 熱中症予防 week<p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjrFmCdpG0nAgnE3xnUkLM2W7sVWGMbbkRGpL0Q_iOv1jrdFQ_20hT33PAB_1ZWnD0gZiZPszT0DVdNkSxumx1hjPIXGjb30jH1vDnRXrTe9-2-NszD05-PTwv9xYCqeZfLM06IuL580dJAtUbf-7G_kd2NfWt_OUK22xIZEGkMRvaayhWKXbascUeaHic/s3655/PXL_20240709_111408969-EDIT.jpg" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="2404" data-original-width="3655" height="420" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjrFmCdpG0nAgnE3xnUkLM2W7sVWGMbbkRGpL0Q_iOv1jrdFQ_20hT33PAB_1ZWnD0gZiZPszT0DVdNkSxumx1hjPIXGjb30jH1vDnRXrTe9-2-NszD05-PTwv9xYCqeZfLM06IuL580dJAtUbf-7G_kd2NfWt_OUK22xIZEGkMRvaayhWKXbascUeaHic/w640-h420/PXL_20240709_111408969-EDIT.jpg" width="640" /></a></div>There were no contests that I'd like to mention last week, so I can get straight to the new format of this blog for the coming week: a travel blog! I am going to the <a href="https://info.atcoder.jp/more/contents/awtf/2024">AtCoder World Tour Finals 2024</a> in Tokyo. I did not manage to <a href="https://clist.by/standings/atcoder-race-ranking-2023-41247385/">qualify</a> this time, placing 14th when I needed to be in top 12, so I am going as a spectator and as a co-commentator for the stream, together with <a href="https://cphof.org/profile/topcoder:maroon_kuri">Riku</a>, the main admin of AtCoder.<p></p><p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhW84Iol3kZk0hlebmaM98Lfue1sz3plM2SXehoHfExvZ1VyzHf7mQb4avCsqMOJVutOK590p57ejjDvAfvws8wn_4EEE6i_-8fQyz-8SExMifRSiN4EPNJm8dyz4UDEISgaKJG-4F_sr-fFE_9jC9do4hE4AZ6L_VVi5V3WnLfOPU3r51v7Ha-J8kRocQ/s1940/Screenshot_20240709-094552.png" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" data-original-height="1940" data-original-width="1080" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhW84Iol3kZk0hlebmaM98Lfue1sz3plM2SXehoHfExvZ1VyzHf7mQb4avCsqMOJVutOK590p57ejjDvAfvws8wn_4EEE6i_-8fQyz-8SExMifRSiN4EPNJm8dyz4UDEISgaKJG-4F_sr-fFE_9jC9do4hE4AZ6L_VVi5V3WnLfOPU3r51v7Ha-J8kRocQ/w178-h320/Screenshot_20240709-094552.png" width="178" /></a></div>For <a href="https://blog.mitrichev.ch/2023/09/awtf22-taifun.html">a second year running</a>, Tokyo welcomes the participants with an extreme weather warning in Japanese, this time for extreme heat. Please all take care, and focus on playing board games in the air conditioned hotel!<div><br /></div><div>Speaking for 5 hours while 12 contestants are facing, to put it mildly, challenging problems is also not a walk in the park. Please help us by suggesting topics that we should discuss or things we should do on stream in comments!<br /><p></p><p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgXrHej2wmoypBkB5d6whA7KA_UUN_AWLlvRPlqeWyGlBjZ7f-X_CB5Mnyb0tbfvVXpKl5sbwvgc6NHWNr66Qlm3ad_FJuWVPhvwFncL5SPWX-1E4UJ7uFNBWqcfci0FbyooNno0rQC0x27ND-a4c7rDz5M4mlsja9-yJ8P5O_gaBFhomVALjncm-bCWiw/s4080/PXL_20240709_123711836.jpg" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="3072" data-original-width="4080" height="482" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgXrHej2wmoypBkB5d6whA7KA_UUN_AWLlvRPlqeWyGlBjZ7f-X_CB5Mnyb0tbfvVXpKl5sbwvgc6NHWNr66Qlm3ad_FJuWVPhvwFncL5SPWX-1E4UJ7uFNBWqcfci0FbyooNno0rQC0x27ND-a4c7rDz5M4mlsja9-yJ8P5O_gaBFhomVALjncm-bCWiw/w640-h482/PXL_20240709_123711836.jpg" width="640" /></a></div>In <a href="https://blog.mitrichev.ch/2024/06/a-code-week.html">my previous summary</a>, I have mentioned <a href="https://contest.ucup.ac/contest/1696/problem/8782">a Universal Cup problem</a>: first, we draw the vertices of a regular <i>n</i>-gon (<i>n</i><=10000) on the plane. Then we repeat the following process <i>m</i> times (<i>m</i><=30000): take any 3 already drawn points (either the original <i>n</i>-gon vertices, or ones drawn during the previous steps) <i>A<sub>i</sub></i>, <i>B<sub>i</sub></i>, <i>C<sub>i</sub></i>, and draw the point <i>A<sub>i</sub></i>+<i>B<sub>i</sub></i>-<i>C<sub>i</sub></i> (the fourth vertex of a parallelogram). Finally, we need to handle multiple queries of the form: given <i>k</i> drawn points (the sum of <i>k</i> over all queries <=30000), do they form the vertices of a regular <i>k</i>-gon in some order?<p></p><p>We can get points that are really close to a regular <i>k</i>-gon but not exactly one in this problem, and no feasible floating point precision is enough. Therefore we need to solve it using only integer computations. Nevertheless, let us first consider how a floating-point solution might work.</p><p>We can imagine that the points lie on the complex plane, and the initial n points are <i>e</i><sup>2π<i>i</i>/<i>n</i></sup>. Drawing a new point corresponds to computing <i>A<sub>i</sub></i>+<i>B<sub>i</sub></i>-<i>C<sub>i</sub></i> using the complex number arithmetic. There are many ways to check if <i>k</i> computed points form a regular <i>k</i>-gon, here is one: we need to check that the <i>k</i> points, in some order, can be represented as <i>x</i>, <i>xy</i>, <i>xy</i><sup>2</sup>, ..., <i>xy</i><sup><i>k</i>-1</sup>, where y is such that <i>y</i><sup><i>k</i></sup>=1 and no smaller power of <i>y</i> is equal to 1. Note that this order does not have to be the clockwise/counter-clockwise order of the vertices: multiplying by <i>y</i> can also represent a jump by any coprime number of edges, and this criterion will still be valid. Also note that we can actually pick any of the vertices as <i>x </i>and such <i>y</i> will exist, moreover there will be φ(<i>k</i>) different values of <i>y</i> that work for each vertex. So one way to find <i>y</i> is to just try a few other vertices <i>z</i> of the polygon, let <i>y</i>=<i>z</i>/<i>x</i>, and check if the criterion is satisfied. Since φ(<i>k</i>) is not too small compared to <i>k</i>, we should find a valid <i>y</i> after a few attempts, let's say at most 50. Of course, we could've just said that <i>y</i>=<i>e</i><sup>2π<i>i</i>/<i>k</i></sup>, but you will see below that the <i>y</i>=<i>z</i>/<i>x</i> approach leads to an interesting question that I want to discuss.</p><p>If we denote the "base" point as <i>u</i>=<i>e</i><sup>2π/<i>n</i></sup>, then all other initial points are powers of <i>u</i>, all computed points are polynomials of <i>u</i>, and the checks we are making boil down to whether a certain polynomial of <i>u</i> with integer coefficients is equal to 0 or not (even though we also use division, checking if poly1(<i>u</i>)/poly2(<i>u</i>)=poly3(<i>u</i>)/poly4(<i>u</i>) is the same as checking if poly1(<i>u</i>)*poly4(<i>u</i>)-poly2(<i>u</i>)*poly3(<i>u</i>)=0). We could try to maintain said polynomials with integer coefficients, but since the degrees would be on the order of <i>n</i>, and the coefficients themselves could be huge, this is not really feasible within the time limit. </p><p>Here comes the key idea: instead of complex numbers and <i>u</i>=<i>e</i><sup>2π/<i>n</i></sup>, let us do the same computations using integers modulo a prime <i>p</i> and using such <i>u</i> that the order of <i>u</i> modulo <i>p</i> is equal to <i>n</i>. Such <i>u</i> exists if and only if <i>p</i>=<i>sn</i>+1 for some <i>s</i>, so we can search for a random big prime number of this form, which can be found quickly since all arithmetic progressions with coprime first element and difference have a lot of prime numbers.</p><p>This actually works very nicely and allowed us to get this problem accepted. However, why does this actually work? The order of <i>u</i> is the same in our two models (complex numbers and modulo <i>p</i>), so every polynomial of the form <i>u</i><sup><i>t</i></sup>-1 is equal to 0 in both or in neither model. However, this does not guarantee the same for an arbitrary polynomial with integer coefficients, or does it?</p><p>Of course it is not true for an arbitrary polynomial. For example, the polynomial <i>p</i> is equal to 0 modulo <i>p</i>, but not equal to 0 in complex numbers. However, we can deal with this by picking the modulo <i>p</i> at random, and potentially also checking several moduli in case the judges actually create testcases against many potential moduli. So the real question is: are there polynomials for which being equal to 0 differs between the complex numbers and computations modulo <i>p</i> for all or a significant fraction of all possible values of <i>p</i>?</p><p>Here we need to bring in some maths. When two polynomials with rational coefficients are equal to 0 for the given <i>u</i> their greatest common divisor also has rational coefficients and is also equal to 0 for the given <i>u</i>, which means that there must exist a <i>minimal polynomial</i> such that a polynomial with rational coefficients is equal to 0 for the given <i>u</i> if an only if the minimal polynomial divides it. Such minimal polynomial for our <i>u</i> is called the <i>n</i>-th <a href="https://en.wikipedia.org/wiki/Cyclotomic_polynomial">cyclotomic polynomial</a> Φ<i><sub>n</sub></i>(<i>u</i>).</p><p>Now, consider the equality <i>u</i><sup><i>n</i></sup>-1=Φ<i><sub>n</sub></i>(<i>u</i>)*<i>g</i><sub style="font-style: italic;">n</sub>(<i>u</i>) (where g<i><sub>n</sub></i>(<i>u</i>) is just the result of dividing <i>u</i><sup><i>n</i></sup>-1 by Φ<i><sub>n</sub></i>(<i>u</i>)). This equality is true in rational numbers, so it is also true modulo <i>p</i> where there is no division by <i>p</i> in it, so for almost all <i>p</i>. The left-hand side is 0 modulo <i>p</i> because of our choice of <i>u</i>, so either Φ<i><sub>n</sub></i>(<i>u</i>) or <i>g<sub>n</sub></i>(<i>u</i>) must be 0. However, from the structure of the cyclotomic polynomials we know that <i>g<sub>n</sub></i>(<i>u</i>) is a product of cyclotomic polynomials of smaller order, so if it was equal to 0, it would mean that the identity <i>u</i><sup><i>t</i></sup>-1=0 would hold for some <i>t</i><<i>n</i>, which contradicts our choice of <i>u</i>. So we know that Φ<i><sub>n</sub></i>(<i>u</i>)=0 modulo <i>p</i>, which means that every polynomial with integer coefficients that is equal to 0 for the given complex <i>u </i>will also be equal to 0 for the given <i>u</i> modulo <i>p</i>. So we have proven one of the two required implications.</p><p>Now let us tackle the the opposite implication. Consider a polynomial <i>h</i>(<i>u</i>) with integer coefficients that is equal to 0 for all or a significant fraction of all possible values of <i>p</i> (with the corresponding <i>u</i>). If Φ<i><sub>n</sub></i>(<i>u</i>) divides this polynomial (as a polynomial with rational coefficients), then it is also equal to 0 for the given complex <i>u</i>, as needed. If Φ<i><sub>n</sub></i>(<i>u</i>) does not divide it, then we can find the greatest common divisor of Φ<i><sub>n</sub></i>(<i>u</i>) and <i>h</i>(<i>u</i>), again doing computations using polynomials with rational coefficients. Since Φ<i><sub>n</sub></i>(<i>u</i>) is irreducible over polynomials with rational coefficients, this greatest common divisor will be 1, so we have 1=Φ<i><sub>n</sub></i>(<i>u</i>)*<i>a</i>(<i>u</i>)+<i>h</i>(<i>u</i>)*<i>b</i>(<i>u</i>). The right side involves a finite number of different integers in denominators, so this equality will also hold modulo <i>p</i> for all <i>p</i> except those dividing one of the denominators, in other words for almost all <i>p</i>. But since both Φ<i><sub>n</sub></i>(<i>u</i>) and <i>h</i>(<i>u</i>) are equal to 0 for all or a significant fraction of all possible values of <i>p</i>, this means that 1 is equal to 0 for all or a significant fraction of all possible values of <i>p</i>, which is a contradiction. Therefore we have also proven the opposite implication and this solution does in fact work.</p><p>There are still a few things I do not fully understand about this setup. One is the following: it turns out that when <i>n</i> is odd, we can actually construct a regular 2<i>n</i>-gon (roughly speaking using the fact that -1 helps generate the other <i>n</i> points; there was such example in the samples for <i>n</i>=3, <i>k</i>=6), so <i>k</i> does not have to divide <i>n</i>. In this case, the number <i>y</i> that we find as part of solving the problem must have order 2<i>n</i> modulo <i>p</i>. However, note that in general it is not even guaranteed that there is any number with order 2<i>n</i> modulo <i>p</i>, as we only choose <i>p</i> in such a way that there is a number with order <i>n</i>. Since we compute <i>y</i>=<i>z</i>/<i>x</i>, we can do this computation for any <i>p</i> where we can compute <i>z</i> and <i>x</i>. So it seems that the above also proves that for almost all primes <i>p</i> if there is a number of odd order <i>n</i> modulo <i>p</i>, there is also a number of order 2<i>n</i> modulo <i>p</i>. This observation is in fact true for a straightforward reason: almost all primes are odd, so there is an even number <i>p</i>-1 of nonzero remainders, therefore there is a number of order 2, and we can multiply the number of odd order <i>n</i> by the number of order 2 to get a number of order 2<i>n</i>. Still, I can't get rid of the feeling that I might be missing something here. Any comments?</p><p>The second thing I don't fully understand is whether we truly need a full understanding of the structure of cyclotomic polynomials to prove that Φ<i><sub>n</sub></i>(<i>u</i>)=0 modulo <i>p</i>. It feels that maybe there is an easier way to explain this that does not require so much knowledge?</p><p>Thanks for reading, and check back for more AWTF updates!</p></div>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com2tag:blogger.com,1999:blog-1953325079793449971.post-12274852367528293102024-06-10T03:11:00.001+02:002024-06-10T03:23:46.130+02:00A code week<p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgyQoEPnpTyyWJrKYNxUTTp47Jo0M1U_Q919iLJerPU7wBZHcABght2NpmP0T6bZFZBtMnuiC6ZqonqaLttwZ741NoJEaxy_H59d1X5uuQjNbLPqwh39ZpS6rdfQ3xxYS74MEHG6dUe1WigbpG-VvBv4zcUuvz1917jUOg74s2RyBFS2xtOTCO-L5WBNZM/s1188/ucup3r1top5.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="241" data-original-width="1188" height="130" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgyQoEPnpTyyWJrKYNxUTTp47Jo0M1U_Q919iLJerPU7wBZHcABght2NpmP0T6bZFZBtMnuiC6ZqonqaLttwZ741NoJEaxy_H59d1X5uuQjNbLPqwh39ZpS6rdfQ3xxYS74MEHG6dUe1WigbpG-VvBv4zcUuvz1917jUOg74s2RyBFS2xtOTCO-L5WBNZM/w640-h130/ucup3r1top5.png" width="640" /></a></div>Universal Cup started its 3rd season this Saturday with Stage 1: St Petersburg (<a href="https://acm.math.spbu.ru/trains/240512/240512.en.pdf">problems</a>, <a href="https://contest.ucup.ac/results/QOJ1696">results</a>, top 5 on the left, <a href="https://acm.math.spbu.ru/trains/240512/ucup-S03E01-slides.pdf">analysis</a>). Team 03 Slimes was in the lead for a long time, then paused a bit and gave everyone a chance to catch up, only to solve 3 more problems in the last hour and claim the clear first place. And all that even though our team stole one of their usual team members and they had to participate with just 2. Well done!<p></p><p>Solving <a href="https://contest.ucup.ac/contest/1696/problem/8782">problem B</a> was very satisfying, and I think describing its solution next week will help me understand the underlying math better, so here is the problem statement: first, we draw the vertices of a regular <i>n</i>-gon (<i>n</i><=10000) on the plane. Then we repeat the following process <i>m</i> times (<i>m</i><=30000): take any 3 already drawn points (either the original <i>n</i>-gon vertices, or ones drawn during the previous steps) <i>A<sub>i</sub></i>, <i>B<sub>i</sub></i>, <i>C<sub>i</sub></i>, and draw the point <i>A<sub>i</sub></i>+<i>B<sub>i</sub></i>-<i>C<sub>i</sub></i> (the fourth vertex of a parallelogram). Finally, we need to handle multiple queries of the form: given <i>k</i> drawn points (the sum of <i>k</i> over all queries <=30000), do they form the vertices of a regular <i>k</i>-gon in some order?</p><p>Initially the problem seems quite straightforward as we can just simulate the process and check the required condition using some simple geometric formulas. However, it turns out that we can get points that are really close to a regular <i>k</i>-gon but not exactly one in this problem, and no feasible floating point precision is enough. So how to solve this using only integer computations?</p><p><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjOEm5SDXMyrgLQ6hOdZehthGFiELCSQoYvxaSP50DhdRUFnwaGkDt-ZYjRimIYtWtAf_a6AwwEOQwgxcKJLqp1u0g-qbPTd8uXgr1WCzlLDKIt5haotLJnWAqc6fTNMNHWSYFabYa1ze1O98aAzmmc-vGovcl7gTKdTPCUMYyfBBUA5vVTDdbzXttXuMw/s1094/cfglobal26top5.png" style="clear: left; display: inline; margin-bottom: 1em; margin-right: 1em; text-align: center;"><img border="0" data-original-height="276" data-original-width="1094" height="162" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjOEm5SDXMyrgLQ6hOdZehthGFiELCSQoYvxaSP50DhdRUFnwaGkDt-ZYjRimIYtWtAf_a6AwwEOQwgxcKJLqp1u0g-qbPTd8uXgr1WCzlLDKIt5haotLJnWAqc6fTNMNHWSYFabYa1ze1O98aAzmmc-vGovcl7gTKdTPCUMYyfBBUA5vVTDdbzXttXuMw/w640-h162/cfglobal26top5.png" width="640" /></a></p><p>Codeforces Global Round 26 wrapped up the week on Sunday (<a href="https://codeforces.com/contest/1984">problems</a>, <a href="https://codeforces.com/contest/1984/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/130252">analysis</a>). One of the highlights of the round was an <a href="https://codeforces.com/blog/entry/130285">amazing successful experiment</a>, but there was also a pretty close fight for the first place, to the point that jiangly needed just one successful hack to win, which he unsuccessfully attempted. <strike>I wanted to check if he had a chance, in other words if there were any failed system tests in jiangly's room, but I could not find a way to find which of the 646 available rooms is it. Does anybody know how to find the room of another contestant?</strike> Apparently this link was staring me in the face, it is shown at the top of the user's submission history, which appears after a double-click in the corresponding standings cell. And it turns out that there were no failed system tests in <a href="https://codeforces.com/contest/1984/room/68">jiangly's room</a>, which means that his only chance for the required +100 could lie in some anti-hash tech.</p><p>In any case, tourist held on to his first place, and increased the gap at the top of the <a href="https://codeforces.com/ratings">rating list</a>. Interestingly, the top 3 in this round coincided with the top 3 by rating after Benq did find his successful hack. Congratulations to tourist, jiangly and Benq!</p><p>Thanks for reading, and check back next week.</p>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com10tag:blogger.com,1999:blog-1953325079793449971.post-38764234642807839932024-05-24T09:44:00.002+02:002024-05-24T09:45:48.487+02:00A return@week<p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEijKhFbg0HdLOzlv7z8OyV8sJnQYdd6buzr-Oa9FgHnzHCrPHrUgvck4TLt-9OZGX29NRtO7lh-GrMZEx30b8_5zI0XW8Xd3YXCFloCM2NuxFzV4Bdpffw__-Q-WQII6hxd5WdAhXCoCtlgwY8n0gPRxDSEGI8oMeu5Y2uM08ZjIvVz05X71vidBkqQbJc/s1320/kotlin10top5.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="324" data-original-width="1320" height="158" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEijKhFbg0HdLOzlv7z8OyV8sJnQYdd6buzr-Oa9FgHnzHCrPHrUgvck4TLt-9OZGX29NRtO7lh-GrMZEx30b8_5zI0XW8Xd3YXCFloCM2NuxFzV4Bdpffw__-Q-WQII6hxd5WdAhXCoCtlgwY8n0gPRxDSEGI8oMeu5Y2uM08ZjIvVz05X71vidBkqQbJc/w640-h158/kotlin10top5.png" width="640" /></a></div>Kotlin Heroes Episode 10 on Codeforces was the main event of last week (<a href="https://codeforces.com/contest/1958">problems</a>, <a href="https://codeforces.com/contest/1958/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/129483">analysis</a>). Only solutions in Kotlin programming language could be submitted. Long gone are <a href="https://blog.mitrichev.ch/2019/10/a-kotlin-week.html">the days</a> of IDEA's Java-to-Kotlin converter, at least nobody in the top 20 seems to use it, and I think the Kotlin Heroes series is quite a success in introducing people to Kotlin and getting them to like it. At the same time, Kotlin knowledge is still not at 100% in the community, so <a href="https://codeforces.com/blog/entry/129252?#comment-1147479">other translation tools</a> are on the rise :)<p></p><p>The top 2 were the same as in <a href="https://codeforces.com/contest/1910/standings">the previous edition</a>, and they were the only participants to solve all problems. However, this time arvindf232 was faster and earned a well-deserved victory. Congratulations to arvindf232 and tourist on the great performance!</p><p>Tourist's wrong submissions on E and F have seriously damaged his winning chances. The wrong submission on E (<a href="https://codeforces.com/contest/1958/submission/260816707">link</a>, compare to <a href="https://codeforces.com/contest/1958/submission/260816933">correct</a>) stems from a wrong understanding of an advanced language feature, <span style="font-family: courier;">return@repeat</span>, which turned out to mean <span style="font-family: courier;">continue</span> and not <span style="font-family: courier;">break</span> :) And the wrong submission on F (<a href="https://codeforces.com/contest/1958/submission/260819008">link</a>, compare to <a href="https://codeforces.com/contest/1958/submission/260819383">correct</a>) stems from not using a prewritten code library, more specifically a modint class. The winner's <a href="https://codeforces.com/contest/1958/submission/260817794">submission</a> to the same problem does use prewritten code to deal with modular arithmetics, but interestingly it is not done through operator overloading, but rather through defining new infix operations that also refer to a global variable, leading to weird-looking code like <span style="font-family: courier;">ret[paths] = ret[paths] mp (count mm FACT.choose(options, k-1))</span>, where "<span style="font-family: courier;">mp</span>" and "<span style="font-family: courier;">mm</span>" stand for modular addition and multiplication. arvindf232 or others reading this, what is the reason for this approach?</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-2715303713310187652024-05-15T21:04:00.001+02:002024-05-15T21:04:11.709+02:00A busy beaver week<p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg8k4ZoplghJfnEotyg_Sk7QjMoS7900p3HsI7jf93z_ZOcj-V7EpOcDoLxvP0tSGKjXxNH72GOXIZXWuwUjoenMhXjCoedwmy4Mms2mJ_KJ1nYi-Wn46TRU_2bKukic59TvPw4h4knq38RLEMcIZJ5WxzmIKtljAQ-HRQjnqq1LjWjKleh-5lXpXlqsHc/s2037/mititspring2024finaltop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="343" data-original-width="2037" height="108" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg8k4ZoplghJfnEotyg_Sk7QjMoS7900p3HsI7jf93z_ZOcj-V7EpOcDoLxvP0tSGKjXxNH72GOXIZXWuwUjoenMhXjCoedwmy4Mms2mJ_KJ1nYi-Wn46TRU_2bKukic59TvPw4h4knq38RLEMcIZJ5WxzmIKtljAQ-HRQjnqq1LjWjKleh-5lXpXlqsHc/w640-h108/mititspring2024finaltop5.png" width="640" /></a></div>The final round of the MIT Informatics Tournament "M(IT)^2" 2024 Spring Invitational took place in Boston last week (<a href="https://codeforces.com/group/UqOrh5VnfT/contest/523714">problems</a>, results are not published yet, top 5 on the left, <a href="https://codeforces.com/group/UqOrh5VnfT/contest/523714/standings/groupmates/true">online mirror results</a>). Even though the competition was open to everybody who is willing to travel to Boston, the top 4 places were occupied by those who have won ICPC gold medals for the MIT team in the past :) Adam Gąsienica-Samek in the fifth place, to the best of my knowledge, is still a high school student in Warsaw (even though the last name does bring some <a href="https://cphof.org/standings/icpc/2003">ICPC memories</a>; is it a coincidence or are they related?). Maybe he will win ICPC gold medals for MIT in the future :) Congratulations to the winners, and also to the organizers! Looking at how <a href="https://mitit.org/About">most of them</a> are not graduating for at least a couple more years, I hope for more tournaments to come.<p></p><p>Thanks for the quick reading, and check back next week.</p>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com1tag:blogger.com,1999:blog-1953325079793449971.post-358921924058514442024-05-05T17:05:00.001+02:002024-05-05T21:07:19.915+02:00A notorious week<p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj1cZSkAXgJj4KSl-zUN35sdiqKZRZp8Lvrujhzx03pXukMcclfdIbCJIpl6pYVMj48Vnz9Q1AnzwI8FJjxMW1naZKH-8wHXmlEUPYkkKPFa5YSY5yzbMrCehSWBv0TH6JK22A-JJyAm6Lrkxee3YLwN5LJ9-D3gBiGHhH7-Zh5DdN4oY4t3AVozQxeYyc/s1323/cf942top5.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="345" data-original-width="1323" height="166" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj1cZSkAXgJj4KSl-zUN35sdiqKZRZp8Lvrujhzx03pXukMcclfdIbCJIpl6pYVMj48Vnz9Q1AnzwI8FJjxMW1naZKH-8wHXmlEUPYkkKPFa5YSY5yzbMrCehSWBv0TH6JK22A-JJyAm6Lrkxee3YLwN5LJ9-D3gBiGHhH7-Zh5DdN4oY4t3AVozQxeYyc/w640-h166/cf942top5.png" width="640" /></a></div>Codeforces Round 942 was the first event of this week (<a href="https://codeforces.com/contest/1967">problems</a>, <a href="https://codeforces.com/contest/1967/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/129027">analysis</a>). tourist has returned to the top of the scoreboard, and also to the top of <a href="https://codeforces.com/ratings">the rating list</a> — congratulations! It is also great to see that <a href="https://cphof.org/profile/topcoder:xudyh">jqdai0815</a> keeps participating actively and getting great results after going for a long break during the pandemic. Who knows, maybe even I still have a chance to return to the top 10 :)<p></p><p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhEBsjgfZa1bdtUszsRCCy392KIaAmy5MGiUKrzVm5pO01Aye5mapnIRFaiIsqBw0alSYMvvkMqmueLhZqQelZw-EnW_03TvwIdjZUZLdX8a-OM3Y8WfK0t0oOf9OyVv_-pVhRVqBLEVzKyX0SzOf4FlaEc6PmkHI70iLxbKAbwShgifYK6Kbk5fIV9p2g/s1855/hc2024mirrortop5.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="400" data-original-width="1855" height="138" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhEBsjgfZa1bdtUszsRCCy392KIaAmy5MGiUKrzVm5pO01Aye5mapnIRFaiIsqBw0alSYMvvkMqmueLhZqQelZw-EnW_03TvwIdjZUZLdX8a-OM3Y8WfK0t0oOf9OyVv_-pVhRVqBLEVzKyX0SzOf4FlaEc6PmkHI70iLxbKAbwShgifYK6Kbk5fIV9p2g/w640-h138/hc2024mirrortop5.png" width="640" /></a></div>On Saturday, we hosted the online mirror of the Helvetic Coding Contest 2024 (<a href="https://codeforces.com/contest/1970">problems</a>, <a href="https://codeforces.com/contest/1967/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/spectator/ranklist/0e3f4002d2169012119f2d83359ada75">onsite results</a>, <a href="https://codeforces.com/blog/entry/129149">analysis</a>). This is originally an onsite competition that took place in Lausanne in April, it is ran completely by <a href="https://polympiads.ch/">a group of student volunteers</a> at the EPFL, who take care of all tasks such as finding sponsors, advertising the event, planning the onsite events, setting up the onsite competition environment, organizing meals, and of course preparing the problems. Seeing this volunteer-driven contest appear out of nowhere after a five-year hiatus really inspires and makes me proud of the competitive programming community. Therefore I have submitted two problems this year (<a href="https://codeforces.com/contest/1970/problem/A3">A</a> and <a href="https://codeforces.com/contest/1970/problem/D3">D</a>), I hope you liked them!<div><br /></div><div>But I also need to mention that this year one of the problems unfortunately was the same as Problem 5 of the <a href="https://www.codechef.com/rankings/LTIME102A?itemsPerPage=100&order=asc&page=1&sortBy=rank">November Lunchtime 2021</a> at Codechef. As you can see, there were quite a few competitors that took part both in that round and in this week's mirror, and there could be much more who have upsolved it or heard about it from a friend, which of course made the contest worse, even though it was unrated. Below I am trying to share my understanding of what happened, but note that my goal is not to absolve myself from the responsibility — I think it was a failure, and I apologize for it.</div><div><br /></div><div>As it is often the case, the reason for this seems to be bad communication along a chain of people operating with good intent. The original author (by the way, nice problem!) <a href="https://codeforces.com/blog/entry/129149?#comment-1146492">clearly knew</a> that this problem was used for the Lunchtime when sending it to one of the HC2 organizers, but expected the HC2 organizers to make their own judgement about how appropriate it is to use it in the onsite event, they likely did not even know that a mirror might happen.</div><div><br /></div><div>But then as the information about this problem propagated from one HC2 organizer to another through a couple of more hops, this fact was lost, with various people thinking that this problem was only used for a private contest with a few participants, or that this problem was prepared but rejected and not used at all in the past.</div><div><br /></div><div>What probably made the matter worse is that different people have different perceptions of what is OK (should we never give the same problem to two contests? Or maybe it is OK if the set of participants is not intersecting and it was not available publicly after the first one? Or maybe it is OK if the first occurrence happened long ago? Or maybe it is OK if the second round is unrated?), and this perception affects what information about the problem they decide to communicate to other people.</div><div><br /></div><div>Moreover, people often expect other people to have the same perception of the situation, and therefore treat the <i>lack</i> of communication as information as well. As a result, the people organizing the mirror (such as myself) did not try to figure out more information about the origins of this problem even though we knew from Polygon that it was prepared a bit earlier, assuming that other organizers who are closer to the beginning of this communication chain know the problem better and therefore are in a better position to judge if it is appropriate to use, so if they say nothing, all is good. But this line of reasoning fails to account for the fact that the people closer to the beginning of the communication chain have a different context (might not even be aware that there's a public mirror, for example) and different perceptions of what is OK.</div><div><br /></div><div>So here is my takeaway from all this: more communication is always better when preparing a contest! I will try to keep this in mind when preparing future rounds, hopefully including the Helvetic Coding Contest 2025.<br /><p></p><p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgECHQVvIq43Y2zsRYED2BGOXwkwwjDYVleIKpKTK8nqXCO55ndazE1ZiDOANvIQCVxzbJSEVCAb4Madl1OQtl4_9UWucLhWwko-QDSMazmuBcCrOC7nD4i2dQZyWRMbNUXyu_v4n6kztXXSMsmcXQYC9s1uiTI6Rsmwn_QUsSLzZKDy8EG8_R6-33CGUM/s4080/PXL_20240120_125423271.jpg" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="3072" data-original-width="4080" height="482" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgECHQVvIq43Y2zsRYED2BGOXwkwwjDYVleIKpKTK8nqXCO55ndazE1ZiDOANvIQCVxzbJSEVCAb4Madl1OQtl4_9UWucLhWwko-QDSMazmuBcCrOC7nD4i2dQZyWRMbNUXyu_v4n6kztXXSMsmcXQYC9s1uiTI6Rsmwn_QUsSLzZKDy8EG8_R6-33CGUM/w640-h482/PXL_20240120_125423271.jpg" width="640" /></a></div>In <a href="https://blog.mitrichev.ch/2024/04/a-jiangly-week.html">my previous summary</a>, I have mentioned <a href="https://codeforces.com/contest/1965/problem/B">a Codeforces problem</a>. You are given two integers <i>n</i> and <i>k</i>. Your goal is to create a (multi-)set of positive integers such that among its sub(-multi-)sets we can find ones which sum to any integer between 1 and <i>n</i>, except <i>k</i>. n is at most 10<sup>6</sup>, and the set you create must have at most 25 elements.<p></p><p>The first part of the solution is somewhat clear/standard: we need to be able to represent all numbers between 1 and <i>k</i>-1, but not the number <i>k</i>. For this, we can take all powers of two less than <i>k: </i>1, 2, 4, ..., 2<sup><i>i</i></sup>, such that 2<sup><i>i</i></sup><<i>k</i><=2<sup><i>i</i>+1</sup>, but then in order to not overshoot <i>k</i> we should replace 2<sup><i>i</i></sup> with <i>k</i>-2<sup><i>i</i></sup>: then the sum of all numbers is <i>k</i>-1, and clearly all numbers between 1 and <i>k</i>-1 are still representable.</p><p>Then, as long as all other numbers that we take into our set are at least <i>k</i>+1, <i>k</i> will still not be representable. But how do we cover all numbers between <i>k</i>+1 and <i>n</i>? After trying to come up with something concrete on paper unsuccessfully for some time, I've decided to just run a dynamic programming that remembers which numbers are representable, and repeatedly take the smallest non-representable number. It is not obvious why this will have at most 25 elements, but it is very easy to try.</p><p>Here is the output of this approach for n=1000000, k=5:<br /><span style="font-family: courier;">21<br />1 2 1 6 11 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288</span></p><p>And for n=1000000, k=6:<br /><span style="font-family: courier;">21<br />1 2 2 7 13 19 38 76 152 304 608 1216 2432 4864 9728 19456 38912 77824 155648 311296 622592</span></p><p>Now we can notice a pattern: the numbers we add in the second phase are <i>k</i>+1, 2<i>k</i>+1, 3<i>k</i>+1, 2(3<i>k</i>+1), 4(3<i>k</i>+1), 8(3<i>k</i>+1), ... We can now both be more confident that it will always fit under 25 elements, and also try to prove that this pattern always works. Or just submit. </p><p><a href="https://codeforces.com/contest/1965/submission/258437552">My submission</a> in the actual contest is more complex than that, and even includes some randomization :) The reason for that is that I had a bug in the implementation of the simple dynamic programming which made me think it produces more than 25 elements sometimes, adding randomization helped fit under 25 but did not fix the bug, and after fixing the bug I did not check if randomization was still needed.</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-84477229178248409202024-04-28T22:19:00.001+02:002024-04-28T22:43:55.258+02:00A jiangly week<p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiCaJU_q0WpToUPyVgUg0nwk1dcxuhgIbNcnTLwsPEO3diFb4mX0rtvzbDdkmPMbjnrs4awyMMbOaZAuu0WIQHByqxDiafaeVlwXag3wS0FIrjT4m0yShyphenhyphenTGiXn3GplmmDbKf9sZBU3vLULBsDuQGMzyUMm7mHPWCvjZDwR0GSfkseJSb_mL12wDqY1xpI/s1095/mititspring2024top5.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="459" data-original-width="1095" height="268" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiCaJU_q0WpToUPyVgUg0nwk1dcxuhgIbNcnTLwsPEO3diFb4mX0rtvzbDdkmPMbjnrs4awyMMbOaZAuu0WIQHByqxDiafaeVlwXag3wS0FIrjT4m0yShyphenhyphenTGiXn3GplmmDbKf9sZBU3vLULBsDuQGMzyUMm7mHPWCvjZDwR0GSfkseJSb_mL12wDqY1xpI/w640-h268/mititspring2024top5.png" width="640" /></a></div>The qualification round of the MIT Informatics Tournament "M(IT)^2" 2024 Spring Invitational took place last Sunday after I published my summary for the week (<a href="https://codeforces.com/gym/105125">problems</a>, <a href="https://mitit.org/Contest/ViewScoreboard/qualification-2024">results</a>, top 5 on the left, <a href="https://www.youtube.com/watch?v=jDmeDxLfko8">analysis</a>, <a href="https://youtu.be/WvuS2049DCM">my screencast</a>). Mingyang Deng was very fast in general, but the final blow was that he could solve P4 a lot faster than other top competitors (25 minutes compared to about 40 for others), leading to a first place with quite significant margin. Congratulations!<div><br /></div><div>More generally, it is awesome to see a new tournament with an onsite round (which was initially USA-only but has since <a href="https://codeforces.com/blog/entry/127830?#comment-1142469">expanded</a>). It's a pity that I will not be able to make it since it was only announced a few weeks in advance. Good luck to all onsite participants, and have fun!<br /><p></p><p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjwKtsEtcEW4PLRgj_lsOST7FUJ8dyxz6Oj9yVPcIzUwKVWsYnDkbFX1JsXs3Lzr9ioAuXbQge65XGKd1JdgBIiTwxz2IFZSdjmECWWbKboW1ve49cIzP0YIAoCXtDJNz6g2qcVXjaStINwNYnEveirvCu9A5052fURQ95NVhndM2ypNcgCYoFd3cV7sOw/s947/srm854top5.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="145" data-original-width="947" height="98" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjwKtsEtcEW4PLRgj_lsOST7FUJ8dyxz6Oj9yVPcIzUwKVWsYnDkbFX1JsXs3Lzr9ioAuXbQge65XGKd1JdgBIiTwxz2IFZSdjmECWWbKboW1ve49cIzP0YIAoCXtDJNz6g2qcVXjaStINwNYnEveirvCu9A5052fURQ95NVhndM2ypNcgCYoFd3cV7sOw/w640-h98/srm854top5.png" width="640" /></a></div>One of the rare TopCoder rounds, SRM 854, took place on Thursday (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=19727">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=19727&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left). This round has once again demonstrated TopCoder's unique format. Being the only competitor to solve the 1000-pointer was only enough for the 3rd place for Nyaan, since nwin and hitonanode accumulated an enormous amount of points during the challenge phase thanks to a corner case in the 350 that was not covered by the sample tests (and TopCoder does not check anything else on submission). Congratulations to all three!<div><br /></div><div>One could argue that it is not very nice to (likely intentionally) exclude this corner case from the sample tests. However, I think it was fair game because there was this phrase in the problem statement: "Only the boxes matter, your final position does not: as soon as all the boxes are at the same coordinate, the task is complete regardless of your position at that moment." This phrase makes no sense if you miss this corner case, and since <a href="https://codeforces.com/blog/entry/62730">problemsetters do not write random things in statements</a>, one had to stop and think why this was emphasized.</div><div><br /></div><div>More generally, I think the TopCoder format with no pretests and therefore many submissions failing system tests often leads to very exciting rounds, allows more people to win from time to time, and also rewards those who can write code with less bugs and/or know which amount of testing is enough. I like all those properties, and therefore it is very sad that this format is slowly fading into the void.<br /><p></p><p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjk9f_R3fbAYlirMNcF5Ik9iMER_wmBVdGqzftO74l_RHXkUesFGtimt0QBrVaPllgUyEu4Si2epjO1piGL_QUIk1bS0VPTjGa5U_QyxQaUVq_FQNSTlFZps8cVlw9ROJvzEXijlsQ5S4q7a26MT3KGbskTP9zhc1Sj2ss5LjemXPeZn1rUKrIWsw30scI/s1321/cf941top5.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="344" data-original-width="1321" height="166" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjk9f_R3fbAYlirMNcF5Ik9iMER_wmBVdGqzftO74l_RHXkUesFGtimt0QBrVaPllgUyEu4Si2epjO1piGL_QUIk1bS0VPTjGa5U_QyxQaUVq_FQNSTlFZps8cVlw9ROJvzEXijlsQ5S4q7a26MT3KGbskTP9zhc1Sj2ss5LjemXPeZn1rUKrIWsw30scI/w640-h166/cf941top5.png" width="640" /></a></div>Finally, Codeforces Round 941 wrapped up the week on Saturday (<a href="https://codeforces.com/contest/1965">problems</a>, <a href="https://codeforces.com/contest/1965/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/128914">analysis</a>). The round had a bit fewer strong participants than usual since the Yandex Cup finalists could not participate, but still winning it was no small feat. jiangly was having a very good round, and was the first to solve problem D near the middle of the contest, but then he probably (or maybe not? Actually I have no idea) looked at the scoreboard and realized that people are solving E faster than D, and therefore even his great performance on the first four problems might not be enough to be in first place after five, simply because he chose the wrong order. On the other hand, rainboy had already demonstrated at that point that F is solvable in less than an hour, so going for F was a risky but potentially contest-winning move. And it worked out very nice for jiangly with 7 minutes remaining. Well done!</div><div><br /></div><div>Some people even <a href="https://codeforces.com/blog/entry/127943#comment-1137305">retire</a> after achieving the first place in a Codeforces round, but even though for jiangly it is already the 13th first place, and he has also <a href="https://cphof.org/profile/icpc:Lingyu%20Jiang">achieved</a> the WTF first place last year and the ICPC first place last week, it feels that the story might be just starting :)</div><div><br /></div><div><a href="https://codeforces.com/contest/1965/problem/B">Problem B</a> was a cute constructive one. You are given two integers <i>n</i> and <i>k</i>. Your goal is to create a (multi-)set of positive integers such that among its sub(-multi-)sets we can find ones which sum to any integer between 1 and <i>n</i>, except <i>k</i>. n is at most 10<sup>6</sup>, and the set you create must have at most 25 elements. Can you find a way?<br /><p></p><p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiBUS_rXjY9tI_zvFCqn_wOgEKvYkhG9JiwpcdSETtdEBk8Irq2vXy1tu0ozU3qLuM5ZYmdzMFk11wzExW56UBU1XpLDLzycIpd49XAZlWPkTrZ7th4EWaAI0Po7e6jgK5Rx7acDBEiZMrJZ4CSOL6NgmQTzkkVSVYvJiTSqUHFeFWI5l-KV25_7AkyBvs/s4080/PXL_20231125_095436991.jpg" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="3072" data-original-width="4080" height="482" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiBUS_rXjY9tI_zvFCqn_wOgEKvYkhG9JiwpcdSETtdEBk8Irq2vXy1tu0ozU3qLuM5ZYmdzMFk11wzExW56UBU1XpLDLzycIpd49XAZlWPkTrZ7th4EWaAI0Po7e6jgK5Rx7acDBEiZMrJZ4CSOL6NgmQTzkkVSVYvJiTSqUHFeFWI5l-KV25_7AkyBvs/w640-h482/PXL_20231125_095436991.jpg" width="640" /></a></div>In <a href="https://blog.mitrichev.ch/2024/04/a-turning-red-week.html">my previous summary</a>, I have mentioned a World Finals problem (<a href="https://scoreboard.icpc.global/46/finals46.pdf">problem T here</a>): you are given two right square pyramids with integer base coordinates, integer height, and non-intersecting (but possibly touching) bases lying on the same plane. What is the shortest path between the tips of the pyramids that always goes either on the surface of one of the pyramids, or on the plane? The coordinates are up to 10<sup>5</sup>, and the output must have relative error of at most 10<sup>-6</sup>.<p></p><p>This problem was not very beautiful. In fact, if you're after beautiful geometry problems, you should check out jeroenodb's <a href="https://codeforces.com/blog/entry/128798">recent post</a>. But I think the problem was very educational, because it both demonstrated the need to understand one's own solution in detail, and the superiority of ternary search :)</p><p>First, we notice that on the suface of each pyramid we must go in a straight line, and the same is true for the plane. So our path will always have three straight segments, and the only choice we have is where the two points where those segments meet lie on the base of each pyramid.</p><p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjPpNHrQkgIor5ohRiXAjHi-EwDbsjDQM_PrUoPmhk9D0Pv1Zif671Bv1ESOAV_PE1QA9ZeLdLeoIJgr0hao6IksL7OLimxw7v9_zSv9UvoyPFP9aXKDprJBwXvSJ4RroD29crNFoFuAbFUhiWstCiJ4ztyf821jNXAn7KCS2TvSPmU4gbw7MlKxzbI1iI/s1548/PXL_20240428_201350317~2.jpg" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" data-original-height="522" data-original-width="1548" height="135" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjPpNHrQkgIor5ohRiXAjHi-EwDbsjDQM_PrUoPmhk9D0Pv1Zif671Bv1ESOAV_PE1QA9ZeLdLeoIJgr0hao6IksL7OLimxw7v9_zSv9UvoyPFP9aXKDprJBwXvSJ4RroD29crNFoFuAbFUhiWstCiJ4ztyf821jNXAn7KCS2TvSPmU4gbw7MlKxzbI1iI/w400-h135/PXL_20240428_201350317~2.jpg" width="400" /></a></div>This is where the two main approaches branch. Our approach, and the approach of many other teams who struggled with this problem during the round, went like this: for each base square, we consider 8 options (so 64 options total): the meeting point is either one of the four vertices, or on one of the four sides. If it is one of the vertices, we just need to find the shortest path from that vertex onwards. If it is on one of the sides, things are more complicated: we notice that we can "fold" the side of the pyramid over this side towards the plane, and the path lengths passing through this side will not change. Now we just need to find the shortest path on the plane between the folded locations of the pyramid tips, and the shortest path on the plane is a straight segment. However, for us to be able to "unfold" this segment back to a path in the original problem, we need to make sure that this segment actually intersects the side or two sides that we used for folding. So you spend quite some time implementing all this carefully, submit, and of course get WA.<p></p><p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhu3sy5cTlxmXb9DoD6_7Tjqf3tD09dYa716eQJmgA0fwyBRH6XNvRKRAqXMCzG8Kug3njOOI5mOXd6XXMTkJsh3Sjehx4l2-hrkHxPz-PrfohX0QNVN9V201-CVbB_S9hB16Guh-W_Sl5Oh5w1PFVTbAqQRsamEvkLUK7DF5DmEnOD5MwJfhHB7PuAbfY/s990/PXL_20240428_201350317~3.jpg" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="385" data-original-width="990" height="155" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhu3sy5cTlxmXb9DoD6_7Tjqf3tD09dYa716eQJmgA0fwyBRH6XNvRKRAqXMCzG8Kug3njOOI5mOXd6XXMTkJsh3Sjehx4l2-hrkHxPz-PrfohX0QNVN9V201-CVbB_S9hB16Guh-W_Sl5Oh5w1PFVTbAqQRsamEvkLUK7DF5DmEnOD5MwJfhHB7PuAbfY/w400-h155/PXL_20240428_201350317~3.jpg" width="400" /></a></div>The reason for the WA (and I was only able to figure this out because Kevin told me, I am not sure I would find this myself during the contest time at all) is that the segment shouldn't just intersect the two sides used for folding, it should intersect them in the correct order! The picture on the left demonstrates two tall pyramids standing next to each other, and how that leads to a segment that does intersect the two sides used for folding, but in the wrong order, and which therefore does not correspond to a valid path in the original problem. You fix this, and then you get OK.<p></p><p>However, there is a much better approach: it is somewhat clear (one can derive a formal proof from the first approach I guess, but one can also <a href="https://codeforces.com/blog/entry/126875">submit without proving</a>) that if we fix which two sides of the base squares the two meeting points lie on, the path length is a convex function, so we can just use two nested ternary searches to get a very easy to implement solution with no corner cases. In this approach we don't even need to handle the base square vertices specially, they will be considered as part of the corresonding sides.</p><p>Thanks for reading, and check back next week!</p></div></div>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com4tag:blogger.com,1999:blog-1953325079793449971.post-43382329948049360442024-04-19T12:31:00.001+02:002024-04-19T12:31:09.439+02:00A turning red week<p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiuDGczR_5dYWfTySCpWdNhNumwk_RF0-NejqoKrXs8lTP8BIh3M6FNU-2CyxYoUYqMU6KNdoq_TATTTNFCP2TbZY6fzJDZsSRBCwZ8hyphenhyphen_CL3FLiTx12PdFjOGhg6ArGhDNftl_2QvSlebjF04rwvWtTdllvMcNvFlxO80bdqT2RDn59leTzD3Imz4bltg/s2203/icpc2022top12.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="946" data-original-width="2203" height="274" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiuDGczR_5dYWfTySCpWdNhNumwk_RF0-NejqoKrXs8lTP8BIh3M6FNU-2CyxYoUYqMU6KNdoq_TATTTNFCP2TbZY6fzJDZsSRBCwZ8hyphenhyphen_CL3FLiTx12PdFjOGhg6ArGhDNftl_2QvSlebjF04rwvWtTdllvMcNvFlxO80bdqT2RDn59leTzD3Imz4bltg/w640-h274/icpc2022top12.png" width="640" /></a></div>The ICPC World Finals in Luxor was the main event of the week. The finals for two years were running in parallel, and our team was solving the mirror of the 2022 season, the 46th World Finals (<a href="https://scoreboard.icpc.global/46/finals46.pdf">problems</a>, <a href="https://zibada.guru/finals/2022/">results</a>, top 12 on the left, <a href="https://youtu.be/an5sBhtktaE">official broadcast</a>, <a href="https://youtu.be/yhp1WLp02nE">our stream</a>). MIT team was dominating the round, solving 8 problems in less than two hours, getting to 9 within 3 hours, and leading by 2 problems for a long time. This reminds me of my own participation in 2005 World Finals (<a href="https://web.archive.org/web/20050409042026fw_/http://icpc.baylor.edu/icpc/Finals/Scoreboard/index.html">frozen detailed standings</a>, <a href="https://cphof.org/standings/icpc/2005">final coarse standings</a>), where we got to 7 problems slightly after the 3 hour mark and were leading 7-5, and with a huge advantage in penalty time, only to get stuck in problem G and have the Shanghai team overtake us thanks to solving 3 problems in the last hour. A very similar thing happened here with another team from China, Peking University, who solved 3 problems in the last 70 minutes and overtook the unlucky MIT team who was stuck with 25 incorrect attempts on problem S. Congratulations to both teams on the amazing performance!<div><br /></div><div><a href="https://scoreboard.icpc.global/46/finals46.pdf">Problem T</a> "Carl's Vacation" was the trademark World Finals geometry problem. You are given two right square pyramids with integer base coordinates, integer height, and non-intersecting (but possibly touching) bases lying on the same plane. What is the shortest path between the tips of the pyramids that always goes either on the surface of one of the pyramids, or on the plane? The coordinates are up to 10<sup>5</sup>, and the output must have relative error of at most 10<sup>-6</sup>. Can you see a way to implement this without getting stuck in the details?<br /><p></p><p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiZ5cLM7O8UuDaZ-b-RfqBRsjAh_tIFqXW6Q9jDPUn_etYKPzsKmN8UL7aFSvSmlG5AmTUeYcydW0PEisGinoRG0Bn-mT3cisiUAwvHTLOKM3eZeXEF6sI3RJJMgQq6LJO5l2vt-isuj3v10LyFLny-paE4B1o7pV4_TW61QgRsxEkGIUWllSGDcOwWwYY/s2211/icpc2023top12.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="948" data-original-width="2211" height="274" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiZ5cLM7O8UuDaZ-b-RfqBRsjAh_tIFqXW6Q9jDPUn_etYKPzsKmN8UL7aFSvSmlG5AmTUeYcydW0PEisGinoRG0Bn-mT3cisiUAwvHTLOKM3eZeXEF6sI3RJJMgQq6LJO5l2vt-isuj3v10LyFLny-paE4B1o7pV4_TW61QgRsxEkGIUWllSGDcOwWwYY/w640-h274/icpc2023top12.png" width="640" /></a></div>The finals of the 2023 season, the 47th World Finals, had 5 shared problems and 6 unique problems (<a href="https://scoreboard.icpc.global/47/finals47.pdf">problems</a>, <a href="https://zibada.guru/finals/2023/">results</a>, top 5 on the left). The Higher School of Economics team took the lead a bit before the 2 hour mark and held it for most of the remaining contest, only allowing the MIPT team to lead briefly for 10 minutes in between. Unlike the first contest, nobody was able to solve the 10th problem and therefore HSE's win stood. Congratulations!<div><br /></div><div>For me, the most amazing part of the Luxor event was meeting so many friends and acquaintances who live all over the world. The ICPC community is amazing by itself, and it also serves as a basis for multiple sub-communities that came together to meet in Luxor, such as the ICPC Live team, or the Universal Cup organizers and participants, or the ICPC alumni who now work for the sponsors, or just came as guests, such as myself. Huge thanks to the organizers, to the sponsors, and to the participants!<br /><p></p><div>Thanks for reading, and check back next week.</div></div></div>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com3tag:blogger.com,1999:blog-1953325079793449971.post-23502310805911043902024-04-18T00:50:00.003+02:002024-04-18T00:50:55.292+02:00ICPC World Finals Luxor mirror stream<p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhJ9_PWK7lh64ee7_WREDy8QaDUCGpiQ5tVPHLriZjpFYVMCh3-KAW2rEkNJpgCPYnA3dNU2FPm2-iJ7B2PxM2N-5E9HyMWHan56xS1LkqA3V1ysnm-B2d3F2EqZaAEl6EglmQKiv8k-0nsK-RX63UvxQPqKujW7j39XLkHEtNc-9rkamUVFaeU9iCfOmA/s4080/PXL_20240416_164423799.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="3072" data-original-width="4080" height="482" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhJ9_PWK7lh64ee7_WREDy8QaDUCGpiQ5tVPHLriZjpFYVMCh3-KAW2rEkNJpgCPYnA3dNU2FPm2-iJ7B2PxM2N-5E9HyMWHan56xS1LkqA3V1ysnm-B2d3F2EqZaAEl6EglmQKiv8k-0nsK-RX63UvxQPqKujW7j39XLkHEtNc-9rkamUVFaeU9iCfOmA/w640-h482/PXL_20240416_164423799.jpg" width="640" /></a></div>The ICPC World Finals in Luxor are happening tomorrow. You can find a lot of useful links <a href="https://codeforces.com/blog/entry/128559">here</a>, but of course you should <a href="https://www.twitch.tv/the__tourist">tune in</a> to watch me, Gennady and Kevin solve the mirror round! We will start around <a href="https://www.timeanddate.com/worldclock/fixedtime.html?msg=2023+ICPC+World+Finals+Luxor&iso=20240418T12&p1=4626&ah=5">noon Egypt time</a>, maybe a bit earlier. To warm up, you can check out the previous streams we did with Mikhail instead of Kevin (<a href="https://youtu.be/BZo23gj9ksk">2017</a>, <a href="https://youtu.be/nF3tSkNWRVQ">2018</a>, <a href="https://youtu.be/X6YdKQspOBk">2019</a>, <a href="https://youtu.be/smdqc1s4vgg">2020</a>).<p></p>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com1tag: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.com0