tag:blogger.com,1999:blog-19533250797934499712019-08-19T11:57:50.747+03:00Algorithms Weekly by Petr MitrichevPetr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.comBlogger419125PetrMitrichevhttps://feedburner.google.comtag:blogger.com,1999:blog-1953325079793449971.post-53554778313533022352019-06-08T12:33:00.000+03:002019-06-08T12:40:09.302+03:00Power towers solution<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/-l9T8xM4DE7I/XPuAjy2db8I/AAAAAAACS0g/SNecg8GnkwIl24AccA5TFXlYqpMrVw12ACLcBGAs/s1600/IMG_20190421_080007.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/-l9T8xM4DE7I/XPuAjy2db8I/AAAAAAACS0g/SNecg8GnkwIl24AccA5TFXlYqpMrVw12ACLcBGAs/s640/IMG_20190421_080007.jpg" width="640" /></a></div>A <a href="https://petr-mitrichev.blogspot.com/2012/05/world-finals-day-2-upe-dinner.html">long</a>, <a href="https://petr-mitrichev.blogspot.com/2012/05/power-towers-problem-testcase.html">long</a> time ago I have mentioned an ICPC practice session problem: given two power towers, which one evaluates to a larger value? A power tower is an expression like 2<sup>2<sup>3<sup>2</sup></sup></sup>, which is evaluated right-to-left like 2^(2^(3^2)). Each number in both power towers is an integer between 1 and 100, and the height of the tower is also between 1 and 100.<br /><br />I have also mentioned that we have came up with a working approach together with Roman Elizarov and Evgeny Kapun, but never got around to actually describing this approach. For some reason, quite a few people asked me to come back to this problem recently, so here we are :)<br /><br />First, we can notice that we can remove any one and everything that comes after it, so let's concentrate on the case where all numbers are between 2 and 100.<br /><br />Let's compare our power towers from top to bottom, aligning them in such a way that the bottom numbers are next to each other. In other words, we will follow this process: we start either with two ones, or with a one and some power tower, then we repeatedly add a number (between 2 and 100) to the bottom of each of the towers.<br /><br />The first observation is that there exists such number <i>k</i> that if the first tower is at least <i>k</i> times bigger, it will keep being at least <i>k</i> times bigger even if we add 2 to it and 100 to the other tower. Effectively it means that as soon as one of the towers is at least <i>k</i> times bigger in our top-down process, we can skip going through the remaining numbers and declare that tower as the winner.<br /><br />To prove it, let's write down some formulas. We have <i>x</i>>=<i>k</i>*<i>y</i>, and we need to prove that 2<sup><i>x</i></sup>>=<i>k</i>*100<sup><i>y</i></sup>. But 2<sup><i>x</i></sup>>=2<sup><i>k</i>*<i>y</i></sup>=100<sup><i>y</i></sup>*(2<sup><i>k</i></sup>/100)<sup><i>y</i></sup>. Since <i>y</i>>=1, we just need 2<sup><i>k</i></sup>/100>=<i>k</i>, which is true for <i>k</i>=10 for example.<br /><br />Intuitively it seems that most likely one of the towers will become at least 10 times bigger pretty quickly, and we won't need to go very deep. In order to check if this is the case, let's define an <i>expand</i> operation: given a set of numbers <i>S</i>, the set expand(<i>S</i>) is built in the following way: first, we build a set <i>T</i> which is obtained by uniting S with all numbers obtained by adding one more power at the bottom: <i>T</i>=<i>S</i>+{2<sup><i>x</i></sup> for <i>x</i> in <i>S</i>}+{3<sup><i>x</i></sup> for <i>x</i> in <i>S</i>}+...+{100<sup><i>x</i></sup> for <i>x</i> in <i>S</i>}. Then, we sort all numbers in T, collapse equal numbers into one, and then remove all numbers which are at least 10 times bigger than the previous number, and at least 10 times smaller than the next number. The resulting set is called expand(<i>S</i>). The motivation behind such definition is: if we have two numbers that are in S during our power tower comparison process, then after adding two more powers to the bottom we will either get a decision (one is at least 10 times bigger than the other), two equal numbers, or two numbers from expand(<i>S</i>).<br /><br />Now let's start with the set <i>S</i>={1,2,..,100}, and repeatedly compute expand(<i>S</i>), expand(expand(<i>S</i>)), .... It turns out that the process stops very quickly, and already expand(expand(<i>S</i>))=expand(expand(expand(<i>S</i>))), and this set has just 17709 elements!<br /><br />It means that if we compare two power towers from top to bottom, then we only need to handle the numbers from expand(expand(<i>S</i>)). If at some point one number is 10 times bigger than the other, we k now the result of the comparison. If at some point the numbers are equal, and are at least 300, then we just need to look at the next differing number going from top to bottom, since (100/99)<sup>300</sup>>10.<br /><br />Now, how do we actually work with the numbers from expand(expand(S)), for example how do we actually find out that it stops growing at 17709 elements? The numbers in that set are still huge. The only way I see to approach this is to experiment, trying out different ideas until one works. In this case, two ideas were necessary:<br /><br />First, we will store the logarithms of elements of our set instead of the elements themselves. It turns out that their logarithms all fit in the double floating-point type (the largest is about 3 million). However, during the expansion step we need to temporarily work with numbers as high as 100<sup><i>x</i></sup> for <i style="font-size: 13.3333px;">x</i> from our set, and those don't fit into double.<br /><br />Therefore, when expanding the set, we will work with logarithms of logarithms of numbers. For example, if we have <i>y</i>=log(<i>x</i>), then we will compare numbers of form log(log(<i>b</i><sup><i>x</i></sup>))=log(<i>x</i>*log(<i>b</i>))=log(<i>x</i>)+log(log(<i>b</i>))=<i>y</i>+log(log(<i>b</i>)).<br /><br />We need to be able to check two things: whether two numbers of this form are equal, and whether one is at least 10 times bigger than the other. For the equality test, we will simply check if the difference is smaller than some constant <i>eps</i>. When running the expansion process, we can print out the biggest difference smaller than <i>eps</i>, and the smallest difference bigger than <i>eps</i> that we encounter. For <i>eps</i>=1e-13, the former is 3e-15, and the latter is 4e-13. Given the more than 100 times difference between the two, it seems plausible that the former is just floating-point rounding error and the two numbers are equal, and the latter is real difference. This is not a proof, of course, but it gives enough confidence (I suspect this leap of faith could be the main reason this problem was only used for ICPC practice session, and not for the real contest).<br /><br />Now we need to check if <i>x/y</i>>=10 when we know <i>p</i>=log(log(<i>x</i>)) and <i>q</i>=log(log(<i>y</i>)). <i>x</i>/<i>y</i>>=10 is the same as log(<i>x</i>)-log(<i>y</i>)>=log(10), which is the same as exp(<i>p</i>)-exp(<i>q</i>)>=log(10), which is the same as (exp(<i>p</i>-<i>q</i>)-1)*exp(<i>q</i>)>=log(10), which is the same as log(exp(<i>p</i>-<i>q</i>)-1)+<i>q</i>>=log(log(10)). To avoid overflow when computing exp(<i>p</i>-<i>q</i>) in this formula, we will simply check if <i>p</i>-<i>q</i>>=5 first, since in that case the inequality is definitely true.<br /><br />Here is the code that we used to come up with and verify all above hypotheses:<br /><br /><pre style="background-color: white; font-family: "Courier New"; font-size: 9pt;"><span style="color: navy; font-weight: bold;">import </span>java.util.ArrayList;<br /><span style="color: navy; font-weight: bold;">import </span>java.util.Arrays;<br /><span style="color: navy; font-weight: bold;">import </span>java.util.List;<br /><br /><span style="color: navy; font-weight: bold;">public class </span>PowerChains {<br /> <span style="color: navy; font-weight: bold;">static final int </span><span style="color: #660e7a; font-style: italic; font-weight: bold;">MAXN </span>= <span style="color: blue;">100</span>;<br /> <br /> <span style="color: navy; font-weight: bold;">static class </span>Number <span style="color: navy; font-weight: bold;">implements </span>Comparable<number> {<br /> <span style="color: navy; font-weight: bold;">double </span><span style="color: #660e7a; font-weight: bold;">what</span>;<br /> <span style="color: navy; font-weight: bold;">int</span>[] <span style="color: #660e7a; font-weight: bold;">origin</span>;<br /> <br /> <span style="color: navy; font-weight: bold;">public </span>Number(Number parent, <span style="color: navy; font-weight: bold;">double </span>value, <span style="color: navy; font-weight: bold;">int </span>extra) {<br /> <span style="color: navy; font-weight: bold;">if </span>(extra < <span style="color: blue;">0</span>) {<br /> <span style="color: #660e7a; font-weight: bold;">origin </span>= parent.<span style="color: #660e7a; font-weight: bold;">origin</span>;<br /> <span style="color: #660e7a; font-weight: bold;">what </span>= value;<br /> <span style="color: navy; font-weight: bold;">return</span>;<br /> }<br /> <span style="color: navy; font-weight: bold;">if </span>(parent != <span style="color: navy; font-weight: bold;">null</span>) {<br /> <span style="color: #660e7a; font-weight: bold;">origin </span>= <span style="color: navy; font-weight: bold;">new int</span>[parent.<span style="color: #660e7a; font-weight: bold;">origin</span>.<span style="color: #660e7a; font-weight: bold;">length </span>+ <span style="color: blue;">1</span>];<br /> System.<span style="font-style: italic;">arraycopy</span>(parent.<span style="color: #660e7a; font-weight: bold;">origin</span>, <span style="color: blue;">0</span>, <span style="color: #660e7a; font-weight: bold;">origin</span>, <span style="color: blue;">1</span>, parent.<span style="color: #660e7a; font-weight: bold;">origin</span>.<span style="color: #660e7a; font-weight: bold;">length</span>);<br /> } <span style="color: navy; font-weight: bold;">else </span>{<br /> <span style="color: #660e7a; font-weight: bold;">origin </span>= <span style="color: navy; font-weight: bold;">new int</span>[<span style="color: blue;">1</span>];<br /> }<br /> <span style="color: #660e7a; font-weight: bold;">origin</span>[<span style="color: blue;">0</span>] = extra;<br /> <span style="color: #660e7a; font-weight: bold;">what </span>= value;<br /> }<br /><br /> <span style="color: navy; font-weight: bold;">public int </span>compareTo(Number number) {<br /> <span style="color: navy; font-weight: bold;">return </span>Double.<span style="font-style: italic;">compare</span>(<span style="color: #660e7a; font-weight: bold;">what</span>, number.<span style="color: #660e7a; font-weight: bold;">what</span>);<br /> }<br /> <br /> <span style="color: navy; font-weight: bold;">public </span>String toString() {<br /> StringBuilder b = <span style="color: navy; font-weight: bold;">new </span>StringBuilder();<br /> b.append(<span style="color: #660e7a; font-weight: bold;">what</span>);<br /> <span style="color: navy; font-weight: bold;">for </span>(<span style="color: navy; font-weight: bold;">int </span>x : <span style="color: #660e7a; font-weight: bold;">origin</span>) b.append(<span style="color: green; font-weight: bold;">" " </span>+ x);<br /> <span style="color: navy; font-weight: bold;">return </span>b.toString();<br /> }<br /> }<br /><br /> <span style="color: navy; font-weight: bold;">public static void </span>main(String[] args) {<br /> Number[] interesting = <span style="color: navy; font-weight: bold;">new </span>Number[<span style="color: #660e7a; font-style: italic; font-weight: bold;">MAXN</span>];<br /> <span style="color: navy; font-weight: bold;">for </span>(<span style="color: navy; font-weight: bold;">int </span>i = <span style="color: blue;">0</span>; i < <span style="color: #660e7a; font-style: italic; font-weight: bold;">MAXN</span>; ++i) {<br /> interesting[i] = <span style="color: navy; font-weight: bold;">new </span>Number(<span style="color: navy; font-weight: bold;">null</span>, Math.<span style="font-style: italic;">log</span>(i + <span style="color: blue;">1</span>), i + <span style="color: blue;">1</span>);<br /> }<br /> <span style="color: navy; font-weight: bold;">while </span>(<span style="color: navy; font-weight: bold;">true</span>) {<br /> Number[] pows = <span style="color: navy; font-weight: bold;">new </span>Number[<span style="color: #660e7a; font-style: italic; font-weight: bold;">MAXN </span>* interesting.<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>i = <span style="color: blue;">1</span>; i < interesting.<span style="color: #660e7a; font-weight: bold;">length</span>; ++i) {<br /> pows[i] = <span style="color: navy; font-weight: bold;">new </span>Number(interesting[i], Math.<span style="font-style: italic;">log</span>(interesting[i].<span style="color: #660e7a; font-weight: bold;">what</span>), -<span style="color: blue;">1</span>);<br /> }<br /> pows[<span style="color: blue;">0</span>] = pows[<span style="color: blue;">1</span>];<br /> <span style="color: navy; font-weight: bold;">for </span>(<span style="color: navy; font-weight: bold;">int </span>b = <span style="color: blue;">2</span>; b <= <span style="color: #660e7a; font-style: italic; font-weight: bold;">MAXN</span>; ++b) {<br /> <span style="color: navy; font-weight: bold;">double </span>logb = Math.<span style="font-style: italic;">log</span>(Math.<span style="font-style: italic;">log</span>(b));<br /> <span style="color: navy; font-weight: bold;">for </span>(<span style="color: navy; font-weight: bold;">int </span>i = <span style="color: blue;">0</span>; i < interesting.<span style="color: #660e7a; font-weight: bold;">length</span>; ++i) {<br /> pows[(b - <span style="color: blue;">1</span>) * interesting.<span style="color: #660e7a; font-weight: bold;">length </span>+ i] =<br /> <span style="color: navy; font-weight: bold;">new </span>Number(interesting[i], interesting[i].<span style="color: #660e7a; font-weight: bold;">what </span>+ logb, b);<br /> }<br /> }<br /> Arrays.<span style="font-style: italic;">sort</span>(pows);<br /> <span style="color: navy; font-weight: bold;">double </span>maxDiff = <span style="color: blue;">0.0</span>;<br /> <span style="color: navy; font-weight: bold;">double </span>minDiff = <span style="color: blue;">1e100</span>;<br /> <span style="color: navy; font-weight: bold;">double </span>maxBase = <span style="color: blue;">0.0</span>;<br /> <span style="color: navy; font-weight: bold;">double </span>needDiff = Math.<span style="font-style: italic;">log</span>(<span style="color: blue;">10</span>);<br /> List<number> newInteresting = <span style="color: navy; font-weight: bold;">new </span>ArrayList<number>();<br /> newInteresting.add(<span style="color: navy; font-weight: bold;">new </span>Number(<span style="color: navy; font-weight: bold;">null</span>, <span style="color: blue;">0.0</span>, <span style="color: blue;">1</span>));<br /> <span style="color: navy; font-weight: bold;">boolean </span>wasBig = <span style="color: navy; font-weight: bold;">true</span>;<br /> <span style="color: navy; font-weight: bold;">for </span>(<span style="color: navy; font-weight: bold;">int </span>i = <span style="color: blue;">0</span>; i + <span style="color: blue;">1 </span>< pows.<span style="color: #660e7a; font-weight: bold;">length</span>; ++i) {<br /> <span style="color: navy; font-weight: bold;">double </span>diff = (pows[i + <span style="color: blue;">1</span>].<span style="color: #660e7a; font-weight: bold;">what </span>- pows[i].<span style="color: #660e7a; font-weight: bold;">what</span>) / (pows[i + <span style="color: blue;">1</span>].<span style="color: #660e7a; font-weight: bold;">what</span>);<br /> <span style="color: navy; font-weight: bold;">if </span>(Math.<span style="font-style: italic;">abs</span>(diff) < <span style="color: blue;">1e-13</span>) {<br /> <span style="color: navy; font-weight: bold;">if </span>(diff > maxDiff) {<br /> maxDiff = diff;<br /> }<br /> } <span style="color: navy; font-weight: bold;">else </span>{<br /> <span style="color: navy; font-weight: bold;">if </span>(diff < minDiff) {<br /> minDiff = diff;<br /> }<br /> <span style="color: navy; font-weight: bold;">double </span>a = pows[i].<span style="color: #660e7a; font-weight: bold;">what</span>;<br /> <span style="color: navy; font-weight: bold;">double </span>b = pows[i + <span style="color: blue;">1</span>].<span style="color: #660e7a; font-weight: bold;">what</span>;<br /> <span style="color: navy; font-weight: bold;">boolean </span>big;<br /> <span style="color: navy; font-weight: bold;">if </span>(b - a > <span style="color: blue;">5</span>)<br /> big = <span style="color: navy; font-weight: bold;">true</span>;<br /> <span style="color: navy; font-weight: bold;">else </span>{<br /> <span style="color: navy; font-weight: bold;">double </span>by = Math.<span style="font-style: italic;">exp</span>(b - a) - <span style="color: blue;">1</span>;<br /> big = a + Math.<span style="font-style: italic;">log</span>(by) > Math.<span style="font-style: italic;">log</span>(needDiff);<br /> }<br /> <span style="color: navy; font-weight: bold;">if </span>(!big) {<br /> <span style="color: navy; font-weight: bold;">if </span>(wasBig)<br /> newInteresting.add(<span style="color: navy; font-weight: bold;">new </span>Number(pows[i], Math.<span style="font-style: italic;">exp</span>(pows[i].<span style="color: #660e7a; font-weight: bold;">what</span>), -<span style="color: blue;">1</span>));<br /> newInteresting.add(<span style="color: navy; font-weight: bold;">new </span>Number(pows[i + <span style="color: blue;">1</span>], Math.<span style="font-style: italic;">exp</span>(pows[i + <span style="color: blue;">1</span>].<span style="color: #660e7a; font-weight: bold;">what</span>), -<span style="color: blue;">1</span>));<br /> maxBase = Math.<span style="font-style: italic;">max</span>(maxBase, pows[i + <span style="color: blue;">1</span>].<span style="color: #660e7a; font-weight: bold;">what</span>);<br /> wasBig = <span style="color: navy; font-weight: bold;">false</span>;<br /> } <span style="color: navy; font-weight: bold;">else </span>{<br /> wasBig = <span style="color: navy; font-weight: bold;">true</span>;<br /> }<br /> }<br /> }<br /> System.<span style="color: #660e7a; font-style: italic; font-weight: bold;">out</span>.println(newInteresting.size() + <span style="color: green; font-weight: bold;">" " </span>+ maxDiff + <span style="color: green; font-weight: bold;">" " </span>+ Math.<span style="font-style: italic;">exp</span>(maxBase) + <span style="color: green; font-weight: bold;">" " </span>+ minDiff);<br /> <span style="color: navy; font-weight: bold;">if </span>(newInteresting.size() == interesting.<span style="color: #660e7a; font-weight: bold;">length</span>) <span style="color: navy; font-weight: bold;">break</span>;<br /> interesting = <span style="color: navy; font-weight: bold;">new </span>Number[newInteresting.size()];<br /> <span style="color: navy; font-weight: bold;">for </span>(<span style="color: navy; font-weight: bold;">int </span>i = <span style="color: blue;">0</span>; i < interesting.<span style="color: #660e7a; font-weight: bold;">length</span>; ++i) {<br /> interesting[i] = newInteresting.get(i);<br /> }<br /> }<br /> }<br />}</number></number></number></pre><br />Thanks for reading, and check back for more!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/1UdmyVT50RA" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com5http://petr-mitrichev.blogspot.com/2019/06/power-towers-solution.htmltag:blogger.com,1999:blog-1953325079793449971.post-81618614521859514262019-05-13T01:07:00.001+03:002019-05-13T01:07:31.179+03:00A fastest 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/-6vPLH9cyiM0/XNiU_UYSiiI/AAAAAAACSPI/KYekKXIVLjwLc2POHSnVuQpDR5SuJn_6ACLcBGAs/s1600/srm756top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="147" data-original-width="781" height="120" src="https://3.bp.blogspot.com/-6vPLH9cyiM0/XNiU_UYSiiI/AAAAAAACSPI/KYekKXIVLjwLc2POHSnVuQpDR5SuJn_6ACLcBGAs/s640/srm756top5.png" width="640" /></a></div>A TopCoder SRM was also the first event of the Apr 22 - Apr 28 week, more precisely SRM 756 (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=17493">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17493&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-756-editorials/">analysis</a>). Stonefeang was not the fastest on any problem, but very fast on all three, and therefore held a commanding coding phase lead that he defended during the challenges. Well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-8_FbrftFiH0/XNiWnJh76UI/AAAAAAACSPU/4hE0oSQj9OU35rYpaqr5nZVam4gZEwdWgCLcBGAs/s1600/oc1819minsktop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="366" data-original-width="1349" height="172" src="https://4.bp.blogspot.com/-8_FbrftFiH0/XNiWnJh76UI/AAAAAAACSPU/4hE0oSQj9OU35rYpaqr5nZVam4gZEwdWgCLcBGAs/s640/oc1819minsktop5.png" width="640" /></a></div>The next Open Cup 2018-19 round, the Grand Prix of Minsk, took place on Sunday (top 5 on the left). Many teams solved everything this time, but team Past Glory did this under 3 hours, and therefore earned a clear first place. Congratulations!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-MCumrVJsdoA/XNiYSDt6QFI/AAAAAAACSPg/wsnv80lJw4cww__gLWI8M-zzsu5WF-ykACLcBGAs/s1600/gcj2019r1btop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="462" data-original-width="1340" height="220" src="https://4.bp.blogspot.com/-MCumrVJsdoA/XNiYSDt6QFI/AAAAAAACSPg/wsnv80lJw4cww__gLWI8M-zzsu5WF-ykACLcBGAs/s640/gcj2019r1btop5.png" width="640" /></a></div>Finally, Google Code Jam 2018 Round 1B wrapped up the week (<a href="https://codingcompetitions.withgoogle.com/codejam/round/0000000000051706/000000000012295c">problems</a>, <a href="https://codingcompetitions.withgoogle.com/codejam/round/0000000000051706">results</a>, top 5 on the left). Benq was a lot faster than everybody else this time, and even one incorrect attempt did not really put his first place in doubt. Great performance!<br /><br />Thanks for reading, and check back for more.</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/zM927ipiG-w" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com1http://petr-mitrichev.blogspot.com/2019/05/a-fastest-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-27742635968822046882019-05-13T00:41:00.003+03:002019-05-13T00:41:50.372+03:00A forethought 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/-Vp00gfSFlzA/XNiOxQYlVWI/AAAAAAACSOY/Hs9pBNUYOG0Vb-Mkn2hBKC3uwZaYf8MGgCLcBGAs/s1600/srm755top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="151" data-original-width="779" height="124" src="https://2.bp.blogspot.com/-Vp00gfSFlzA/XNiOxQYlVWI/AAAAAAACSOY/Hs9pBNUYOG0Vb-Mkn2hBKC3uwZaYf8MGgCLcBGAs/s640/srm755top5.png" width="640" /></a></div>The Apr 15 - Apr 21 week was quite busy. TopCoder SRM 755 kicked things off on Monday (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=17457">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17457&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-755-editorials/">analysis</a>). The problems were quite straightforward, therefore the coding speed and the challenge phase came to the forefront. Tourist did very well on both, and got a well-deserved first place. Congratulations!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-Bt5w_AnyuMM/XNiQPmAPImI/AAAAAAACSOk/vCW2xC7j0-M1RKv2R2-RxLCuRzpCWPdzgCLcBGAs/s1600/tco19r1atop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="152" data-original-width="785" height="122" src="https://4.bp.blogspot.com/-Bt5w_AnyuMM/XNiQPmAPImI/AAAAAAACSOk/vCW2xC7j0-M1RKv2R2-RxLCuRzpCWPdzgCLcBGAs/s640/tco19r1atop5.png" width="640" /></a></div>TopCoder hosted a second round this week, the TCO 2019 Round 1A (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=17488">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17488&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://www.topcoder.com/blog/2019-topcoder-open-algorithm-round-1a-editorials/">analysis</a>). Most high-rated contestants got a bye to Round 2, therefore it was a chance to see some new names on the scoreboard. Congratulations to mrho888 on the great challenge phase performance and the win!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-4nzo9304DSM/XNiRXYITRbI/AAAAAAACSOw/V_jDwAy21-IbU6fNs4pwAE7a-hmForfCgCLcBGAs/s1600/cfforethoughtelimtop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="277" data-original-width="1099" height="160" src="https://4.bp.blogspot.com/-4nzo9304DSM/XNiRXYITRbI/AAAAAAACSOw/V_jDwAy21-IbU6fNs4pwAE7a-hmForfCgCLcBGAs/s640/cfforethoughtelimtop5.png" width="640" /></a></div>Codeforces ran the Elimination Round for the Forethought Future Cup right after the TCO round (<a href="https://codeforces.com/contest/1146">problems</a>, <a href="https://codeforces.com/contest/1146/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/66639">analysis</a>). There were eight problems and therefore the round was slightly longer at 2:30, but this did not stop tourist from solving everything in just over an hour. Well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-9B4jb3g0lfo/XNiSkaOkrQI/AAAAAAACSO8/Hh-IgXH0oSQfLn82tPdduD-_uuTLHmhqQCLcBGAs/s1600/oc1819balticseatop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="226" data-original-width="718" height="201" src="https://1.bp.blogspot.com/-9B4jb3g0lfo/XNiSkaOkrQI/AAAAAAACSO8/Hh-IgXH0oSQfLn82tPdduD-_uuTLHmhqQCLcBGAs/s640/oc1819balticseatop5.png" width="640" /></a></div>Finally, the Open Cup 2018-19 returned with the Grand Prix of Baltic Sea on Sunday (<a href="http://opentrains.snarknews.info/~ejudge/res/res10457">results</a>, top 5 on the left). The team Gifted Infants solved 10 problems in just under three hours and nothing in the remaining two, and yet nobody could catch them. Congratulations on the victory!<br /><br />Thanks for reading, and check back for more!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/1mfKlO5GRxA" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com0http://petr-mitrichev.blogspot.com/2019/05/a-forethought-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-91115582950604559322019-05-13T00:14:00.000+03:002019-05-13T00:14:18.918+03:00A postponed 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/-dyIE18d9F1s/XNiBVEG9-HI/AAAAAAACSN0/ngwes4pxSnAflQJHP9jVIUWJEK6mTGnzQCLcBGAs/s1600/gcj2019r1atop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="466" data-original-width="1189" height="250" src="https://4.bp.blogspot.com/-dyIE18d9F1s/XNiBVEG9-HI/AAAAAAACSN0/ngwes4pxSnAflQJHP9jVIUWJEK6mTGnzQCLcBGAs/s640/gcj2019r1atop5.png" width="640" /></a></div>The Apr 8 - Apr 14 week was light on contests from the usual suspects, but Google Code Jam Round 1A filled the void (<a href="https://codingcompetitions.withgoogle.com/codejam/round/0000000000051635/0000000000104e03">problems</a>, <a href="https://codingcompetitions.withgoogle.com/codejam/round/0000000000051635">results</a>, top 5 on the left). Gennady.Korotkevich required just 26 minutes to wrap things up, with others following in approximately 5-minute increments. Congratulations to everybody who made it to Round 2!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-OtsTRFq37PA/XNiLUjhgTVI/AAAAAAACSOE/gi03ES_8cTQSVZa9PtqEcf9s0VIr0O1QgCLcBGAs/s1600/IMG_20190403_103649.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/-OtsTRFq37PA/XNiLUjhgTVI/AAAAAAACSOE/gi03ES_8cTQSVZa9PtqEcf9s0VIr0O1QgCLcBGAs/s640/IMG_20190403_103649.jpg" width="640" /></a></div>In <a href="https://petr-mitrichev.blogspot.com/2019/05/a-double-moscow-week.html">my previous summary</a>, I have mentioned two problems. The first once came from ICPC World Finals: you are given a street with <i>n</i><=500 traffic lights on it arranged from left to right. The <i>i</i>-th traffic light stays red for <i>r<sub>i</sub></i> seconds, then green for <i>g<sub>i</sub></i> seconds, then repeats this cycle infinitely. The cycles for all traffic lights start at the same time 0, <i>r<sub>i</sub></i> and <i>g<sub>i</sub></i> are integers, and <i>r<sub>i</sub></i>+<i>g<sub>i</sub></i> does not exceed 100. Suppose you approach this street from the left at a random moment in time, and drive until you encounter a red light for the first time, or until you pass the entire street. What is the probability that you see red for the first time on 1st, 2nd, ..., <i>n</i>-th traffic light?<br /><br />The solutions gives a whole new meaning to the "meet in the middle" term. First of all, suppose all periods <i>r<sub>i</sub></i>+<i>g<sub>i</sub></i> are relatively prime. In this case seeing red on each of the traffic lights are independent random events, and therefore our answers are <i>r</i><sub>1</sub>/(<i>r</i><sub>1</sub>+<i>g</i><sub>1</sub>), <i>g</i><sub>1</sub>/(<i>r</i><sub>1</sub>+<i>g</i><sub>1</sub>)*<i>r</i><sub>2</sub>/(<i>r</i><sub>2</sub>+<i>g</i><sub>2</sub>), ...<br /><br />Moreover, only slightly more complex solution exists in case any two periods are either relatively prime, or one divides the other. In each group of periods where one divides the other we'll pick the largest one, and go from left to right which units of time modulo that largest period have already seen red, and the probabilities for different groups can still be simply multiplied since they're independent.<br /><br />However, we have arbitrary periods up to 100 in this problem, so the above condition does not hold. In order to overcome this, let's split the time into <i>m</i> parts: first part will have units 0, <i>m</i>, 2<i>m</i>, ..., the second part will have units 1, <i>m</i>+1, 2<i>m</i>+1, ..., and so on. Each of the parts can be "compressed" <i>m</i> times to obtain an instance of the same problem, but a period of <i>p</i> gets replaced by a period of <i>p</i>/gcd(<i>p</i>,<i>m</i>).<br /><br />The only remaining task is to find which value of <i>m</i> will guarantee that for any two numbers <i>p</i> and <i>q</i> up to 100, the numbers <i>p</i>'=<i>p</i>/gcd(<i>p</i>,<i>m</i>) and <i>q</i>'=<i>q</i>/gcd(<i>p</i>,<i>m</i>) are always relatively prime or one divides the other. We can write a small program for that, and it turns out that <i>m</i> can be as small as 2520=2<sup>3</sup>*3<sup>2</sup>*5*7.<br /><br />More generally, if the numbers were up to <i>x</i> instead of 100, <i>m</i> could be equal to the product of largest powers of primes not exceeding sqrt(<i>x</i>). For p' and q' to have a non-trivial greatest common divisor means for them to have two different primes in their factorization, which would mean that original numbers <i>p</i> and <i>q</i> were a product of two prime powers each exceeding sqrt(<i>x</i>), which is a contradiction.<br /><br />We have essentially decomposed the problem <i>m</i> times from the top, and that allowed to split it into independent problems of size at most <i>x</i> at the bottom, hence the "meet in the middle" mention above. The running time of this solution is O(<i>n</i>*<i>m</i>*<i>x</i>), which is fast enough.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-cYgbOaKkP50/XNiMHGu3eSI/AAAAAAACSOM/vOfhJdyLl6cwedGp3UuqCca-CeUjljnpwCLcBGAs/s1600/IMG_20190420_160044.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/-cYgbOaKkP50/XNiMHGu3eSI/AAAAAAACSOM/vOfhJdyLl6cwedGp3UuqCca-CeUjljnpwCLcBGAs/s640/IMG_20190420_160044.jpg" width="640" /></a></div>The second problem I mentioned came from Codeforces: you have <i>n</i> game units, each capable of causing 1 unit of damage per second. You need to merge them into <i>m</i> bigger game units, and if <i>a<sub>i</sub></i> units were merged into the <i>i</i>-th bigger unit, it will cause <i>a<sub>i</sub></i> units of damage per second. The <i>m</i> bigger units will then attack an enemy army also consisting of <i>m</i> units, with the <i>j</i>-th enemy unit having <i>b<sub>j</sub></i> hit points. The attack will happen second-by-second, and in each second each of your big units attacks one enemy unit. It is allowed for multiple units to attack one enemy unit in one second. What is the fastest way to decrease the hit points of all enemy units to zero or negative? You can choose the way you merge the <i>n</i> units into <i>m</i> big units, but you can do it only once, before all attacks.<br /><br />The key idea in solving this problem is to postpone the choice of <i>a<sub>i</sub></i>. Let's imagine we start with a single big unit of size <i>n</i>. Let it keep attacking the first enemy unit, until at some second its hit points drop to zero or below. If they dropped below zero, it means that we have wasted some attacking power; to avoid that, let us split this big unit into two now, one that can exactly finish the first enemy unit, and the other can now attack the second enemy unit during that second. In the following seconds, both units would keep attacking the second enemy unit, and when its hit points drop below zero, we will split one of our units again to avoid wasting attacking power.<br /><br />We will end up with at most <i>m</i>+1 units after all splitting is done, since we split once per enemy unit, but we can notice that the last split was not necessary, so we can skip doing it and end up with <i>m</i> units as required. And we have clearly spent the smallest possible time, since we never wasted a single unit of damage during all seconds except the last one.<br /><br />In some sense, the main obstacle in solving this problem is not realizing that it is actually easy :)<br /><br />Thanks for reading, and check back for more!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/G2qMPKTCkjE" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com0http://petr-mitrichev.blogspot.com/2019/05/a-postponed-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-34661917760732870812019-05-12T22:44:00.001+03:002019-05-12T22:44:13.988+03:00A double Moscow 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/-cdax9Aaeyq4/XNgL_gN9jOI/AAAAAAACSLc/6YMEvzB3yK8mN4_vSfIM96dXdFc-7GrTgCLcBGAs/s1600/icpc2019top12.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="679" data-original-width="1600" height="270" src="https://4.bp.blogspot.com/-cdax9Aaeyq4/XNgL_gN9jOI/AAAAAAACSLc/6YMEvzB3yK8mN4_vSfIM96dXdFc-7GrTgCLcBGAs/s640/icpc2019top12.png" width="640" /></a></div>The first week of April was of course focused on ICPC 2019 World Finals (<a href="https://icpc.baylor.edu/xwiki/wiki/public/download/worldfinals/WebHome/icpc2019.pdf">problems</a>, <a href="https://icpc.baylor.edu/scoreboard/">results</a>, top 12 on the left, <a href="https://youtu.be/pzoD0JgTBFA">official broadcast</a>, <a href="https://youtu.be/X6YdKQspOBk?t=1040">our stream</a>, <a href="https://icpc.baylor.edu/download/worldfinals/problems/finals2019solutions.pdf">analysis</a>). It feels strange to write a short summary given the amount of coverage available for the contest, but I'll do it anyway :) Warsaw took a huge early lead, but almost stopped after two hours, spending eternity on the technically tricky problem C and still not solving it. The three pre-tournament favorites Moscow, MIT and Tokyo overtook them, but only Moscow could solve all 10 solvable problems. Congratulations to the winners and to all medalists!<br /><br />Problem K was the most exciting for me, even though I didn't actually solve it myself. It went like this: you are given a street with <i>n</i><=500 traffic lights on it arranged from left to right. The <i>i</i>-th traffic light stays red for <i>r<sub>i</sub></i> seconds, then green for <i>g<sub>i</sub></i> seconds, then repeats this cycle infinitely. The cycles for all traffic lights start at the same time 0, <i>r<sub>i</sub></i> and <i>g<sub>i</sub></i> are integers, and <i>r<sub>i</sub></i>+<i>g<sub>i</sub></i> does not exceed 100. Suppose you approach this street from the left at a random moment in time, and drive until you encounter a red light for the first time, or until you pass the entire street. What is the probability that you see red for the first time on 1st, 2nd, ..., <i>n</i>-th traffic light?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-P5hp-KsmUWg/XNhptTMYZPI/AAAAAAACSNo/IwLnyJk6YP4uACFsCFW1vF_m-Rmf6k8iwCLcBGAs/s1600/cfglobal2top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="271" data-original-width="1103" height="156" src="https://4.bp.blogspot.com/-P5hp-KsmUWg/XNhptTMYZPI/AAAAAAACSNo/IwLnyJk6YP4uACFsCFW1vF_m-Rmf6k8iwCLcBGAs/s640/cfglobal2top5.png" width="640" /></a></div>Codeforces Global Round 2 took place on Saturday, when most of the teams were already back home or on the way there (<a href="https://codeforces.com/contest/1119">problems</a>, <a href="https://codeforces.com/contest/1119/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/66411">analysis</a>). ICPC gold medalist ecnerwala got enough points for the first place in less than an hour, even though our entire streaming team was trying to catch him as you can see :) Well done!<br /><br /><a href="https://codeforces.com/contest/1119/problem/G">Problem G</a> in this round was very nice. You have <i>n</i> game units, each capable of causing 1 unit of damage per second. You need to merge them into <i>m</i> bigger game units, and if <i>a<sub>i</sub></i> units were merged into the <i>i</i>-th bigger unit, it will cause <i>a<sub>i</sub></i> units of damage per second. The <i>m</i> bigger units will then attack an enemy army also consisting of <i>m</i> units, with the <i>j</i>-th enemy unit having <i>b<sub>j</sub></i> hit points. The attack will happen second-by-second, and in each second each of your big units attacks one enemy unit. It is allowed for multiple units to attack one enemy unit in one second. What is the fastest way to decrease the hit points of all enemy units to zero or negative? You can choose the way you merge the <i>n</i> units into <i>m</i> big units, but you can do it only once, before all attacks.<br /><br />Thanks for reading, and check back for more!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/75_q1VLskTw" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com0http://petr-mitrichev.blogspot.com/2019/05/a-double-moscow-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-51267502537752387982019-05-05T23:58:00.001+03:002019-05-05T23:58:39.952+03:00An order statistic 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/-wSOJl8J_OX4/XM7VF16IvtI/AAAAAAACSBw/omAzmnIKjCc1sDhkv3u5ArYhYedzzvPYgCLcBGAs/s1600/srm754top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="147" data-original-width="776" height="120" src="https://4.bp.blogspot.com/-wSOJl8J_OX4/XM7VF16IvtI/AAAAAAACSBw/omAzmnIKjCc1sDhkv3u5ArYhYedzzvPYgCLcBGAs/s640/srm754top5.png" width="640" /></a></div>The weekend of the Mar 25 - Mar 31 week was already the time to travel to Porto for ICPC World Finals for participants, but it still had a couple of rounds. TopCoder SRM 754 was the first one (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=17450">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17450&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-754-editorials/">analysis</a>). tourist's solution for the medium was challenged, which doesn't happen very often, but he more than made up for that by being the only contestant to solve the hard. Congratulations on the win!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-6UYUYz2iqwI/XM7W6oYxQBI/AAAAAAACSB8/uoPEvRYoghYm0UfW_akHEOUa1Q8VNxJLACLcBGAs/s1600/cf549top5.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/-6UYUYz2iqwI/XM7W6oYxQBI/AAAAAAACSB8/uoPEvRYoghYm0UfW_akHEOUa1Q8VNxJLACLcBGAs/s640/cf549top5.png" width="640" /></a></div>Codeforces Round 549 followed a few hours later (<a href="https://codeforces.com/contest/1142">problems</a>, <a href="https://codeforces.com/contest/1142/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/66301">analysis</a>). It was Um_nik's turn to dominate, being the only one to solve all problems but already leading the field with a sizable margin after solving 4 out of 5. Well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-1bsfbPYvs2A/XM9OIM-r9OI/AAAAAAACSFw/-n_JshGvWioCVIIW6UsP2Zc32EWsmB6XgCLcBGAs/s1600/IMG_20190401_112541.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/-1bsfbPYvs2A/XM9OIM-r9OI/AAAAAAACSFw/-n_JshGvWioCVIIW6UsP2Zc32EWsmB6XgCLcBGAs/s640/IMG_20190401_112541.jpg" width="640" /></a></div>In <a href="https://petr-mitrichev.blogspot.com/2019/05/a-close-to-third-week.html">the previous summary</a>, I have mentioned an AtCoder problem: we pick <i>n</i> independent uniformly random points on a circle, and then find two points the (circular/angular) distance between which is as close to 1/3 of the circle as possible. What is the expected value of the difference between that distance, expressed as a fraction of the circle, and 1/3? <i>n</i> is up to 10<sup>6</sup>, and you need to compute the answer using division modulo 10<sup>9</sup>+7.<br /><br /><a href="https://img.atcoder.jp/agc032/editorial.pdf">The official editorial</a> has a similar but not exactly the same explanation that does not require any googling to solve the problem. However, I'd like to share my approach as well.<br /><br />Let's collapse the circle 3 times, in other words project each point between 1/3 and 2/3 to <i>x</i>-1/3, and each point between 2/3 and 1 to <i>x</i>-2/3. The original question of finding two points with distance as close to 1/3 as possible <i>almost</i> translates into finding two closest points on this projection: if two points <i>x</i> and <i>y</i> are close, then these two points are either also close on the original circle (with probability 1/3), or the distance between them on the original circle is close to 1/3 (with probability 2/3), since 2/3 is also 1/3 when viewed from another angle. Moreover, these probabilities of 1/3 are <i>almost</i> independent for pairs of consecutive points: it's impossible that all pairs of consecutive points are close on original circle as well, but apart from that the probability that any <i>k</i><<i>n</i> consecutive pairs each are close on the original circle as well is equal to 1/3<sup><i>k</i></sup>.<br /><br />Now, in order to find the expected value of the difference between the sought distance and 1/3, define f(<i>x</i>) as the probability that this difference is >=<i>x</i>, then our answer is the integral of f(<i>x</i>).<br /><br />Consider g(<i>x</i>,<i>k</i>) to be the probability that the <i>k-</i>th smallest distance (in sorted order, the so-called order statistic) between consecutive points from n uniformly random ones being >=<i>x</i>. Then we can find the probability that exactly <i>k</i> distances between consecutive points are less than <i>x</i> as g(<i>x</i>,<i>k</i>+1)-g(<i>x</i>,<i>k</i>) (we define g(<i>x</i>,0)=0 here). If the points are picked on a circle of size 1/3 instead of the unit circle, that probability is equal to g(3<i>x</i>,<i>k</i>+1)-g(3<i>x</i>,<i>k</i>). Finally, if we have <i>k</i> such distances on the 1/3 circle less than <i>x</i>, then in order to have our answer >=<i>x</i>, we need all of those small distances to be "also close" on the original circle, the probability of which is 1/3<sup><i>k</i></sup>, therefore we have established that f(x)=sum<sub><i>k</i></sub>((g(3<i>x</i>,<i>k</i>+1)-g(3<i>x</i>,<i>k</i>))/3<sup><i>k</i></sup>).<br /><br />Since we're interested in the integral of f(<i>x</i>), we can swap summation and integration in the above formula, and learn that we're interested in sum<sub><i>k</i></sub>((int(g(3<i>x</i>,<i>k</i>+1))-int(g(3<i>x</i>,<i>k</i>)))/3<sup><i>k</i></sup>)=sum<sub><i>k</i></sub>((int(g(<i>x</i>,<i>k</i>+1))-int(g(<i>x</i>,<i>k</i>)))/3<sup><i>k+1</i></sup>).<br /><br />Finally, int(g(<i>x</i>,<i>k</i>)) is simply the expected value of the <i>k</i>-th order statistic of distances between consecutive points when n uniformly random points are chosen on a circle. It turns out it's possible to <a href="https://math.stackexchange.com/questions/13959/if-a-1-meter-rope-is-cut-at-two-uniformly-randomly-chosen-points-what-is-the-av">google it</a>: int(g(<i>x</i>,<i>k</i>))=1/<i>n</i>*(1/(<i>n</i>-<i>k</i>+1)+1/(<i>n</i>-<i>k</i>+2)+....+1/<i>n</i>).<br /><br />Most of the terms cancel out, and we get int(g(<i>x</i>,<i>k</i>+1))-int(g(<i>x</i>,<i>k</i>))=1/(<i>n</i>*(<i>n</i>-<i>k</i>)), and int(f(x))=sum<sub><i>k</i></sub>(1/(<i>n</i>*(<i>n</i>-<i>k</i>)*3<sup><i>k+1</i></sup>)), where the summation is done over all values of <i>k</i> from 0 to <i>n</i>-1, which solves our problem, and the actual code we submit just computes this sum.<br /><br />As I was coming up with this solution, I did not just invent it from top to bottom. Instead, I was digging from both ends: first, I've noticed that the setting is similar but not exactly the same as just finding the smallest distance between <i>n</i> random points on a circle of size 1/3. Then, I've googled that such distance has a known closed-form expression, and the same is true for <i>k</i>-th order statistic. Then, I've noticed that knowing how the <i>k</i>-th order statistic behaves allows us to split the probability space into areas where we just need to multiply by 1/3<sup><i>k</i></sup>. Finally, I've put the pieces together and verified that swapping summation and integration checks out, implemented the solution and got wrong answer for all samples: I forgot the extra 1/3 that comes from the fact that our circle is of size 1/3 instead of 1, and thus had 3<sup><i>k</i></sup> instead of 3<sup><i>k+1</i></sup> in the formula. The contest time was running out, and I've almost given up hope, but still started to make small changes to the code expecting that I have some issue in that vein, 3<sup><i>k-1</i></sup> didn't help but 3<sup><i>k+1</i></sup> did, and I very happily submitted with just 1 minute left in the round :)<br /><br />Thanks for reading, and check back for more!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/8IBGhjSGnCA" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com0http://petr-mitrichev.blogspot.com/2019/05/an-order-statistic-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-17167761457076620592019-05-02T17:18:00.005+03:002019-05-02T17:18:57.340+03:00A close to third 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/-WeCkqqmcU_U/XMrusno1XlI/AAAAAAACR8o/smPwgRt1-akOzx_0k4lTlM3Am-9_xLc4ACLcBGAs/s1600/srm753top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="150" data-original-width="784" height="122" src="https://3.bp.blogspot.com/-WeCkqqmcU_U/XMrusno1XlI/AAAAAAACR8o/smPwgRt1-akOzx_0k4lTlM3Am-9_xLc4ACLcBGAs/s640/srm753top5.png" width="640" /></a></div>TopCoder SRM 753 opened the Mar 18 - Mar 24 week in competitive programming (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=17422">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17422&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-753-editorials/">analysis</a>). Just ecnerwal and mnbvmar solved all three problems, and ecnerwal was so much faster that the challenge phase did not really matter. Congratulations on the victory!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-CO_sssZYCBs/XMr0hnBHGGI/AAAAAAACR80/Pw2CVqenLUMJgIeqsXkwJshBpFA9ZtBVwCLcBGAs/s1600/agc032top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="349" data-original-width="832" height="268" src="https://4.bp.blogspot.com/-CO_sssZYCBs/XMr0hnBHGGI/AAAAAAACR80/Pw2CVqenLUMJgIeqsXkwJshBpFA9ZtBVwCLcBGAs/s640/agc032top5.png" width="640" /></a></div>AtCoder Grand Contest 032 took place on Saturday (<a href="https://atcoder.jp/contests/agc032/tasks">problems</a>, <a href="https://atcoder.jp/contests/agc032/standings">results</a>, top 5 on the left, <a href="https://img.atcoder.jp/agc032/editorial.pdf">analysis</a>). ksun48 solved problem F in just 30 minutes, and tourist solved problem E in just 15 minutes, but nobody was able to solve both during the round. Therefore the advantage went to contestants who went for F, and ksun48 was by far the fastest of those. Well done!<br /><br />The hardest <a href="https://atcoder.jp/contests/agc032/tasks/agc032_f">problem F</a> had a very simple-looking statement. We pick <i>n</i> independent uniformly random points on a circle, and then find two points the (circular/angular) distance between which is as close to 1/3 of the circle as possible. What is the expected value of the difference between that distance, expressed as a fraction of the circle, and 1/3? <i>n</i> is up to 10<sup>6</sup>, and you need to compute the answer using division modulo 10<sup>9</sup>+7.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-2qXhYcmdukE/XMr6kSIHMyI/AAAAAAACR9A/qlRq4cJ0ldQP8Jye7rA4GrP1wtD12tK-wCLcBGAs/s1600/oc1819moscowtop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="269" data-original-width="874" height="196" src="https://4.bp.blogspot.com/-2qXhYcmdukE/XMr6kSIHMyI/AAAAAAACR9A/qlRq4cJ0ldQP8Jye7rA4GrP1wtD12tK-wCLcBGAs/s640/oc1819moscowtop5.png" width="640" /></a></div>Open Cup 2018-19 Grand Prix of Moscow was the last Open Cup round before the ICPC 2019 World Finals (<a href="http://opencup.ru/index.cgi?data=macros/stage&head=index&menu=index&stg=16&region=main&ncup=ocj&class=ocj">results</a>, top 5 on the left). Moscow SU team was setting the problems, but many other top ICPC teams competed. Three future gold medalists appear on the screenshot on the left :) Team Past Glory was head and shoulders above everybody, being the only team to finish all 13 problems, and doing it in just 3:40. Amazing dominance!<br /><br />Thanks for reading, and check back for more.</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/EJQAfv_hTqQ" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com1http://petr-mitrichev.blogspot.com/2019/05/a-close-to-third-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-76149521198740495882019-04-28T00:15:00.000+03:002019-04-28T00:15:55.215+03:00A week of 715<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/-FMlD1yEzYoE/XMS24QEmTfI/AAAAAAACR2g/UmrHzIZBNTUJtOAuhWj-hvD1-X2oP7t2wCLcBGAs/s1600/agc031top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="350" data-original-width="836" height="266" src="https://1.bp.blogspot.com/-FMlD1yEzYoE/XMS24QEmTfI/AAAAAAACR2g/UmrHzIZBNTUJtOAuhWj-hvD1-X2oP7t2wCLcBGAs/s640/agc031top5.png" width="640" /></a></div>AtCoder Grand Contest 031 was the main event of the Mar 11 - Mar 17 week (<a href="https://atcoder.jp/contests/agc031/tasks">problems</a>, <a href="https://atcoder.jp/contests/agc031/standings">results</a>, top 5 on the left, <a href="https://img.atcoder.jp/agc031/editorial.pdf">analysis</a>). I was stuck for a long time trying to solve any of the last three problems, finally getting F in with some serious squeezing into the time limit. eatmore solved that problem and had enough time and energy left for problem D, thus winning a clear first place. Congratulations!<br /><br />Said squeezing was required because I over-complicated a simple step of the solution. There was an odd number <i>m</i> up to 10<sup>6</sup>, and up to 10<sup>5</sup> queries (<i>a</i>, <i>b</i>), and I needed to check for each query if there exists a number <i>k</i> such that <i>a</i>*4<sup><i>k</i></sup>=<i>b</i> modulo <i>m</i>. I ended up grouping queries (<i>a</i>, <i>b</i>) by gcd(<i>a</i>, <i>b</i>), then in each group we need to answer discrete logarithm queries "is this number a power of 4 modulo <i>q</i>=<i>m</i>/gcd(<i>a</i>,<i>b</i>)", which can be done using big-step-small-step algorithm. This was still not fast enough, but we can actually do big steps only once per group, and small steps once per query, then the optimal size of a big step (and the overall complexity of answering one query) becomes not sqrt(<i>q</i>) but sqrt(<i>q</i>/<i>c</i>) where <i>c</i> is the number of queries in the group, and the solution runs in time.<br /><br />Of course, all this was completely unnecessary and I should've just found connected components in the graph where edges connect <i>x</i> with 4*<i>x</i> modulo <i>m</i> :)<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-EFAbhiGcOQM/XMTGERMNmuI/AAAAAAACR2s/ef868h718h0DitqPm7pdyrmu1c9QeZUZQCLcBGAs/s1600/IMG_20190303_142544.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/-EFAbhiGcOQM/XMTGERMNmuI/AAAAAAACR2s/ef868h718h0DitqPm7pdyrmu1c9QeZUZQCLcBGAs/s640/IMG_20190303_142544.jpg" width="640" /></a></div>In <a href="https://petr-mitrichev.blogspot.com/2019/03/a-painful-week.html">the previous summary</a>, I have mentioned an Open Cup problem: let's define f(<i>x</i>) as the smallest non-negative number that can be obtained by placing + or - before each digit in the decimal representation of <i>x</i>, and computing the resulting sum. What is the sum of all numbers <i>x</i> between <i>l</i> and <i>r</i> that have f(<i>x</i>) equal to 0, 1, ..., 9, modulo 10<sup>9</sup>+7? <i>l</i> and <i>r</i> have at most 100 digits, and there are 10000 testcases to solve in 2 seconds.<br /><br />The first step is pretty typical for such "between <i>l</i> and <i>r</i>" problems: let's compute the answers for segments [0,<i>r</i>] and [0,<i>l</i>-1] and get the final answer by subtraction. The second step is as typical: let's build our number <i>x</i> from left to right, then as soon as the next digit is smaller than the corresponding digit of <i>r</i>, the remaining digits can be arbitrary and we can use dynamic programming to share computations within testcase and between testcases.<br /><br />The dynamic programming state will consist of two parts: the number of remaining digits, and something describing the digits already chosen. However, it's not entirely clear what that something should be :) As the first approximation, we would need to store a set of numbers achievable by placing + or - before all digits already chosen. However, with 100 digits the achievable numbers would be up to 900, so we'd have something like 2<sup>901</sup> states.<br /><br />Here we need to become more practical. First, it seems natural to expect that there's no need to use very big intermediate sums, so we can take a guess and introduce a cap of, say, 100. This still leaves us with at most 2<sup>100</sup> states. Most of those states are not reachable, though, so we can write a small program that would generate all reachable states and learn that there are only 23108 states with a cap of 100, and 65618 states with a cap of 200 (the program uses BigIntegers as bitmasks):<br /><br /><pre style="background-color: white; font-family: "Courier New"; font-size: 9pt;"><span style="color: navy; font-weight: bold;">import </span>java.math.BigInteger;<br /><span style="color: navy; font-weight: bold;">import </span>java.util.*;<br /><br /><span style="color: navy; font-weight: bold;">public class </span>PlusMinusSums {<br /> <span style="color: navy; font-weight: bold;">static final int </span><span style="color: #660e7a; font-style: italic; font-weight: bold;">BUBEN </span>= <span style="color: blue;">200</span>;<br /> <span style="color: navy; font-weight: bold;">static final </span>BigInteger <span style="color: #660e7a; font-style: italic; font-weight: bold;">MASK </span>= BigInteger.<span style="color: #660e7a; font-style: italic; font-weight: bold;">ONE</span>.shiftLeft(<span style="color: #660e7a; font-style: italic; font-weight: bold;">BUBEN</span>).subtract(BigInteger.<span style="color: #660e7a; font-style: italic; font-weight: bold;">ONE</span>);<br /><br /> <span style="color: navy; font-weight: bold;">public static void </span>main(String[] args) {<br /> ArrayDeque<biginteger> queue = <span style="color: navy; font-weight: bold;">new </span>ArrayDeque<>();<br /> Map<biginteger iginteger="" list="">> stateToMoves = <span style="color: navy; font-weight: bold;">new </span>HashMap<>();<br /> queue.push(BigInteger.<span style="color: #660e7a; font-style: italic; font-weight: bold;">ONE</span>);<br /> stateToMoves.put(BigInteger.<span style="color: #660e7a; font-style: italic; font-weight: bold;">ONE</span>, <span style="color: navy; font-weight: bold;">null</span>);<br /> <span style="color: navy; font-weight: bold;">while </span>(!queue.isEmpty()) {<br /> BigInteger cur = queue.poll();<br /> List<biginteger> moves = <span style="color: navy; font-weight: bold;">new </span>ArrayList<>();<br /> <span style="color: navy; font-weight: bold;">for </span>(<span style="color: navy; font-weight: bold;">int </span>digit = <span style="color: blue;">0</span>; digit < <span style="color: blue;">10</span>; ++digit) {<br /> BigInteger next = <span style="font-style: italic;">makeMove</span>(cur, digit);<br /> <span style="color: navy; font-weight: bold;">if </span>(!stateToMoves.containsKey(next)) {<br /> queue.add(next);<br /> stateToMoves.put(next, <span style="color: navy; font-weight: bold;">null</span>);<br /> }<br /> moves.add(next);<br /> }<br /> stateToMoves.put(cur, moves);<br /> }<br /> System.<span style="color: #660e7a; font-style: italic; font-weight: bold;">err</span>.println(stateToMoves.size());</biginteger></biginteger></biginteger><br /> }<br /><br /> <span style="color: navy; font-weight: bold;">private static </span>BigInteger makeMove(BigInteger cur, <span style="color: navy; font-weight: bold;">int </span>digit) {<br /> BigInteger ifAdd = cur.shiftLeft(digit);<br /> BigInteger ifSub = cur.shiftRight(digit);<br /> BigInteger ifSubMinus = BigInteger.<span style="font-style: italic;">valueOf</span>(Integer.<span style="font-style: italic;">reverse</span>(cur.intValue() & ((<span style="color: blue;">1 </span><< digit) - <span style="color: blue;">1</span>)) >>> (<span style="color: blue;">31 </span>- digit));<br /> <span style="color: navy; font-weight: bold;">return </span>ifAdd.or(ifSub).or(ifSubMinus).and(<span style="color: #660e7a; font-style: italic; font-weight: bold;">MASK</span>);<br /> }<br />}</pre><br />This is already quite promising, but still not enough to fit in the time limit. But we can take this idea of automatically discovering the state space further, and say that many of the states we have are actually equivalent. All that matters in the end is the lowest bit set in the final state, and that bit is always between 0 and 9. Therefore, we can do the following process, which is essentially <a href="https://en.wikipedia.org/wiki/DFA_minimization">automaton minimization</a>: first, color all states in 10 colors based on the lowest bit set in them. Then repeatedly iterate over all states, and create a new coloring based on the following 11-tuple of colors for each state: the color of this state and the 10 states we can reach from it. After some amount of iterations the number of colors stops changing, which means we have found the equivalence classes of states. It turns out we have only 715 different states in this problem! Here's the code to be inserted into the main() method above:<br /><br /><pre style="background-color: white; font-family: "Courier New"; font-size: 9pt;">Map<biginteger long=""> stateToKey = <span style="color: navy; font-weight: bold;">new </span>HashMap<>();<br /><span style="color: navy; font-weight: bold;">for </span>(BigInteger x : stateToMoves.keySet()) {<br /> <span style="color: navy; font-weight: bold;">long </span>key = x.getLowestSetBit();<br /> <span style="color: navy; font-weight: bold;">if </span>(key >= <span style="color: blue;">10</span>) <span style="color: navy; font-weight: bold;">throw new </span>RuntimeException();<br /> stateToKey.put(x, key);<br />}<br /><span style="color: navy; font-weight: bold;">int </span>numStates = <span style="color: blue;">10</span>;<br />Random random = <span style="color: navy; font-weight: bold;">new </span>Random(<span style="color: blue;">54815353151L</span>);<br /><span style="color: navy; font-weight: bold;">while </span>(<span style="color: navy; font-weight: bold;">true</span>) {<br /> <span style="color: navy; font-weight: bold;">long </span>base = random.nextLong() * <span style="color: blue;">2 </span>+ <span style="color: blue;">1</span>;<br /> Map<biginteger long=""> newStateToKey = <span style="color: navy; font-weight: bold;">new </span>HashMap<>();<br /> Set<long> newKeys = <span style="color: navy; font-weight: bold;">new </span>HashSet<>();<br /> <span style="color: navy; font-weight: bold;">for </span>(BigInteger x : stateToMoves.keySet()) {<br /> <span style="color: navy; font-weight: bold;">long </span>key = stateToKey.get(x);<br /> <span style="color: navy; font-weight: bold;">for </span>(BigInteger dest : stateToMoves.get(x)) {<br /> <span style="color: navy; font-weight: bold;">long </span>childKey = stateToKey.get(dest);<br /> key = key * base + childKey;<br /> }<br /> newKeys.add(key);<br /> newStateToKey.put(x, key);<br /> }<br /> <span style="color: navy; font-weight: bold;">if </span>(newKeys.size() == numStates) <span style="color: navy; font-weight: bold;">break</span>;<br /> <span style="color: navy; font-weight: bold;">if </span>(newKeys.size() < numStates) <span style="color: navy; font-weight: bold;">throw new </span>RuntimeException();<br /> numStates = newKeys.size();<br /> stateToKey = newStateToKey;<br /> System.<span style="color: #660e7a; font-style: italic; font-weight: bold;">err</span>.println(numStates);<br />}</long></biginteger></biginteger></pre><br />Having just 715 states makes the overall solution run in time. Moreover, now we can also check the validity of our original assumption: we can notice that the number of different states does not change if we restrict the intermediate sums to 100 or 200, strongly suggesting that we have found all of them.<br /><br />Thanks for reading, and check back for more!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/n0xLHJ_pSjs" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com1http://petr-mitrichev.blogspot.com/2019/04/a-week-of-715.htmltag:blogger.com,1999:blog-1953325079793449971.post-8790865919243480292019-04-04T00:09:00.001+03:002019-04-08T18:56:17.333+03:00ICPC 2019 World Finals mirror stream<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/-vgnnUdGVxPI/WtQG4sH17qI/AAAAAAACA9Q/bLAMDTiABjcoFWfjp-E8CBeC5nJfDuDKQCLcBGAs/s1600/team.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="540" data-original-width="960" height="360" src="https://2.bp.blogspot.com/-vgnnUdGVxPI/WtQG4sH17qI/AAAAAAACA9Q/bLAMDTiABjcoFWfjp-E8CBeC5nJfDuDKQCLcBGAs/s640/team.jpg" width="640" /></a></div>ICPC 2019 World Finals take place tomorrow on Thursday at approximately 11:30 Porto time (<a href="https://www.timeanddate.com/worldclock/fixedtime.html?msg=ICPC+2019+World+Finals&iso=20190404T1130&p1=320&ah=5">click for other timezones</a>). Just like <a href="https://youtu.be/BZo23gj9ksk">last</a> <a href="https://youtu.be/nF3tSkNWRVQ">two</a> years, we'll try to solve it in parallel with tourist and Endagorion, and stream the process, assuming the problems will be available for submission <a href="https://judge.icpc.global/problems">on Kattis</a>.<br /><br />Tune in <a href="https://youtu.be/X6YdKQspOBk">on Youtube</a>!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/H4MvyvzziAY" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com1http://petr-mitrichev.blogspot.com/2019/04/icpc-2019-world-finals-mirror-stream.htmltag:blogger.com,1999:blog-1953325079793449971.post-29624124802899274752019-03-11T22:02:00.000+03:002019-04-27T23:40:17.793+03:00A painful 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/--hx64s4KH-8/XIajUibYykI/AAAAAAACQho/l7MwQnWrsnU08G9zPSQ1IhHcqIC1xn8CwCLcBGAs/s1600/srm752top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="98" data-original-width="635" src="https://2.bp.blogspot.com/--hx64s4KH-8/XIajUibYykI/AAAAAAACQho/l7MwQnWrsnU08G9zPSQ1IhHcqIC1xn8CwCLcBGAs/s1600/srm752top5.png" /></a></div>TopCoder SRM 752 was the first round of the last week (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=17420">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17420&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-752-editorials/">analysis</a>). rng_58 maintained his advantage in <a href="https://tco19.topcoder.com/home/algorithm/algorithm-leaderboard">the race for the third TCO19 spot</a> and was quite close to increasing his lead even further as he was just 4 points behind the first place before the challenge phase, and pashka was outside the top 10. However, tourist found 100 challenge points and won (congratulations!) and pashka found 50 challenge points and jumped into exactly 10th place, meaning that both rng_58 and pashka got 4 tournament points for this round.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-d_Ak-PgSXXQ/XIakygTJD6I/AAAAAAACQh0/Y2f1zpri-So3aFG0XiI7RAouyoRnu_K-ACLcBGAs/s1600/cf545top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="271" data-original-width="1102" height="156" src="https://1.bp.blogspot.com/-d_Ak-PgSXXQ/XIakygTJD6I/AAAAAAACQh0/Y2f1zpri-So3aFG0XiI7RAouyoRnu_K-ACLcBGAs/s640/cf545top5.png" width="640" /></a></div>Codeforces held its Round 545 early on Friday (<a href="https://codeforces.com/contest/1137">problems</a>, <a href="https://codeforces.com/contest/1137/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/65825">analysis</a>). Only sunset was able to solve very tricky problem F, so even exceeding the memory limit in problem C (thanks to implementing an asymptotically optimal solution but with a huge constant both for time and memory) did not change the outcome. Congratulations on the win!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-t2V7CdVHq8M/XIalcz-z54I/AAAAAAACQh8/OZrnAKNYuhkfXg-m__BC9QAm8ZvsgLAWQCLcBGAs/s1600/oc1819chinatop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="458" data-original-width="1206" height="242" src="https://2.bp.blogspot.com/-t2V7CdVHq8M/XIalcz-z54I/AAAAAAACQh8/OZrnAKNYuhkfXg-m__BC9QAm8ZvsgLAWQCLcBGAs/s640/oc1819chinatop5.png" width="640" /></a></div>Open Cup 2018-19 Grand Prix of China wrapped up the week (<a href="https://official.contest.yandex.ru/opencupXIX/contest/12242/standings/">results</a>, top 5 on the left, <a href="https://drive.google.com/file/d/19mOJBXxJ6O6XXG_7BUy1ZwVxaJ8e6cTd/view">analysis</a>). All problems were solvable in this round, but all of them required quite a bit of thinking and quite a bit of coding, and also, <a href="https://codeforces.com/blog/entry/65836?#comment-498254">as zeliboba quite succinctly formulated</a>, had a few somewhat unnecessary corner cases. Team Past Glory still prevailed in those tricky conditions with the last problem accepted at 4:59. Well done!<br /><br />Problem E in this round reminded me of <a href="https://petr-mitrichev.blogspot.com/2014/05/coming-up-with-tough-dynamic.html">my earlier post</a> where I tried to describe a way to find dynamic programming states semi-automatically. The problem went like this: let's define f(<i>x</i>) as the smallest non-negative number that can be obtained by placing + or - before each digit in the decimal representation of <i>x</i>, and computing the resulting sum. What is the sum of all numbers <i>x</i> between <i>l</i> and <i>r</i> that have f(<i>x</i>) equal to 0, 1, ..., 9, modulo 10<sup>9</sup>+7? <i>l</i> and <i>r</i> have at most 100 digits, and there are 10000 testcases to solve in 2 seconds.<br /><br />The idea to use dynamic programming is on the surface, but it's completely unclear how to achieve a manageable number of states. Do you see a way to find a small state space algorithmically?<br /><br />Thanks for reading, and check back next week!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/Uj-Ft6XjVeg" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com4http://petr-mitrichev.blogspot.com/2019/03/a-painful-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-51888867217662450332019-03-10T23:32:00.001+03:002019-03-11T22:17:19.926+03:00An oracle 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/-BYZpMGpzXiY/XIU-33br-CI/AAAAAAACQgY/V17dS0tzZPcWHI6dYnz4l4eFNtaJY19swCLcBGAs/s1600/oc1819americatop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="208" data-original-width="801" height="166" src="https://3.bp.blogspot.com/-BYZpMGpzXiY/XIU-33br-CI/AAAAAAACQgY/V17dS0tzZPcWHI6dYnz4l4eFNtaJY19swCLcBGAs/s640/oc1819americatop5.png" width="640" /></a></div>Last week had an Open Cup round for the fourth week in a row. Open Cup 2018-19 Grand Prix of America allowed teams from all over the world to participate in NAIPC 2019 (<a href="https://naipc19.kattis.com/standings">problems</a>, <a href="http://opentrains.snarknews.info/~ejudge/res/res10454">results</a>, top 5 on the left, <a href="https://naipc19.kattis.com/standings">NAIPC results</a>, <a href="https://www.youtube.com/watch?v=lotwdEK6DUU">analysis</a>). Just 3.5 hours were enough for team Past Glory to wrap the problemset up, a good 40 minutes before other teams could do the same. Congratulations on the win!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-nVcILP412Pg/XIVy-7XBs5I/AAAAAAACQgw/X1EV_oBoEvA9bWgdw-PQ9SoxuVxYFY6YwCLcBGAs/s1600/IMG_20190223_175327.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/-nVcILP412Pg/XIVy-7XBs5I/AAAAAAACQgw/X1EV_oBoEvA9bWgdw-PQ9SoxuVxYFY6YwCLcBGAs/s640/IMG_20190223_175327.jpg" width="640" /></a></div>In <a href="https://petr-mitrichev.blogspot.com/2019/02/a-wtf-week.html">my previous summary</a>, I have mentioned two (in some sense three :)) problems. The first group was from the AtCoder World Tour Finals: consider an infinite 2D grid, where each cell can be either black or white. Initially, exactly one cell was black, and then we repeatedly applied the following operation: take some integers <i>x</i> and <i>y</i>, and invert the color of three cells: (<i>x</i>, <i>y</i>), (<i>x</i>+1, <i>y</i>) and (<i>x</i>, <i>y</i>+1). You are given the set of black cells in the final state of the grid. There are at most 10<sup>5</sup> black cells in C1 and at most 10<sup>4</sup> in C2, and each black cell has coordinates not exceeding 10<sup>17</sup> by absolute value. Your goal is to find the coordinates of the only cell that was black originally. In problem C1 you know that its <i>y</i>-coordinate was 0, and in C2 there are no further constraints.<br /><br />A typical idea in this type of problem is to come up with an invariant that is not changed by the operation and that can be efficiently computed for source and target positions. A typical invariant that plays well with inversions is boolean or bitwise xor. Let's say that a white cell is a 0, a black cell is a 1, let's also pick some set of cells <i>S</i>, then our invariant will be their bitwise xor (in other words, the parity of the number of black cells in <i>S</i>).<br /><br />Not any set <i>S</i> works, though: we must make sure that for each invertible triple (<i>x</i>, <i>y</i>), (<i>x</i>+1, <i>y</i>) and (<i>x</i>, <i>y</i>+1) either 0 or 2 cells belong to <i>S</i>, to make sure the xor does not change when we invert the triple. Suppose that for some row <i>y</i>=<i>y</i><sub>0</sub> the set <i>S</i> contains exactly one cell (<i>x</i><sub>0</sub>,<i>y</i><sub>0</sub>). The triple (<i>x</i><sub>0</sub>,<i>y</i><sub>0</sub>), (<i>x</i><sub>0</sub>+1,<i>y</i><sub>0</sub>), (<i>x</i><sub>0</sub>,<i>y</i><sub>0</sub>+1) must have 0 or 2 cells in <i>S</i>, and since (<i>x</i><sub>0</sub>,<i>y</i><sub>0</sub>) is in <i>S</i> but (<i>x</i><sub>0</sub>+1,<i>y</i><sub>0</sub>) is not, (<i>x</i><sub>0</sub>,<i>y</i><sub>0</sub>+1) must be in <i>S</i>. Applying a similar argument, we find that in the row <i>y</i>=<i>y</i><sub>0</sub> exactly two cells must be in <i>S</i>: (<i>x</i><sub>0</sub>,<i>y</i><sub>0</sub>+1) and (<i>x</i><sub>0</sub>-1,<i>y</i><sub>0</sub>+1). Then we can compute which cells must be in S in the row <i>y</i>=<i>y</i><sub>0</sub>+2, and so on.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-TromSWd2ddo/XIV0HSxuGXI/AAAAAAACQhM/PMuOuAuQoe4IzpU1gBi8xtUUljqLGlX5gCKgBGAs/s1600/IMG_20190310_213004.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" data-original-height="1600" data-original-width="1487" height="400" src="https://4.bp.blogspot.com/-TromSWd2ddo/XIV0HSxuGXI/AAAAAAACQhM/PMuOuAuQoe4IzpU1gBi8xtUUljqLGlX5gCKgBGAs/s400/IMG_20190310_213004.jpg" width="371" /></a></div>We can realize by looking at the resulting pattern, or by understanding what the process really is, that in general a cell (<i>x</i><sub>0</sub>-<i>k</i>,<i>y</i><sub>0</sub>+<i>n</i>) is in <i>S</i> if and only if C(<i>n</i>,<i>k</i>) is odd. And that, in turn, is true if and only if <i>n</i>&<i>k</i>=<i>k</i>, where & denotes bitwise and. There are still multiple ways to extend the set <i>S</i> to rows with <i>y</i><<i>y</i><sub>0</sub>, so to avoid thinking about that we will always pick very small <i>y</i><sub>0</sub> that is below all interesting points.<br /><br />Now it is very easy to compute our invariant for the input set of cells: we need to count the parity of the number of such (<i>x</i>,<i>y</i>) in the set that (<i>y</i>-<i>y</i><sub>0</sub>)&(<i>x</i><sub>0</sub>-<i>x</i>)=<i>x</i><sub>0</sub>-<i>x</i>. But we know that the operations do not change the invariant, and that initially we had only one cell (<i>x</i><sub><i>A</i></sub>,<i>y</i><sub><i>A</i></sub>). This means that we have an oracle that can tell us whether (<i>y</i><sub><i>A</i></sub>-<i>y</i><sub>0</sub>)&(<i>x</i><sub>0</sub>-<i>x</i><sub><i>A</i></sub>)=<i>x</i><sub>0</sub>-<i>x</i><sub><i>A</i></sub> for any two numbers <i>x</i><sub>0</sub> and <i>y</i><sub>0</sub> such that <i>y</i><sub>0</sub><=<i>y</i><sub><i>A</i></sub>.<br /><br />In problem C1, we know that <i>y</i><sub><i>A</i></sub>=0, so we can just pick <i>y</i><sub>0</sub> in such a way that -<i>y</i><sub>0</sub> has all bits set except one, and then the oracle will effectively tell us the corresponding bit of <i>x</i><sub>0</sub>-<i>x</i><sub><i>A</i></sub>, so we can determine <i>x</i><sub><i>A</i></sub> in logarithmic number of queries.<br /><br />In problem C2 the things are not so simple. However, suppose we have found some <i>x</i><sub>0</sub> and <i>y</i><sub>0</sub> such that (<i>y</i><sub><i>A</i></sub>-<i>y</i><sub>0</sub>)&(<i>x</i><sub>0</sub>-<i>x</i><sub><i>A</i></sub>)=<i>x</i><sub>0</sub>-<i>x</i><sub><i>A</i></sub>, in other words we made our oracle return 1. Now we can go from the highest bits to the lowest bit, and by calling our oracle 3 additional times checking what happens if we add 2<sup><i>k</i></sup> to <i>x</i><sub>0</sub> and/or subtract 2<sup><i>k</i></sup> from <i>y</i><sub>0</sub>, we can determine the <i>k</i>-th bit of <i>y</i><sub><i>A</i></sub>-<i>y</i><sub>0</sub> and <i>x</i><sub>0</sub>-<i>x</i><sub><i>A</i></sub>, then setting both to 0 and proceeding to the lower bits, and eventually recovering <i>y</i><sub><i>A </i></sub>and <i>x</i><sub><i>A</i></sub>.<br /><br />The tricky part lies in the initial step of making the oracle return 1 for something: the probability of <i>n</i>&<i>k</i>=<i>k</i> for random <i>n</i> and <i>k</i> is roughly 0.75<sup>number_of_bits</sup>, which is way too low to just stumble upon it. This is how far I got during the contest, so the remaining magic is closely based on the official editorial and my conversations with Makoto.<br /><br />Instead of running the oracle for the set <i>S</i> with just one cell (<i>x</i><sub>0</sub>,<i>y</i><sub>0</sub>) in the row <i>y</i>=<i>y</i><sub>0</sub>, we will run it with the set <i>S</i> which has all cells (<i>x</i><sub>0</sub>,<i>y</i><sub>0</sub>) in the row <i>y</i>=<i>y</i><sub>0 </sub>where <i>x</i><sub>0</sub> mod 3=<i>u</i>, <i>l</i><=<i>x</i><sub>0</sub><=<i>r</i>, where <i>y</i><sub>0</sub>, <i>u</i>, <i>l</i> and <i>r</i> are the parameters of the oracle. This requires counting the number of <i>x</i><sub>0 </sub>satisfying the above criteria and also the constraint (<i>y</i>-<i>y</i><sub>0</sub>)&(<i>x</i><sub>0</sub>-<i>x</i>)=<i>x</i><sub>0</sub>-<i>x</i> for each black cell in the input, which can be done by a relatively standard dynamic programming on the bitwise representation of <i>x</i><sub>0</sub>.<br /><br />As we know, this will give us the parity of the amount of such <i>x</i><sub>0</sub> that <i>x</i><sub>0</sub> mod 3=<i>u</i>, <i>l</i><=<i>x</i><sub>0</sub><=<i>r</i>, and (<i>y</i><sub><i>A</i></sub>-<i>y</i><sub>0</sub>)&(<i>x</i><sub>0</sub>-<i>x</i><sub><i>A</i></sub>)=<i>x</i><sub>0</sub>-<i>x</i><sub><i>A</i></sub>. A crucial observation is: no matter what <i>y</i><sub>0</sub> we pick, if <i>l </i>is very small and <i>r</i> is very large, then for at least one <i>u</i> from the set {0, 1, 2} this oracle will return 1! This can be proven by induction by <i>y</i><sub><i>A</i></sub>: when <i>y</i><sub><i>A</i></sub>=<i>y</i><sub>0</sub>, (<i>y</i><sub><i>A</i></sub>-<i>y</i><sub>0</sub>)&(<i>x</i><sub>0</sub>-<i>x</i><sub><i>A</i></sub>)=<i>x</i><sub>0</sub>-<i>x</i><sub><i>A</i></sub> only when <i>x</i><sub>0</sub>=<i>x</i><sub><i>A</i></sub>, so the oracle will return 1 when u=<i>x</i><sub><i>A</i></sub> mod 3 and zero in the other two cases. When <i>y</i><sub><i>A </i></sub>increases by one, given our C(<i>n</i>,<i>k</i>)-like propagation, every <i>x</i><sub>0 </sub>for which the oracle returns 1 contributes one to itself and <i>x</i><sub>0</sub>+1, which means that we go from parities (<i>a</i>, <i>b</i>, <i>c</i>) for the three remainders modulo 3 to parities (<i>a</i>+<i>b</i>, <i>b</i>+<i>c</i>, <i>a</i>+<i>c</i>), so from (1, 0, 0) to (1, 0, 1), and then to (1, 1, 0), and then to (0, 1, 1), and then to (1, 0, 1) and so on, and never get (0, 0, 0).<br /><br />This means that in at most three attempts we can make this complex oracle return 1. Now (more magic incoming!) we can do a binary search: if for (<i>y</i><sub>0</sub>, <i>u</i>, <i>l</i>, <i>r</i>) the oracle returns 1, then it must return 1 for exactly one of (<i>y</i><sub>0</sub>, <i>u</i>, <i>l</i>, <i>m</i>) and (<i>y</i><sub>0</sub>, <i>u</i>, <i>m</i>+1, <i>r</i>). This way we can find a single cell (<i>x</i><sub>0</sub>,<i>y</i><sub>0</sub>) for which the oracle returns 1 in a logarithmic number of requests to the complex oracle, and then switch to using the simple oracle and proceed with reconstructing the answer as described above, completing the solution of C2.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-P0KVALcJWWY/XIVzEWKHOgI/AAAAAAACQg0/CBBeMjB9WosbvpPcgstGzY4L4EQsmJUowCLcBGAs/s1600/IMG_20190303_135957.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/-P0KVALcJWWY/XIVzEWKHOgI/AAAAAAACQg0/CBBeMjB9WosbvpPcgstGzY4L4EQsmJUowCLcBGAs/s640/IMG_20190303_135957.jpg" width="640" /></a></div>I have also mentioned an Open Cup problem: you have some amount <i>x</i> of money between 0 and 1. You're playing a betting game where in one turn, you bet some amount <i>y</i>, and with probability <i>p</i> (<i>p</i><0.5) your amount of money becomes <i>x</i>+<i>y</i>, and with probability 1-<i>p</i> it becomes <i>x</i>-<i>y</i>. Your bet must not exceed your current amount of money. Your goal is to reach amount 1. So far this setup is somewhat standard, but here comes the twist: your bets must be non-decreasing, in other words at each turn you must bet at least the amount you bet in the previous turn. In case you don't have enough money for that, you lose. What is the probability of winning if you play optimally? More precisely, what is the supremum of the set of probabilities of winning of all possible strategies? Both <i>x</i> and <i>p</i> are given as fractions with numerator and denominator not exceeding 10<sup>6</sup>, and you need to return the answer using division modulo 998244353.<br /><br />You can find my approach to solving it in <a href="https://codeforces.com/blog/entry/65510?#comment-495131">this Codeforces comment</a>.<br /><br />Thanks for reading, and check back for this week's summary!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/er8RDaFQ5QQ" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com0http://petr-mitrichev.blogspot.com/2019/03/an-oracle-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-67194231488627845602019-02-27T08:51:00.001+03:002019-02-27T08:51:09.373+03:00A WTF 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/-_ig0BKG88cs/XHNpkaDAhXI/AAAAAAACQLo/zbrudwU5BrwbINL6AWosfDK1PTLEQ1DvwCLcBGAs/s1600/acwtf19top8.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="519" data-original-width="826" height="402" src="https://3.bp.blogspot.com/-_ig0BKG88cs/XHNpkaDAhXI/AAAAAAACQLo/zbrudwU5BrwbINL6AWosfDK1PTLEQ1DvwCLcBGAs/s640/acwtf19top8.png" width="640" /></a></div>AtCoder World Tour Finals 2019 in Tokyo headlined the last week (<a href="https://atcoder.jp/contests/wtf19/tasks">problems</a>, <a href="https://atcoder.jp/contests/wtf19/standings">results</a> on the left, <a href="https://atcoder.jp/contests/wtf19-open/standings">open round results</a>, <a href="https://youtu.be/DLRYW7yQNfU">my screencast</a>, <a href="https://img.atcoder.jp/wtf19-open/editorial.pdf">analysis</a>). The last three problems turned out too difficult to solve during the contest, so it all came down to speed on the first three. yutaka1999 was the fastest, but his five incorrect attempts gave the competitors 25 minutes to overtake him, and apiad did just that and won the first ever AtCoder World Tour. Congratulations!<br /><br />I was pretty quick with solving A and C1, but then tried to solve B, C2 and E in parallel, switching often from one to another, instead of focusing on just one of them as it was not clear at that point that solving just one more would be enough for a good result. By the time I managed to come up with a solution for B, it was already too late to catch apiad and yutaka1999.<br /><br />I found the problems <a href="https://atcoder.jp/contests/wtf19/tasks/wtf19_c1">C1</a> and <a href="https://atcoder.jp/contests/wtf19/tasks/wtf19_c2">C2</a> the most exciting. Consider an infinite 2D grid, where each cell can be either black or white. Initially, exactly one cell was black, and then we repeatedly applied the following operation: take some integers <i>x</i> and <i>y</i>, and invert the color of three cells: (<i>x</i>, <i>y</i>), (<i>x</i>+1, <i>y</i>) and (<i>x</i>, <i>y</i>+1). You are given the set of black cells in the final state of the grid. There are at most 10<sup>5</sup> black cells in C1 and at most 10<sup>4</sup> in C2, and each black cell has coordinates not exceeding 10<sup>17</sup> by absolute value. Your goal is to find the coordinates of the only cell that was black originally. In problem C1 you know that its <i>y</i>-coordinate was 0, and in C2 there are no further constraints. Can you see a way to solve at least C1?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-wx27LwInpNE/XHNu9-A8ROI/AAAAAAACQL0/dw6zNxNp4ssoM5yLlJtXEZKnDtVSzr5YQCLcBGAs/s1600/srm751top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="95" data-original-width="628" src="https://4.bp.blogspot.com/-wx27LwInpNE/XHNu9-A8ROI/AAAAAAACQL0/dw6zNxNp4ssoM5yLlJtXEZKnDtVSzr5YQCLcBGAs/s1600/srm751top5.png" /></a></div>TopCoder SRM 751 followed on Friday (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=17400">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17400&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-751-editorials/">analysis</a>). Only rng_58 and pashka submitted all three problems, but the challenge phase did not leave them unscathed, and IH19980412 emerged in the first place thanks to three successful challenges, including one on rng_58 himself. Well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-HA-RuryY3kY/XHNwNEKcSTI/AAAAAAACQMA/vkgagupRaWU48mchCpyJwh7VlnR8R78YQCLcBGAs/s1600/oc1819bytedancetop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="211" data-original-width="787" height="170" src="https://4.bp.blogspot.com/-HA-RuryY3kY/XHNwNEKcSTI/AAAAAAACQMA/vkgagupRaWU48mchCpyJwh7VlnR8R78YQCLcBGAs/s640/oc1819bytedancetop5.png" width="640" /></a></div>Open Cup 2018-19 Grand Prix of Bytedance presented problems from the team Moscow SU: Red Panda on Sunday (<a href="http://opentrains.snarknews.info/~ejudge/res/res10453">results</a>, top 5 on the left, <a href="https://drive.google.com/file/d/1aV_UGxlTh00PsiqUnKN_mOGoL26KrhuO/view?usp=sharing">analysis</a>). There were several nice problems in this contest, and problem C was the one I've enjoyed solving the most.<br /><br />You have some amount <i>x</i> of money between 0 and 1. You're playing a betting game where in one turn, you bet some amount <i>y</i>, and with probability <i>p</i> (<i>p</i><0.5) your amount of money becomes <i>x</i>+<i>y</i>, and with probability 1-<i>p</i> it becomes <i>x</i>-<i>y</i>. Your bet must not exceed your current amount of money. Your goal is to reach amount 1. So far this setup is somewhat standard, but here comes the twist: your bets must be non-decreasing, in other words at each turn you must bet at least the amount you bet in the previous turn. In case you don't have enough money for that, you lose. What is the probability of winning if you play optimally? More precisely, what is the supremum of the set of probabilities of winning of all possible strategies? Both <i>x</i> and <i>p</i> are given as fractions with numerator and denominator not exceeding 10<sup>6</sup>, and you need to return the answer using division modulo 998244353.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-lHDeXZUTteY/XHWYtpFLh4I/AAAAAAACQMQ/Yz9lnr8xz4MNwpcvHpoLJSfg8un6-lhFwCLcBGAs/s1600/cf542top5.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://3.bp.blogspot.com/-lHDeXZUTteY/XHWYtpFLh4I/AAAAAAACQMQ/Yz9lnr8xz4MNwpcvHpoLJSfg8un6-lhFwCLcBGAs/s640/cf542top5.png" width="640" /></a></div>Finally, Codeforces Round 542 wrapped up the week on Sunday evening (<a href="https://codeforces.com/contest/1129">problems</a>, <a href="https://codeforces.com/contest/1129/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/65520">analysis</a>). Three contestants solved all problems correctly, and there wasn't much challenge activity, so everything was decided by the problem solving order and speed. mnbvmar was the fastest to solve everything, and did (the slightly faster to solve) problem E before problem D unlike the others. Congratulations on the victory!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/--OBnfnWvW2g/XHYlDjmqLzI/AAAAAAACQMo/z2Ui6GhRBe8D0TIx5eSILlClsqq7UGn7gCLcBGAs/s1600/MVIMG_20190220_123030.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/--OBnfnWvW2g/XHYlDjmqLzI/AAAAAAACQMo/z2Ui6GhRBe8D0TIx5eSILlClsqq7UGn7gCLcBGAs/s640/MVIMG_20190220_123030.jpg" width="640" /></a></div><a href="https://petr-mitrichev.blogspot.com/2019/02/a-snack-week.html">Last week</a> I have mentioned another Open Cup problem: there's a hidden not necessarily convex polygon with <i>n</i> vertices (<i>n</i><=200). Your goal is to find its area, but the only thing you can do is to pick a subset of its vertices by their numbers (the vertices are numbered in the order they appear along the polygon), and the system will tell you the area of the convex hull of the chosen points. You can retrieve the convex hull areas for at most <i>n</i>*(<i>n</i>-1)/2 subsets before you need to give back the area of the hidden polygon.<br /><br />During the contest we tried to invent a solution based on representing the area of the polygon as the sum of signed areas of triangles using one of its vertices as the base point. We could not figure out a way to deal with "signed" part: we need to determine the orientation of each triangle, and while in most cases we can determine orientation of triangle ACD given the orientation of triangle ABC and ability to ask convex hull area queries, we could not see a way to make it work in all cases. Is there one?<br /><br />The approach that works involves a completely different idea: first, let's find the area of the convex hull of all vertices. Since our polygon is not necessarily convex, then we need to subtract something from it.<br /><br />For each particular vertex, we can find whether it lies on the boundary of the convex hull or not by checking if the area of the convex hull of all vertices except this one is smaller. Now we know which vertices do not lie on the convex hull of everything.<br /><br />Now let's take segments of consecutive vertices that do not lie on the convex hull, together with one vertex of convex hull before and after such segment. We claim that those are precisely the polygons whose areas we need to subtract from the area of the big convex hull to find the answer.<br /><br />The only remaining step is to recursively apply the same algorithm to find the areas of those smaller polygons.<br /><br />Thanks for reading, and check back next week!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/YXoebqlJAAs" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com3http://petr-mitrichev.blogspot.com/2019/02/a-wtf-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-19842146769572369662019-02-18T02:51:00.002+03:002019-02-18T02:51:47.052+03:00A snack week<div dir="ltr" style="text-align: left;" trbidi="on"><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/-gA3qEJChOr8/XGmsRWZhflI/AAAAAAACP5w/UCOFloct6jYa7eE8tGdlJMLYVauhoveWwCLcBGAs/s1600/snackdown2019top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="450" data-original-width="1534" height="186" src="https://1.bp.blogspot.com/-gA3qEJChOr8/XGmsRWZhflI/AAAAAAACP5w/UCOFloct6jYa7eE8tGdlJMLYVauhoveWwCLcBGAs/s640/snackdown2019top5.png" width="640" /></a></div>CodeChef SnackDown 2019 onsite finals early on Saturday was the main event of the week (<a href="https://www.codechef.com/SNCKFL19">problems</a>, <a href="https://www.codechef.com/rankings/SNCKFL19">results</a>, top 5 on the left). Team ovuvuevuevue enyetuenwuevue ugbemugbem osas looked to have pretty good winning chances when they were the first to solve 8 problems with a couple of hours still left in the contest, but they could not make further progress in the remaining time. Team Dandelion solved the ninth problem with about five minutes remaining to go on top, but team pastry was working on the same problem and could still overtake them on penalty time. It turned out that they were comparing their solution locally against a slower but simpler one, and there were still cases of disagreement as the end of the contest was approaching. With nothing left to lose, they submitted whatever they had 30 seconds before the end of the round — and it passed the system test. Congratulations to team pastry on the super narrow victory!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-N2CB2w2WAnM/XGnvGvMsBYI/AAAAAAACP6E/sJ3joKu9TnYTed4dqmJtaYRAhfntOCjDgCLcBGAs/s1600/cf539top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="273" data-original-width="1105" height="158" src="https://4.bp.blogspot.com/-N2CB2w2WAnM/XGnvGvMsBYI/AAAAAAACP6E/sJ3joKu9TnYTed4dqmJtaYRAhfntOCjDgCLcBGAs/s640/cf539top5.png" width="640" /></a></div>Later that day, Codeforces hosted its Round 539 (<a href="https://codeforces.com/contest/1109">problems</a>, <a href="https://codeforces.com/contest/1109/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/65295">analysis</a>). The participants of the Codechef finals occupied most of the top spots in this round as well. wxhtxdy was the only contestant to solve all problems, but as his solution to E turned out to be incorrect, Um_nik emerged in the first place. Congratulations to Um_nik on the win!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-S5NJiVYxnNU/XGnxJ2FKbmI/AAAAAAACP6Y/Q_JreMTt7y0nifYOV737E6uwfoAmoWR7gCLcBGAs/s1600/oc1819belarustop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="213" data-original-width="725" height="188" src="https://1.bp.blogspot.com/-S5NJiVYxnNU/XGnxJ2FKbmI/AAAAAAACP6Y/Q_JreMTt7y0nifYOV737E6uwfoAmoWR7gCLcBGAs/s640/oc1819belarustop5.png" width="640" /></a></div></div>Finally, the Open Cup 2018-19 Grand Prix of Belarus wrapped up the week (<a href="http://opentrains.snarknews.info/~ejudge/res/res10452">results</a>, top 5 on the left). Team MIT THREE won the second round in a row, this time solving three in the last hour including two hardest ones in the last fifteen minutes. Amazing persistence once again, well done!<br /><br />Problem A was a very nice interactive one: there's a hidden not necessarily convex polygon with <i>n</i> vertices (<i>n</i><=200). Your goal is to find its area, but the only thing you can do is to pick a subset of its vertices by their numbers (the vertices are numbered in the order they appear along the polygon), and the system will tell you the area of the convex hull of the chosen points. You can retrieve the convex hull areas for at most <i>n*</i>(<i>n</i>-1)/2 subsets before you need to give back the area of the hidden polygon.<br /><br />Thanks for reading, and check back next week!<br /><br />I will also try to post something here and/or on <a href="https://twitter.com/petrmitrichev">Twitter</a> about the first ever <a href="https://codeforces.com/blog/entry/64174">AtCoder World Tour finals</a> in Tokyo on Thursday — already looking forward to the event! </div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/ALTvoy0ghSk" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com1http://petr-mitrichev.blogspot.com/2019/02/a-snack-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-69270846871127641422019-02-11T01:22:00.000+03:002019-02-11T01:22:27.875+03:00A tourist 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/-DuhFWevNeHk/XGCRIgyO4nI/AAAAAAACPrM/qbOeRZejpvcY_RS6v0aeV2yGI-_Rgw3FwCLcBGAs/s1600/cfglobal1top5.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://3.bp.blogspot.com/-DuhFWevNeHk/XGCRIgyO4nI/AAAAAAACPrM/qbOeRZejpvcY_RS6v0aeV2yGI-_Rgw3FwCLcBGAs/s640/cfglobal1top5.png" width="640" /></a></div>Codeforces hosted its Global Round 1 on Thursday (<a href="https://codeforces.com/contest/1110">problems</a>, <a href="https://codeforces.com/contest/1110/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/65079">analysis</a>). tourist and Um_nik were quite close, both finishing the problem-solving part around 1:20 mark and having some challenge fun thereafter. However, in the end the challenges did not affect the standings, and tourist stayed in first place. Congratulations!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-oMTf78iu-1w/XGCR4am9uXI/AAAAAAACPrU/20RU_jaCAeYLxONYeMSo0UhWs7MIYa1uACLcBGAs/s1600/srm750top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="95" data-original-width="636" src="https://4.bp.blogspot.com/-oMTf78iu-1w/XGCR4am9uXI/AAAAAAACPrU/20RU_jaCAeYLxONYeMSo0UhWs7MIYa1uACLcBGAs/s1600/srm750top5.png" /></a></div>TopCoder SRM 750 followed a day later (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=17399">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17399&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-750-editorials/">analysis</a>). This time tourist managed to get a commanding lead thanks to solving the 1000-pointer in just 8 minutes, while rng_58 needed 22 minutes and others even more. Well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-IyNFhiDosPQ/XGCXjrN-E4I/AAAAAAACPrg/n3qLRmcHPsY18ktfKHmDXQjNmlGF1V8_gCLcBGAs/s1600/oc1819gomeltop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="205" data-original-width="753" height="174" src="https://3.bp.blogspot.com/-IyNFhiDosPQ/XGCXjrN-E4I/AAAAAAACPrg/n3qLRmcHPsY18ktfKHmDXQjNmlGF1V8_gCLcBGAs/s640/oc1819gomeltop5.png" width="640" /></a></div>Finally, the Open Cup returned on Sunday with the Grand Prix of Gomel (<a href="http://opentrains.snarknews.info/~ejudge/res/res10451">results</a>, top 5 on the left). This was the first of seven consecutive Open Cup Sundays stretching right up to the ICPC World Finals, and that will provide a good preview as many top-rated ICPC teams are competing. The team from MIT earned the first place with just four minutes remaining, solving two of the hardest problems in the last hour. Amazing performance!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-b2scHcycaNw/XGCj5OYjh_I/AAAAAAACPrs/P89q5tj8Y0gyOHZ3dBlsEXqupfz4V4KKACLcBGAs/s1600/IMG_20190204_081201.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/-b2scHcycaNw/XGCj5OYjh_I/AAAAAAACPrs/P89q5tj8Y0gyOHZ3dBlsEXqupfz4V4KKACLcBGAs/s640/IMG_20190204_081201.jpg" width="640" /></a></div>In <a href="https://petr-mitrichev.blogspot.com/2019/02/a-mumbling-week.html">the previous summary</a>, I have mentioned a TopCoder problem: you are given a 9x47 grid of zeroes and ones. In one step, you can take any cell that contains a one, and another cell that is either in the same row but to the right or in the same column but to the bottom from the first cell, and flip both of them (so one changes to zero, and zero changes to one). You are given the initial and the final state of the grid, and need to produce any (not necessarily the shortest) sequence of operations that transforms one to the other with at most 947 operations.<br /><br />When we apply this operation to a one and a zero, we're effectively moving the one to the bottom or to the right. By applying this operation several times, the one can move to the bottom <i>and</i> to the right. Moreover, the opposite is true: for any position to the bottom and to the right, we can move the one there in exactly two operations. If the cell in the middle (in the same row or column as both source and target cells) contains a zero, then we just move the one twice in a straightforward manner. If the cell in the middle contains a one, then we can first move that one to the target, and then move the one from the source to the middle cell, restoring the one there.<br /><br />Finally, the other option of applying the operation to a one and a one, or moving a one onto a one in two operations as described above, results in both ones disappearing. Now we're in a very nice position: we understand the full structure of the problem, and have described everything that is possible in a very concise manner, which allows to see the solution.<br /><br />More precisely, we need find a "source" one in the initial grid to the left and/or to the top for each one from the final grid, which might also leave some ones in the initial grid unused. Note that if the number of unused ones is odd, there's no solution since all operations preserve parity, and if the number of unused ones is even, we can always get rid of them by moving each to the bottom-right corner in at most two operations.<br /><br />This observation leaves us with a matching problem which can actually be solved greedily because of the special structure of the graph. If we traverse the ones from the final grid in row-major order, we can simply always pick the rightmost yet-unused one in the initial grid to the left and/or to the top from the current position. This can be proven by a typical exchange argument: let's look at the first time in this row-major traversal when the optimal solution uses a different one to cover the final one in the current position, and uses the greedy choice to cover something else. We can swap the assignments of those two ones and still obtain a valid solution.<br /><br />Thanks for reading, and check back next week!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/RjEQewnPVGc" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com2http://petr-mitrichev.blogspot.com/2019/02/a-tourist-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-27624436295978650502019-02-03T22:09:00.000+03:002019-02-03T22:09:02.540+03:00A mumbling 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/-4pOqM2YSz8c/XFcymvpnqiI/AAAAAAACPmg/m8tNmYaxVL8wo1WmR8BbnOv3D-KxQxbvgCLcBGAs/s1600/srm749top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="97" data-original-width="637" src="https://1.bp.blogspot.com/-4pOqM2YSz8c/XFcymvpnqiI/AAAAAAACPmg/m8tNmYaxVL8wo1WmR8BbnOv3D-KxQxbvgCLcBGAs/s1600/srm749top5.png" /></a></div>TopCoder SRM 749 was the main event of this week (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=17398">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17398&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://youtu.be/hqCECmi_AJc">my screencast with mumbling</a>). All three problems were quite tricky, and passing the sample cases did not really mean that much. As he often does, rng_58 excelled in such circumstances and claimed the first place with a sizable margin — congratulations!<br /><br />The only other contestant to solve the hardest problem, pashka, was actually unable to figure out the proper algorithmic solution in time; so he decided to take his chances and treat the problem as a general hamiltonian cycle problem and solve it with a simple but powerful heuristic, <a href="https://petr-mitrichev.blogspot.com/2014/09/this-week-in-competitive-programming_14.html">just like I did in 2014</a>. It seems that participating in IOI 2002 has finally paid off for both of us :)<br /><br /><a href="https://community.topcoder.com/stat?c=problem_statement&pm=15298&rd=17398">The medium problem</a> was quite nice in this round. After removing some unnecessary complications, the statement boiled down to: you are given a 9x47 grid of zeroes and ones. In one step, you can take any cell that contains a one, and another cell that is either in the same row but to the right or in the same column but to the bottom from the first cell, and flip both of them (so one changes to zero, and zero changes to one). You are given the initial and the final state of the grid, and need to produce any (not necessarily the shortest) sequence of operations that transforms one to the other with at most 947 operations.<br /><br />Thanks for reading, and check back next week!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/w7YB5HavwmA" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com2http://petr-mitrichev.blogspot.com/2019/02/a-mumbling-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-28134008761600270852019-01-27T22:38:00.001+03:002019-01-27T23:35:43.802+03:00A Galois 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/-IeVOTbVFI7o/XE4FcJa5yKI/AAAAAAACPeM/HKB9S8DJNB0G1e07NkvQQkWSR7qHb6uoQCLcBGAs/s1600/cf534top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="272" data-original-width="1110" height="156" src="https://4.bp.blogspot.com/-IeVOTbVFI7o/XE4FcJa5yKI/AAAAAAACPeM/HKB9S8DJNB0G1e07NkvQQkWSR7qHb6uoQCLcBGAs/s640/cf534top5.png" width="640" /></a></div>Codeforces returned this week with its Round 534 on Tuesday (<a href="https://codeforces.com/contest/1103">problems</a>, <a href="https://codeforces.com/contest/1103/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/64722">analysis</a>). mnbvmar won not just thanks to being the only contestant to solve the hardest problem E, but also thanks to being much faster than his peers on the first three problems, which might've been the key to unlocking the strategy of solving E instead of D. Well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-vl1HU2OcmfM/XE3yor5U7AI/AAAAAAACPeA/1yUiHq58NicNCAl9nhfNZxQ7EzDopsfCQCLcBGAs/s1600/srm748top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="95" data-original-width="635" src="https://4.bp.blogspot.com/-vl1HU2OcmfM/XE3yor5U7AI/AAAAAAACPeA/1yUiHq58NicNCAl9nhfNZxQ7EzDopsfCQCLcBGAs/s1600/srm748top5.png" /></a></div>TopCoder SRM 748 on Saturday wrapped up the second stage of the race to TCO19 (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=17397">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17397&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://youtu.be/yDrUX0qQIkY">my screencast</a>, <a href="https://www.topcoder.com/blog/single-round-match-748-editorials/">analysis</a>). tourist was the only one able to solve the hard problem, but he also had the fastest time on both the easy and the medium. Congratulations on the very convincing victory!<br /><br /><a href="https://community.topcoder.com/stat?c=problem_statement&pm=15294&rd=17397">The hard problem</a> has introduced me to the concept of <a href="https://www.google.com/search?q=nim+multiplication">nim multiplication</a> which, on one side, allows <a href="https://www.stat.berkeley.edu/~mlugo/stat155-f11/tartan2.pdf">solving products of coin turning games</a>, and on the other side, together with the nim addition — bitwise xor — <a href="https://en.wikipedia.org/wiki/Nimber#Multiplication">induces a finite field</a> of characteristic 2 over the nimbers less than 2<sup>2<sup><i>n</i></sup></sup> for any <i>n</i>. I find this sudden appearance of finite fields exceedingly beautiful :)<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-JhIhJ40jLbg/XE4InRqauoI/AAAAAAACPew/_mBkvuCu1HMg51uZSaaIVmJ7SJ_wd_cXACLcBGAs/s1600/IMG_20190127_083801.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="764" data-original-width="1600" height="304" src="https://2.bp.blogspot.com/-JhIhJ40jLbg/XE4InRqauoI/AAAAAAACPew/_mBkvuCu1HMg51uZSaaIVmJ7SJ_wd_cXACLcBGAs/s640/IMG_20190127_083801.jpg" width="640" /></a></div><a href="https://en.wikipedia.org/wiki/Nimber#Multiplication">The Wikipedia article</a> implies that for computing the nim multiplication, we just need the following two facts:<br /><br /><ol style="text-align: left;"><li>The nim product of a Fermat power of two (numbers of the form 2<sup>2<sup><i>n</i></sup></sup>) with a smaller number is equal to their ordinary product;</li><li>The nim square of a Fermat power of two <i>x</i> is equal to 3<i>x</i>/2 as evaluated under the ordinary multiplication of natural numbers.</li></ol><br />It took me quite some time to understand how to compute the nim multiplication using those facts, but now I think I got it, so I'll try to explain (also, does anybody have a link to where this is explained nicely? I could not find one).<br /><br />First, suppose we know the nim products of powers of two. Then we can use the fact that we have a field to compute all other products by representing the multipliers as xors (nim-sums) of powers of two, for example (where all additions and multiplications are the nim ones): 3*6=(2+1)*(4+2)=2*4+2*2+1*4+1*2=8+3+4+2=8+4+1=13.<br /><br />Now, the above rules allow to multiply Fermat powers of two, but we need to learn to multiply arbitrary powers of two. Here we once again use the binary representation, this time of the exponent, to represent any power of two as a (both nim and ordinary) product of Fermat powers of two, and then rely on associativity of multiplication to rearrange the Fermat powers of two in sorted order. If they're all distinct, then we can go from smallest to largest to learn that their product is equal to their ordinary product according to the first rule above; and if a Fermat power is repeated, then we use the second rule above to effectively decompose the problem into two. If we always apply the second rule to the smallest repeated power, I think we never end up with more than two occurrences of any power in our intermediate computations.<br /><br />Here's an example: 2048*128=(256*4*2)*(16*4*2)=2*2*4*4*16*256=(1+2)*4*4*16*256=4*4*16*256+2*4*4*16*256=(2+4)*16*256+2*(2+4)*16*256=2*16*256+4*16*256+2*2*16*256+2*4*16*256=2*16*256+4*16*256+(1+2)*16*256+2*4*16*256=2*16*256+4*16*256+16*256+2*16*256+2*4*16*256=4*16*256+16*256+2*4*16*256=16384+4096+32768=53248.<br /><br />Those two ideas can be combined to obtain a single algorithm as described in the exercise 4 at the bottom of page 14 in <a href="https://openaccess.leidenuniv.nl/bitstream/handle/1887/2125/346_027.pdf">this article</a> from 1978.<br /><br />Thanks for reading, and check back next week!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/gFG3Nqa8cok" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com0http://petr-mitrichev.blogspot.com/2019/01/a-galois-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-64201223253251889262019-01-20T20:44:00.002+03:002019-01-20T20:46:47.367+03:00An anti-library 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/-YVk0JGOP6q0/XESjc1WFdpI/AAAAAAACPUc/0evKGCYe2FAb4Llxi6JXQXzgtazjtcVQQCLcBGAs/s1600/srm746top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="95" data-original-width="637" src="https://4.bp.blogspot.com/-YVk0JGOP6q0/XESjc1WFdpI/AAAAAAACPUc/0evKGCYe2FAb4Llxi6JXQXzgtazjtcVQQCLcBGAs/s1600/srm746top5.png" /></a></div>TopCoder held two SRMs this week. SRM 746 took place on Tuesday (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=17395">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17395&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://youtu.be/EhkGX648sNI">my screencast</a>, <a href="https://www.topcoder.com/blog/single-round-match-746-editorials/">analysis</a>). Once again the topic of floating-point precision took center stage: 27 solutions were submitted for <a href="https://community.topcoder.com/stat?c=problem_statement&pm=15268&rd=17395">the hard problem</a>, many relying on floating-point and/or ternary search, but only 5 passed, all computing the answer exactly and using either arbitrary-length integers, arbitrary-length floating point, or int128.<br /><br />I've already made this point in the <a href="https://codeforces.com/blog/entry/64554?#comment-485100">Codeforces discussion thread</a>, but let me repeat here: the super high precision requirement had a side effect of essentially penalizing the contestants that had a prewritten 3D geometry library: using the library as-is would fail because of precision issues, and adapting a set of interconnected methods from floating-point to big integers is actually much more time-consuming than figuring out the relatively simple required computation from scratch and implementing it. Looking at the five accepted solutions, four or maybe all five seem to be written from scratch.<br /><br />This has also provided for an unusual challenge phase, with 9 out of 26 successful challenges coming on the hardest problem. In most cases ending up in room 1 is a bad sign for the challenge phase (I believe the rooms are sorted by decreasing average rating, or something like that), but here it was exactly the opposite :)<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-IY1WsuVDDlk/XESljMRpW9I/AAAAAAACPUo/b3Kz5-si1bQ_4R6XjAt7zahBfC0mA8qEwCLcBGAs/s1600/srm747top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="98" data-original-width="638" src="https://3.bp.blogspot.com/-IY1WsuVDDlk/XESljMRpW9I/AAAAAAACPUo/b3Kz5-si1bQ_4R6XjAt7zahBfC0mA8qEwCLcBGAs/s1600/srm747top5.png" /></a></div>SRM 747 followed on Saturday (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=17396">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17396&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://youtu.be/EUP-kY-sZ18">my screencast</a>). The relatively standard medium and hard meant that the first place was decided during the challenge phase, and <a href="https://community.topcoder.com/stat?c=problem_statement&pm=15286&rd=17396">the easy problem</a> seemed to have been designed specifically to make the challenge phase more interesting: it was a constructive problem with such loose requirements that a lot of solutions worked, and even more solutions passed the sample cases. In fact, one could almost say that it was possible to pass the samples by accident :) However, challenging those solutions was also not trivial, as they might pass a challenge case by accident just as well.<br /><br />Thanks for reading, and check back next week!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/m6KswF-iV04" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com0http://petr-mitrichev.blogspot.com/2019/01/an-anti-library-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-67000391570987264442019-01-13T12:32:00.000+03:002019-01-13T12:32:06.861+03:00A Dilworth 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/-eSpx-iDJ4l8/XDsFL_ic9CI/AAAAAAACPFI/TNMkeAhj0DMkyPCuxizKtESJhajkZIg2gCLcBGAs/s1600/IMG_20181228_140312.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://2.bp.blogspot.com/-eSpx-iDJ4l8/XDsFL_ic9CI/AAAAAAACPFI/TNMkeAhj0DMkyPCuxizKtESJhajkZIg2gCLcBGAs/s640/IMG_20181228_140312.jpg" width="640" /></a></div>This week was light on contests, so let me talk about the Codeforces problems I've mentioned in <a href="https://petr-mitrichev.blogspot.com/2019/01/a-radewoosh-week.html">last week's summary</a>. The <a href="https://codeforces.com/contest/1097/problem/E">first one</a> was: you are given a permutation of size <i>n</i> <= 100000, and you need to split it into subsequences such that each subsequence is either monotonically decreasing or monotonically increasing. The number of subsequences needs to be small, but does not need to be minimal. More precisely, your solution should have the optimal <i>worst</i> case performance for any given <i>n</i>: the number of subsequences should not exceed the maximum number of subsequences necessary for any permutation of size <i>n</i>.<br /><br />One fact that definitely looks helpful is the <a href="https://en.wikipedia.org/wiki/Dilworth%27s_theorem">Dilworth's theorem</a>: it tells us that we either have a long increasing subsequence, or can split our sequence into few decreasing subsequences. More formally, let's define f(<i>n</i>) to be the maximum number of subsequences our solution produces for any permutation of size <i>n</i>. Applying the Dilworth's theorem allows to build a solution with the following recurrence on f():<br /><br />f(<i>n</i>)=max<sub><i>k</i></sub>(min(<i>k</i>,1+f(<i>n</i>-<i>k</i>))<br /><br />where the inner minimum corresponds to the fact that we can either split everything into <i>k</i> decreasing subsequences, or remove an increasing subsequence of length <i>k</i> and apply our solution recursively.<br /><br />Printing a few first values of f(<i>n</i>) computed the recurrence above, we get:<br /><br /><span style="font-family: Courier New, Courier, monospace;">f(1) = 1</span><br /><span style="font-family: Courier New, Courier, monospace;">f(2) = 1</span><br /><span style="font-family: Courier New, Courier, monospace;">f(3) = 2</span><br /><span style="font-family: Courier New, Courier, monospace;">f(4) = 2</span><br /><span style="font-family: Courier New, Courier, monospace;">f(5) = 2</span><br /><span style="font-family: Courier New, Courier, monospace;">f(6) = 3</span><br /><span style="font-family: Courier New, Courier, monospace;">f(7) = 3</span><br /><span style="font-family: Courier New, Courier, monospace;">f(8) = 3</span><br /><span style="font-family: Courier New, Courier, monospace;">f(9) = 3</span><br /><span style="font-family: Courier New, Courier, monospace;">f(10) = 4</span><br /><span style="font-family: Courier New, Courier, monospace;">f(11) = 4</span><br /><span style="font-family: Courier New, Courier, monospace;">f(12) = 4</span><br /><span style="font-family: Courier New, Courier, monospace;">f(13) = 4</span><br /><span style="font-family: Courier New, Courier, monospace;">f(14) = 4</span><br /><span style="font-family: Courier New, Courier, monospace;">f(15) = 5</span><br /><span style="font-family: Courier New, Courier, monospace;">f(16) = 5</span><br /><div><span style="font-family: Courier New, Courier, monospace;">...</span></div><div><br /></div><div>Here we can notice that the smallest value of n such that f(<i>n</i>)=<i>k</i> is the <i>k</i>-th triangular number: 1+2+...+<i>k</i>=<i>k</i>*(<i>k</i>+1)/2. Having noticed it, it's relatively easy to prove it by induction.</div><div><br /></div><div>So we have a solution using Dilworth's theorem, but is it good enough for the problem? Does it have the same worst case performance as the best possible solution for any given <i>n</i>?</div><div><br /></div><div>The answer is yes, and the triangular numbers together with the recurrence above give us a hint how to see it. We need to come up with some permutation of size 1+2+...+<i>k</i> for which we can prove that it can't be split into less than k increasing or decreasing subsequences. </div><div><br /></div><div>Here is one such sequence for k=5: <span style="font-family: Courier New, Courier, monospace;">1, 3, 2, 6, 5, 4, 10, 9, 8, 7, 15, 14, 13, 12, 11.</span> In other words, we take a decreasing segment of length 1, then append a decreasing segment of length 2 with all numbers bigger than the previous segment, then append a decreasing segment of length 3 with all numbers bigger than the previous segment, and so on until a segment of length <i>k</i>. Consider any split of this sequence into increasing and decreasing subsequences. Suppose it has <i>x</i> increasing subsequences. Each increasing subsequence covers at most one element of each decreasing segment, so for <i>k</i>-<i>x</i> segments with more than <i>x</i> elements at least one number will be left uncovered. But a decreasing subsequence can't have numbers from two different segments, so we will need at least <i>k</i>-<i>x</i> decreasing subsequences to cover the rest, and the total will be at least <i>k</i>.</div><div><br /></div><div>This proves that our solution does in fact have the optimal worst case performance for any given <i>n</i>. One small thing that the Wikipedia article doesn't give is a constructive way to apply the theorem: finding the longest increasing subsequence is a well-known algorithm, but how do we actually split the sequence into as many decreasing subsequences quickly? Some quick googling helped me find the answer during the contest: in the longest increasing subsequence algorithm, let's call the length of the longest increasing subsequence ending in each element the <i>level</i> of this element. It turns out that the elements of the same level always form a non-increasing (and since we have a permutation, decreasing) subsequence, as otherwise the element to the right would have a higher level, so we just split by level.</div><div><br /></div><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-DFZgQfcKARg/XDsFTr1H_TI/AAAAAAACPFM/Kuv6nr3g-Hk5HgGCP3LyVBMDZ0bsRDgOQCLcBGAs/s1600/IMG_20181228_161345_1.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/-DFZgQfcKARg/XDsFTr1H_TI/AAAAAAACPFM/Kuv6nr3g-Hk5HgGCP3LyVBMDZ0bsRDgOQCLcBGAs/s640/IMG_20181228_161345_1.jpg" width="640" /></a></div><div>The <a href="https://codeforces.com/contest/1098/problem/B">second problem</a> I mentioned <a href="https://petr-mitrichev.blogspot.com/2019/01/a-radewoosh-week.html?showComment=1546934865319#c6990024409469331025">turned out</a> to be <a href="https://community.topcoder.com/stat?c=problem_statement&pm=10758&rd=14154">a repeat</a> from 9 years ago: you are given a <i>n</i>x<i>m</i> matrix such that <i>n</i>*<i>m</i><=300000, with one character from the set A, C, G or T in each cell. You need to change as few characters as possible (to other characters from the set) in such a way that each 2x2 submatrix has all four different characters.</div><div><br /></div><div>Given that there are consequently <a href="https://apps.topcoder.com/wiki/display/tc/SRM+472">two</a> <a href="https://codeforces.com/blog/entry/64331">editorials</a> for it, I don't think I can add much :)</div><div><br /></div><div>Thanks for reading, and check back next week!</div></div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/uMrikDCpYkE" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com2http://petr-mitrichev.blogspot.com/2019/01/a-dilworth-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-42243977595853498372019-01-06T15:05:00.001+03:002019-01-06T15:25:45.160+03:00A Radewoosh 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/-3HPkNxoDxss/XDHeZtQm1LI/AAAAAAACOqQ/hkUSRigQEls69pqG8mX8-CRbqHhmSDNJgCLcBGAs/s1600/cfhello2019top5.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://2.bp.blogspot.com/-3HPkNxoDxss/XDHeZtQm1LI/AAAAAAACOqQ/hkUSRigQEls69pqG8mX8-CRbqHhmSDNJgCLcBGAs/s640/cfhello2019top5.png" width="640" /></a></div>Codeforces did not take any breaks, and held two contests in the first week of 2019. The first one was appropriately named "Hello 2019" (<a href="https://codeforces.com/contest/1097">problems</a>, <a href="https://codeforces.com/contest/1097/standings">results</a>, top 5 on the left, <a href="https://youtu.be/UxtEMlc0sHM">my screencast</a>, <a href="https://codeforces.com/blog/entry/64310">analysis</a>). V--o_o--V took a gamble and started with problem G which looks doable on the surface but takes quite a lot of time to get right. This was not optimal in terms of the number of points, but it or the five incorrect attempts did not matter in the end as nobody else was able to solve all problems. Congratulations to V--o_o--V!<br /><br />I was actually quite close to getting all problems, as I've fixed the last bug in my solution for H just 30 seconds after the end of the contest (you can still see it on the screencast). And given the unexpectedly low point total of V--o_o--V, that would be enough for the first place :)<br /><br /><a href="https://codeforces.com/contest/1097/problem/E">Problem E</a> mostly relied on a well-known theorem, but had an interesting twist on top of it: you are given a permutation of size <i>n</i> <= 100000, and you need to split it into subsequences such that each subsequence is either monotonically decreasing or monotonically increasing. The number of subsequences needs to be small, but does not need to be minimal. More precisely, your solution should have the optimal <i>worst</i> case performance for any given <i>n</i>: the number of subsequences should not exceed the maximum number of subsequences necessary for any permutation of size <i>n</i>.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-hEzDShxtoN4/XDHenAcU7XI/AAAAAAACOqY/sy4XYO_1-H8z0F_WbI6M4SB4Z_EbbUvKACLcBGAs/s1600/cf530top5.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://4.bp.blogspot.com/-hEzDShxtoN4/XDHenAcU7XI/AAAAAAACOqY/sy4XYO_1-H8z0F_WbI6M4SB4Z_EbbUvKACLcBGAs/s640/cf530top5.png" width="640" /></a></div>Codeforces Round 530 took place one day later (<a href="https://codeforces.com/contest/1098">problems</a>, <a href="https://codeforces.com/contest/1098/standings">results</a>, top 5 on the left, <a href="https://youtu.be/WR9rMvE-d9Y">my screencast</a>, <a href="https://codeforces.com/blog/entry/64331">analysis</a> so far partially in Russian). Problem E required a lot of careful implementation, and the speed of that implementation was the deciding factor in the standings. Of the four contestants finishing before the round ended, Radewoosh was the fastest. Well done!<br /><br />I found <a href="https://codeforces.com/contest/1098/problem/B">problem B</a> quite cute: you are given a <i>n</i>x<i>m</i> matrix such that <i>n</i>*<i>m</i><=300000, with one character from the set A, C, G or T in each cell. You need to change as few characters as possible (to other characters from the set) in such a way that each 2x2 submatrix has all four different characters. Can you see a way?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-6BCIFxIkf3Y/XDHs1rBr_RI/AAAAAAACOqw/k1OIIGuaN4k1pLFv2P7Cm4WtFWGqcLq6gCKgBGAs/s1600/IMG_20190106_125541.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1600" data-original-width="1507" height="400" src="https://4.bp.blogspot.com/-6BCIFxIkf3Y/XDHs1rBr_RI/AAAAAAACOqw/k1OIIGuaN4k1pLFv2P7Cm4WtFWGqcLq6gCKgBGAs/s400/IMG_20190106_125541.jpg" width="376" /></a></div>In <a href="https://petr-mitrichev.blogspot.com/2018/12/a-probably-prime-week.html">my previous summary</a>, I've mentioned a couple of problems. The <a href="https://atcoder.jp/contests/agc030/tasks/agc030_c">first one</a> came from AtCoder: you are given a number <i>k</i> which is at most 1000. You need to come up with any <i>n</i>x<i>n</i> toroidal grid (the first row is adjacent to the last row, and the first column is adjacent to the last column), where you choose the number <i>n</i> but it must be at most 500, such that each cell of the grid is colored with one of the <i>k</i> colors, each color is used at least once, and for all pairs of colors <i>i</i> and <i>j</i> all cells with color <i>i</i> must have the same number of neighbors with color <i>j</i>.<br /><br />During the round, I could only come up with approaches that produce a number of colors that is either smaller than <i>n</i>, or divisible by <i>n</i>. At some point I had an idea to write a backtracking solution that would find me any solution that does not have these properties, hoping that would help come up with its generalization. In retrospect, that might have done it, as the following approach (which seems to be the only one that works) does look recognizable from one example: let's pick an even <i>n</i>, and split the grid into <i>n</i> (toroidal) diagonals. For each diagonal, we either color it with one color, or with two alternating colors, thus making it possible to get any number of colors between <i>n</i> and 2<i>n</i>. Since each element of a diagonal has exactly two neighbors from each neighboring diagonal, the required properties hold.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-DWcam0BOwfA/XDHvAdvW6nI/AAAAAAACOrg/h0mBbc22z6sQB9kHjL4tSiIJEEglBfOKgCLcBGAs/s1600/IMG_20190101_125903.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/-DWcam0BOwfA/XDHvAdvW6nI/AAAAAAACOrg/h0mBbc22z6sQB9kHjL4tSiIJEEglBfOKgCLcBGAs/s640/IMG_20190101_125903.jpg" width="640" /></a></div>The <a href="https://codeforces.com/contest/1091/problem/H">other problem</a> came from Codeforces. I've cited a simplified version of the statement: there is a pile with <i>n</i><=200000 stones, and two players are playing <a href="https://en.wikipedia.org/wiki/Nim">Nim</a> with a fixed set of possible moves <i>a</i><sub>1</sub>, <i>a</i><sub>2</sub>, ..., <i>a<sub>k</sub></i>: in each turn a player can take a number of stones that is equal to one of the <i>a<sub>i</sub></i>, and the player who can't make a move loses. Your goal is to find the <a href="https://en.wikipedia.org/wiki/Nimber">nimbers</a> for all values of <i>n</i> between 1 and 200000.<br /><br />I have forgot to mention one important additional property in this simplification: that the nimbers are guaranteed to be not too big (below 100), which is actually important for the solution below to be fast — sorry for that!<br /><br />Let's put all possible moves in one bitmask <i>m</i>, and also store a bitmask for each nimber value that represents which pile sizes have a move <i>to</i> a position with that nimber value. Those bitmasks start as empty. In order to determine the nimber for the next pile size, we go through those bitmasks until we find one that has a zero in the corresponding position. Then we need to update the bitmasks for higher pile sizes, and the key trick is that we only need to update one of them: the one corresponding to the newly determined nimber, and the update is simply applying bitwise or with the move bitmask <i>m</i> shifted left by the current pile size. This means that the solution runs in O(<i>n</i><sup>2</sup>/64+<i>n</i>*<i>max_nimber</i>) (I know, this is not a perfect use of the O-notation, but I hope you understand what I mean), which is fast enough.<br /><br />Thanks for reading, and check back next week!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/Q3Aw02QtiOU" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com8http://petr-mitrichev.blogspot.com/2019/01/a-radewoosh-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-51213542330639783992019-01-06T12:47:00.001+03:002019-01-06T12:47:16.042+03:00And the best problem of 2018 is...<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/-nRrE3L_gjjs/XDHOdw3o0YI/AAAAAAACOp8/B5XrWNHdioIYal9qDMKEhL17KZw9N8WhwCLcBGAs/s1600/IMG_20181208_153315%2B%25281%2529.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="984" data-original-width="1600" height="392" src="https://1.bp.blogspot.com/-nRrE3L_gjjs/XDHOdw3o0YI/AAAAAAACOp8/B5XrWNHdioIYal9qDMKEhL17KZw9N8WhwCLcBGAs/s640/IMG_20181208_153315%2B%25281%2529.jpg" width="640" /></a></div>According to <a href="https://petr-mitrichev.blogspot.com/2019/01/best-problems-of-2018.html">the vote</a>, the best problem of 2018 is <a href="https://drive.google.com/file/d/1yv_d9MYT5oeR8woWUdBs1N5GQa9Q8Aa2/view?usp=sharing">the Open Cup problem</a> about rolling a ball in a maze while collecting all targets in some order, by <a href="https://codeforces.com/profile/jh05013">jh05013</a>, with solution in <a href="https://petr-mitrichev.blogspot.com/2018/12/a-rolling-week.html">this post</a>. My vote also went to this problem.<br /><br />Here's its statement in an abridged form once again: you are given a 50x50 grid where some cells are empty, and some are walls. There are also walls surrounding the grid. Some empty cells are marked as targets, and there's also a ball in one of the empty cells. You can move the ball in each of the four cardinal directions, but once it starts rolling, it rolls in the same direction until it hits the wall, at which point you can pick a new direction, and so on. Can you roll the ball in such a way that it passes through all targets in some order?<br /><br />Congratulations to jh05013, to the Open Cup, and thanks to all problemsetters of 2018!<br /><br />More precisely, since there were only 91 people voting, I'd say we're about 60% confident that the best problem of 2018 is that one :) Here's <a href="https://colab.research.google.com/drive/1suQATpo3_5uYaJIoegttp7qjVYbWKLgm#scrollTo=iHt6M8jUeAMz">the Colab</a> where I try estimate that confidence. Of course that number is meaningless without explaining the assumed underlying model yada yada, but I hope it's good enough for a ballpark estimate. If people who actually, unlike myself, understand how statistics and polling work are reading this: is that a good way to get confidence numbers for a poll? What is a better way?<br /><br />Thanks for reading, and check back later today for this week's summary!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/_hZ3d8PemJA" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com6http://petr-mitrichev.blogspot.com/2019/01/and-best-problem-of-2018-is.htmltag:blogger.com,1999:blog-1953325079793449971.post-10932030889071531572019-01-02T12:22:00.000+03:002019-01-02T12:22:15.318+03:00Best problems of 2018<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/-MRTazCifeqU/XCyCcOIFnZI/AAAAAAACOe4/4f_ZvaG3ZQAXvcQzt7S_gKFNuzd4QDN2QCLcBGAs/s1600/IMG_20180623_122919.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="300" src="https://1.bp.blogspot.com/-MRTazCifeqU/XCyCcOIFnZI/AAAAAAACOe4/4f_ZvaG3ZQAXvcQzt7S_gKFNuzd4QDN2QCLcBGAs/s400/IMG_20180623_122919.jpg" width="400" /></a></div>Just like <a href="https://petr-mitrichev.blogspot.com/2017/12/best-problems-of-2017.html">last year</a>, I have reviewed the problems I've highlighted in this blog, and have picked the shortlist of five problems that I think were the best in 2018 (in chronological order):<br /><ul style="text-align: left;"><li><a href="https://agc023.contest.atcoder.jp/tasks/agc023_f">The AtCoder problem</a> about traversing the vertices of a 0/1-labeled tree minimizing the number of inversions, by <a href="https://codeforces.com/profile/maroonrk">maroonrk</a>, with solution in <a href="https://petr-mitrichev.blogspot.com/2018/05/a-prefix-xor-week.html">this post</a>.</li><li><a href="https://codeforces.com/contest/925/problem/C">The Codeforces problem</a> about rearranging an array in such a way that prefix xors are increasing, by <a href="https://codeforces.com/profile/Endagorion">Endagorion</a>, with solution in <a href="https://petr-mitrichev.blogspot.com/2018/05/a-prefix-xor-week.html">the same post</a>. </li><li><a href="https://agc026.contest.atcoder.jp/tasks/agc026_f">The AtCoder problem</a> about two players taking numbers from an array, where one must take adjacent number when available, by <a href="https://codeforces.com/profile/sugim48">sugim48</a>, with solution in <a href="https://petr-mitrichev.blogspot.com/2018/10/a-decision-tree-week.html">this post</a>.</li><li><a href="https://drive.google.com/file/d/1yv_d9MYT5oeR8woWUdBs1N5GQa9Q8Aa2/view?usp=sharing">The Open Cup problem</a> about rolling a ball in a maze while collecting all targets in some order, by <a href="https://codeforces.com/profile/jh05013">jh05013</a>, with solution in <a href="https://petr-mitrichev.blogspot.com/2018/12/a-rolling-week.html">this post</a>.</li><li><a href="https://community.topcoder.com/stat?c=problem_statement&pm=15159&rd=17348">The TopCoder problem</a> about creating a figure with exactly <i>n</i> domino tilings, by <a href="https://codeforces.com/profile/Alex_2oo8">Alex_2oo8</a>, with solution in <a href="https://petr-mitrichev.blogspot.com/2018/12/a-center-week.html">this post</a>.</li></ul>Which one do you think is the very best?<br /><div><br /></div><div><iframe frameborder="0" height="633" marginheight="0" marginwidth="0" src="https://docs.google.com/forms/d/e/1FAIpQLSc30po_IP9DVeBhse-yMQygb2h6Kil-PFdE_6Rx8K9Y6RItUg/viewform?embedded=true" width="640">Загрузка...</iframe></div><div><br /></div><div>There are other <a href="https://codeforces.com/blog/entry/64025">discussions</a> and <a href="https://codeforces.com/blog/entry/64186">votes</a> about the best problem of 2018, check those out :) In that second <a href="https://codeforces.com/blog/entry/64186">post</a>, snarknews is also announcing the Prime New Year contest, which consists of problems given at top-level team competitions in 2018 but not solved by anybody there. If you like real challenge and don't have much to do during the holidays, here's your <a href="https://contest.yandex.com/newyear2019/contest/11451/enter/">link</a>.<br /><div><div><br /></div><div>Happy New Year!</div></div></div></div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/B5mcLjbe0ic" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com0http://petr-mitrichev.blogspot.com/2019/01/best-problems-of-2018.htmltag:blogger.com,1999:blog-1953325079793449971.post-47373985870342108032018-12-30T21:39:00.000+03:002018-12-30T23:06:04.136+03:00A probably prime 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/-PRzEqN_F8tc/XCfPCg0xViI/AAAAAAACN3M/jkygrryL-8E70ZzaAPqv8fI3qQ8GZGWkgCLcBGAs/s1600/srm745top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="96" data-original-width="1057" height="58" src="https://2.bp.blogspot.com/-PRzEqN_F8tc/XCfPCg0xViI/AAAAAAACN3M/jkygrryL-8E70ZzaAPqv8fI3qQ8GZGWkgCLcBGAs/s640/srm745top5.png" width="640" /></a></div>This week had one contest from each of the major platforms to wrap up 2018. First off, TopCoder held an experimental SRM 745 on Friday (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=17392">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17392&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/64080?#comment-479298">analysis</a>). I did not participate myself, but I'd guess that solving 6 problems in 75 minutes felt a bit like <a href="http://snss2018.snarknews.info/">SnarkNews Winter/Summer Series</a>. The change of format did not stop Stonefeang from continuing his string of excellent results and winning this round. Well done!<br /><div><br /></div><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-mEQ5J96rC80/XCfRGTPWR5I/AAAAAAACN3Y/WPMzfxrZS-M2I_0XGdKWy9gUR9VbevifACLcBGAs/s1600/agc030top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="352" data-original-width="835" height="268" src="https://1.bp.blogspot.com/-mEQ5J96rC80/XCfRGTPWR5I/AAAAAAACN3Y/WPMzfxrZS-M2I_0XGdKWy9gUR9VbevifACLcBGAs/s640/agc030top5.png" width="640" /></a></div><div>AtCoder held its last contest of the year (and thus the last contest included in the onsite finals selection) on Saturday, the Grand Contest 030 (<a href="https://atcoder.jp/contests/agc030/tasks">problems</a>, <a href="https://atcoder.jp/contests/agc030/standings">results</a>, top 5 on the left, <a href="https://youtu.be/qRsyaYBmFeM">my screencast</a>, <a href="https://img.atcoder.jp/agc030/editorial.pdf">analysis</a>, <a href="https://docs.google.com/spreadsheets/d/1T-hKu_vIh8l4EiW6XTWOvP0evzsWj0f45JNNgou21Cc/edit#gid=695896678">onsite finals selection standings</a>, top 8 below on the right). Reading all problems really paid off in this round, as different contestants found different problems the hardest. For me problems B and C were the most difficult — in fact, I could not come up with a solution for any of them. It seems that the top two contestants cospleermusora and tourist had a similar story with problem C, but since it was worth less than problems E and F they ended up on top of the contestants with a different set of 5 problems solved. Congratulations to cospleermusora on the win!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-9_nur10wQJ4/XCfTnNGvq6I/AAAAAAACN3k/iBS0SmFd6aMjrKtLb2jZMy1_QDTYkYfjgCLcBGAs/s1600/atcoder2018top8.png" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" data-original-height="234" data-original-width="1338" height="110" src="https://2.bp.blogspot.com/-9_nur10wQJ4/XCfTnNGvq6I/AAAAAAACN3k/iBS0SmFd6aMjrKtLb2jZMy1_QDTYkYfjgCLcBGAs/s640/atcoder2018top8.png" width="640" /></a></div>Here is that <a href="https://atcoder.jp/contests/agc030/tasks/agc030_c">problem C</a> that was obvious for some and impossible to get for others: you are given a number <i>k</i> which is at most 1000. You need to come up with any <i>n</i>x<i>n</i> toroidal grid (the first row is adjacent to the last row, and the first column is adjacent to the last column), where you choose the number <i>n</i> but it must be at most 500, such that each cell of the grid is colored with one of the <i>k</i> colors, each color is used at least once, and for all pairs of colors <i>i</i> and <i>j</i> all cells with color <i>i</i> must have the same number of neighbors with color <i>j</i>. Can you see a way?<br /><br /><div class="separator" style="clear: both; text-align: center;"></div><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-hR9C-Wvdbt8/XCklIpDLAvI/AAAAAAACN9c/bLDihKFcyM8mmH3l9vMCfW4OsiLFEH79QCLcBGAs/s1600/cfgoodbye2018top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="273" data-original-width="1111" height="156" src="https://1.bp.blogspot.com/-hR9C-Wvdbt8/XCklIpDLAvI/AAAAAAACN9c/bLDihKFcyM8mmH3l9vMCfW4OsiLFEH79QCLcBGAs/s640/cfgoodbye2018top5.png" width="640" /></a></div>Codeforces held the Good Bye 2018 round on Sunday (<a href="https://codeforces.com/contest/1091">problems</a>, <a href="https://codeforces.com/contest/1091/standings">results</a>, top 5 on the left, <a href="https://youtu.be/KasLE9vzLaY">my screencast</a>, <a href="https://codeforces.com/blog/entry/64196">analysis</a>). tourist had one more great performance, going through the problems in order and finishing all of them more than 30 minutes faster than the only other contestant to solve everything, MakeRussiaGreatAgain. Congratulations to both!<br /><br />My round was going pretty well right up to the point when I <a href="https://crypto.stackexchange.com/questions/34061/factoring-large-n-given-oracle-to-find-square-roots-modulo-n">googled</a> the main idea of the solution for problem G, but then made a bug in the implementation (I forgot that the square roots are always returned modulo n, and not modulo the "remaining" number that I still need to factorize), and instead of looking for it I assumed there's a problem with BigInteger.isProbablePrime in Codeforces and tried to work around it for quite some time. I've found <a href="https://codeforces.com/blog/entry/14877">this post</a> with no answers and the post linked from it, and the fact that some of my submissions were getting "Denial of judgement" strongly supported the isProbablePrime failure theory.<br /><br /><a href="https://codeforces.com/contest/1091/problem/H">Problem H</a> had a pretty convoluted statement which boiled down to: there is a pile with <i>n</i><=200000 stones, and two players are playing <a href="https://en.wikipedia.org/wiki/Nim">Nim</a> with a fixed set of possible moves <i>a</i><sub>1</sub>, <i>a</i><sub>2</sub>, ..., <i>a<sub>k</sub></i>: in each turn a player can take a number of stones that is equal to one of the <i>a<sub>i</sub></i>, and the player who can't make a move loses. Your goal is to find the <a href="https://en.wikipedia.org/wiki/Nimber">nimbers</a> for all values of <i>n</i> between 1 and 200000.<br /><br />I've tried to solve this problem at the end of the contest, but my mental state after fighting with G for an hour was not ideal :) I realized that I needed to speed up the standard quadratic approach 64 times using bitsets, but could not find a good way to do that. Can you see a way?<br /><br />Thanks for reading, and check back [hopefully] tomorrow for my take on the best problems of 2018!</div></div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/XbGcdcPTNZU" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com0http://petr-mitrichev.blogspot.com/2018/12/a-probably-prime-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-72676656813418977902018-12-29T22:39:00.002+03:002018-12-29T22:39:53.485+03:00A wave 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/-9JUVjIDeiYg/XCe6tIvXYOI/AAAAAAACN10/Dfeq3n2XIOAI4ErFeoIph_m1RRT5zEjCgCLcBGAs/s1600/oc1819xiantop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="195" data-original-width="813" height="152" src="https://1.bp.blogspot.com/-9JUVjIDeiYg/XCe6tIvXYOI/AAAAAAACN10/Dfeq3n2XIOAI4ErFeoIph_m1RRT5zEjCgCLcBGAs/s640/oc1819xiantop5.png" width="640" /></a></div>The Dec 17 - Dec 23 week contained a surprise extra Open Cup round: Open Cup 2018-19 Grand Prix of Xi'An (<a href="http://opencup.ru/index.cgi?data=macros/stage&head=index&menu=index&stg=10&region=main&ncup=ocj&class=ocj">results</a>, top 5 on the left, <a href="http://acm.nwpu.edu.cn/Scoreboard.htm">official round results</a>, <a href="http://opencup.ru/index.cgi?data=macros/results&menu=index&head=index&ncup=ocj&class=ocj&region=main">overall Open Cup standings so far</a>). The Moscow SU team solved three problems in the last hour, including problem A which was solved by only three teams out of 150 attempts, and ended up winning by a problem. Congratulations on the great performance!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-PRuSj_3dLr4/XCe_CtHFPZI/AAAAAAACN2A/SFazE9oXDgwPed_tF0Uskh_o74YtvnYEgCLcBGAs/s1600/cf528top5.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://1.bp.blogspot.com/-PRuSj_3dLr4/XCe_CtHFPZI/AAAAAAACN2A/SFazE9oXDgwPed_tF0Uskh_o74YtvnYEgCLcBGAs/s640/cf528top5.png" width="640" /></a></div>Codeforces Round 528 followed on Sunday evening (<a href="https://codeforces.com/contest/1086">problems</a>, <a href="https://codeforces.com/contest/1086/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/64078">analysis</a>). It was mnbvmar's turn to be the only contestant to solve the hardest problem F, and thus win with a huge margin. Congratulations on the victory!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-rzeBtqESbNQ/XCfMbgUupGI/AAAAAAACN2c/FcWIb6c2DmIbsbCeCq-0XiBi-67A4F3SwCKgBGAs/s1600/IMG_20181229_203412.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1033" data-original-width="1019" height="400" src="https://2.bp.blogspot.com/-rzeBtqESbNQ/XCfMbgUupGI/AAAAAAACN2c/FcWIb6c2DmIbsbCeCq-0XiBi-67A4F3SwCKgBGAs/s400/IMG_20181229_203412.jpg" width="393" /></a></div>In <a href="https://petr-mitrichev.blogspot.com/2018/12/a-kuhns-week.html">my previous summary</a>, I have mentioned several problems. <a href="https://community.topcoder.com/stat?c=problem_statement&pm=14587&rd=17373">The first one</a> came from TopCoder: you are given a rooted tree with 100000 vertices. Each vertex has a demand <i>d<sub>i</sub></i> and a cost <i>c<sub>i</sub></i>. Your goal is to assign some non-negative value <i>v<sub>i</sub></i> to each vertex so that the demand of each vertex is less than or equal to the sum of values on the path from this vertex to the root of the tree, and the sum of <i>c<sub>i</sub></i>*<i>v<sub>i</sub></i> is minimized.<br /><br />Let's look at the top-most vertices with non-zero value in the solution (such that all their parents and ancestors have zero value). Those vertices are not parents of one another, and thus they satisfy exactly one unit of demand of themselves and their descendants. If we now reduce their value by 1 and repeat, we can split into our solution into "waves" each wave satisfying one unit of demand in all remaining vertices with non-zero demand.<br /><br />We can also notice that each wave can be constructed as follows: first, start with a wave that contains only the root vertex. Then repeatedly do the following: take any vertex with zero demand that is in the wave, remove it from the wave but add all its children. Each such operation changes the cost of the wave by the sum of costs of the children minus the cost of the removed vertex. Let's call this value the <i>delta</i> of the removed vertex.<br /><br />Now we'll build the waves one by one while always maintaining the minimum cost wave. Initially such wave is just a root vertex. As soon as the number of waves we've built reaches the demand of a vertex, this vertex becomes available for replacement, which would change the weight of the wave by its delta. If the delta is positive, we don't need to do anything. If the delta is negative, and the vertex is in the minimum cost wave, then we need to do the replacement. If the delta is negative but the vertex is not yet in the minimum cost wave, we will need to do its replacement as soon as it gets into the wave, in other word we should add its delta to the delta of its parent. If the delta of the parent becomes negative, then we propagate it to its parent, and so on, so that at every moment we have only the optimal wave plus some non-negative deltas remaining.<br /><br />In order for this to run fast, we need to directly propagate to the closest non-zero ancestor instead of going through all parents in the chain to it, which can be accomplished by keeping a disjoint-set union data structure where each set has a vertex with non-zero delta as its representative, and contains all vertices with zero deltas which have it as the closest non-zero ancestor.<br /><br />This was quite tricky to come up with, but the implementation was rather simple and without any corner cases or data structures more complex than disjoint-set union.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-PJXyeUg79dw/XCfMfi9ffdI/AAAAAAACN2g/tiAdyiBwaR4QNuJmp-y1pWtBvLbKyvxpACKgBGAs/s1600/IMG_20181229_203406.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="818" data-original-width="941" height="347" src="https://3.bp.blogspot.com/-PJXyeUg79dw/XCfMfi9ffdI/AAAAAAACN2g/tiAdyiBwaR4QNuJmp-y1pWtBvLbKyvxpACKgBGAs/s400/IMG_20181229_203406.jpg" width="400" /></a></div><a href="https://atcoder.jp/contests/agc029/tasks/agc029_f">The second problem</a> I mentioned came from AtCoder: you are given <i>n</i> vertices, and <i>n</i>-1 sets of those vertices, each of size at least 2. Your goal is to pick exactly two vertices in each of the <i>n</i>-1 sets in such a way that if we draw the <i>n</i>-1 edges connecting each chosen pair to each other, we get a tree. <i>n</i> is at most 100000, and the total size of the given sets is at most 200000.<br /><br />The first step is to think when is this actually impossible. The sample cases provided a helpful example: there was a case where there were two vertices that belonged to just one set, and moreover to the same set. Since only one edge will come out of this set, we will not be able to connect both of those vertices to the rest of the graph.<br /><br />This obstacle can be generalized as follows: if there's a set of vertices of size <i>k</i> which is less than <i>n</i> such that the number of input sets containing at least one of those vertices is less than <i>k</i>, there's no solution.<br /><br />But wait, we <a href="https://en.wikipedia.org/wiki/Hall%27s_marriage_theorem#Graph_theoretic_formulation">have seen</a> such obstacles before! Consider the bipartite graph where the left part is the input vertices and the right part is the input sets, with edges connecting each set with its members. If there's no obstacle as described above, then by Hall's theorem in this graph there's a matching covering any (<i>n</i>-1)-element subset of the left part.<br /><br />Let's find any such matching, it covers some (<i>n</i>-1)-element subset of vertices. The fact that all other (<i>n</i>-1)-element subsets can also be covered by a matching means that if we run one more step of the maximum matching algorithm, it must find augmenting paths from the only remaining uncovered vertex to all covered vertices (so that flipping this augmenting path would result in the solution for the corresponding (<i>n</i>-1)-element subset). These augmenting paths form a subtree of the residual network.<br /><br />Now we can see that if we take any vertex covered by matching, its previous vertex in the augmenting path tree (which will be in the right part, so represent a set), and the set's previous vertex in the augmenting path tree (which will be in the left part, so represent a vertex), then we get two vertices belonging to the corresponding set, and those <i>n</i>-1 pairs are exactly the solution to our problem as they necessarily form a tree!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-r6KmCDrSPEY/XCfNRma-WgI/AAAAAAACN2w/OdUOJbf36DguotqoaFPbqiVctgH1zc8ngCLcBGAs/s1600/IMG_20181124_161730.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="879" data-original-width="1600" height="350" src="https://3.bp.blogspot.com/-r6KmCDrSPEY/XCfNRma-WgI/AAAAAAACN2w/OdUOJbf36DguotqoaFPbqiVctgH1zc8ngCLcBGAs/s640/IMG_20181124_161730.jpg" width="640" /></a></div>Finally, there was an Open Cup problem: two players are playing a game on a rooted tree with 100000 vertices. They make moves in turn. In each move of the first player, she colors one of the leaves of the tree black (initially all leaves are colored white). The root of the tree also initially contains a token. In each move of the second player, she can move the token from a vertex to any adjacent vertex. The second player wins if she moves the token to a leaf that is still white. The first player wins when all leaves are colored black and the second player has not yet won. Who will win if both players play optimally?<br /><br />First, we can notice that it doesn't make sense for the second player to go up, as they will end up in a strictly worse state than before. So for each subtree, there's at most one moment in the game when the token enters this subtree, and then the game continues just in this subtree.<br /><br />Moreover, suppose that the first player has made <i>x</i> moves into this subtree before the token enters it. Then it's clear that there's some boundary <i>b</i> such that when <i>x</i><<i>b</i> the second player wins if the token enters this subtree, and when <i>x</i>>=<i>b </i>the first player wins if the token enters this subtree. This finally gives us a linear-time dynamic programming solution: we will compute this boundary <i>b</i> for each subtree going from the bottom to the top.<br /><br />Thanks for reading, and check back tomorrow!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/hfCJCuvWWoE" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com3http://petr-mitrichev.blogspot.com/2018/12/a-wave-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-35698926208857489442018-12-29T21:06:00.000+03:002018-12-29T21:06:17.929+03:00A Kuhn's 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/-Occ7KdeJUtE/XCdTTK0cK7I/AAAAAAACN0o/PuHgi0t0AAUaItlAX6Q1bJi0ov5Sk6ZZQCLcBGAs/s1600/cf526top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="279" data-original-width="1102" height="162" src="https://2.bp.blogspot.com/-Occ7KdeJUtE/XCdTTK0cK7I/AAAAAAACN0o/PuHgi0t0AAUaItlAX6Q1bJi0ov5Sk6ZZQCLcBGAs/s640/cf526top5.png" width="640" /></a></div>The Dec 10 - Dec 16 week was livelier than a few previous ones. Codeforces Round 526 started the fun right on Monday (<a href="https://codeforces.com/contest/1083">problems</a>, <a href="https://codeforces.com/contest/1083/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/63753?locale=en">analysis</a>). Radewoosh continued his string of excellent results, was the only contestant to solve five problems, got the first place with a huge margin and also overtook tourist for the first place in the <a href="https://codeforces.com/ratings">rating list</a> — very well done!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-kjT162xDM8o/XCdWo1n7PWI/AAAAAAACN04/HBVgfXsVldABnu782QNK90snWKLCbrHewCLcBGAs/s1600/srm744top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="146" data-original-width="780" height="118" src="https://2.bp.blogspot.com/-kjT162xDM8o/XCdWo1n7PWI/AAAAAAACN04/HBVgfXsVldABnu782QNK90snWKLCbrHewCLcBGAs/s640/srm744top5.png" width="640" /></a></div>TopCoder SRM 744 took place on Friday (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=17373">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17373&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://youtu.be/Cn3JWz_ocPY">my screencast</a>, <a href="https://www.topcoder.com/blog/single-round-match-744-editorials/">analysis</a>). Trying to learn from <a href="https://petr-mitrichev.blogspot.com/2018/12/when-it-should-have-returned-30.html">my experience</a> in the TCO final, when approaching the hard problem I have decided to not implement relatively straightforward solutions involving either heavy-light decomposition or propagating piecewise-linear functions up the tree, but instead think a bit more to come up with an easier to implement solution. The strategy has almost backfired as I got my "simple" solution to work with less than two minutes into the contest. However, it did work in the end as a few other contestants going for the straightforward but complicated implementation approaches have failed because of subtle bugs (for example, ainta was above me after the coding phase but his solution failed as he should've used a multiset instead of a set, presumably inside the representation of a piecewise-linear function or something similar).<br /><br />Here's <a href="https://community.topcoder.com/stat?c=problem_statement&pm=14587&rd=17373">that problem</a>: you are given a rooted tree with 100000 vertices. Each vertex has a demand <i>d<sub>i</sub></i> and a cost <i>c<sub>i</sub></i>. Your goal is to assign some non-negative value <i>v<sub>i</sub></i> to each vertex so that the demand of each vertex is less than or equal to the sum of values on the path from this vertex to the root of the tree, and the sum of <i>c<sub>i</sub></i>*<i>v<sub>i</sub></i> is minimized. What's the easiest to implement approach, in your opinion?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-G2qleo2NfMI/XCesOUu3z6I/AAAAAAACN1Q/4PTwj2eOgnAdLZBT3RyxfqrAVTZMeOwTQCLcBGAs/s1600/agc029top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="352" data-original-width="836" height="268" src="https://2.bp.blogspot.com/-G2qleo2NfMI/XCesOUu3z6I/AAAAAAACN1Q/4PTwj2eOgnAdLZBT3RyxfqrAVTZMeOwTQCLcBGAs/s640/agc029top5.png" width="640" /></a></div>AtCoder Grand Contest 029 followed on Saturday (<a href="https://atcoder.jp/contests/agc029/tasks">problems</a>, <a href="https://atcoder.jp/contests/agc029/standings">results</a>, top 5 on the left, <a href="https://youtu.be/02VV330Avc8">my screencast with commentary</a>, <a href="https://img.atcoder.jp/agc029/editorial.pdf">analysis</a>). The problemset was relatively approachable this time, so to win one had to be fast and to minimize incorrect attempts. LHiC executed very well on both fronts and got first place with the margin of 12 penalty minutes. Well done!<br /><br />I was submitting my last problem around 88-th minute for the first time, but <a href="https://atcoder.jp/contests/agc029/submissions/3799908">got time limit exceeded</a> on just one testcase. My solution involved Dinic's maximum flow algorithm that I have copy-pasted from a previous solution. Later I <a href="https://atcoder.jp/contests/agc029/submissions/3801131">submitted</a> the same solution in C++ and it passed in just 0.5s, while the time limit is 4s. Maybe somebody can tell why Java is more than 8x slower this time?<br /><br />Of course, later I tried submitting Kuhn's maximum matching algorithm in Java instead, which is supposed to be quadratic in the worst case, but it actually passed within the time limit :)<br /><br />Reducing the problem to maximum matching is also quite fun. Here's <a href="https://atcoder.jp/contests/agc029/tasks/agc029_f">the statement</a>: you are given <i>n</i> vertices, and <i>n</i>-1 sets of those vertices, each of size at least 2. Your goal is to pick exactly two vertices in each of the <i>n</i>-1 sets in such a way that if we draw the <i>n</i>-1 edges connecting each chosen pair to each other, we get a tree. <i>n</i> is at most 100000, and the total size of the given sets is at most 200000.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/--8Gfw47N4tA/XCezQ-LrzxI/AAAAAAACN1c/pkQs6_eo60Mz3ITTd6evrcPt040lmkZIACLcBGAs/s1600/oc1819peterhoftop5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="211" data-original-width="745" height="180" src="https://3.bp.blogspot.com/--8Gfw47N4tA/XCezQ-LrzxI/AAAAAAACN1c/pkQs6_eo60Mz3ITTd6evrcPt040lmkZIACLcBGAs/s640/oc1819peterhoftop5.png" width="640" /></a></div>Open Cup 2018-19 Grand Prix of Peterhof took place on Sunday (<a href="http://opencup.ru/index.cgi?data=macros/stage&head=index&menu=index&stg=9&region=main&ncup=ocj&class=ocj">results</a>, top 5 on the left). Compared to a few previous rounds, the Moscow SU team has cut down dramatically on incorrect attempts, and thus got their first win of the season. Congratulations!<br /><br />Problem G was a nice dynamic programming exercise. Two players are playing a game on a rooted tree with 100000 vertices. They make moves in turn. In each move of the first player, she colors one of the leaves of the tree black (initially all leaves are colored white). The root of the tree also initially contains a token. In each move of the second player, she can move the token from a vertex to any adjacent vertex. The second player wins if she moves the token to a leaf that is still white. The first player wins when all leaves are colored black and the second player has not yet won. Who will win if both players play optimally? Can you see a way to avoid traversing the entire ~2<sup>100000</sup> state space?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-ClToLlv9r2Q/XCe2yLj--XI/AAAAAAACN1o/BhefW2-HbG4rdk4dcV6u50-9ujbIwe8zQCLcBGAs/s1600/avitocool2018top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="271" data-original-width="1107" height="156" src="https://4.bp.blogspot.com/-ClToLlv9r2Q/XCe2yLj--XI/AAAAAAACN1o/BhefW2-HbG4rdk4dcV6u50-9ujbIwe8zQCLcBGAs/s640/avitocool2018top5.png" width="640" /></a></div>Finally, Codeforces ran Avito Cool Challenge 2018 later on Sunday (<a href="https://codeforces.com/contest/1081">problems</a>, <a href="https://codeforces.com/contest/1081/standings">results</a>, top 5 on the left, <a href="https://codeforces.com/blog/entry/63888">analysis</a>). tourist was a bit slower than LHiC but was able to find two challenges and regain the first place in the round, and with it the first place in <a href="https://codeforces.com/ratings">the rating list</a>. Congratulations!<br /><br />Thanks for reading, and check back for more!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/AWW6NvL_ZVM" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com1http://petr-mitrichev.blogspot.com/2018/12/a-kuhns-week.htmltag:blogger.com,1999:blog-1953325079793449971.post-49604325491289285122018-12-29T13:51:00.001+03:002018-12-29T13:51:48.906+03:00A lazy 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/-rBmdUSs58nk/XCdNZspKGpI/AAAAAAACN0c/y-KI-uAysK4zVPqm7AjkLJg3ZoS9XtZQgCLcBGAs/s1600/srm743top5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="148" data-original-width="781" height="120" src="https://2.bp.blogspot.com/-rBmdUSs58nk/XCdNZspKGpI/AAAAAAACN0c/y-KI-uAysK4zVPqm7AjkLJg3ZoS9XtZQgCLcBGAs/s640/srm743top5.png" width="640" /></a></div>The Dec 3 - Dec 9 week featured TopCoder SRM 743 (<a href="https://community.topcoder.com/stat?c=round_overview&er=5&rd=17370">problems</a>, <a href="https://community.topcoder.com/stat?c=round_stats_sorted&rd=17370&dn=1&sq=Round_Statistics_Data&sc=16&sd=asc">results</a>, top 5 on the left, <a href="https://youtu.be/bAz3gdwEPyc">my screencast</a>, <a href="https://www.topcoder.com/blog/single-round-match-743-editorials/">analysis</a>). Stonefeang was quite close to increasing his lead in <a href="https://tco19.topcoder.com/home/algorithm/algorithm-leaderboard">the overall standings</a> as he was temporarily in first place during the challenge phase after finding a successful challenge. However, ksun48 then found a successful challenge of his own, regained his first place from the coding phase, and joined Stonefeang at the top of the overall leaderboard. Congratulations!<br /><br />Thanks for reading (was this the shortest post of the year?) and check back for more!</div><img src="http://feeds.feedburner.com/~r/PetrMitrichev/~4/726r3K4jfdI" height="1" width="1" alt=""/>Petr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.com0http://petr-mitrichev.blogspot.com/2018/12/a-lazy-week.html