tag:blogger.com,1999:blog-19533250797934499712018-02-19T12:16:00.414+03:00Algorithms Weekly by Petr MitrichevPetr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.comBlogger348125PetrMitrichevhttps://feedburner.google.comtag:blogger.com,1999:blog-1953325079793449971.post-6062008360648049262018-02-18T22:49:00.002+03:002018-02-19T12:16:00.508+03:00A Fenwick bound week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-awKrgQjT350/WomSwzr2qjI/AAAAAAAB-2M/zVG2IlWG3joqtmemRnDmLo46kp1FI3jzACLcBGAs/s1600/cf462top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="272" data-original-width="1102" height="157" src="https://3.bp.blogspot.com/-awKrgQjT350/WomSwzr2qjI/AAAAAAAB-2M/zVG2IlWG3joqtmemRnDmLo46kp1FI3jzACLcBGAs/s640/cf462top5.png" width="640" /></a></div>Codeforces was quite active this week with two Division 1 rounds. The 462nd one took place on Wednesday (<a href="http://codeforces.com/contest/933">problems</a>, <a href="http://codeforces.com/contest/933/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/57763">analysis</a>). Um_nik was the only one able to solve all problems, submitting one in the last minute — but he would've won without that one anyway. Congratulations on the great performance!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-wPeOFwyYe0w/WomTpEUvugI/AAAAAAAB-2U/iHnypLHmY1UZAPXx4idNdRAsn9hp-iTBQCLcBGAs/s1600/cf463top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="270" data-original-width="1104" height="156" src="https://3.bp.blogspot.com/-wPeOFwyYe0w/WomTpEUvugI/AAAAAAAB-2U/iHnypLHmY1UZAPXx4idNdRAsn9hp-iTBQCLcBGAs/s640/cf463top5.png" width="640" /></a></div>Round 463 took place on Thursday (<a href="http://codeforces.com/contest/932">problems</a>, <a href="http://codeforces.com/contest/932/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/57796">analysis</a>). It was Radewoosh's turn to be the only competitor to solve all problems, with 7 minutes to spare this time. Well done!<br /><br />He <a href="http://codeforces.com/blog/entry/57257">will be representing</a> his university in the upcoming ICPC World Finals in Beijing, along with a few others that you can see in the screenshots on the left, so the competition there promises to be very interesting :)<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-pk4T1lcwi-E/WomWgMWcaxI/AAAAAAAB-2g/ScEKlOCldAY8899XQvtQczwQw5ont7LCQCLcBGAs/s1600/oc1718gomeltop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="208" data-original-width="802" height="164" src="https://4.bp.blogspot.com/-pk4T1lcwi-E/WomWgMWcaxI/AAAAAAAB-2g/ScEKlOCldAY8899XQvtQczwQw5ont7LCQCLcBGAs/s640/oc1718gomeltop5.png" width="640" /></a></div>Finally, the Open Cup Grand Prix of Gomel on Sunday provided another glimpse into full team performances (<a href="http://opentrains.snarknews.info/~ejudge/res/res10412">results</a>, top 5 on the left). Moscow SU team Red Panda has found the winning ways again, this time thanks to being the only team to solve problem I — and doing it in the beginning of the third hour of the contest, which is quite unusual for a problem with only one solver. Congratulations!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-WEfvf-hmRJM/WomYxZ4FE1I/AAAAAAAB-2w/xqqyJFnE1i0b1I_1PVw9XubXs64dTi58QCLcBGAs/s1600/IMG_20180205_124154.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1200" data-original-width="1600" height="480" src="https://4.bp.blogspot.com/-WEfvf-hmRJM/WomYxZ4FE1I/AAAAAAAB-2w/xqqyJFnE1i0b1I_1PVw9XubXs64dTi58QCLcBGAs/s640/IMG_20180205_124154.jpg" width="640" /></a></div><a href="http://petr-mitrichev.blogspot.com/2018/02/a-leafy-week.html">Last week</a>, I have mentioned a data structure problem from the Open Cup. <i>n</i> people are coming to lunch and forming a queue. The people are split into disjoint groups. When <i>i</i>-th person comes to the lunch, if there's nobody from their group <i>c<sub>i</sub></i> already in the queue, they stand at the back of the queue. When there is somebody from their group already in the queue, they can also stand next to any such person (directly before or after), but only if they would be cutting in front of at most <i>a<sub>i</sub></i> people by doing so. If they have multiple positions where they can join the queue according to the above restrictions, they always pick the front-most one. Initially the queue is empty. Given the values of <i>c<sub>i</sub></i> and <i>a<sub>i</sub></i> in the order the people come to lunch, how will the final queue look like?<br /><br />One could immediately start thinking about standard approaches applicable in this problem. The fact that we need to be able to run a query against the last <i>a<sub>i</sub></i> people in the queue suggests that we should probably use a balanced tree that supports quick splitting, like a treap, and maintain the size of the subtree plus some additional structures necessary to answer queries in each node. This approach can probably be made to work, but the nice thing about the problem is that we can obtain a much easier to code solution.<br /><br />Since every person only ever joins the queue either in last position, or next to a person from their group, if we maintain the queue as a list of segments of people from the same group, in other words as a list of (group, counter) pairs, then the only operations we need to support is to increment a counter and to add a new group to the end of the list. Now in order to find a place for the next person we need to find the set of groups corresponding to the last <i>a<sub>i</sub></i>+1 people, and then find the first group of the required type in that set.<br /><br />In order to find the boundary on the group level, we need to be able to find the largest prefix for which the sum of counters does not exceed a given value. This can be done in O(log<i>n</i>) by maintaining the counters in <a href="http://petr-mitrichev.blogspot.com/2013/05/fenwick-tree-range-updates.html">a Fenwick tree</a>, I will give more details below.<br /><br />And in order to find the first group of the required kind after the given one, we can simply maintain a vector of indices of groups for each kind. Since we only ever create new groups at the end, these indices never change, and a simple binary search can find the first group of the given kind after a given index.<br /><br />Finally, after we know what happens with groups we know at which position does each person enter the queue, but we still need to output the final order. This can be done using the same Fenwick tree with "largest prefix with sum not exceeding <i>x</i>" operation we already used: we go from the end and maintain the free spots in the Fenwick tree.<br /><br />So instead of a balanced tree with extra information in nodes, we've managed to get by using two very easy to code data structures: a Fenwick tree, and a vector. The solution is O(<i>n</i>log<i>n</i>), and the constant hidden in O() is also really small.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-E6bkp1G9WUQ/WonYDa4qttI/AAAAAAAB-3E/hP1Kq8fxV2cG5V3F8N7peZ0u0O_yJYU1wCLcBGAs/s1600/IMG_20180205_125812.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" data-original-height="1200" data-original-width="1600" height="480" src="https://1.bp.blogspot.com/-E6bkp1G9WUQ/WonYDa4qttI/AAAAAAAB-3E/hP1Kq8fxV2cG5V3F8N7peZ0u0O_yJYU1wCLcBGAs/s640/IMG_20180205_125812.jpg" width="640" /></a></div>This solution used the following non-standard operation on <a href="http://petr-mitrichev.blogspot.com/2013/05/fenwick-tree-range-updates.html">a Fenwick tree</a>: find the largest prefix with sum not exceeding <i>x</i>. A naive implementation using binary search and Fenwick prefix sums would give O(log<sup>2</sup><i>n</i>) complexity, which would most likely still be fast enough to get the problem accepted. However, <a href="http://codeforces.com/profile/tgehr">tgehr</a> has pointed out to me that the standard Fenwick tree allows an extremely simple O(log<i>n</i>) way to answer this question.<br /><br />Suppose our Fenwick tree has <i>n</i> elements, and <i>k</i> is the largest power of 2 not exceeding <i>n</i>. The (2<sup><i>k</i></sup>-1)-th element of the Fenwick tree array contains the sum <i>s</i> of elements on the segment [0;2<sup><i>k</i></sup>-1], so by comparing <i>x</i> with just this number we know if our answer is below or above 2<sup><i>k</i></sup>. Let's suppose it's above 2<sup><i>k</i></sup>. Then we notice that (2<sup><i>k</i></sup>+2<sup><i>k-1</i></sup>-1)-th element of the Fenwick tree array contains the sum of elements on the segment [2<sup><i>k</i></sup>;2<sup><i>k</i></sup>+2<sup><i>k-1</i></sup>-1], so by comparing <i>x</i>-<i>s</i> with just this number we know if our answer is below or above 2<sup><i>k</i></sup>+2<sup><i>k-1</i></sup>. We continue traversing the powers of two in the same manner, and it turns out that the standard Fenwick tree stores exactly the sums needed to execute this binary search! Here's the actual code:<br /><br /><pre style="font-family: "Courier New"; font-size: 9pt;"><span style="color: navy; font-weight: bold;">private int </span>upperBound(<span style="color: navy; font-weight: bold;">int</span>[] f, <span style="color: navy; font-weight: bold;">int </span>x) {<br /> <span style="color: navy; font-weight: bold;">int </span>res = <span style="color: blue;">0</span>;<br /> <span style="color: navy; font-weight: bold;">int </span>max = Integer.<span style="font-style: italic;">numberOfTrailingZeros</span>(<br /> Integer.<span style="font-style: italic;">highestOneBit</span>(f.<span style="color: #660e7a; font-weight: bold;">length</span>));<br /> <span style="color: navy; font-weight: bold;">for </span>(<span style="color: navy; font-weight: bold;">int </span>k = max; k >= <span style="color: blue;">0</span>; --k) {<br /> <span style="color: navy; font-weight: bold;">int </span>p = res + (<span style="color: blue;">1 </span><< k) - <span style="color: blue;">1</span>;<br /> <span style="color: navy; font-weight: bold;">if </span>(p < f.<span style="color: #660e7a; font-weight: bold;">length </span>&& f[p] <= x) {<br /> x -= f[p];<br /> res += <span style="color: blue;">1 </span><< k;<br /> }<br /> }<br /> <span style="color: navy; font-weight: bold;">return </span>res;<br />}</pre><pre style="font-family: "Courier New"; font-size: 9pt;"></pre>Thanks for reading, and check back next week.</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/nDCbo53MML8" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2018/02/a-fenwick-bound-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-77502096597372205262018-02-12T01:33:00.002+03:002018-02-12T01:33:48.754+03:00A leafy week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-Lc0I4uXSuXk/WoCzS85OQjI/AAAAAAAB-jo/CBZczFflSIEdf5i3u6u9Z9_LLLBej1UDwCLcBGAs/s1600/srm729top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="95" data-original-width="639" height="94" src="https://4.bp.blogspot.com/-Lc0I4uXSuXk/WoCzS85OQjI/AAAAAAAB-jo/CBZczFflSIEdf5i3u6u9Z9_LLLBej1UDwCLcBGAs/s640/srm729top5.png" width="640" /></a></div>This week featured two weekend contests. First, TopCoder SRM 729 took place on Saturday (<a href="https://community.topcoder.com/stat?c=round_overview&rd=17082">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17082&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://youtu.be/Ugf5kbxmV_8">my screencast with commentary</a>). If you sum up the problem columns in the screenshot on the left, you can notice that the sum doesn't match the score column, and that's because the match presented ample opportunities for challenging. You can see on the screencast as I try to prepare an uber-challenge-case for the 450 during the intermission, and spent the beginning of the challenge phase getting it to work, while many solutions were already being challenged. uwi has made the best use of the challenge opportunities and thus claimed the first place. Well done!<br /><br />Most of the challenge opportunities presented themselves in <a href="https://community.topcoder.com/stat?c=problem_statement&pm=14716&rd=17082">the medium problem</a>, which looked very standard at first glance. You are given a 1000x1000 grid. In one jump, you can move from a cell to any other cell that's <i>at least</i> the given distance <i>d</i> away — you can't jump very close. What is the smallest number of jumps required to get from one given cell to another given cell?<br /><br />We could use a standard breadth-first search to solve this problem, but we have 1 million cells and potentially 1 million jumps from each cell, so the total running time would be on the order of 10<sup>12</sup> which is too slow. Can you see at least one way to speed this solution up? (there are many!)<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-LzovCJtgAVM/WoC2if692jI/AAAAAAAB-j0/wo5tqAS8xooSkg_5XqtL1qpxMkl-ivUnwCLcBGAs/s1600/oc1718khamovnikitop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="356" data-original-width="1508" height="150" src="https://3.bp.blogspot.com/-LzovCJtgAVM/WoC2if692jI/AAAAAAAB-j0/wo5tqAS8xooSkg_5XqtL1qpxMkl-ivUnwCLcBGAs/s640/oc1718khamovnikitop5.png" width="640" /></a></div>The other weekend contest was the Open Cup 2017-18 Grand Prix of Khamovniki (<a href="http://opentrains.snarknews.info/~ejudge/res/res10411">results</a>, top 5 on the left). Unlike the previous round, the active ICPC teams from Russia were not at the top of the standings, with only two ICPC teams from Asia and a veteran team Past Glory able to solve 10 problems — congratulations, and especially to Seoul National U 2 team for another Open Cup victory!<br /><br /><a href="https://official.contest.yandex.ru/opencupXVIII/contest/7410/problems/D/">Problem D</a> "Lunch Queue" was from the rare species of data structure problems that I enjoyed solving. <i>n</i> people are coming to lunch and forming a queue. The people are split into disjoint groups. When <i>i</i>-th person comes to the lunch, if there's nobody from their group <i>c<sub>i</sub></i> already in the queue, they stand at the back of the queue. When there is somebody from their group already in the queue, they can also stand next to any such person (directly before or after), but only if they would be cutting in front of at most <i>a<sub>i</sub></i> people by doing so. If they have multiple positions where they can join the queue according to the above restrictions, they always pick the front-most one. Initially the queue is empty. Given the values of <i>c<sub>i</sub></i> and <i>a<sub>i</sub></i> in the order the people come to lunch, how will the final queue look like?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-HrwOnXLaIrQ/WoDEeesX_5I/AAAAAAAB-k8/VSRIGkUmZYI8pxDgyKrQVqF6jC-sJk4MgCLcBGAs/s1600/IMG_20180120_134215.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="817" data-original-width="1600" height="326" src="https://1.bp.blogspot.com/-HrwOnXLaIrQ/WoDEeesX_5I/AAAAAAAB-k8/VSRIGkUmZYI8pxDgyKrQVqF6jC-sJk4MgCLcBGAs/s640/IMG_20180120_134215.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2018/02/a-red-panda-week.html">my previous summary</a>, I have mentioned a hard AtCoder problem: you are given a rooted tree with <i>n</i> vertices, and each vertex contains an integer between 1 and <i>n</i>, each number appearing exactly once. Your goal is to rearrange the numbers in such a way that vertex 1 has number 1, vertex 2 has number 2, and so on. You're allowed to do the following transformation: take the path connecting the root of the tree with any vertex <i>v</i>, and cyclically rotate it, placing the number that was in root into <i>v</i>, the number that was in <i>v</i> into the parent of <i>v</i>, and so on — essentially a generalization of insertion sort from a single path to an arbitrary tree. You need to sort the tree in at most 25000 operations for <i>n</i>=2000.<br /><br />I did not solve the problem myself, so I will describe the solution from the official analysis. First, we can notice that given any leaf, we can put the correct value into it in <=<i>n</i> operations (first pull it up to the root, then put it into the leaf in one rotation, and then never touch this leaf again, so we could sort everything in <i>n</i><sup>2</sup> operations, which is too much.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-yD6nzIjFeMQ/WoDDiLabZlI/AAAAAAAB-kg/cH1yleFlC38Y3YO6x2g5Qht3rCwj4RPTACKgBGAs/s1600/IMG_20180211_231731.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" data-original-height="858" data-original-width="1600" height="213" src="https://1.bp.blogspot.com/-yD6nzIjFeMQ/WoDDiLabZlI/AAAAAAAB-kg/cH1yleFlC38Y3YO6x2g5Qht3rCwj4RPTACKgBGAs/s400/IMG_20180211_231731.jpg" width="400" /></a></div>However, we can notice that in this approach we have quite a lot of freedom for choosing the moves that pull the given number up. We could try to use this freedom to try to pull up the numbers for all leaves, not just for one leaf. But even that would not be enough, as when our rooted tree is a chain it only has one leaf. However, we know that for a chain a simple solution is possible, called the normal insertion sort: we'll do exactly <i>n</i> operations, and after <i>k</i> operations we'd have <i>k</i> bottom numbers of the chain already sorted in correct order, in each turn inserting the new number to the appropriate place.<br /><br />Now we need to combine the ideas of pulling the required number from anywhere in the tree with the idea of filling a chain in one O(<i>n</i>) operation stage in such a way that the number of stages would be O(log(<i>n</i>)) for any rooted tree. More precisely, we will find all <i>leaf chains</i> in the tree — chains that hang at the bottom with nothing else attached to them, and fill them all with correct values in one stage. This guarantees O(log(<i>n</i>)) stages since the number of leaves is divided by at least two after each stage.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-4sdw9pAN-Pk/WoDDnJhsUCI/AAAAAAAB-ko/2oavhsGNvUQzRAw4LjV15sa4KAvGhZ0OwCKgBGAs/s1600/IMG_20180211_232515.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1600" data-original-width="1330" height="640" src="https://2.bp.blogspot.com/-4sdw9pAN-Pk/WoDDnJhsUCI/AAAAAAAB-ko/2oavhsGNvUQzRAw4LjV15sa4KAvGhZ0OwCKgBGAs/s640/IMG_20180211_232515.jpg" width="530" /></a></div>Whenever the root of the tree has a <i>useful</i> value — one that must be in one of the leaf chains — we will send it there, inserting it into the correct place relative to other values that we've sent to the same leaf chain, just like the insertion sort approach above. And when the root has a useless value, we need to send it somewhere, so let's send it to any position which contains a useful number, but such that all its subtree contains either only useless numbers, or useful numbers that are already placed into the corresponding leaf chain (in other words, the numbers that we don't need to get to the root anymore). This will push this useful number towards the root, and create a subtree that doesn't have any numbers that we want to get to the root.<br /><br />Why does this cycle finish eventually, and more importantly why does it run in O(<i>n</i>) operations? Each useful value passes through the root only once. A useless value, after passing through the root, ends up being in a dormant subtree, and would never pass through the root again, unless we need to touch this subtree because we're putting a useful value into it. In each such operation, at most one value moves from a dormant subtree back into circulation, and thus can reach the root again. So the total number of times a useless value that we've already seen once returns to the root does not exceed the total number of times we put a useful value into its place, meaning that the total number of operations for one stage is at most <i>n</i> plus total size of leaf paths, so O(<i>n</i>).<br /><br />Thanks for reading, and check back next week!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/wO-7fBCpt1c" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2018/02/a-leafy-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-33498081314498190062018-02-10T01:16:00.000+03:002018-02-10T01:16:32.193+03:00A Red Panda week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-dn2cZ_z7rCA/WnzHMhO8HpI/AAAAAAAB-gE/dvcULUKJqMcJt9PDvLMtFnIYuoCOFGzSwCLcBGAs/s1600/cf459top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="274" data-original-width="1449" height="120" src="https://2.bp.blogspot.com/-dn2cZ_z7rCA/WnzHMhO8HpI/AAAAAAAB-gE/dvcULUKJqMcJt9PDvLMtFnIYuoCOFGzSwCLcBGAs/s640/cf459top5.png" width="640" /></a></div>Last week started with Codeforces Round 459 on Monday (<a href="http://codeforces.com/contest/917">problems</a>, <a href="http://codeforces.com/contest/917/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/57420">analysis</a>). Once again the hardest problem was too much to handle, and OO0OOO00O0OOO0O00OOO0OO was quite a lot faster on the first four. Congratulations on the win!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-2WIfwix18RA/Wn2O69ZjvRI/AAAAAAAB-hs/37H2-P_sbogIAawhvbnUvCMdorAPLuepgCLcBGAs/s1600/apc001top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="495" data-original-width="1173" height="268" src="https://1.bp.blogspot.com/-2WIfwix18RA/Wn2O69ZjvRI/AAAAAAAB-hs/37H2-P_sbogIAawhvbnUvCMdorAPLuepgCLcBGAs/s640/apc001top5.png" width="640" /></a></div>On Saturday, AtCoder hosted an unusually long 5-hour contest called AtCoder Petrozavodsk Contest 001 (<a href="https://apc001.contest.atcoder.jp/assignments">problems</a>, <a href="https://apc001.contest.atcoder.jp/standings#page_1">results</a>, top 5 on the left, <a href="https://youtu.be/oiJW5-wp_a8">my screencast</a>, <a href="https://img.atcoder.jp/apc001/editorial.pdf">analysis</a>). There was a huge difficulty gap between the first six problems, all of which were solved by 52 contestants, and the last four. Only two contestants have managed to solve two of the more difficult kind. Congratulations to Marcin and vepifanov on this amazing feat!<br /><br />The most approachable problem of the difficult kind, <a href="https://apc001.contest.atcoder.jp/tasks/apc001_h">problem H</a>, went like this: you are given a rooted tree with <i>n</i> vertices, and each vertex contains an integer between 1 and <i>n</i>, each number appearing exactly once. Your goal is to rearrange the numbers in such a way that vertex 1 has number 1, vertex 2 has number 2, and so on. You're allowed to do the following transformation: take the path connecting the root of the tree with any vertex <i>v</i>, and cyclically rotate it, placing the number that was in root into <i>v</i>, the number that was in <i>v</i> into the parent of <i>v</i>, and so on — essentially a generalization of insertion sort from a single path to an arbitrary tree. You need to sort the tree in at most 25000 operations for <i>n</i>=2000.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-PE373O3yt64/Wn4YUyCa5rI/AAAAAAAB-ik/4kgq-Ju3IqQgjg2qHPjMsUFhrs6Hp6QpgCLcBGAs/s1600/oc1718koreatop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="269" data-original-width="886" height="194" src="https://4.bp.blogspot.com/-PE373O3yt64/Wn4YUyCa5rI/AAAAAAAB-ik/4kgq-Ju3IqQgjg2qHPjMsUFhrs6Hp6QpgCLcBGAs/s640/oc1718koreatop5.png" width="640" /></a></div>Finally, the Open Cup season came back from the winter break on Sunday with the Grand Prix of Korea (<a href="http://opencup.ru/index.cgi?data=macros/stage&head=index&menu=index&stg=10&region=main&ncup=oci&class=oci">results</a>, top 5 on the left). Moscow State University team Red Panda have won the contest by a whole problem ahead of other super strong university and veteran teams. Congratulations on the victory!<br /><br />Since the problems for this contest came from Korea, I can't help but wonder if top Korean/Asian ICPC teams have also solved this problemset elsewhere, or will do that later. Does anybody have some scoreboards to share?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-dw2qhzaPsTs/Wn4dYoChGqI/AAAAAAAB-jA/lUUu-R1xT6wSofmvAMSSrGY0cZ8VaELJgCLcBGAs/s1600/IMG_20180113_151939%2B%25281%2529.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1200" data-original-width="1600" height="480" src="https://4.bp.blogspot.com/-dw2qhzaPsTs/Wn4dYoChGqI/AAAAAAAB-jA/lUUu-R1xT6wSofmvAMSSrGY0cZ8VaELJgCLcBGAs/s640/IMG_20180113_151939%2B%25281%2529.jpg" width="640" /></a></div><a href="http://petr-mitrichev.blogspot.com/2018/01/a-topcoder-week.html">Last week</a> I have mentioned a 250-point TopCoder problem: you are given 50 integers, each up to a billion. In one step, you can take any integer that is greater than 1 and divide it by 2. If it was odd, you can choose whether to round up or down. What is the smallest number of steps required to make all integers equal?<br /><br />My thinking went like this: instead of deciding immediately whether we'd round up or down, let's keep a set of possible values for each integer, which will always be a segment [<i>min</i>;<i>max</i>]. After dividing some numbers by 2 a few times, we'll have such segment for each number. Whenever these segments all have a non-empty intersection, we're done.<br /><br />For example, if our initial numbers are 3, 5, and 13, then we start with segments [3;3], [5;5] and [13;13]. After dividing the last number by 2 we have [3;3], [5;5] and [6;7]. After doing it again we have [3;3], [5;5] and [3;4]. After dividing the second number by 2 we have [3;3], [2;3] and [3;4]. Now all our segments intersect in point 3, so we can make all numbers equal to 3.<br /><br />The only remaining thing is to decide which numbers to divide by 2, but it actually flows naturally from the above observation. What does it mean when all segments do <i>not</i> have an intersection? It means that there are two segments [<i>a</i>;<i>b</i>] and [<i>c</i>;<i>d</i>] that do not intersect (this is not true for arbitrary sets, but it is true for segments), without loss of generality we have <i>b</i><<i>c</i>. But then we must divide the segment [<i>c</i>;<i>d</i>] by 2, otherwise it will never intersect with [<i>a</i>;<i>b</i>] or its descendants. So as long as we don't have an intersection, we can always find a segment to divide by 2 this way.<br /><br />Thanks for reading, and check back in a couple of days for this week's summary!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/9Mtp9zJuvZs" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2018/02/a-red-panda-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-62919371577215882682018-01-28T23:54:00.001+03:002018-01-28T23:54:11.350+03:00A TopCoder week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-cQG2v6fYUnE/Wm4x_-wYYHI/AAAAAAAB94E/AFdGzLaSjj42FLPl8PL0u4ufMkwtwqRnQCLcBGAs/s1600/srm728top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="98" data-original-width="639" src="https://4.bp.blogspot.com/-cQG2v6fYUnE/Wm4x_-wYYHI/AAAAAAAB94E/AFdGzLaSjj42FLPl8PL0u4ufMkwtwqRnQCLcBGAs/s1600/srm728top5.png" /></a></div>TopCoder SRM 728 was this week's contest (<a href="https://community.topcoder.com/stat?c=round_overview&rd=17064">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17064&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/57324?#comment-409800">analysis</a>, <a href="https://youtu.be/7ZBljIFRgFU">my screencast</a>). <a href="https://community.topcoder.com/stat?c=problem_statement&pm=13257&rd=17064">The hard problem</a> was a relatively straightforward application of the Burnside's lemma, which I <a href="http://petr-mitrichev.blogspot.com/2008/11/burnsides-lemma.html">described in this blog</a> more than 9 (!) years ago. <a href="https://community.topcoder.com/stat?c=problem_statement&pm=14807&rd=17064">The easy problem</a> allowed a ton of completely different correct approaches, and thus in a sense was more interesting: you are given 50 integers, each up to a billion. In one step, you can take any integer that is greater than 1 and divide it by 2. If it was odd, you can choose whether to round up or down. What is the smallest number of steps required to make all integers equal?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-mjAt8oV_QaY/Wm42QoPl5dI/AAAAAAAB94Y/v-3-1Rp3XH02X0Vu7vxt9YKO8IS_MYcNgCLcBGAs/s1600/srm727top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="149" data-original-width="775" height="122" src="https://2.bp.blogspot.com/-mjAt8oV_QaY/Wm42QoPl5dI/AAAAAAAB94Y/v-3-1Rp3XH02X0Vu7vxt9YKO8IS_MYcNgCLcBGAs/s640/srm727top5.png" width="640" /></a></div>I've also just realized that I forgot to cover the previous SRM, TopCoder SRM 727 which took place two weeks ago very early in the morning (<a href="https://community.topcoder.com/stat?c=round_overview&rd=17055">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17055&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/57012?#comment-406865">analysis</a>). lych_cys, participating in Division 1 for the first time, has squeezed the victory during the challenge phase from wxh010910, who was doing only his third Division 1 round himself, while the rest of the pack was more than 100 points behind. Congratulations to the winning newcomers!<br /><br />Thanks for reading, and check back next week!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/M-xetJx0tx0" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2018/01/a-topcoder-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-23919236988833755622018-01-22T03:49:00.002+03:002018-01-22T03:49:32.346+03:00A mean median week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-3D_vOE0aPGM/WmUSQXOXF-I/AAAAAAAB8-g/HCHd1NV5YZo2EfIDzfFHojrU5Lo7wYWogCLcBGAs/s1600/cf458top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="273" data-original-width="1106" height="156" src="https://3.bp.blogspot.com/-3D_vOE0aPGM/WmUSQXOXF-I/AAAAAAAB8-g/HCHd1NV5YZo2EfIDzfFHojrU5Lo7wYWogCLcBGAs/s640/cf458top5.png" width="640" /></a></div>This week Codeforces hosted its Round 458, also known as CodeCraft-18 (<a href="http://codeforces.com/contest/914">problems</a>, <a href="http://codeforces.com/contest/914/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/57250">analysis</a>). Syloviaely has made a solid claim to the first place by submitting the 3000-point problem F just 13 minutes after the contest started (was it a previously known problem, or was it really fast solving?..), but SkyDec has gathered a whopping 800 points from challenges on two different problems, 450 on B and 350 on C, and thus finished first with quite a margin. Congratulations!<br /><br />This round also had a great side story — the top-rated contestant, Um_nik, decided to go for the hardest problem H, and that bet did not play out well as he spent too much time on it and as I understood also discovered an incorrect output in one of the samples (which means an incorrect reference solution?..). The admins <a href="http://codeforces.com/blog/entry/57208?#comment-408909">have decided</a> to make the round unrated for him because of the incorrect sample issue, but he asked them to reverse that decision (and thus make him lose rating) because he <a href="http://codeforces.com/blog/entry/57208?#comment-408890">deemed</a> the issue did not impact him significantly. Kudos to Um_nik for the admirable honesty!<br /><br /><div style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><iframe allow="autoplay; encrypted-media" allowfullscreen="" frameborder="0" height="315" src="https://www.youtube.com/embed/_EAAPHgEFYk" width="560"></iframe></div><a href="http://petr-mitrichev.blogspot.com/2018/01/an-umnik-week.html">Last week</a>, I have mentioned <a href="https://agc020.contest.atcoder.jp/tasks/agc020_c">an AtCoder problem</a>: you are given <i>n</i><=2000 positive integers, each up to <i>a</i><=2000. Consider all 2<sup><i>n</i></sup>-1 nonempty subsets, and compute the sum of the numbers in each subset. Now sort those sums, and find the median sum — the 2<sup><i>n</i>-1</sup>-th in the sorted order. You need to output this median sum. Time limit is 2 seconds.<br /><br />At first sight, the problem appears somewhat standard: we can run the knapsack dynamic programming that computes the number of ways to get each possible sum, and then go from lower sums to higher sums until we get 2<sup><i>n</i>-1 </sup>in total.<br /><br />This has two issues, though: first, the maximum sum is <i>n</i>*<i>a</i>, so the dynamic programming runs in O(<i>n</i><sup>2</sup>*<i>a</i>). Second, the number ways to get each sum can be on the order of 2<sup><i>n</i></sup>, so we need big integers, and the running time after accounting for that is more like O(<i>n</i><sup>3</sup>*<i>a</i>). Even O(<i>n</i><sup>2</sup>*<i>a</i>) is too slow.<br /><br />Here comes the insight: notice that all sums can be split in pairs. If the sum of all numbers is <i>s</i>, then for each subset with sum <i>x</i> we'll have the complementary subset with sum <i>s</i>-<i>x</i> (let's also include the empty subset). One of those sums is <=<i>s</i>/2, and the other is >=<i>s</i>/2, so the median is roughly equal to <i>s</i>/2. More precisely, the median will always be the smallest sum that is >=<i>s</i>/2.<br /><br />This allows us to get rid of the big integers, as now we merely need to know which sums are possible, and don't care about the number of ways anymore. Moreover, we can use bitmasks to speed up this O(<i>n</i><sup>2</sup>*<i>a</i>) solution ~32-64 times which makes it fast enough.<br /><br />Thanks for reading, and check back next week!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/mQaypV05LHA" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2018/01/a-mean-median-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-60810786266368224952018-01-15T00:32:00.000+03:002018-01-15T00:32:05.366+03:00An Um_nik week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-CvofOhRiXd8/WlvF7X7Wo8I/AAAAAAAB80Y/j425zUJ8W2oRheJwgD6bGWslRZSMGraOACLcBGAs/s1600/hello2018top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="274" data-original-width="1106" height="158" src="https://1.bp.blogspot.com/-CvofOhRiXd8/WlvF7X7Wo8I/AAAAAAAB80Y/j425zUJ8W2oRheJwgD6bGWslRZSMGraOACLcBGAs/s640/hello2018top5.png" width="640" /></a></div>This week's contests shared one of the problemsetters — and the winner. On Monday, Codeforces hosted its Hello 2018 round (<a href="http://codeforces.com/contest/913">problems</a>, <a href="http://codeforces.com/contest/913/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/56992">analysis</a>). With the hardest problem having too much piecewise polynomial integration, the competition focused on the remaining seven. Only Um_nik could get them all, and even with 24 minutes to spare — congratulations!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-ztxD2wBTnxc/WlvFLlqvKgI/AAAAAAAB80Q/s6fv3UfXUzoxblK_WsUlnJT4xwXzAtjiwCLcBGAs/s1600/agc020top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="446" data-original-width="905" height="314" src="https://2.bp.blogspot.com/-ztxD2wBTnxc/WlvFLlqvKgI/AAAAAAAB80Q/s6fv3UfXUzoxblK_WsUlnJT4xwXzAtjiwCLcBGAs/s640/agc020top5.png" width="640" /></a></div>On Sunday, AtCoder Grand Contest 020 started <a href="https://atcoder.jp/post/171">the race to Japan</a> (<a href="https://agc020.contest.atcoder.jp/assignments">problems</a>, <a href="https://agc020.contest.atcoder.jp/standings#page_1">results</a>, top 5 on the left, <a href="https://youtu.be/6rFmqWl_RwA">my screencast</a>, <a href="https://img.atcoder.jp/agc020/editorial.pdf">analysis</a>). Once again the hardest problem by tourist was a tiny bit too hard (and I even solved it after the contest by integrating polynomials, probably inspired by the analysis of the previous contest), and once again Um_nik was way faster than everybody else on the remaining problems — big congratulations again!<br /><br />I found <a href="https://agc020.contest.atcoder.jp/tasks/agc020_c">problem C</a> quite cute. You are given <i>n</i><=2000 positive integers, each up to 2000. Consider all 2<sup>n</sup>-1 nonempty subsets, and compute the sum of the numbers in each subset. Now sort those sums, and find the median sum — the 2<sup>n-1</sup>-th in the sorted order. You need to output this median sum. Time limit is 2 seconds.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-u4HjmJRYhmY/WlvME4BS8jI/AAAAAAAB804/pfJxX291iLgQjEjHpAVce5B1bESvjhipgCLcBGAs/s1600/IMG_20180106_134848.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1165" data-original-width="1600" height="466" src="https://1.bp.blogspot.com/-u4HjmJRYhmY/WlvME4BS8jI/AAAAAAAB804/pfJxX291iLgQjEjHpAVce5B1bESvjhipgCLcBGAs/s640/IMG_20180106_134848.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2018/01/an-otherland-week.html">my last post</a> I've discussed what was arguably <a href="http://codeforces.com/gym/101611/problem/E">the hardest contest problem</a> of 2017: you are given an undirected graph with at most 200000 vertices and edges. Your goal is to split its vertices into four disjoint groups A, B, C, D in such a way that:<br /><ul style="text-align: left;"><li>The subgraph formed by groups A+B is connected and has at least 2 vertices.</li><li>The subgraph formed by groups C+D is connected and has at least 2 vertices.</li><li>Each vertex in A has an edge to each vertex in C.</li><li>There are no other edges between subgraphs A+B and C+D.</li></ul>If there are many possible solutions, you need to output any one of them.<br /><br />Thanks to great ideas and pointers by Swistakk, mnbvmar and lewin, we were able to put together a O(<i>n*</i>log<i>n</i>) solution — you can check it out in <a href="http://codeforces.com/blog/entry/56977?#comment-406180">this comment thread</a>.<br /><br />Thanks for reading, and check back next week!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/qeYbQW_151s" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2018/01/an-umnik-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-1039776478056843932018-01-08T01:37:00.001+03:002018-01-08T01:37:52.851+03:00An Otherland week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-i7OFSaWC9b0/WlKgbzS90mI/AAAAAAAB8qI/wKk5N-WuvvIE3cAT6G3cOuu2OmdRkLQYQCKgBGAs/s1600/IMG_20180107_233307.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1104" data-original-width="1600" height="275" src="https://1.bp.blogspot.com/-i7OFSaWC9b0/WlKgbzS90mI/AAAAAAAB8qI/wKk5N-WuvvIE3cAT6G3cOuu2OmdRkLQYQCKgBGAs/s400/IMG_20180107_233307.jpg" width="400" /></a></div>The first week of 2018 was quite calm, with the most devoted taking stabs at the still-ongoing <a href="https://contest.yandex.com/newyear2018/contest/7006/standings/">Prime New Year contest</a> by snarknews. Only one problem remains unsolved there, and it looks like it might take some team effort to crack it. I think it's within the spirit of the contest to discuss its problems publicly (after all, many even have analysis posted online), so I propose to do just that. Please skip the following paragraphs if you don't want spoilers!<br /><br /><a href="https://contest.yandex.com/newyear2018/contest/7006/problems/19/">The problem</a> goes like this: you are given an undirected graph with at most 200000 vertices and edges. Your goal is to split its vertices into four disjoint groups A, B, C, D in such a way that:<br /><ul style="text-align: left;"><li>The subgraph formed by groups A+B is connected and has at least 2 vertices.</li><li>The subgraph formed by groups C+D is connected and has at least 2 vertices.</li><li>Each vertex in A has an edge to each vertex in C.</li><li>There are no other edges between subgraphs A+B and C+D.</li></ul>If there are many possible solutions, you need to output any one of them.<br /><br />I have been thinking about the problem for some time, but only have the following not very helpful observations:<br /><ul style="text-align: left;"><li>If the graph has an articulation point, then we can take this point as set A, any of the components it separates as set B, and the rest as C+D. So we can assume the graph is vertex-biconnected.</li><li>The answer is not always "Yes" - the smallest counterexample is the graph with 4 vertices and 5 edges. This example also shows that if a biconnected graph has a vertex of degree 2, then this vertex and both adjacent vertices must be in the same half of our splitting, since both ends of a splitting edge must have degree of at least 3 (two splitting edges plus one inside the half).</li><li>There are also counterexamples without vertices of degree 2.</li><li>There might be some hashing trick involved. I.e., for example suppose we assign a random number <i>a<sub>i</sub></i> to each vertex, and compute for each vertex the value sum(<i style="font-style: italic;">a<sub>i</sub></i><i style="font-style: italic;">-a<sub>j</sub></i>), where the summation goes over all adjacent vertices <i>j</i>. Then if we add up those values within one half of the graph (A+B in the above terminology), then almost everything will cancel out, leaving us |C|*<i>a</i><sub>A</sub>-|A|*<i>a</i><sub>C</sub>, where <i>a</i><sub>A</sub> is the sum of <i>a<sub>i </sub></i>in A. But where to go from here?..</li></ul>Please share your ideas!<br /><div><br /><div><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-gA9fL0DOvW0/WlKfGDCJ5bI/AAAAAAAB8p0/RJjBvR772KkgH0Fy5iD8AVK9GOdMEwNSwCLcBGAs/s1600/IMG_20180106_123832.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1200" data-original-width="1600" height="480" src="https://4.bp.blogspot.com/-gA9fL0DOvW0/WlKfGDCJ5bI/AAAAAAAB8p0/RJjBvR772KkgH0Fy5iD8AVK9GOdMEwNSwCLcBGAs/s640/IMG_20180106_123832.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2017/12/best-problems-of-2017.html">my last post</a>, I have held a vote for the best problem of 2017. And the winner is <a href="https://agc018.contest.atcoder.jp/tasks/agc018_f">this AtCoder problem</a> by <a href="https://twitter.com/maroon_kuri">maroonrk</a>: you are given two rooted trees on the same set of 10<sup>5</sup> vertices. You need to assign integer weights to all vertices in such a way that for <i>each</i> subtree of <i>each</i> of the trees the sum of weights is either 1 or -1, or report that it's impossible. The solution is explained in <a href="http://petr-mitrichev.blogspot.com/2017/07/a-week-with-two-trees.html">this post</a>. Congratulations to the problemsetter and to AtCoder, and thanks to all problemsetters of 2017!<br /><br />Thanks for reading, and check back next week.</div></div></div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/T2pX8PrZ63k" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2018/01/an-otherland-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-43662458876712853732017-12-31T20:43:00.000+03:002017-12-31T20:43:21.135+03:00Best problems of 2017<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-1QN3REiUF74/WkkhYnCWiVI/AAAAAAAB8L0/Ci5aAA70WoQl9Azw6HFUDYFXD29Dx9p1gCLcBGAs/s1600/IMG_20171216_120511.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1200" data-original-width="1600" height="300" src="https://2.bp.blogspot.com/-1QN3REiUF74/WkkhYnCWiVI/AAAAAAAB8L0/Ci5aAA70WoQl9Azw6HFUDYFXD29Dx9p1gCLcBGAs/s400/IMG_20171216_120511.jpg" width="400" /></a></div>I have reviewed all problems I've highlighted this year in my blog, and also the problems sent by the readers in response to my question — thanks a lot for your input! I've distilled everything to a shortlist of five problems (in chronological order):<br /><br /><ul style="text-align: left;"><li>The Open Cup problem about interactively proving the pigeonhole principle, by <a href="http://codeforces.com/profile/tunyash">tunyash</a>, with solution in <a href="http://petr-mitrichev.blogspot.com/2017/05/a-zero-pigeon-week.html">this post</a>.</li><li>The AtCoder problem about moving two chips on a subset of a DAG, by <a href="http://codeforces.com/profile/sugim48">sugim48</a>, with solution in <a href="http://petr-mitrichev.blogspot.com/2017/07/a-dynamic-nimber-week.html">this post</a>.</li><li>The IPSC problem about picking optimal sequences of red and black cards to get the first match, by <a href="http://codeforces.com/profile/misof">misof</a>, with solution in <a href="http://petr-mitrichev.blogspot.com/2017/07/a-red-black-week.html">this post</a>.</li><li>The AtCoder problem about assigning numbers to shared vertices of two trees so that all subtrees sum to +-1, by <a href="http://codeforces.com/profile/maroonrk">maroonrk</a>, with solution in <a href="http://petr-mitrichev.blogspot.com/2017/07/a-week-with-two-trees.html">this post</a>.</li><li>The Open Cup problem about interactively exploring a maze on Mars with a communication delay, by <a href="http://codeforces.com/profile/gassa">Gassa</a>, discussed in <a href="http://petr-mitrichev.blogspot.com/2017/12/a-delayed-week.html">this post</a>. </li></ul><br />What is the best problem of 2017?<br /><iframe allowtransparency="true" frameborder="0" height="176px" name="poll-widget-1975279128869797257" src="https://www.google.com/reviews/polls/display/-1975279128869797257/blogger_template/run_app?txtclr=%23666666&lnkclr=%235588aa&chrtclr=%235588aa&font=normal+normal+100%25+Georgia,+Serif&hideq=true&purl=http://petr-mitrichev.blogspot.com/" style="border: none; width: 100%;"></iframe> <br /><div>As usual around New Year, <a href="http://codeforces.com/blog/snarknews">snarknews</a> is hosting the Prime New Year contest, which consists of problems given at top-level team competitions in 2017 but not solved by anybody there. If you like real challenge and don't have much to do during the holidays, here's <a href="https://contest.yandex.com/newyear2018/contest/7006/enter/">your link</a> :)<br /><br />Guten Rutsch!<br /><br /></div></div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/D9800lGJ3P4" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/12/best-problems-of-2017.htmltag:blogger.com,1999:blog-1953325079793449971.post-18946464027473545752017-12-31T00:06:00.000+03:002017-12-31T00:06:16.396+03:00A sparse week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-CjcpnyxEKt0/WkfyOa_9D_I/AAAAAAAB8Ic/SEbicbD-LZ01WVhfYlcHpQM21bFiMLTCgCLcBGAs/s1600/goodbye2017top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="270" data-original-width="1104" height="156" src="https://4.bp.blogspot.com/-CjcpnyxEKt0/WkfyOa_9D_I/AAAAAAAB8Ic/SEbicbD-LZ01WVhfYlcHpQM21bFiMLTCgCLcBGAs/s640/goodbye2017top5.png" width="640" /></a></div>This week had the now traditional last contest of the year: Good Bye 2017 at Codeforces (<a href="http://codeforces.com/contest/908">problems</a>, <a href="http://codeforces.com/contest/908/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/56713">analysis</a>, <a href="https://youtu.be/I_dvna43rY0">my screencast</a>). The hardest problem H, after removing some layers, ended up being about finding a <a href="https://en.wikipedia.org/wiki/Graph_coloring#Vertex_coloring">proper vertex coloring</a> for a graph with <i>n</i><=23 vertices with the smallest number of colors. My first thought was: surely for such classical problem the best approaches are well-known? However, it turned out that the algorithms I could remember were a O(3<sup><i>n</i></sup>) subset dynamic programming and various heuristics to speed up backtracking, both of which seemed too slow. Thanks to <a href="http://www.wisdom.weizmann.ac.il/~dinuri/courses/11-BoundaryPNP/L01.pdf">this paper</a> I have now learned how to do this in O(<i>n</i>*2<sup><i>n</i></sup>), see point 4.2 "Inclusion-exclusion". Always nice to discover better approaches to classical problems!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-ASx3FWuA0f0/Wkf_dmdJLcI/AAAAAAAB8Jc/53-4Dum1fMwMT6FcOkEiRuDfNYRrgizrQCLcBGAs/s1600/IMG_20171217_191048.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1200" data-original-width="1600" height="480" src="https://4.bp.blogspot.com/-ASx3FWuA0f0/Wkf_dmdJLcI/AAAAAAAB8Jc/53-4Dum1fMwMT6FcOkEiRuDfNYRrgizrQCLcBGAs/s640/IMG_20171217_191048.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2017/12/a-quadratic-week.html">my previous summary</a>, I have mentioned a TopCoder problem: you are given <i>n</i>=2000000 tasks, to be done in <i>m</i>=2000 days, at most one task per day (so most of the tasks will end up not being done). For each task you know three numbers: the segment of days when it can be done (from <i>l<sub>i</sub></i> to <i>r<sub>i</sub></i>), and the profit <i>c<sub>i</sub></i> from doing it. You need to pick the task to be done in each day in such a way that the total profit is maximized.<br /><br />This can be naturally viewed as a weighted maximum matching problem, which thanks to <a href="http://petr-mitrichev.blogspot.com/2017/12/a-transversal-week.html">the transversal matroid</a> can be solved by trying to add tasks to the matching in decreasing order of profit, trying to find the augmenting path each time, and only resetting the "visited" state of each vertex once the matching is increased (this is called "Kuhn's algorithm" in the Russian-speaking community, but I couldn't find an authoritative link for it). Since the matching is only increased <i>m</i> times, we process each edge of the graph at most <i>m</i> times. The problem is that we have O(<i>n</i>*<i>m</i>) edges, so the total running time seems to be O(<i>n</i>*<i>m</i><sup>2</sup>). However, we can notice that for each task that we end up not adding to the matching we process its edges only once (since we will never visit it in subsequent iterations), so the number of actually revisited edges is O(<i>m</i><sup>2</sup>), and the running time is only O(<i>n</i>*<i>m+</i><i>m</i><sup>3</sup>), which is of course still too slow.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-EGDWp0P6jeY/Wkf-PgWSvoI/AAAAAAAB8JM/AwbzfJnAH9Aev6-t_Iz1r_bCiCxwVBAkwCKgBGAs/s1600/IMG_20171230_215810.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" data-original-height="857" data-original-width="1600" height="342" src="https://4.bp.blogspot.com/-EGDWp0P6jeY/Wkf-PgWSvoI/AAAAAAAB8JM/AwbzfJnAH9Aev6-t_Iz1r_bCiCxwVBAkwCKgBGAs/s640/IMG_20171230_215810.jpg" width="640" /></a></div>But now we can use another relatively standard trick: let's reduce the number of "active" edges from O(<i>m</i><sup>2</sup>) to O(<i>m*</i>log<i>m</i>) in the following manner: instead of a matching problem we'll now have a flow problem, and we'll add auxiliary vertices between left and right parts. The vertices will correspond to segments. First, we'll pick the middle point <i>b</i>=<i>m</i>/2, and add vertices corresponding to segments [1,<i>b</i>], [2,<i>b</i>], ..., [<i>b</i>-1,<i>b</i>], [<i>b</i>,<i>b</i>], and infinite capacity edges in this manner: [1,<i>b</i>]->[2,<i>b</i>]->...->[<i>b</i>,<i>b</i>]; [1,<i>b</i>]->1; [2,<i>b</i>]->2; ..., [<i>b</i>,<i>b</i>]-><i>b</i>. The idea is that if we add an edge from some vertex in the left part to a segment [<i>a</i>,<i>b</i>], then the flow can then go to any vertex in the right part between <i>a</i> and <i>b</i> using those infinite edges, and only to those vertices. We handle the other half in a similar way: [<i>b</i>+1,<i>b</i>+1]<-[<i>b</i>+1,<i>b</i>+2]<-...<-[<i>b</i>+1,<i>m-1</i>]<-[<i>b</i>+1,<i>m</i>]. These two sets of segments already allow to handle any task that can be done in days <i>b</i> and <i>b</i>+1 using only two edges: to [<i>l<sub>i</sub></i>,<i>b</i>] and to [<i>b</i>+1,<i>r<sub>i</sub></i>].<br /><br />We can then apply the same procedure recursively to segments [1,<i>b</i>] and [<i>b</i>+1,<i>m</i>]: for example, we'll pick the middle point <i>c</i>=<i>b</i>/2, and build the auxiliary vertices [1,<i>c</i>]->[2,<i>c</i>]->...->[<i>c</i>,<i>c</i>] and [<i>c</i>+1,<i>c</i>+1]<-[<i>c</i>+1,<i>c</i>+2]<-...<-[<i>c</i>+1,<i>b</i>], and so on. Overall we'll have log<i>m</i> sets of <i>m</i> auxiliary vertices each (one per level of recursion), with two outgoing edges for each vertex, and every task can now be handled with at most two edges to auxiliary vertices instead of O(<i>m</i>) edges to the right part. This approach resembles the centroid decomposition of a tree when applied to a chain; we could also have used the sparse table to achieve the same result.<br /><br />Now our graph has O(<i>m</i>log<i>m</i>) active edges, and additional O(<i>n</i>) edges that are visited only once, so the total running time is O(<i>n</i>+<i>m</i><sup>2</sup>*log<i>m</i>), which is fast enough.<br /><br />That's it for the contests of 2017 — thanks for reading, and check back tomorrow (hopefully) for the best problems of 2017!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/wzWFDtvO31E" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/12/a-sparse-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-87234728919840945702017-12-30T23:03:00.002+03:002017-12-31T00:17:29.290+03:00A quadratic week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-BgQ1L6gYBMI/WkfiKSoPFsI/AAAAAAAB8Hk/KPs0Ny1Djxwf_NeC85Ax7V_5Arz1R_RngCLcBGAs/s1600/cf453top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="273" data-original-width="1103" height="158" src="https://1.bp.blogspot.com/-BgQ1L6gYBMI/WkfiKSoPFsI/AAAAAAAB8Hk/KPs0Ny1Djxwf_NeC85Ax7V_5Arz1R_RngCLcBGAs/s640/cf453top5.png" width="640" /></a></div>Last week had a relatively high density of contests, so much that two of them collided: Codeforces Round 453 and TopCoder SRM 726 took place at the same time on Tuesday. The Codeforces round started 25 minutes earlier, so we'll begin with it (<a href="http://codeforces.com/contest/901">problems</a>, <a href="http://codeforces.com/contest/901/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/56478">analysis</a>). dotorya had chosen a seemingly suboptimal order to solve the first four problems, as A and B required disproportionately much time relative to their value, but he was faster than the competition and thus still ended up in first place — well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-7ED5pgjKFxw/WkfjRHRAlGI/AAAAAAAB8Hw/BXZ5kLBwazcZ9VaAAvu-jw0k3XVPhbFBgCLcBGAs/s1600/srm726top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="94" data-original-width="629" src="https://3.bp.blogspot.com/-7ED5pgjKFxw/WkfjRHRAlGI/AAAAAAAB8Hw/BXZ5kLBwazcZ9VaAAvu-jw0k3XVPhbFBgCLcBGAs/s1600/srm726top5.png" /></a></div>TopCoder SRM 726 at roughly the same time attracted the second half of the community (<a href="https://community.topcoder.com/stat?c=round_overview&rd=17048">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17048&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://youtu.be/BG2tGOJmjO0">my screencast</a>). <a href="https://community.topcoder.com/stat?c=problem_statement&pm=14750&rd=17048&rm=330805&cr=10574855">The hard problem</a> has proved decisive: you are given 2000000 tasks, to be done in 2000 days, at most one task per day (so most of the tasks will end up not being done). For each task you know three numbers: the segment of days when it can be done (from <i>l<sub>i</sub></i> to <i>r<sub>i</sub></i>), and the profit <i>c<sub>i</sub></i> from doing it. You need to pick the task to be done in each day in such a way that the total profit is maximized. This is naturally reduced to a weighted maximum matching problem, but surely it will time out with 2 million vertices in the graph — or will it?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-ZJZ3GwzJPMo/Wkflgqm7RhI/AAAAAAAB8H8/AMDXQa2ghuExhMCLI4xlblsy04TSrlCWACLcBGAs/s1600/cf454top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="273" data-original-width="1114" height="156" src="https://1.bp.blogspot.com/-ZJZ3GwzJPMo/Wkflgqm7RhI/AAAAAAAB8H8/AMDXQa2ghuExhMCLI4xlblsy04TSrlCWACLcBGAs/s640/cf454top5.png" width="640" /></a></div>Codeforces ran another round, Round 454, on Saturday (<a href="http://codeforces.com/contest/906">problems</a>, <a href="http://codeforces.com/contest/906/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/56601">analysis</a>). All problems were tractable this time for moejy0viiiiiv and Radewoosh, and in case of the former with 30 minutes to spare. Congratulations on the victory!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-O6RDnkfTK3Y/Wkfw8Ps4XpI/AAAAAAAB8IQ/CoX1NzlWcGoAueteM_XN-OUz8CLPq3wxACLcBGAs/s1600/IMG_20171216_120459.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1200" data-original-width="1600" height="480" src="https://2.bp.blogspot.com/-O6RDnkfTK3Y/Wkfw8Ps4XpI/AAAAAAAB8IQ/CoX1NzlWcGoAueteM_XN-OUz8CLPq3wxACLcBGAs/s640/IMG_20171216_120459.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2017/12/a-newton-week.html">my previous summary</a>, I have mentioned an Open Cup problem: you are given an integer <i>n</i> with at most a million digits. You need to determine if it's a perfect square or not. You don't need to actually find the square root.<br /><br />As is often the case in problems with a Yes/No answer, it suffices to find an algorithm that always finds one of the two answers correctly, and the other with a certain probability that is greater than zero. We can then apply it repeatedly until the probability of not finding the correct answer is exponentiated to become essentially zero.<br /><br />Let's pick a prime number <i>p</i>. If n is a perfect square, then <i>n</i> mod <i>p</i> is always a quadratic residue. If not, then assuming <i>p</i> is picked randomly the probability of <i>n</i> mod <i>p</i> being a quadratic residue is roughly 0.5, since roughly half of all numbers mod <i>p</i> are quadratic residues (this is merely handwaving; can anyone prove this probability estimation formally?).<br /><br />So we can pick, say, 30 random prime numbers, and check if <i>n</i> is a quadratic residue modulo each of them. If at least one says no, then the overall answer is no, otherwise it's yes. Checking if a number is a quadratic residue modulo p is done by checking if <i>n</i><sup>(<i>p</i>-1)/2</sup>=1 (mod <i>p</i>).<br /><br />Thank for reading, and check back for this week's summary!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/zOEzhkZBcqU" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/12/a-quadratic-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-52504790878233327282017-12-30T21:33:00.000+03:002017-12-30T21:33:24.868+03:00A Newton week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-ntOrf0Qgp64/WkfZYL4kFKI/AAAAAAAB8HU/-3q0rDW5XswSl9Pi3X7okCh4xlrxBnkOwCLcBGAs/s1600/oc1718peterhoftop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="269" data-original-width="849" height="202" src="https://1.bp.blogspot.com/-ntOrf0Qgp64/WkfZYL4kFKI/AAAAAAAB8HU/-3q0rDW5XswSl9Pi3X7okCh4xlrxBnkOwCLcBGAs/s640/oc1718peterhoftop5.png" width="640" /></a></div>The Dec 11 - Dec 17 week contained the last Open Cup round of the year: the Grand Prix of Peterhof (<a href="http://opencup.ru/files/oci/gp9/problems1-e.pdf">problems</a>, <a href="http://opencup.ru/index.cgi?data=macros/stage&head=index&menu=index&stg=9&region=main&ncup=oci&class=oci">results</a>, top 5 on the left). The deciding problem H required the ability to find the exponent a formal series fast, and the teams that were able to do so claimed the first two places — congratulations to the Moscow IPT team and to SPb Havka-papstvo!<br /><br />I found the relatively easy problem J very nice. You are given an integer with at most a million digits. You need to determine if it's a perfect square or not. You don't need to actually find the square root. Can you see how to get this problem accepted on the 8th minute of the contest?<br /><br />Thanks for reading, and check back soon!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/zHAamKHEpS8" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/12/a-newton-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-85839071069456912642017-12-30T20:45:00.000+03:002017-12-30T20:45:01.492+03:00A correlation week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-440xu7Mlzr4/WkfQaZfThGI/AAAAAAAB8HE/tsojKOjOXJstuaTnAyuxEbzjnhVmmqgkACLcBGAs/s1600/IMG_20171211_151032.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1200" data-original-width="1600" height="480" src="https://1.bp.blogspot.com/-440xu7Mlzr4/WkfQaZfThGI/AAAAAAAB8HE/tsojKOjOXJstuaTnAyuxEbzjnhVmmqgkACLcBGAs/s640/IMG_20171211_151032.jpg" width="640" /></a></div>The Dec 4 - Dec 10 week was another of the calm ones, so let's use this post to discuss the interactive NEERC problem I mentioned in <a href="http://petr-mitrichev.blogspot.com/2017/12/a-timing-week.html">the previous one</a>: you work with a device that takes an <i>a</i> as input and computes <i>a</i><sup><i>d</i></sup> mod <i>n</i> using the following pseudocode:<br /><br /><span style="font-family: "courier new" , "courier" , monospace;">1 modPow(a, d, n) {</span><br /><span style="font-family: "courier new" , "courier" , monospace;">2 r = 1;</span><br /><span style="font-family: "courier new" , "courier" , monospace;">3 for (i = 0; i < 60; ++i) {</span><br /><span style="font-family: "courier new" , "courier" , monospace;">4 if ((d & (1 << i)) != 0) {</span><br /><span style="font-family: "courier new" , "courier" , monospace;">5 r = r * a % n;</span><br /><span style="font-family: "courier new" , "courier" , monospace;">6 }</span><br /><span style="font-family: "courier new" , "courier" , monospace;">7 a = a * a % n;</span><br /><span style="font-family: "courier new" , "courier" , monospace;">8 }</span><br /><span style="font-family: "courier new" , "courier" , monospace;">9 }</span><br /><div><br /></div><div>However, instead of receiving the result of the computation, you only receive the <i>time</i> it took the device to execute it, which is computed in the following way: only the multiplications on lines 5 and 7 take nonzero time, and multiplying <i>x</i> by <i>y</i> modulo <i>n</i> takes (bits(<i>x</i>)+1)*(bits(<i>y</i>)+1), where bits(<i>x</i>) is the length of the binary representation of <i>x</i> without leading zeroes.</div><div><br /></div><div>You know the number <i>n</i> but not the number <i>d</i>, and your goal is to find <i>d</i> after sending at most 30000 requests to the device. You know that <i>n</i> and <i>d</i> were chosen in the following way: first, two prime numbers <i>p</i> and <i>q </i>with bits(<i>p</i>)=bits(<i>q</i>)=30 were picked independently and uniformly at random. Then <i>n</i> was computed as <i>p</i>*<i>q</i>. Then the number <i>m</i>=(<i>p</i>-1)*(<i>q</i>-1) was computed. Then <i>d</i> was picked uniformly at random between 1 and <i>m</i>-1 inclusive, such that it is coprime with <i>m</i>.<br /><br /><a href="http://neerc.ifmo.ru/archive/2017/neerc-2017-analysis.pdf">The official analysis</a> has a pretty detailed description of the intended solution starting from page 8, so let me just recap it here briefly;<br /><ul style="text-align: left;"><li>We're going to just send 30000 random queries.</li><li>Lowest bit of d is always 1, let's determine the second lowest.</li><li>If it's also 1, then we multiply <i>a</i> by <i>a</i><sup>2</sup>, otherwise we don't.</li><li>For queries where <i>a</i> and/or <i>a</i><sup>2 </sup>have less bits than usual, the overall modPow time will also be less than usual, but only on average, so we can't just tell from one <i>a</i>.</li><li>However, the correlation between the time to multiply <i>a</i> by <i>a</i><sup>2</sup> and the overall modPow time over all 30000 queries can tell us this bit with extremely high certainty.</li><li>We can then determine the next bit in the same manner, and so on.</li><li><a href="https://en.wikipedia.org/wiki/Timing_attack#Examples">This Wikipedia page</a> also describes the same idea.</li></ul>This solution is very easy to code and generalizes well to bigger constraints, but it might be hard to intuitively feel if 30000 queries gives enough certainty. Egor has suggested another approach which is a bit harder to code but easier to believe that it works (but we have not actually tried to implement it): instead of sending random queries, we will send queries such that one repeated square of them is very small modulo <i>n</i>, say, at most 10 bits. Such a query will give much more signal on whether this repeated square is used in the multiplications, since multiplying 10 by 60 bits, compared to multiplying 60 by 60 bits, is about 3000 nanoseconds faster, and standard deviation of modPow computation time if we just feed it random inputs is on the order of 1700, so the middle point is roughly one standard deviation away from each expectation. If we try, say, 49 such numbers for every bit, then we'll have seven standard deviations and will always guess correctly, so we need only 60*49 which is about 3000 queries to find all bits.<br /><br />Of course, finding a number that has few bits in a certain power modulo <i>n</i> is a hard task in itself, but here <i>n</i> is small enough that we can factorize it using <a href="https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm">Pollard's rho</a> algorithm, and after that we just need to invert the said power modulo phi(<i>n</i>) to be able to find the root of this power of any number, including ones with few bits.<br /><br />Thanks for reading, and check back for more!</div></div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/UksLI8hNvcs" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/12/a-correlation-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-88068206679876038102017-12-30T14:35:00.001+03:002017-12-30T14:35:45.078+03:00A timing week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-dUhoGkV-_Rw/Wkdrlj0FVrI/AAAAAAAB8GY/dIaEBVjXB1QFmas9dCvrdF-Y1NjWx631wCLcBGAs/s1600/srm724top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="97" data-original-width="629" src="https://3.bp.blogspot.com/-dUhoGkV-_Rw/Wkdrlj0FVrI/AAAAAAAB8GY/dIaEBVjXB1QFmas9dCvrdF-Y1NjWx631wCLcBGAs/s1600/srm724top5.png" /></a></div>The Nov 27 - Dec 3 week started with TopCoder SRM 724 (<a href="https://community.topcoder.com/stat?c=round_overview&rd=17033">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17033&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left). snuke, sugim48 and Swistakk had more coding phase points but this round was ultimately decided during the challenge phase, as <a href="https://community.topcoder.com/stat?c=problem_statement&pm=14744&rd=17033">the easy problem</a> allowed for a lot of incorrect approaches.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-6DpliuaCFZs/WkdvQSLQ99I/AAAAAAAB8Gk/Nl2TM6u8vMgxORcmTU7OCY_pa_JvozsCQCLcBGAs/s1600/cf449top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="269" data-original-width="1106" height="154" src="https://1.bp.blogspot.com/-6DpliuaCFZs/WkdvQSLQ99I/AAAAAAAB8Gk/Nl2TM6u8vMgxORcmTU7OCY_pa_JvozsCQCLcBGAs/s640/cf449top5.png" width="640" /></a></div>On Saturday, Codeforces Round 449 gave ACM ICPC 2017-18 NEERC contestants the last chance to practice, although I'm not sure if many of them did (<a href="http://codeforces.com/contest/896">problems</a>, <a href="http://codeforces.com/contest/896/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/56135">analysis</a>). In a somewhat unusual outcome, MrDindows has won the round with less problems than the second place, thanks to an extremely fast solution to the hardest problem — congratulations on the victory!<br /><br />He's managed to pull this off thanks to being able to squeeze a "naive" quadratic solution under the time limit in <a href="http://codeforces.com/contest/896/problem/E">a problem</a> with <i>n</i>=100000. This is no small feat, as demonstrated by the fact that just one other contestant was able to do it at all, even within the full two hours. Thankfully he <a href="http://codeforces.com/blog/entry/56101?#comment-398797">has explained</a> how he was able to achieve this, so that we all can learn the tricks and/or deepen our understanding of compilers!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-EehJGiSQ-5Q/Wkd2adQIOLI/AAAAAAAB8G0/o86jfgiFkFk4j_2YAWSQRilj24Xm7P6dwCLcBGAs/s1600/neerc2017top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="268" data-original-width="1184" height="144" src="https://4.bp.blogspot.com/-EehJGiSQ-5Q/Wkd2adQIOLI/AAAAAAAB8G0/o86jfgiFkFk4j_2YAWSQRilj24Xm7P6dwCLcBGAs/s640/neerc2017top5.png" width="640" /></a></div>On Sunday, the said ACM ICPC 2017-18 NEERC took place in St Petersburg (<a href="https://neerc.ifmo.ru/archive/2017/neerc-2017-statement.pdf">problems</a>, <a href="https://neerc.ifmo.ru/archive/2017/standings.html">results</a>, top 5 on the left, <a href="https://neerc.ifmo.ru/archive/2017/neerc-2017-analysis.pdf">analysis</a>, <a href="https://youtu.be/X9OLK-2Zwg8">broadcast in Russian</a>). The competition was very tight, and Moscow IPT 1 team has earned the first place with 10 minutes to go, in no small part thanks to solving the tricky problem K with just two attempts, whereas the only two other teams to get it accepted required 10 and 14 attempts. Congratulations!<br /><br />I have set problem H for this round, which was unfortunately the only one left unsolved. This is an interactive problem where you work with a device that takes an <i>a</i> as input and computes <i>a</i><sup><i>d</i></sup> mod <i>n</i> using the following pseudocode:<br /><br /><span style="font-family: Courier New, Courier, monospace;">1 modPow(a, d, n) {</span><br /><span style="font-family: Courier New, Courier, monospace;">2 r = 1;</span><br /><span style="font-family: Courier New, Courier, monospace;">3 for (i = 0; i < 60; ++i) {</span><br /><span style="font-family: Courier New, Courier, monospace;">4 if ((d & (1 << i)) != 0) {</span><br /><span style="font-family: Courier New, Courier, monospace;">5 r = r * a % n;</span><br /><span style="font-family: Courier New, Courier, monospace;">6 }</span><br /><span style="font-family: Courier New, Courier, monospace;">7 a = a * a % n;</span><br /><span style="font-family: Courier New, Courier, monospace;">8 }</span><br /><span style="font-family: Courier New, Courier, monospace;">9 }</span><br /><div><br /></div><div>However, instead of receiving the result of the computation, you only receive the <i>time</i> it took the device to execute it, which is computed in the following way: only the multiplications on lines 5 and 7 take nonzero time, and multiplying <i>x</i> by <i>y</i> modulo <i>n</i> takes (bits(<i>x</i>)+1)*(bits(<i>y</i>)+1), where bits(<i>x</i>) is the length of the binary representation of <i>x</i> without leading zeroes.</div><div><br /></div><div>You know the number <i>n</i> but not the number <i>d</i>, and your goal is to find <i>d</i> after sending at most 30000 requests to the device. You know that <i>n</i> and <i>d</i> were chosen in the following way: first, two prime numbers <i>p</i> and <i>q </i>with bits(<i>p</i>)=bits(<i>q</i>)=30 were picked independently and uniformly at random. Then <i>n</i> was computed as <i>p</i>*<i>q</i>. Then the number <i>m</i>=(<i>p</i>-1)*(<i>q</i>-1) was computed. Then <i>d</i> was picked uniformly at random between 1 and <i>m</i>-1 inclusive, such that it is coprime with <i>m</i>.</div><div><br /></div><div>Surprisingly, just knowing the time the computation takes for a few requests is enough to extract the value of <i>d</i>. Can you see how to do it?</div><div><br /></div><div>Thanks for reading, and check back later today!</div><div><br /></div></div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/c3EUKspB0sc" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/12/a-timing-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-58782618145675052552017-12-28T02:16:00.000+03:002017-12-28T02:16:10.344+03:00A directly opposite week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-Jg4Gi9_Hddo/WkQeQgjTlrI/AAAAAAAB8Do/Vifg8cl6AyYcunZ6gK2xynX7J2A4ZYN9ACLcBGAs/s1600/codefestival2017finaltop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="446" data-original-width="1175" height="242" src="https://4.bp.blogspot.com/-Jg4Gi9_Hddo/WkQeQgjTlrI/AAAAAAAB8Do/Vifg8cl6AyYcunZ6gK2xynX7J2A4ZYN9ACLcBGAs/s640/codefestival2017finaltop5.png" width="640" /></a></div>Code Festival 2017 onsite for university students and recent graduates ran by AtCoder was the biggest event of the Nov 20 - Nov 26 week. It consisted of multiple rounds, but the main and rated one was the Final (<a href="https://cf17-final.contest.atcoder.jp/assignments">problems</a>, <a href="https://cf17-final.contest.atcoder.jp/standings">results</a>, top 5 on the left, <a href="https://cf17-final-open.contest.atcoder.jp/standings">parallel round results</a>, <a href="https://img.atcoder.jp/cf17-final/editorial.pdf">analysis</a>). The problemset has provided a lot of variety, and the people at the top had quite different sets of problems solved. tourist was quite a bit faster than others — big congratulations on the victory!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-7AavdkkTqyo/WkQkErixhdI/AAAAAAAB8EI/hln8ebIHmjIixYAyXrldv7qgx0g-oJSCgCLcBGAs/s1600/oc1718europetop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="269" data-original-width="907" height="188" src="https://2.bp.blogspot.com/-7AavdkkTqyo/WkQkErixhdI/AAAAAAAB8EI/hln8ebIHmjIixYAyXrldv7qgx0g-oJSCgCLcBGAs/s640/oc1718europetop5.png" width="640" /></a></div>The Open Cup continued its weekly cadence with the Grand Prix of Europe on Sunday (<a href="http://opencup.ru/files/oci/gp8/problems1-e.pdf">problems</a>, <a href="http://opencup.ru/index.cgi?data=macros/stage&head=index&menu=index&stg=8&region=main&ncup=oci&class=oci">results</a>, top 5 on the left, <a href="http://cerc.hsin.hr/index.php?page=results">CERC results on the same problems</a>). Team japan02 had 10 problems solved even before the last hour, but could not make further progress and allowed ITMO 1 to steal the victory with two minutes to go — congratulations to both teams solving 10 problems, and to the Warsaw team who got 10 at the onsite round, also with a last-minute accepted submission!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-KbSic0d8ugU/WkQpeYMyANI/AAAAAAAB8Eg/L36wDdH5yjUfYn2nbfp0pVcyu-nN0Ph3gCLcBGAs/s1600/IMG_20171211_155643.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1127" data-original-width="1600" height="450" src="https://3.bp.blogspot.com/-KbSic0d8ugU/WkQpeYMyANI/AAAAAAAB8Eg/L36wDdH5yjUfYn2nbfp0pVcyu-nN0Ph3gCLcBGAs/s640/IMG_20171211_155643.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2017/12/a-test-driven-week.html">my previous summary</a>, I have mentioned an interactive Open Cup problem happening on the faces of a cube with each face divided into <i>n</i> times <i>n</i> cells (<i>n</i><=300). You are located on some cell on some face of the cube, facing one of the four cardinal directions, and your goal is located on some cell on some face of the cube, but you don't know where you are located and where the goal is located. All you can do is to issue commands left, right or forward, with the first two causing you to rotate in place by 90 degrees, and the last one causing you to move one cell in the direction you're facing, with moving through the sides of the cube handled in the natural way. For each move forward, the system tells you whether your new cell is closer, farther or at the same distance from the goal as the old one. The distance is defined as the Euclidean distance between the centers of the cells. You need to stop moving at the goal cell after using at most 100<i>n</i> commands.<br /><br />The solution that we got accepted looked like this: first, we try to move closer to the goal whenever we can, until we reach a cell from which all four moves don't give us a "closer" reply. This can be coded with a simple loop without the need to remember the coordinates or to even represent the sides of the cube, and will always converge in O(<i>n</i>) steps.<br /><br />Then, we're either in the goal cell or in the cell directly opposite it on the opposite face. We don't know the size of the cube, but even without it in order to transition from one to the other we can walk forward while we're not seeing a "closer" answer, and then keep moving forward while we're seeing "closer" answer. If we were in the opposite cell, we will reach the goal. If we were in the goal, then we'll either be in the opposite cell, or in the goal again after making a full loop. To distinguish the cases, we can compare the number of moves in the "not closer" state to the number of moves in the "closer" state. In case the former is bigger than the latter, we started our forward walk in the goal, and we will undo all those moves to go back to the goal. In case the latter is bigger, we're done.<br /><br />It takes some case studying and convincing oneself that this approach works in various corner cases as well, but after that the actual implementation is just a few lines.<br /><br />Thanks for reading, and check back for more!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/6y-uwELIgeI" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/12/a-directly-opposite-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-71422608987398029542017-12-27T02:09:00.002+03:002017-12-27T02:09:48.780+03:00A test-driven week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-DWYH8gR_feU/WkLJMXBdlEI/AAAAAAAB744/tpnculTqIbENFRzkBIRVLC7GPnhMoI6ZACLcBGAs/s1600/cf446top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="273" data-original-width="1102" height="158" src="https://2.bp.blogspot.com/-DWYH8gR_feU/WkLJMXBdlEI/AAAAAAAB744/tpnculTqIbENFRzkBIRVLC7GPnhMoI6ZACLcBGAs/s640/cf446top5.png" width="640" /></a></div>The Nov 13 - Nov 19 week had one each of the usual suspects. First off, Codeforces Round 446 took place on Friday (<a href="http://codeforces.com/contest/891">problems</a>, <a href="http://codeforces.com/contest/891/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/55841">analysis</a>). moejy0viiiiiv has earned his first place at the very last minute of the contest by solving D — very well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-n8xe5lZWnpA/WkLKARHwOrI/AAAAAAAB75A/iug9aUSHJsYDex_LDC_udLjEB8rM78T6gCLcBGAs/s1600/srm723top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="149" data-original-width="775" height="122" src="https://3.bp.blogspot.com/-n8xe5lZWnpA/WkLKARHwOrI/AAAAAAAB75A/iug9aUSHJsYDex_LDC_udLjEB8rM78T6gCLcBGAs/s640/srm723top5.png" width="640" /></a></div>Then, TopCoder SRM 723 happened on Saturday (<a href="https://community.topcoder.com/stat?c=round_overview&rd=17027">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17027&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://www.topcoder.com/blog/single-round-match-723-editorials/">analysis</a>, <a href="https://youtu.be/PDtOOwQcgco">my screencast</a>). Only ksun48 was able to solve the hard problem, but it took him so long that his score was on par with scores people got for their medium problem, and the first place was decided during the challenge phase.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-5WNuqsAA0TY/WkLKbCwS60I/AAAAAAAB75E/-wlX0x3qBagFiFELFQNytPfkhGP_mtk5wCLcBGAs/s1600/oc1718siberiatop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="271" data-original-width="959" height="180" src="https://2.bp.blogspot.com/-5WNuqsAA0TY/WkLKbCwS60I/AAAAAAAB75E/-wlX0x3qBagFiFELFQNytPfkhGP_mtk5wCLcBGAs/s640/oc1718siberiatop5.png" width="640" /></a></div>And finally, the Open Cup Grand Prix of Siberia wrapped up the week on Sunday (<a href="http://opencup.ru/files/oci/gp7/problems1-e.pdf">problems</a>, <a href="http://opencup.ru/index.cgi?data=macros/stage&head=index&menu=index&stg=7&region=main&ncup=oci&class=oci">results</a>, top 5 on the left). Team Past Glory has continued their streak which is now up to 4 consecutive victories, this one by a mere 29 penalty minutes. Well done!<br /><br />Problem 2 in this round is a good example of a problem that is not so hard to solve in some way, but is harder to solve in a way that is really easy to code without bugs. This is an interactive problem happening on the faces of a cube with each face divided into <i>n</i> times <i>n</i> cells (<i>n</i><=300). You are located on some cell on some face of the cube, facing one of the four cardinal directions, and your goal is located on some cell on some face of the cube, but you don't know where you are located and where the goal is located. All you can do is to issue commands left, right or forward, with the first two causing you to rotate in place by 90 degrees, and the last one causing you to move one cell in the direction you're facing, with moving through the sides of the cube handled in the natural way. For each move forward, the system tells you whether your new cell is closer, farther or at the same distance from the goal as the old one. The distance is defined as the Euclidean distance between the centers of the cells. You need to stop moving at the goal cell after using at most 100<i>n</i> commands. Which approach is the easiest to implement here?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-ZqzdkFV94lI/WkLWfWinC9I/AAAAAAAB75U/dBZx7mjRjcsDkjSdflZ_68NGT8K6N3L3QCLcBGAs/s1600/IMG_20171125_160311.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1200" data-original-width="1600" height="480" src="https://2.bp.blogspot.com/-ZqzdkFV94lI/WkLWfWinC9I/AAAAAAAB75U/dBZx7mjRjcsDkjSdflZ_68NGT8K6N3L3QCLcBGAs/s640/IMG_20171125_160311.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2017/12/a-f5-week.html">my previous summary</a>, I have mentioned <a href="http://codeforces.com/contest/889/problem/C">a Codeforces problem</a>: how many permutations of size <i>n</i> have the following property: if you go from left to right, and keep track of the maximum seen so far, there will be no time where it will not change for <i>k</i> consecutive steps, except if it's already equal to <i>n</i>. <i>n</i> and <i>k</i> are up to a million, and the answer needs to be returned modulo 10<sup>9</sup>+7.<br /><br />First, let's come up with a standard but slow solution. We'll do dynamic programming that finds the number of such permutations of size <i>m</i><=<i>n</i> that the last element is the maximum and there's always an update to the maximum in each <i>k</i> consecutive steps when we go from left to right. In order to find this number, we iterate over the step <i>p</i> where the previous maximum appeared: it has to be between <i>m</i>-<i>k</i> and <i>m</i>-1. Then we need to multiply the answer for <i>p</i> by the number of ways to choose which <i>m</i>-<i>p-1</i> numbers out of <i>m-2</i> form the numbers on positions between <i>p</i>+1 and <i>m</i>-1, and in which order, which turns out to be simply (<i>m</i>-2)!/(<i>p</i>-1)!, so our final formula becomes:<br /><br />dp[<i>m</i>] = sum(dp[<i>p</i>]*(<i>m</i>-2)!/(<i>p</i>-1)!, <i>m</i>-<i>k</i><=<i>p</i><=<i>m</i>-1)<br /><br />This looks to be O(<i>n</i><sup>2</sup>), but we can now notice that (<i>m</i>-2)! can be moved outside the sum, and the remaining sum can be computed in O(1) if we store prefix sums of dp[<i>p</i>]/(<i>p</i>-1)!, bringing the overall running time to O(<i>n</i>).<br /><br />You can watch <a href="https://youtu.be/H9QhxYHcT8M?t=2h15m21s">as I code the solution in the screencast</a> to see my proposed way of implementing such solutions: start by implementing the quadratic approach, get it to pass the sample cases, then start implementing the optimizations one by one while keeping it passing the sample cases. One step that I did not make but should have is to also add a few random cases that are still small enough for the quadratic solution to handle to the samples, and make sure the outputs don't change on them while optimizing, too.<br /><br />Thanks for reading, and check back for more!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/ClTO_ycYe00" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/12/a-test-driven-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-20101208013169742862017-12-27T01:06:00.001+03:002017-12-27T01:06:44.084+03:00A F5 week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-onvEh4n_GfM/WkLCip-ogAI/AAAAAAAB74c/ZPeXzG7aqno72LexBDjWBZICykJwQKGWQCLcBGAs/s1600/oc1718ukrainetop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="269" data-original-width="901" height="190" src="https://2.bp.blogspot.com/-onvEh4n_GfM/WkLCip-ogAI/AAAAAAAB74c/ZPeXzG7aqno72LexBDjWBZICykJwQKGWQCLcBGAs/s640/oc1718ukrainetop5.png" width="640" /></a></div>The Nov 6 - Nov 12 week had two contests on Sunday. First off, it was time for the Open Cup Grand Prix of Ukraine (<a href="http://opencup.ru/files/oci/gp6/problems1-e.pdf">problems</a>, <a href="http://opencup.ru/index.cgi?data=macros/stage&head=index&menu=index&stg=6&region=main&ncup=oci&class=oci">results</a>, top 5 on the left). Team Past Glory has won their third Grand Prix in a row — what an amazing achievement! Both Moscow IPT Cryptozoology and japan02 teams were quite close and had real chances for the first place as well — congratulations, too!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-l3nmMyCaWR8/WkLEI8MefvI/AAAAAAAB74o/Jk-maSXAlwsKpwfFOXz9HNJvlNfZCMl0wCLcBGAs/s1600/cf445top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="269" data-original-width="1104" height="154" src="https://4.bp.blogspot.com/-l3nmMyCaWR8/WkLEI8MefvI/AAAAAAAB74o/Jk-maSXAlwsKpwfFOXz9HNJvlNfZCMl0wCLcBGAs/s640/cf445top5.png" width="640" /></a></div>A bit later, Codeforces hosted its Round 445 (<a href="http://codeforces.com/contest/889">problems</a>, <a href="http://codeforces.com/contest/889/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/55734">analysis</a>, <a href="https://youtu.be/H9QhxYHcT8M">my screencast</a>). V--o_o--V was way too fast and thus got an easy first place — great job!<br /><br />Somewhat surprisingly, <a href="http://codeforces.com/contest/889/problem/C">problem C</a> was the most difficult to solve (as opposed to implement) for me this round — you can probably find around 20 minutes of staring at its statement in the screencast during the moments I was trying to solve it on paper. It asked: how many permutations of size <i>n</i> have the following property: if you go from left to right, and keep track of the maximum seen so far, there will be no time where it will not change for <i>k</i> consecutive steps, except if it's already equal to <i>n</i>. <i>n</i> and <i>k</i> are up to a million, and the answer needs to be returned modulo 10<sup>9</sup>+7. Is it easy for you?<br /><br />Thanks for reading, and check back soon for the solution!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/vKLsQuCeu-I" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/12/a-f5-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-53728523736962384062017-12-27T00:34:00.001+03:002017-12-27T00:41:24.261+03:00An empty week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-kYkz1BvkzoQ/WkLAGahAL8I/AAAAAAAB74Q/pD3gO3PwV-cObyVQEieSZUauItoTtM8KQCLcBGAs/s1600/IMG_20171122_134934.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1060" data-original-width="1600" height="422" src="https://2.bp.blogspot.com/-kYkz1BvkzoQ/WkLAGahAL8I/AAAAAAAB74Q/pD3gO3PwV-cObyVQEieSZUauItoTtM8KQCLcBGAs/s640/IMG_20171122_134934.jpg" width="640" /></a></div>There were no contests I'd like to mention during the Oct 30 - Nov 5 week, so let me use this summary for an audience question.<br /><br />I'm planning to finish all summaries for 2017 during this week, and then put together a shortlist of best problems of 2017 to my taste, chosen from the ones I've highlighted in my blog, just like <a href="http://petr-mitrichev.blogspot.com/2017/01/a-week-of-five.html">I did last year</a>. However, the "to my taste" criterion is more important to me than "highlighted in my blog", so if you think you know a 2017 problem that I'd like a lot, but which did not get mentioned in the blog, most likely because I solved less contests and thus saw less problems, please mention it in comments!<br /><br />I should also note that the New Year tradition of picking the best of the past year in competitive programming was pioneered and is still being pursued by Snarknews, so consider taking part in his (unfortunately, Russian-only, but maybe automatic translation is good enough these days?..) <a href="http://codeforces.com/blog/entry/56637">poll</a> as well!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/1xtLKze2yJw" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/12/an-empty-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-13059712095980294972017-12-23T22:30:00.000+03:002017-12-23T22:30:12.962+03:00A transversal week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-Mdz2PL86Uyg/Wj6hMElWxbI/AAAAAAAB70M/cX9lWov9y2I_BDsGu1JpvXtEaW1ynvkYQCLcBGAs/s1600/tco17semi2top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="169" data-original-width="760" height="142" src="https://2.bp.blogspot.com/-Mdz2PL86Uyg/Wj6hMElWxbI/AAAAAAAB70M/cX9lWov9y2I_BDsGu1JpvXtEaW1ynvkYQCLcBGAs/s640/tco17semi2top5.png" width="640" /></a></div>The TopCoder Open onsite continued during the Oct 23 - Oct 29 week with Semifinal 2 on Monday (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=17017">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17017&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a> on the left, <a href="https://youtu.be/AqpjM86iZlc">our commentary</a>). Two contestants got the medium problem this time, tourist and ikatanic, and bcip was the third advancer thanks to fast time on the easy. Congratulations to all advancers!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-vfiPInkX7sg/Wj6i16w8ioI/AAAAAAAB70Y/gtbH4u33-iEnT-gMVfeTo_dCMBgl890dwCLcBGAs/s1600/tco17finaltop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="174" data-original-width="762" height="146" src="https://2.bp.blogspot.com/-vfiPInkX7sg/Wj6i16w8ioI/AAAAAAAB70Y/gtbH4u33-iEnT-gMVfeTo_dCMBgl890dwCLcBGAs/s640/tco17finaltop5.png" width="640" /></a></div>The final round of the TopCoder Open took place just 24 hours later (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=17018">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17018&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a> on the left, <a href="https://youtu.be/qrlDoP3JQkI">our commentary</a>). One again just two contestants have managed to solve two problems, and xudyh was quite a lot faster than rng_58. Congratulations on the TopCoder Open victory!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-GSz_iPr8iL0/Wj6kvJUXWPI/AAAAAAAB70k/CR_TTU5Z54snsAkVH2L9QwXkDhxQ122AACLcBGAs/s1600/cf443top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="273" data-original-width="1104" height="158" src="https://4.bp.blogspot.com/-GSz_iPr8iL0/Wj6kvJUXWPI/AAAAAAAB70k/CR_TTU5Z54snsAkVH2L9QwXkDhxQ122AACLcBGAs/s640/cf443top5.png" width="640" /></a></div>Codeforces Round 443 took place on Thursday (<a href="http://codeforces.com/contest/878">problems</a>, <a href="http://codeforces.com/contest/878/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/55435">analysis</a>). dotorya has dominated the proceedings, solving all problems in the end, but having enough points for a clear first place with just four of them. Amazing performance!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-wX4h9ZIMrls/Wj6lAB4-WrI/AAAAAAAB70o/wO2fC7BtwEMyuoSzuIzwwcaW9Q_rNTGQQCLcBGAs/s1600/oc1719easterntop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="270" data-original-width="918" height="188" src="https://1.bp.blogspot.com/-wX4h9ZIMrls/Wj6lAB4-WrI/AAAAAAAB70o/wO2fC7BtwEMyuoSzuIzwwcaW9Q_rNTGQQCLcBGAs/s640/oc1719easterntop5.png" width="640" /></a></div>On the weekend, the Open Cup Eastern Grand Prix took place (<a href="http://opencup.ru/files/oci/gp5/problems1-e.pdf">problems</a>, <a href="http://opencup.ru/index.cgi?data=macros/stage&head=index&menu=index&stg=5&region=main&ncup=oci&class=oci">results</a>, top 5 on the left). Five teams have solved all problems, and team Past Glory did it faster than everybody else. Well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-aU-42lmhaDM/Wj6ulrEZQMI/AAAAAAAB71M/QAz2OxnmZWUjfG_g76lozfaugzIjrC63wCLcBGAs/s1600/IMG_20171118_133041.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="989" data-original-width="1600" height="394" src="https://4.bp.blogspot.com/-aU-42lmhaDM/Wj6ulrEZQMI/AAAAAAAB71M/QAz2OxnmZWUjfG_g76lozfaugzIjrC63wCLcBGAs/s640/IMG_20171118_133041.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2017/12/an-extremely-formal-week.html">my previous summary</a>, I have mentioned <a href="http://codeforces.com/contest/875/problem/F">a Codeforces problem</a>: you are given a bipartite graph with at most 200000 vertices each each part. Each vertex in the left part has exactly two edges to different vertices in the right part. Each vertex in the left part also has a weight. You need to find the weight of the maximum weight matching in this graph (but you don't need to output the matching itself).<br /><br />First of all, we can find the maximum weight matching greedily, by trying to add the vertices in the left part in decreasing order of weight, since the set of left parts of matchings forms <a href="https://mathoverflow.net/a/96676">the transversal matroid</a>. How do we check if a vertex in the left part can be added to the matching without building the traditional augmenting path, which would be too slow in this problem? Since we don't need to build the matching itself, we will rely on <a href="https://en.wikipedia.org/wiki/Hall%27s_marriage_theorem#Graph_theoretic_formulation">the Hall's theorem</a>. Suppose we're adding a vertex <i>a</i> in the left part that is connected to vertices <i>b</i> and <i>c </i>in the right part. Consider the connected components of the graph formed by the right part plus the vertices in the left part which have been matched (whenever we can't match a vertex in the left part, we disregard it together with the adjacent edges). Each of those components has at least as many vertices in the right part as in the left part, since all vertices of the left part are matched. Moreover, if it has <i>k</i> vertices in the left part, then it has 2<i>k</i> edges, and since it also has at least <i>k</i> vertices in the right part, its total number of vertices is at least 2<i>k</i>. A connected graph with at least 2<i>k</i> vertices and 2<i>k</i> edges does not have that many possibilities: it either has exactly 2<i>k</i> vertices and has one cycle, or it has 2<i>k</i>+1 vertices and is a tree.<br /><br />We claim that we can add the vertex <i>a</i> to the matching if and only if one of the components corresponding to <i>b</i> and <i>c</i> is such a tree, so all we need to maintain in our solution is a set of connected components using a disjoint set union data structure, and the number of vertices in each part for each connected component.<br /><br />If both components corresponding to <i>b</i> and <i>c</i> are not trees, they have the same number of vertices in left and right parts, and the union of those components and vertex <i>a</i> has more vertices in the left part than in the right part, so the Hall's theorem tells us it's impossible to add <i>a</i> to the matching. If the component corresponding to say, <i>b</i>, is a tree, then let's prove it's possible to rearrange the matching inside this component in such a way that we can add <i>a</i> to the matching. Suppose it's impossible, then the Hall's theorem tells us that there exists a subset <i>U</i> of vertices of the left part of the component such that if <i>V</i> is the set of the right part vertices adjacent to <i>U</i>, then the size of <i>V</i> is equal to the size of <i>U</i>. If <i>U</i> has <i>k</i> vertices, then the graph formed by <i>U</i> and <i>V</i> has 2<i>k</i> vertices and 2<i>k</i> edges, which means that it has a cycle, which is a contradiction.<br /><br />Thanks for reading, and check back for more!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/96lJ3j5VUx8" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/12/a-transversal-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-79380877233585502442017-12-23T20:47:00.002+03:002017-12-23T20:47:43.722+03:00An extremely formal week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-ACHgGKPJCAU/Wj6TNGMV-yI/AAAAAAAB7zg/Ghfxa-06HcovJvkA9w7xFdeknCNQLprMgCLcBGAs/s1600/cf441top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="274" data-original-width="1119" height="156" src="https://1.bp.blogspot.com/-ACHgGKPJCAU/Wj6TNGMV-yI/AAAAAAAB7zg/Ghfxa-06HcovJvkA9w7xFdeknCNQLprMgCLcBGAs/s640/cf441top5.png" width="640" /></a></div>The Oct 16 - Oct 22 week started with Codeforces Round 441 on Monday (<a href="http://codeforces.com/contest/875">problems</a>, <a href="http://codeforces.com/contest/875/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/55233">analysis</a>). fateice demonstrated impressive speed in solving 6 problems in 50 minutes only, good 20 minutes earlier than everybody else. Congratulations on the victory!<br /><br /><a href="http://codeforces.com/contest/875/problem/F">The problem F</a> in this round was quite nice: you are given a bipartite graph with at most 200000 vertices each each part. Each vertex in the left part has exactly two edges to different vertices in the right part. Each vertex in the left part also has a weight. You need to find the weight of the maximum weight matching in this graph (but you don't need to output the matching itself). Of course, the standard maximum matching algorithms would be quadratic or at least O(<i>n</i>*sqrt(<i>n</i>)) and thus too slow for this problem. How to solve it faster?<br /><div><br /></div><div><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-1Pl2_RhxEqU/Wj6UT8FOauI/AAAAAAAB7zo/4J_vXbjV1v4QrjFHp4zHeskieVTVVNr2wCLcBGAs/s1600/tco17semi1top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="174" data-original-width="777" height="142" src="https://2.bp.blogspot.com/-1Pl2_RhxEqU/Wj6UT8FOauI/AAAAAAAB7zo/4J_vXbjV1v4QrjFHp4zHeskieVTVVNr2wCLcBGAs/s640/tco17semi1top5.png" width="640" /></a></div>On Sunday, the onsite portion of TopCoder Open 2017 started with its Semifinal 1 (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=17016">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17016&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a> on the left). xudyh solved the medium problem in 25 minutes, while everybody else could not solve it at all — what a commanding performance! scott_wu and rng_58 also advanced to the finals thanks to fast times on the easy problem.<br /><div><br /></div><div></div><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-ZjgvvzgAGrg/Wj6Wm9EZyII/AAAAAAAB7z8/G4uYose41PAC3HpqDH4-X-2WwDvXBeeHACLcBGAs/s1600/IMG_20171114_145105.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1200" data-original-width="1600" height="480" src="https://3.bp.blogspot.com/-ZjgvvzgAGrg/Wj6Wm9EZyII/AAAAAAAB7z8/G4uYose41PAC3HpqDH4-X-2WwDvXBeeHACLcBGAs/s640/IMG_20171114_145105.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2017/12/a-delayed-week.html">my previous summary</a>, I have mentioned an Open Cup problem about formal proofs (<a href="http://opencup.ru/files/oci/gp4/problems-e.pdf">problem H here</a>): you are given an undirected connected graph with at most 73 vertices and 492 edges, and a desired parity for each vertex (either odd, denoted by 1, or even, denoted by 0). The sum of all parities is 1 modulo 2. You need to <i>prove</i> that there doesn't exist a subset of edges of the graph with the desired parity of the number of edges adjacent to each vertex. It would be easy to prove, as it is well known that the number of vertices of odd degree in any graph is always even. However, you're only interested in proofs stated in a specific form.<br /><br />Such proof is a sequence of <i>clauses</i>. Each clause is an "or" of zero or more <i>variables</i> and/or their negations. Each variable corresponds to an edge in the graph, and is true if we take this edge, and false otherwise. Each clause must be built in one of the three ways:<br /><ol style="text-align: left;"><li>In can be an <i>axiom</i>, which in our case means that it must contain the variables corresponding to all edges adjacent to some vertex of the graph, with the number of negated variables having the parity that is opposite to the desired parity for this vertex. For example, consider a vertex of degree 5 and desired parity 0, with adjacent edges <i>a</i>, <i>b</i>, <i>c</i>, <i>d</i>, <i>e</i>. A valid axiom for this vertex would be for example !<i>a</i>|!<i>b</i>|<i>c</i>|<i>d</i>|!<i>e</i>, which would be false only if variables <i>a</i>,<i>b</i>,<i>e</i> are true, and variables <i>c</i>,<i>d</i> are false, but that would mean that the vertex has 3 adjacent edges which doesn't satisfy its parity requirement, so this axiom is always true.</li><li>It can be a <i>conclusion</i>, in which we take two previous clauses of form <i>A</i>|<i>x</i> and <i>B</i>|!<i>x</i>, and make a new clause <i>A</i>|<i>B</i>. Since both original clauses are true the conclusion is true as well.</li><li>It can be a <i>transformation</i> of a previous clause. We take a previous clause and a permutation of the set of all variables and their negations, and apply the permutation to the elements of the clause to get the new clause. The permutation can not be arbitrary: it must be an automorphism of the set of axioms (map every axiom to an axiom). Note that transformations are not a strictly necessary operation, as we could have constructed the resulting clause by applying the automorphism to the axioms used to build the original clause, and then repeating how it was built, but it allows to dramatically reduce the number of clauses in a proof.</li></ol><div>Your goal to derive an empty clause in at most 1000 steps, which would mean a contradiction, and prove that the parities goal is impossible to achieve.<br /><br />First, let's solve our problem for the case where our graph is a tree. We will apply a recursive procedure that takes a subtree, and builds a clause with just one variable corresponding to the edge going into that subtree, either negated or not. For a leaf, such clause is just an axiom. For an internal vertex, we can recursively build such clauses for edges going to its children, and then build an axiom from negations of those clauses, and choosing whether to negate the edge to the parent to obtain the required parity for the axiom. We can then eliminate all variables but one from this axiom using the conclusion, as we have negated single variables for all edges going to the children.<br /><br />When we reach the root of the tree, we apply the same procedure, only there's no extra variable for the edge to the parent. The condition on the sum of all parities will guarantee that the above approach is still applicable, i.e. the axiom we need to cancel out all variables will be a valid axiom for the root (a formal proof of that fact would probably inductively find that the edge going from a subtree gives us a negated or non-negated clause based on the sum of parities in that subtree). And we will obtain an empty clause after eliminating all variables in the root, thus completing the required formal proof in less than 2<i>n</i> steps, where <i>n</i> is the number of vertices.<br /><br />Now how to adapt this approach for the case where the graph is not a tree? Let's pick an arbitrary spanning tree in it, and apply the same idea. Whenever we need to create a new axiom for a vertex, let's keep all variables corresponding to the edges that are <i>not</i> in the spanning tree non-negated. This does not affect the validity of axioms since it depends only on the number of negated variables. In the end, instead of an empty clause we will get a clause that is an or of all edges that are not in the spanning tree, and does not have variables corresponding to the edges of the spanning tree.<br /><br />This is where the third operation type, the transformation, comes into play. For each edge not in the spanning tree consider its <i>fundamental cycle</i> formed by this edge and the path between its ends in the spanning tree. Let's apply a transformation that negates all variables corresponding to this cycle. This is a valid transformation since for each vertex it negates 0 or 2 variables, which does not affect the parity, and thus maps axioms to axioms. In our clause it will negate exactly one variable, since we don't have variables corresponding to the edges of the spanning tree, and we can then use conclusion to remove that variable from our clause. We can then repeat this process for all edges not in the spanning tree and obtain the empty clause in 2(<i>m</i>-<i>n</i>+1) additional operations, or less than 2(<i>m</i>+1<i>)</i> overall, where <i>m</i> is the number of edges, which is good enough.<br /><br />Thanks for reading, and check back soon!</div></div></div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/acR4SNKkM2E" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/12/an-extremely-formal-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-10341294432337633032017-12-23T20:19:00.001+03:002017-12-23T20:19:41.269+03:00A delayed week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-SqBPZNrgXK4/WjbTJ0TJG8I/AAAAAAAB7sg/gOHFnjvHO3MWvUH2p1APHOVlf6f9qpazgCLcBGAs/s1600/srm722top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="148" data-original-width="783" height="120" src="https://2.bp.blogspot.com/-SqBPZNrgXK4/WjbTJ0TJG8I/AAAAAAAB7sg/gOHFnjvHO3MWvUH2p1APHOVlf6f9qpazgCLcBGAs/s640/srm722top5.png" width="640" /></a></div>TopCoder SRM 722 on Thursday was the first contest of the Oct 9 - Oct 15 week (<a href="https://community.topcoder.com/stat?c=round_overview&rd=17010">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17010&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://www.topcoder.com/blog/single-round-match-722-editorials/">analysis</a>). TopCoder has put together an easier problemset with a very tricky medium problem this time, which put a great emphasis on the challenge phase. tourist, uwi and gainullin.ildar have found enough challenges to overtake the others into the top three. Congratulations!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-HsgjkHTnlV0/WjbUEPd9fxI/AAAAAAAB7so/B9ZnMPJRvOgBCLgfBn5jjo7dcErcU3e-ACLcBGAs/s1600/cf440top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="272" data-original-width="1105" height="156" src="https://2.bp.blogspot.com/-HsgjkHTnlV0/WjbUEPd9fxI/AAAAAAAB7so/B9ZnMPJRvOgBCLgfBn5jjo7dcErcU3e-ACLcBGAs/s640/cf440top5.png" width="640" /></a></div>Codeforces Round 440 took place early on Sunday (<a href="http://codeforces.com/contest/871">problems</a>, <a href="http://codeforces.com/contest/871/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/55200">analysis</a>). All top scorers solved 4 problems, albeit different ones, and mere minutes separated them. khadaev was 1 minute faster than Errichto, and thus earned the first place. Well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-5ahEBCgHP1Y/WjbUw9ggPLI/AAAAAAAB7sw/gKsyBiWf-vAd3dLNsXS2PAIpvHdIhaGsQCLcBGAs/s1600/oc1718spbtop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="286" data-original-width="866" height="210" src="https://2.bp.blogspot.com/-5ahEBCgHP1Y/WjbUw9ggPLI/AAAAAAAB7sw/gKsyBiWf-vAd3dLNsXS2PAIpvHdIhaGsQCLcBGAs/s640/oc1718spbtop5.png" width="640" /></a></div>Overlapping with that round, the Open Cup Grand Prix of SPb took place just an hour later (<a href="http://opencup.ru/files/oci/gp4/problems-e.pdf">problems</a>, <a href="http://opencup.ru/index.cgi?data=macros/stage&head=index&menu=index&stg=4&region=main&ncup=oci&class=oci">results</a>, top 5 on the left). Uncharacteristically for our team we had reasonable penalty time and just needed to solve the last problem in an hour to win — but missed a small detail in the problem statement and could not get it accepted, which allowed team Past Glory to score another victory — congratulations!<br /><br />In continuing the great traditions of St. Petersburg State University championships, this contest featured many interesting problems, of which I'd like to highlight the two hardest ones. Problem F was an interactive problem about exploring a random maze with a communication delay. You are given a maze in a 20x20 grid with walls between cells. The maze is randomly generated to form a tree using the Kruskal-like approach. You control a robot that starts in the bottom-left corner. You can command the robot to move in one of the four cardinal directions, and you would receive a reply telling you that the robot has moved in that direction (if there was no wall there), or that it stayed in its current cell (if there was a wall). You need to get the robot in the bottom-right corner in 10000 moves. The catch is that you don't receive the replies right away: the reply to the <i>i</i>-th command only arrives after you send the (<i>i</i>+100)-th command. We can't afford 100 moves per cell, so we have to somehow continue exploring without knowing where exactly we are. Can you see an effective approach?<br /><br />I have explained and analyzed our approach in <a href="http://codeforces.com/blog/entry/55204?#comment-390856">this comment thread</a>.<br /><br />Problem H discussed formal proofs in the spirit of <a href="http://petr-mitrichev.blogspot.com/2017/05/a-zero-pigeon-week.html">the Dirichlet problem</a> from another St. Petersburg State University Championship this spring. You are given an undirected connected graph with at most 73 vertices and 492 edges, and a desired parity for each vertex (either odd, denoted by 1, or even, denoted by 0). The sum of all parities is 1 modulo 2. You need to <i>prove</i> that there doesn't exist a subset of edges of the graph with the desired parity of the number of edges adjacent to each vertex. It would be easy to prove, as it is well known that the number of vertices of odd degree in any graph is always even. However, you're only interested in proofs stated in a specific form.<br /><br />Such proof is a sequence of <i>clauses</i>. Each clause is an "or" of zero or more <i>variables</i> and/or their negations. Each variable corresponds to an edge in the graph, and is true if we take this edge, and false otherwise. Each clause must be built in one of the three ways:<br /><ol style="text-align: left;"><li>In can be an <i>axiom</i>, which in our case means that it must contain the variables corresponding to all edges adjacent to some vertex of the graph, with the number of negated variables having the parity that is opposite to the desired parity for this vertex. For example, consider a vertex of degree 5 and desired parity 0, with adjacent edges <i>a</i>, <i>b</i>, <i>c</i>, <i>d</i>, <i>e</i>. A valid axiom for this vertex would be for example !<i>a</i>|!<i>b</i>|<i>c</i>|<i>d</i>|!<i>e</i>, which would be false only if variables <i>a</i>,<i>b</i>,<i>e</i> are true, and variables <i>c</i>,<i>d</i> are false, but that would mean that the vertex has 3 adjacent edges which doesn't satisfy its parity requirement, so this axiom is always true.</li><li>It can be a <i>conclusion</i>, in which we take two previous clauses of form <i>A</i>|<i>x</i> and <i>B</i>|!<i>x</i>, and make a new clause <i>A</i>|<i>B</i>. Since both original clauses are true the conclusion is true as well.</li><li>It can be a <i>transformation</i> of a previous clause. We take a previous clause and a permutation of the set of all variables and their negations, and apply the permutation to the elements of the clause to get the new clause. The permutation can not be arbitrary: it must be an automorphism of the set of axioms (map every axiom to an axiom). Note that transformations are not a strictly necessary operation, as we could have constructed the resulting clause by applying the automorphism to the axioms used to build the original clause, and then repeating how it was built, but it allows to dramatically reduce the number of clauses in a proof.</li></ol><div>Your goal to derive an empty clause in at most 1000 steps, which would mean a contradiction, and prove that the parities goal is impossible to achieve. Can you do that?</div><div><br /></div><div><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-kj4oYAbI4z4/Wj6P7KIolLI/AAAAAAAB7zE/miP6LKpvXo4vW4pOhwenQApmexoJZbLSgCLcBGAs/s1600/IMG_20171025_153244.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1065" data-original-width="1600" height="426" src="https://3.bp.blogspot.com/-kj4oYAbI4z4/Wj6P7KIolLI/AAAAAAAB7zE/miP6LKpvXo4vW4pOhwenQApmexoJZbLSgCLcBGAs/s640/IMG_20171025_153244.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2017/12/a-future-week.html">my previous summary</a>, I have mentioned <a href="http://codeforces.com/contest/868/problem/E">a Codeforces problem</a>: two players are playing a real-time game on a tree. The first player has one token, and in one second can move it to an adjacent vertex of the tree. The second player has several tokens, and can move them with infinite speed whenever they want. However, as soon as a token of the second player meets the token of the first player, this second player's token is removed from the game. The goal of the first player is to remove all tokens of the second player as fast as possible. How long would it take in worst case? You are given the tree and the starting locations of all tokens. There are at most 50 vertices in the tree, and at most 50 tokens.<br /><br />We can notice that whenever we (the first player) are walking along an edge, only two numbers matter: how many tokens are there on each side of this edge in the tree. When we approach a vertex, the second player has to decide how to distribute the tokens on the side we're approaching between different subtrees of that vertex. We must then proceed into one of those subtrees, as going back along the edge we just arrived on just wastes two seconds. We must proceed into a subtree that has at least one token. Eventually, we will reach a leaf and remove all tokens which are there (at least one).<br /><br />This makes our game acyclic, and we can solve it using dynamic programming where the state is the directed edge of the tree we're traversing, and two numbers: the number of second player tokens on each side of it. When we reach a vertex, in order to find how the second player will divide their tokens, we use an inner dynamic programming which computes the highest minimum time to finish the game if we placed <i>a</i> tokens into the first <i>b</i> subtrees of this vertex. This means we process one state in O(<i>n</i><sup>3</sup>), and we have O(<i>n</i><sup>2</sup>) states, for the total running time of O(<i>n</i><sup>5</sup>). However, we can notice that the inner dynamic programming actually computes the answers not just for one state, but for all states with the same total number of tokens of the second player left, and thus the running time becomes O(<i>n</i><sup>4</sup>) which is fast enough.<br /><br />Thanks for reading, and check back soon for the next week's summary!<br /><br /></div></div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/pbohgAWNTSE" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/12/a-delayed-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-25328163564479646322017-12-17T23:12:00.002+03:002017-12-23T20:11:41.845+03:00A future week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-dIxd5AqrGVw/WjbIIgvCQkI/AAAAAAAB7ro/UskKjcMv7dw4sTZnwcjnFc-Ct1pFqc7sgCLcBGAs/s1600/cf438top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="271" data-original-width="1104" height="156" src="https://3.bp.blogspot.com/-dIxd5AqrGVw/WjbIIgvCQkI/AAAAAAAB7ro/UskKjcMv7dw4sTZnwcjnFc-Ct1pFqc7sgCLcBGAs/s640/cf438top5.png" width="640" /></a></div>The Oct 2 - Oct 8 week contained Codeforces Round 438 (<a href="http://codeforces.com/contest/868">problems</a>, <a href="http://codeforces.com/contest/868/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/55046">analysis</a>). With problem G out of reach, the competition turned to the first six problems + challenges, and cubelover has excelled at both — congratulations on the win!<br /><br /><a href="http://codeforces.com/contest/868/problem/E">Problem E</a> continued the streak of problems with nice and simple statements. Two players are playing a real-time game on a tree. The first player has one token, and in one second can move it to an adjacent vertex of the tree. The second player has several tokens, and can move them with infinite speed whenever they want. However, as soon as a token of the second player meets the token of the first player, this second player's token is removed from the game. The goal of the first player is to remove all tokens of the second player as fast as possible. How long would it take in worst case? You are given the tree and the starting locations of all tokens. There are at most 50 vertices in the tree, and at most 50 tokens.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-Kdj8MLd2lYE/WjbPhSW0ZgI/AAAAAAAB7sA/ZZZGFuRB2JQQkdaa8sIifwyDYSjTA6umgCLcBGAs/s1600/IMG_20171021_143759.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1200" data-original-width="1600" height="480" src="https://3.bp.blogspot.com/-Kdj8MLd2lYE/WjbPhSW0ZgI/AAAAAAAB7sA/ZZZGFuRB2JQQkdaa8sIifwyDYSjTA6umgCLcBGAs/s640/IMG_20171021_143759.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2017/12/a-stock-week.html">my previous summary</a>, I have mentioned a similarly simple sounding problem: you are given the price of a stock for each of <i>n</i> days. You start with 0 stocks, want to finish with 0 stocks, and do one of three things each day: buy 1 stock, sell 1 stock, or do nothing. How much money you can earn? <i>n</i> is up to 300000.<br /><br />The solution proceeds as follows. A new day starts, with stock price <i>a</i>. We will then create two <i>futures</i> for this stock: we will remember that we can buy two units of stock at price <i>a</i> (the reason for creating two futures instead of one will become clear soon). Then we will sell one unit of stock at price <i>a</i>. Which one? Of course, we will take the remaining future with the lowest price, act on it (i.e. buy a unit a stock at that price), and then sell it at price <i>a</i>, realizing the profit. Note that this might be the future that we just created, in case all previous ones were more expensive, in which case the buy and sell cancel out.<br /><br />Note that for each stock, we create one sale and at most two buys via the futures. We can treat the first buy as cancelling the sale, and the second buy as the actual buy — this is the reason we need two futures.<br /><br />As an example, suppose the stock prices are 4, 3, 6, 5. Then our algorithm proceeds as follows:<br /><br /><ul style="text-align: left;"><li>Add two 4s to the futures priority queue, now it has [4, 4].</li><li>Remove the lowest future and pair it with a sale at 4, for a profit of 4-4=0. Our queue is now [4].</li><li>Add two 3s: [3, 3, 4].</li><li>Remove the lowest and pair it with 3: profit is 3-3=0, queue is [3, 4].</li><li>Add two 6s: [3, 4, 6, 6].</li><li>Remove the lowest and pair it with 6: profit is 6-3=3, queue is [4, 6, 6].</li><li>Add two 5s: [4, 5, 5, 6, 6].</li><li>Remove the lowest and pair it with 5: profit is 5-4=1, queue is [5, 5, 6, 6].</li></ul>The total profit is 0+0+3+1=4, and what happened is that we bought at 4 and 3 and sold at 6 and 5. After careful consideration one can see that all valid sequences of stock sales can be expressed in our framework, and that greedily choosing the cheapest future every time leads to an optimal solution thanks to an exchange argument. Still, I find the fact that this greedy approach works very beautiful!<br /><br />Thanks for reading, and check back later!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/0SQ1cHXCAfs" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/12/a-future-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-39811669026214212212017-12-17T22:32:00.001+03:002017-12-17T22:32:23.633+03:00A stock week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-aDi_7g0MrUI/Wja-5guG79I/AAAAAAAB7rA/5cnuqCthaJUzuq03JAzHPrzogQ8mOXsOACLcBGAs/s1600/srm721top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="149" data-original-width="785" height="120" src="https://2.bp.blogspot.com/-aDi_7g0MrUI/Wja-5guG79I/AAAAAAAB7rA/5cnuqCthaJUzuq03JAzHPrzogQ8mOXsOACLcBGAs/s640/srm721top5.png" width="640" /></a></div>The last September week featured the relatively rare guest: a TopCoder SRM, number 721 (<a href="https://community.topcoder.com/stat?c=round_overview&rd=16983">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=16983&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://www.topcoder.com/blog/single-round-match-721-editorials/">analysis</a>). eddy1021 scored the most points from the problems, but K.A.D.R has overtaken him thanks to his 100 challenge points. Congratulations on the win!<div><br /></div><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-I_exQQsK7TY/WjbA1POOHII/AAAAAAAB7rM/MAc5FcD5kCwahlkyh1x2NsNOkAnEwcNZACLcBGAs/s1600/memsql2017r2top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="271" data-original-width="1104" height="156" src="https://3.bp.blogspot.com/-I_exQQsK7TY/WjbA1POOHII/AAAAAAAB7rM/MAc5FcD5kCwahlkyh1x2NsNOkAnEwcNZACLcBGAs/s640/memsql2017r2top5.png" width="640" /></a></div><div>MemSQL Start[c]UP round 2 took place on Saturday (<a href="http://codeforces.com/contest/866">problems</a>, <a href="http://codeforces.com/contest/866/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/contest/865/standings">onsite results</a>, <a href="http://codeforces.com/blog/entry/54888">analysis</a>). There was a wide variety of problems to solve, and tourist has made the right choice and claimed the first place with A+B+C+D+F. Well done!</div><div><br /></div><div>Problem D had deceptively simple statement which led to a lot of frustration as I was unable to come up with its solution for two hours :) You are given the price of a stock for each of <i>n</i> days. You start with 0 stocks, want to finish with 0 stocks, and do one of three things each day: buy 1 stock, sell 1 stock, or do nothing. How much money you can earn? <i>n</i> is up to 300000.</div><div><br /></div><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-Fh6e0Glv1UU/WjbFtssNggI/AAAAAAAB7rc/qniDPN4m-UcYF1ODHW6BEqLcBMrMHkohQCLcBGAs/s1600/oc1718eurasiatop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="268" data-original-width="951" height="180" src="https://1.bp.blogspot.com/-Fh6e0Glv1UU/WjbFtssNggI/AAAAAAAB7rc/qniDPN4m-UcYF1ODHW6BEqLcBMrMHkohQCLcBGAs/s640/oc1718eurasiatop5.png" width="640" /></a></div><div>Finally, the third Open Cup stage, the Grand Prix of Eurasia, took place on Sunday (<a href="http://opencup.ru/files/oci/gp3/problems-e.pdf">problems</a>, <a href="http://opencup.ru/index.cgi?data=macros/stage&head=index&menu=index&stg=3&region=main&ncup=oci&class=oci">results</a>, top 5 on the left). This time the active Russian ICPC teams stepped forward, with Moscow SU and ITMO leading everybody else by a problem. Well done!</div><div><br /></div><div>Thanks for reading, and check back later as we dive into October!</div></div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/4EiRcS0MoTo" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/12/a-stock-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-39928829441238147982017-12-11T21:54:00.000+03:002017-12-11T21:54:05.894+03:00A global shift week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-3kX6WqD9xqA/Wi66H90WcWI/AAAAAAAB7co/rkWETvHgJUg3S5gMCyF9sGmkSoJJnKVSgCLcBGAs/s1600/oc1718uraltop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="267" data-original-width="876" height="194" src="https://4.bp.blogspot.com/-3kX6WqD9xqA/Wi66H90WcWI/AAAAAAAB7co/rkWETvHgJUg3S5gMCyF9sGmkSoJJnKVSgCLcBGAs/s640/oc1718uraltop5.png" width="640" /></a></div>The Sep 18 - Sep 24 week featured the second Open Cup stage: the Grand Prix of Ural (<a href="http://opencup.ru/files/oci/gp2/problems1-e.pdf">problems</a>, <a href="http://opencup.ru/index.cgi?data=macros/stage&head=index&menu=index&stg=2&region=main&ncup=oci&class=oci">results</a>, top 5 on the left). The Seoul National U 2 team continued to amaze, this time claiming the victory by 1 problem to Past Glory and by 2 problems to everybody else. Very well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-f4LY-UdtufU/Wi63zo3hOCI/AAAAAAAB7cc/Sq8BHJXwmwAUWvxLaMTE2tZ2B9OZgu1CACLcBGAs/s1600/manthan17top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="271" data-original-width="1102" height="156" src="https://4.bp.blogspot.com/-f4LY-UdtufU/Wi63zo3hOCI/AAAAAAAB7cc/Sq8BHJXwmwAUWvxLaMTE2tZ2B9OZgu1CACLcBGAs/s640/manthan17top5.png" width="640" /></a></div>Later on Sunday, Codeforces hosted a contest titled "Manthan, Codefest 17" (<a href="http://codeforces.com/contest/855">problems</a>, <a href="http://codeforces.com/contest/855/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/54750">analysis</a>). anta has stumbled on the tricky problem D (less than a third of contestants who submitted got it accepted), but has still came out clearly on top thanks to being the only contestant to submit all problems. Congratulations on the victory!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-ASA8cwiP7pA/Wi7SriWVh-I/AAAAAAAB7dc/1wQzVkvNkQQ4Y8lxAewck9HGAzIloao7gCLcBGAs/s1600/IMG_20171007_195629.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1200" data-original-width="1600" height="480" src="https://4.bp.blogspot.com/-ASA8cwiP7pA/Wi7SriWVh-I/AAAAAAAB7dc/1wQzVkvNkQQ4Y8lxAewck9HGAzIloao7gCLcBGAs/s640/IMG_20171007_195629.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2017/12/a-chain-cut-week.html">my previous summary</a>, I have mentioned a couple of problems. One was with a recursive background: there are many contestants taking part in a competition, and top <i>c</i> will be awarded with t-shirts. There are <i>n</i> available t-shirt sizes (<i>n</i><=200000). Each contestant has indicated one of two things: either they need a t-shirt with some concrete size, or they need a t-shirt with one of the two concrete adjacent sizes. More precisely, for each size <i>i</i> we know the number <i>a<sub>i</sub></i> of contestants (up to 10<sup>8</sup>) that need a t-shirt of size <i>i</i>, and the number <i>b<sub>i</sub></i> of contestants (also up to 10<sup>8</sup>) that need either a t-shirt of size <i>i</i> or a t-shirt of size <i>i</i>+1. What is the minimal number of t-shirts we need to buy in order to be able to give t-shirts to top <i>c</i> contestants, no matter which ones end up in top <i>c</i>?<br /><br />First, we can notice that we need to buy such set of t-shirts that in the resulting (huge) graph there's a full matching for any set of <i>c</i> nodes in the left part. <a href="https://en.wikipedia.org/wiki/Hall%27s_marriage_theorem">Hall's theorem</a> gives us an equivalent formulation: we need to make sure that for any set of sizes for which we buy <i>x</i> t-shirts in total, and <i>x</i> is less than <i>c</i>, the number of people who can only wear a t-shirt from this set must not exceed <i>x</i>.<br /><br />Then, we can notice that we can only consider segments of sizes, and not arbitrary sets, in the above condition, as when we have multiple disjoint segments that violate the constraint together, one of them will also provide a constraint violation.<br /><br />Then, just like in many other problems with constraints on segments, we can buy the t-shirts greedily: going in increasing order of sizes, for each size, we will buy just enough t-shirts to make sure the constraint is not violated for all segments that ends with this size. It doesn't make sense to buy more of this size as we can replace those extra t-shirts with ones of size one higher without making things worse.<br /><br />Formally speaking, <i>s<sub>i</sub></i>=max(min(<i>c</i>,<i>a<sub>i</sub></i>), min(<i>c</i>,<i>a<sub>i</sub></i>+<i>b</i><sub><i>i</i>-1</sub>+<i>a</i><sub><i>i</i>-1</sub>)-<i>s</i><sub><i>i</i>-1</sub>, min(<i>c</i>,<i>a<sub>i</sub></i>+<i>b</i><sub><i>i</i>-1</sub>+<i>a</i><sub><i>i</i>-1</sub>+<i>b</i><sub><i>i</i>-2</sub>+<i>a</i><sub><i>i</i>-2</sub>)-<i>s</i><sub><i>i</i>-2</sub>-<i>s</i><sub><i>i</i>-1</sub>, ...). As we move from <i>i</i> to <i>i</i>+1, the arguments to max() change in the following way: the subtracted part increases by <i>s<sub>i</sub></i> for all terms, the <i>a</i>+<i>b</i> part increases by <i>a<sub>i+1</sub></i>+<i>b</i><sub><i>i</i></sub>, and we get a new term. The latter causes some terms to jump over <i>c</i>, in which case the corresponding min() will forever stay equal to <i>c</i>, and these terms will be zero or negative in all subsequent steps, so we can forget about them.<br /><br />This leads to the following approach: let's keep a set of terms for which the min() is still less than <i>c</i>, then we only need to be able to add a constant to the positive part of all terms, add a constant to the negative part of all terms, to find all terms where the positive part exceeds <i>c</i>, and to find the term with the largest difference between positive and negative parts. Such set of operations can be most straightforwardly implemented by keeping two priority queues of those terms: ordered by positive part and ordered by difference, and to implement adding a constant by keeping an extra "global shift" variable.<br /><br />This yields a O(<i>nlogn</i>) solution which is fast enough, but it can also be made O(<i>n</i>) as described in <a href="http://codeforces.com/blog/entry/54572">the official analysis</a>.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-YgXGP0-pR_U/Wi7TH3Y54eI/AAAAAAAB7dk/vl6xYUbE2JcrgYTLTlZJT4zcAk_SwKeCgCLcBGAs/s1600/IMG_20171008_181838.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" data-original-height="1200" data-original-width="1600" height="480" src="https://2.bp.blogspot.com/-YgXGP0-pR_U/Wi7TH3Y54eI/AAAAAAAB7dk/vl6xYUbE2JcrgYTLTlZJT4zcAk_SwKeCgCLcBGAs/s640/IMG_20171008_181838.jpg" width="640" /></a></div>Another problem I mentioned was: two players have a sequence of 50000 integers, and alternately take numbers from either end of the sequence. When all numbers have been taken, each player computes the bitwise xor of their numbers, and the one with a higher bitwise xor wins. Who will win?<br /><br />I have described our solution in <a href="http://codeforces.com/blog/entry/54587?#comment-386036">this comment</a>, but I still feel a bit uneasy about it. It can probably be proven by induction, but it would seem that in such simple setting there should be a simple argument that proves it. I'm really curious to see such argument, please share if you know one!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-efZ5h0mW940/Wi7T8pW27xI/AAAAAAAB7eI/72hGuf42YtAfbW7bN4nAmlLru_rAZUTCACLcBGAs/s1600/IMG_20171017_151704.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="941" data-original-width="1600" height="376" src="https://2.bp.blogspot.com/-efZ5h0mW940/Wi7T8pW27xI/AAAAAAAB7eI/72hGuf42YtAfbW7bN4nAmlLru_rAZUTCACLcBGAs/s640/IMG_20171017_151704.jpg" width="640" /></a></div>Finally, I've just remembered an interesting bit about the TopCoder problem which I explained in <a href="http://petr-mitrichev.blogspot.com/2017/12/a-chain-cut-week.html">the previous summary</a>, about the attractions, mornings, evenings and constraints. During the contest, I was unable to come up with a max flow solution even though I felt like one is possible, and out of desperation started to implement backtracking that greedily does things that are obviously good to do, branches when we don't have an obvious next step, and cuts branches that are definitely worse than the current best answer. To my surprise, I've received a wrong answer instead of time limit exceeded on the system test. The reason for that was that I assumed that I've taken a transitive closure of the set of constraints when implementing the solution, and forgot to actually take the closure. After making this fix, the backtracking passed the system test in the practice room in 42ms :)<br /><br />Thanks for reading, and check back later for more September stories!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/R5WpHziv2UI" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/12/a-global-shift-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-80587062104169735822017-12-11T16:58:00.002+03:002017-12-11T16:58:20.804+03:00A chain cut week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-jPfRDDTEPqE/Wi5fSV_Zk0I/AAAAAAAB7PY/uHugsZ2tvpst_UQP2X33g7yk4sfyfJvNACLcBGAs/s1600/memsql2017r1top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="273" data-original-width="1103" height="158" src="https://4.bp.blogspot.com/-jPfRDDTEPqE/Wi5fSV_Zk0I/AAAAAAAB7PY/uHugsZ2tvpst_UQP2X33g7yk4sfyfJvNACLcBGAs/s640/memsql2017r1top5.png" width="640" /></a></div>The Sep 11 - Sep 17 week had its contests on the weekend. On Saturday MemSQL Start[c]UP has returned to Codeforces after a three-year absence with Round 1 of its third edition (<a href="http://codeforces.com/contest/859">problems</a>, <a href="http://codeforces.com/contest/859/standings">results</a>, top 5 on the left, <a href="https://youtu.be/XdF5C7clLzs">my screencast</a>, <a href="http://codeforces.com/blog/entry/54572">analysis</a>). moejy0viiiiiv was 25 minutes faster than everybody else to solve all problems, and made sure to protect his lead with a few challenges. Congratulations on the win!<br /><br />The round had a few nice problems, but let me highlight <a href="http://codeforces.com/contest/859/problem/F">problem F</a>: there are many contestants taking part in a competition, and top <i>c</i> will be awarded with t-shirts. There are <i>n</i> available t-shirt sizes (<i>n</i><=200000). Each contestant has indicated one of two things: either they need a t-shirt with some concrete size, or they need a t-shirt with one of the two concrete adjacent sizes. More precisely, for each size <i>i</i> we know the number <i>a<sub>i</sub></i> of contestants (up to 10<sup>8</sup>) that need a t-shirt of size <i>i</i>, and the number <i>b<sub>i</sub></i> of contestants (also up to 10<sup>8</sup>) that need either a t-shirt of size <i>i</i> or a t-shirt of size <i>i</i>+1. What is the minimal number of t-shirts we need to buy in order to be able to give t-shirts to top <i>c</i> contestants, no matter which ones end up in top <i>c</i>?<br /><br />Apart from being an interesting problem in general, it's a great example for <a href="http://codeforces.com/blog/entry/55596">this recent discussion</a> about stories in problem statements. I think that here the t-shirt and contestant story actually makes the problem statement really easy to understand and think about, while a completely formal mathematical statement would be hard to parse.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-YoK26-h0eDQ/Wi5f_K-bWuI/AAAAAAAB7Pg/2hAYr-U_wEg7hbQDyrZxvbS1Jnbkjtz8QCLcBGAs/s1600/oc1718romaniatop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="273" data-original-width="915" height="190" src="https://1.bp.blogspot.com/-YoK26-h0eDQ/Wi5f_K-bWuI/AAAAAAAB7Pg/2hAYr-U_wEg7hbQDyrZxvbS1Jnbkjtz8QCLcBGAs/s640/oc1718romaniatop5.png" width="640" /></a></div>On Sunday the new season of the Open Cup started with the Grand Prix of Romania (<a href="http://opencup.ru/files/oci/gp1/problems1-e.pdf">problems</a>, <a href="http://opencup.ru/index.cgi?data=macros/stage&head=index&menu=index&stg=1&region=main&ncup=oci&class=oci">results</a>, top 5 on the left). Team Past Glory did not show any signs of slowing down and won convincingly by a problem — well done! The great performance and second place of the Seoul National U 2 team was a great surprise, and even more so given that this is a different team from the one that <a href="https://icpc.baylor.edu/worldfinals/results">earned gold medals</a> at the last ICPC World Finals for Seoul.<br /><br />Problem L of this contest showed that we can still find new games with non-trivial solutions in a very simple setup: two players have a sequence of 50000 integers, and alternately take numbers from either end of the sequence. When all numbers have been taken, each player computes the bitwise xor of their numbers, and the one with a higher bitwise xor wins. Who will win?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-_al19xnZGrY/Wi5gq14KpBI/AAAAAAAB7Ps/pm2uSiLJ-rMFKBD7iGE3HHBGf0ppoIQRACLcBGAs/s1600/cf434top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="273" data-original-width="1101" height="158" src="https://2.bp.blogspot.com/-_al19xnZGrY/Wi5gq14KpBI/AAAAAAAB7Ps/pm2uSiLJ-rMFKBD7iGE3HHBGf0ppoIQRACLcBGAs/s640/cf434top5.png" width="640" /></a></div>And right after the end of the Grand Prix, Codeforces held its Round 434 (<a href="http://codeforces.com/contest/860">problems</a>, <a href="http://codeforces.com/contest/860/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/54604">analysis</a>). The battle for the first place was quite tight. Congratulations to kmjp who came out on top by a mere 25 points!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-UgZnsMg1M_I/Wi6NMRDJFTI/AAAAAAAB7QM/txj0LoWUjswaBtKFs2FajkNy0UQsXJq0gCLcBGAs/s1600/IMG_20171007_194607.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1200" data-original-width="1600" height="480" src="https://3.bp.blogspot.com/-UgZnsMg1M_I/Wi6NMRDJFTI/AAAAAAAB7QM/txj0LoWUjswaBtKFs2FajkNy0UQsXJq0gCLcBGAs/s640/IMG_20171007_194607.jpg" width="640" /></a></div>In <a href="http://petr-mitrichev.blogspot.com/2017/12/an-almost-there-week.html">my previous summary</a>, I have mentioned <a href="https://community.topcoder.com/stat?c=problem_statement&pm=14687&rd=16991&rm=330540&cr=10574855">a hard TopCoder problem</a>: you are given 50 attractions in a city. You will visit exactly one attraction per day. Each attraction can be visited either in the morning, costing <i>a<sub>i</sub></i>, or in the evening, costing <i>b<sub>i</sub></i>. Every time you visit an attraction in the morning after visiting another attraction the previous evening, you pay an extra cost <i>c</i>. Every time you switch from evening to morning, you pay an extra cost <i>d</i>. Additionally, you are given a directed graph of restrictions — a set pairs of attractions that constrain the order of visits: in each pair, the first attraction must be visited before the second one. What is the minimal cost to perform all visits?<br /><br />First of all, let's split our visits into groups: a group of morning visits, then a group of evening visits, then a group of morning visits, and so on (we need to consider two cases based on whether the very first visit is in the morning or in the evening). Since we only pay extra costs when we switch groups, the total cost depends on the number of groups and on the assignment of visits to groups, but not on the order of visits within each group.<br /><br />Now let's try to build a network in which a cost of a cut would correspond to the total cost of the visits, so that we can solve our problem with the minimum cut algorithm. For each attraction, let us build a chain of vertices, with all chains having the source and sink as start and end respectively. A chain for one attraction looks like: <i>s</i>-><i>v</i><sub>1</sub>-><i>v</i><sub>2</sub>->..-><i>v<sub>n</sub></i>-><i>t</i>. Let's add infinite capacity edges going backwards in the chain, to guarantee that any finite cut separates some prefix of this chain from the rest. The size of this prefix will correspond to the number of the group that this attraction belongs to, and thus the capacity of the edges should be alternating <i>a<sub>i</sub></i> and <i>b<sub>i</sub></i>: if the vertex belongs to an even-numbered group, the corresponding edge will contribute <i>a<sub>i</sub></i> to the total capacity of the cut, and otherwise <i>b<sub>i</sub></i>, just as we need.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-u5evZ_mvzd0/Wi6OiULXmGI/AAAAAAAB7Rk/zAeMXjQGtOgH2KvO9drRwEu7ORRXzt4zgCKgBGAs/s1600/IMG_20171211_145422.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" data-original-height="1193" data-original-width="1600" height="297" src="https://1.bp.blogspot.com/-u5evZ_mvzd0/Wi6OiULXmGI/AAAAAAAB7Rk/zAeMXjQGtOgH2KvO9drRwEu7ORRXzt4zgCKgBGAs/s400/IMG_20171211_145422.jpg" width="400" /></a></div>In order incorporate a restriction "<i>p</i> must be visited before <i>q</i>" into our network, we will add infinite capacity edges from the vertices of the chain for <i>p</i> to the corresponding vertices of the chain for <i>q</i>. This guarantees that with any finite cut, the position we cut the chain for <i>p</i> will be the same or earlier than the position we cut the chain for <i>q</i>.<br /><br />Finally, in order to incorporate the morning/evening switching costs, let us add an extra attraction that must be visited after all others, and set up the capacities on its chain not as alternating <i>a<sub>i</sub></i> and <i>b<sub>i</sub></i>, but rather as 0, <i>c</i>, <i>c</i>+<i>d</i>, 2<i>c</i>+<i>d</i>, 2<i>c</i>+2<i>d</i>, ...<br /><br />The finite cuts in the resulting network correspond to valid ways of visiting the attractions, and the capacity of the cut is equal to the total visit cost, so now we just need to find the minimum cut. Also note that we have built our network using two relatively standard building blocks: infinite edges can give us constraints on the cut, and a chain of vertices with infinite backwards edges implements a choice from several alternatives with specific costs.<br /><br />Thanks for reading, and check back soon!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/ttsNodl3s9E" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/12/a-chain-cut-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-59197597818434274902017-12-10T20:00:00.001+03:002017-12-10T20:00:14.966+03:00An almost there week<div dir="ltr" style="text-align: left;" trbidi="on"><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-gWODG0OFKag/Wi1YouJgv6I/AAAAAAAB7Mo/PB10LCgPwTcTRO0VFlK52gXuMfncge70QCLcBGAs/s1600/cf432top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="272" data-original-width="1125" height="154" src="https://4.bp.blogspot.com/-gWODG0OFKag/Wi1YouJgv6I/AAAAAAAB7Mo/PB10LCgPwTcTRO0VFlK52gXuMfncge70QCLcBGAs/s640/cf432top5.png" width="640" /></a></div>The Sep 4 - Sep 10 week started with two Codeforces rounds. On Monday, Codeforces Round 432 took place (<a href="http://codeforces.com/contest/850">problems</a>, <a href="http://codeforces.com/contest/850/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/54317">analysis</a>). AngryBacon has started with the hardest problem F and solved it very fast, which gave them a clear path to victory. Congratulations!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-uBWv0XitHOE/Wi1ZHKlh1UI/AAAAAAAB7Ms/RWjO_hervFQ3ujH6WNML-31AnFyC90-DQCLcBGAs/s1600/cf433top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="272" data-original-width="1105" height="157" src="https://3.bp.blogspot.com/-uBWv0XitHOE/Wi1ZHKlh1UI/AAAAAAAB7Ms/RWjO_hervFQ3ujH6WNML-31AnFyC90-DQCLcBGAs/s640/cf433top5.png" width="640" /></a></div>On Wednesday, Codeforces hosted the next Round 433 (<a href="http://codeforces.com/contest/853">problems</a>, <a href="http://codeforces.com/contest/853/standings">results</a>, top 5 on the left, <a href="http://codeforces.com/blog/entry/54368">analysis</a>). In a round with 4 problems solvable within an hour and the fifth one too hard to crack, Um_nik has combined excellent speed with 3 successful challenges for a clear first place. Well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-QGL_mq06Hk0/Wi1a0xOj8gI/AAAAAAAB7M4/FLDa1WlHeScBEx9IOkHqUh6dqB0366v-ACLcBGAs/s1600/tco17r3btop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="150" data-original-width="771" height="124" src="https://2.bp.blogspot.com/-QGL_mq06Hk0/Wi1a0xOj8gI/AAAAAAAB7M4/FLDa1WlHeScBEx9IOkHqUh6dqB0366v-ACLcBGAs/s640/tco17r3btop5.png" width="640" /></a></div>On the weekend TopCoder hosted not one but two rounds that finalized the list of finalists for its flagship tournament TopCoder Open 2017. Round 3B took place on Saturday (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=16988">problems</a> — unavailable now, but hopefully the TopCoder website will be fixed soon, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=16988&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left). In order to advance one simply needed to solve either the first two (like qwerty787788, Um_nik and ikatanic did), or the third problem (like rng_58 and RRx did). Congratulations to all advancers!<br /><br />With 1.5 minutes to go in the challenge phase, I had 344.14 points which would be enough to advance with just the easy problem solved, only to <a href="http://codeforces.com/blog/entry/54433?#comment-384840">make an incorrect challenge</a> that brought me down to 319.14 which was not enough. Of course I didn't know that 344.14 would be enough during the round itself, but seeing the final scoreboard made me quite annoyed at myself for that -25 :)<br /><br />Here is <a href="https://community.topcoder.com/stat?c=problem_statement&pm=14685&rd=16988&rm=330537&cr=10574855">the easy problem</a> that brought the challenge phase excitement about: you are given two strings of the same length, which is at most 50. You are allowed to swap corresponding characters in the strings (<i>i</i>-th character of the first string with the <i>i</i>-th character of the second string) as many times as you want. Your goal is to obtain two strings with as large as possible longest common substring. Can you see the right approach?<br /><br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-HK2R3KVJiNA/Wi1cywgDh7I/AAAAAAAB7NI/-Ejbq1wJruAWvJ5-83PN36i4mk105qSmACLcBGAs/s1600/rcc2017finaltop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="480" data-original-width="1086" height="282" src="https://4.bp.blogspot.com/-HK2R3KVJiNA/Wi1cywgDh7I/AAAAAAAB7NI/-Ejbq1wJruAWvJ5-83PN36i4mk105qSmACLcBGAs/s640/rcc2017finaltop5.png" width="640" /></a></div>In between the TopCoder rounds, Russian Code Cup 2017 Final Round saw the top contestants compete for glory and prizes (<a href="http://www.russiancodecup.ru/en/championship/">problems</a>, <a href="http://www.russiancodecup.ru/en/championship/result/58/">results</a>, top 5 on the left, <a href="https://youtu.be/6mglruO5eDU">my screencast</a>, <a href="http://www.russiancodecup.ru/en/press/razbor-zadach-finalnogo-raunda-rcc-2017/">analysis</a>). xudyh was about half an hour faster than everybody else on the first 5 problems. I have tried to leapfrog him by trying to squeeze in a suboptimal solution for the last problem that is fast to code, but it did not pass and xudyh has maintained his first place — congratulations on the win!<br /><br />I have found the easiest problem of this round to be the cutest. You are given a set 100 distinct integers <i>a<sub>i</sub></i> each up to a million, and need to find any set of 100 integers <i>b<sub>j</sub></i> also each up to a million, such that all 100<sup>2</sup> pairwise sums <i>a<sub>i</sub></i>+<i>b<sub>j</sub></i> are distinct. What is the nicest way to achieve that?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-XhqHY8lTQy8/Wi1ciDQ-GkI/AAAAAAAB7NE/xYFkYcT-5sIzW_9grdNouuKezsTO5OYMACLcBGAs/s1600/tco17wildtop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="146" data-original-width="778" height="120" src="https://3.bp.blogspot.com/-XhqHY8lTQy8/Wi1ciDQ-GkI/AAAAAAAB7NE/xYFkYcT-5sIzW_9grdNouuKezsTO5OYMACLcBGAs/s640/tco17wildtop5.png" width="640" /></a></div>And finally, the Wildcard Round of TCO 2017 determined the last two finalists on Sunday (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=16991">problems</a> — unavailable now, but hopefully the TopCoder website will be fixed soon, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=16991&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://youtu.be/XNphi0sE_T4">my screencast</a>). Only kuniavski and xudyh have solved the hard problem, so it is only fitting that they qualified for the TCO onsite — great job!<br /><br />I have once again tried to compensate the poor coding phase performance with lots of successful challenges, but was unable to find enough and got eliminated from the TCO. <a href="https://community.topcoder.com/stat?c=problem_statement&pm=14687&rd=16991&rm=330540&cr=10574855">The hard problem</a> that I couldn't crack stated: you are given 50 attractions in a city. You will visit exactly one attraction per day. Each attraction can be visited either in the morning, costing <i>a<sub>i</sub></i>, or in the evening, costing <i>b<sub>i</sub></i>. Every time you visit an attraction in the morning after visiting another attraction the previous evening, you pay an extra cost <i>c</i>. Every time you switch from evening to morning, you pay an extra cost <i>d</i>. Additionally, you are given a directed graph of restrictions — a set pairs of attractions that constrain the order of visits: in each pair, the first attraction must be visited before the second one. Can you see the way to use max flow to find the minimal cost to perform all visits?<br /><br />Thanks for reading, and check back tomorrow for more backfills!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/USMwu19eCw8" height="1" width="1" alt=""/>Petr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.com0http://petr-mitrichev.blogspot.com/2017/12/an-almost-there-week.html