Jekyll2021-09-02T19:59:47-04:00http://4fecta.ca//feed.xml4fecta’s SiteMy personal websiteEdward Xiaoyour-email@email.comA Deeper Look at the Small-to-Large Heuristic2021-09-01T20:30:13-04:002021-09-01T20:30:13-04:00http://4fecta.ca//a-deeper-look-at-the-small-to-large-heuristic<p>The small-to-large heuristic is well known among the competitive programming community, but most problems that require it are straightforward applications of set merging. Here, we introduce a different way to think about the heuristic so that it may be applicable to a wider variety of problems. Consider the problem <a href="https://open.kattis.com/problems/nonboringsequences">Non-boring Sequences</a>. In short, the problem asks to determine whether all consecutive subsequences of a sequence \(A\) contain a unique element (such sequences are termed “non-boring”). Surely, after a quick read, we can start to brainstorm some segment tree or other data structure based solution, but what if we try some brute force approaches as well?</p>
<p>Consider a recursive <code class="language-plaintext highlighter-rouge">check</code> function taking parameters \(l\) and \(r\) for whether the subsequence \(A[l, r]\) is non-boring. For some \(i\) in \([l, r]\), if \(A_i\) is unique (the previous and next appearance of \(A_i\) in \(A\) occurs outside of \([l, r]\)), then all subsequences of \(A[l, r]\) “crossing” \(i\) are non-boring. Thus, it suffices to check that both \(A[l, i-1]\) and \(A[i+1, r]\) are non-boring with a recursive call to <code class="language-plaintext highlighter-rouge">check</code> (note that we only need to recurse for one such \(i\) if it exists, think about why this is).</p>
<p>Naively, the algorithm above runs in \(\mathcal{O}(N^2)\), far too slow for the given constraint of \(N \leq 200\;000\). However, what if we try a different order of looping \(i\) in the <code class="language-plaintext highlighter-rouge">check</code> function? Instead of looping \(i\) in the order \([l, l+1, l+2, .., r]\), we will loop \(i\) “outside-in”, in the order \([l, r, l+1, r-1, l+2, r-2, ...]\). As it turns out, this provides us with an \(\mathcal{O}(N \log N)\) algorithm, which is a dramatic improvement from what we thought would be \(\mathcal{O}(N^2)\)!</p>
<p>To prove this, consider the tree formed by our decisions for \(i\) for each \(i\) recursively chosen by <code class="language-plaintext highlighter-rouge">check</code>. This will be a binary tree, where the number of children in the left child is the size of the left side of our split \([l, i-1]\), and the number of children in the right child is the size of \([i+1, r]\). At each step of the algorithm, we are essentially “unmerging” a set of objects into the left and right children, giving each child the corresponding number of objects to its size. Note that this unmerging happens in a time complexity proportional to the size of the smaller child, by nature of us looping outside-in. However, considering the reverse process, this is exactly the process of small-to-large set merging, which is \(\mathcal{O}(N \log N)\)! Thus, we have obtained the correct complexity of our algorithm, and this problem is solved with barely any pain or book-code. Below shows a C++ implementation of <code class="language-plaintext highlighter-rouge">check</code>, where <code class="language-plaintext highlighter-rouge">lst</code> and <code class="language-plaintext highlighter-rouge">nxt</code> store the index of the previous and next appearance of \(A_i\) respectively:</p>
<figure class="highlight"><pre><code class="language-cpp" data-lang="cpp"><span class="kt">bool</span> <span class="nf">check</span><span class="p">(</span><span class="kt">int</span> <span class="n">l</span><span class="p">,</span> <span class="kt">int</span> <span class="n">r</span><span class="p">)</span> <span class="p">{</span>
<span class="k">if</span> <span class="p">(</span><span class="n">l</span> <span class="o">></span> <span class="n">r</span><span class="p">)</span> <span class="k">return</span> <span class="mi">1</span><span class="p">;</span>
<span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="n">l</span><span class="p">,</span> <span class="n">j</span> <span class="o">=</span> <span class="n">r</span><span class="p">;</span> <span class="n">i</span> <span class="o"><=</span> <span class="n">j</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">,</span> <span class="n">j</span><span class="o">--</span><span class="p">)</span> <span class="p">{</span>
<span class="k">if</span> <span class="p">(</span><span class="n">lst</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o"><</span> <span class="n">l</span> <span class="o">&&</span> <span class="n">nxt</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">></span> <span class="n">r</span><span class="p">)</span> <span class="k">return</span> <span class="n">check</span><span class="p">(</span><span class="n">l</span><span class="p">,</span> <span class="n">i</span> <span class="o">-</span> <span class="mi">1</span><span class="p">)</span> <span class="o">&&</span> <span class="n">check</span><span class="p">(</span><span class="n">i</span> <span class="o">+</span> <span class="mi">1</span><span class="p">,</span> <span class="n">r</span><span class="p">);</span>
<span class="k">if</span> <span class="p">(</span><span class="n">lst</span><span class="p">[</span><span class="n">j</span><span class="p">]</span> <span class="o"><</span> <span class="n">l</span> <span class="o">&&</span> <span class="n">nxt</span><span class="p">[</span><span class="n">j</span><span class="p">]</span> <span class="o">></span> <span class="n">r</span><span class="p">)</span> <span class="k">return</span> <span class="n">check</span><span class="p">(</span><span class="n">l</span><span class="p">,</span> <span class="n">j</span> <span class="o">-</span> <span class="mi">1</span><span class="p">)</span> <span class="o">&&</span> <span class="n">check</span><span class="p">(</span><span class="n">j</span> <span class="o">+</span> <span class="mi">1</span><span class="p">,</span> <span class="n">r</span><span class="p">);</span>
<span class="p">}</span>
<span class="k">return</span> <span class="mi">0</span><span class="p">;</span>
<span class="p">}</span></code></pre></figure>
<p>In conclusion, it may be worth the time to consider seemingly brute force solutions to some problems, as long as there is a merging or unmerging process that can happen proportional to the size of the smaller set, capitalizing on the small-to-large heuristic when it seems like the last thing one could do.</p>Edward Xiaoyour-email@email.comThe small-to-large heuristic is well known among the competitive programming community, but most problems that require it are straightforward applications of set merging. Here, we introduce a different way to think about the heuristic so that it may be applicable to a wider variety of problems. Consider the problem Non-boring Sequences. In short, the problem asks to determine whether all consecutive subsequences of a sequence \(A\) contain a unique element (such sequences are termed “non-boring”). Surely, after a quick read, we can start to brainstorm some segment tree or other data structure based solution, but what if we try some brute force approaches as well?A Soft Introduction to Plug DP2021-05-17T10:54:01-04:002021-05-17T10:54:01-04:00http://4fecta.ca//a-soft-introduction-to-plug-dp<p>So I realized that there are literally 0 resources written in English on Plug DP, which is one of my favourite DP tricks/techniques that I know of so far. Thus, I hope this serves as a soft introduction for English speakers to this technique, and maybe sheds some light on how powerful it can be. Before we start, I would recommend having a solid understanding of bitmask DP in general in order to get the most out of this blog. Now, let’s begin.</p>
<h3 id="what-is-plug-dp">What is Plug DP?</h3>
<p>In short, Plug DP is a bitmasking technique that allows us to solve complicated problems with relatively simple states and transitions. To illustrate Plug DP in its most primitive form, let’s visit a rather classical problem: <strong>How many ways can we fully tile an \(N \times M\) grid with \(1 \times 2\) dominoes?</strong></p>
<p>This problem can be solved with a standard row-by-row bitmasking approach, but the transitions for that DP state is annoying and unclear at best. Instead, let’s investigate an approach that uses a slightly different state. Our state, \(dp[i][j][mask]\), will represent the number of possible full tilings of all cells in rows \(i-1\) and earlier, and the first \(j\) cells in row \(i\), with a plug mask of \(mask\). The first two dimensions are relatively straightforward, but what do I mean by “plug mask”?</p>
<h3 id="the-plug-mask">The Plug Mask</h3>
<figure>
<img src="fig1.jpg" alt="figure 1" />
<figcaption>What the state represents</figcaption>
</figure>
<p>Let’s consider a concrete example to understand the concept of plug masks. Consider the diagram above, where the first two dimensions \((i, j) = (3, 4)\). The red line denotes the line which separates the cells we’ve already processed and the cells we have yet to consider. This line can be split into \(M+1\) segments of length 1, and each of the arrows on these segments represent a plug. The plug itself can represent a variety of things, but for our purposes here it represents whether we have placed a domino that crosses the plug (i.e. the two halves of the domino lie on separate sides of the plug). The plug will be \(1\) (toggled) if there is a domino laid over it, and \(0\) otherwise. For example, the diagram below depicts one of the tilings that has the plugs with states \([1, 0, 1, 0, 1, 0, 0, 1, 0]\) from left to right. We can obviously represent the set of states of the plugs using a bitmask of length \(M+1\), so the DP state which the tiling below belongs to is \(dp[3][4][101010010_2]\) (I’ve written the binary number in reverse here for readability. Just to be clear, the decimal equivalent of this mask is \(149\) and not \(338\)).</p>
<figure>
<img src="fig2.jpg" alt="figure 2" />
<figcaption>A possible tiling represented by the binary mask 101010010</figcaption>
</figure>
<h3 id="transitions">Transitions</h3>
<p>In general, we want to transition from cell \((i, j - 1)\) to cell \((i, j)\) (i.e. across each row). Notice that only 2 plugs change locations when we move horizontally, which is the main reason why Plug DP ends up being so powerful. If we number the plugs from \(0\) to \(M\), then only plugs \(j-1\) and \(j\) change locations. Specifically, \(j-1\) goes from the vertical plug in the previous state to a horizontal plug in the next, while \(j\) goes from a horizontal plug to the vertical plug. For example, the diagram below depicts the differences between the set of plugs for a state at \((3, 3)\) versus the set of plugs for a state at \((3, 4)\). The orange plugs are all shared and do not change during the transition, so we only need to consider how plugs \(3\) and \(4\) change in our transition from \((3, 3)\) to \((3, 4)\). It is convenient to note that if we \(1\)-index the columns and \(0\)-index the plugs, then plug \(j\) will always be the vertical plug when considering a state at column \(j\).</p>
<figure>
<img src="fig3.jpg" alt="figure 3" />
<figcaption>Going from (3, 3) to (3, 4)</figcaption>
</figure>
<p>So how do we transition? First, we notice that if both plugs \(j-1\) and \(j\) are toggled from the previous state then it leads to an overlap of 2 dominoes on cell \((i, j)\), so we don’t need to consider this case. Let’s handle the other 3 cases separately.</p>
<p><strong>Case 1:</strong> none of plug \(j-1\) and \(j\) are toggled.</p>
<p>This means that \((i, j)\) does not have anything covering it, so we must place one end of a domino there to cover. We can either place a horizontal domino going from \((i, j)\) to \((i, j+1)\) toggling plug \(j\), or we can place a vertical domino going from \((i, j)\) to \((i+1, j)\) toggling plug \(j-1\). Note that we cannot place a domino going to \((i, j-1)\) or \((i-1, j)\) since these cells are already occupied by the definition of our state.</p>
<p><strong>Case 2:</strong> only plug \(j-1\) is toggled.</p>
<p>This means that \((i, j)\) is already covered (by a domino going from \((i, j-1)\) to \((i, j)\)), so all we have to do is untoggle plug \(j-1\) and move on.</p>
<p><strong>Case 3:</strong> only plug \(j\) is toggled.</p>
<p>Extemely similar to the previous case, This means that \((i, j)\) is already covered (by a domino going from \((i-1, j)\) to \((i, j)\)), so all we have to do is untoggle plug \(j\) and move on.</p>
<p>And that’s really all there is! Now we just need to handle some special procedures and we are good to go.</p>
<h3 id="going-from-row-i-1-to-row-i">Going from row \(i-1\) to row \(i\)</h3>
<p>If you’ve been following along, you may be wondering how we go from one row to the next. It turns out that all we need to do is move some values from one place to another. Specifically, when we first process row \(i\), we will transfer all the values stored in \(dp[i - 1][M][mask]\) to \(dp[i][0][mask << 1]\). It may be confusing as to why we are shifting all bits to the left by 1, but the following diagram should clear things up.</p>
<figure>
<img src="fig4.jpg" alt="figure 4" />
<figcaption>Shifting rows</figcaption>
</figure>
<p>As you may notice, the vertical plug \(0\) on the next row shifts all the plug indices by 1, so we must shift all bits in the mask by 1 to compensate. Also, the vertical plugs here \(0\) and \(M\) should never be toggled since having a domino go outside the grid would be absurd, so we don’t have to worry about the bit we lose from shifting or the new bit introduced.</p>
<h3 id="final-details">Final details</h3>
<p>Our base case will be \(dp[0][M][0] = 1\), and you can see how this easily fits in from the previous section. The final answer will be stored in \(dp[N][M][0]\), since having any plugs toggled at that point would mean having a domino go outside of the grid.</p>
<h3 id="implementation">Implementation</h3>
<p>Here, you can find my implementation for the procedure described above. I take all values modulo <code class="language-plaintext highlighter-rouge">MOD</code> since the number of tilings grows rapidly for larger \(N\) and \(M\). The time complexity is \(\mathcal{O}(NM2^{M+1})\), which means we can solve the problem for \(N, M \le 20\) with ease.</p>
<figure class="highlight"><pre><code class="language-cpp" data-lang="cpp"><span class="n">cin</span> <span class="o">>></span> <span class="n">n</span> <span class="o">>></span> <span class="n">m</span><span class="p">;</span>
<span class="kt">int</span> <span class="n">full</span> <span class="o">=</span> <span class="p">(</span><span class="mi">1</span> <span class="o"><<</span> <span class="p">(</span><span class="n">m</span> <span class="o">+</span> <span class="mi">1</span><span class="p">))</span> <span class="o">-</span> <span class="mi">1</span><span class="p">;</span> <span class="c1">//the maximum possible mask with all m+1 bits set
</span>
<span class="n">dp</span><span class="p">[</span><span class="mi">0</span><span class="p">][</span><span class="n">m</span><span class="p">][</span><span class="mi">0</span><span class="p">]</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="c1">//base case
</span>
<span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">i</span> <span class="o"><=</span> <span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span>
<span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">msk</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">msk</span> <span class="o"><=</span> <span class="n">full</span><span class="p">;</span> <span class="n">msk</span><span class="o">++</span><span class="p">)</span> <span class="n">dp</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="mi">0</span><span class="p">][</span><span class="n">msk</span> <span class="o"><<</span> <span class="mi">1</span><span class="p">]</span> <span class="o">+=</span> <span class="n">dp</span><span class="p">[</span><span class="n">i</span> <span class="o">-</span> <span class="mi">1</span><span class="p">][</span><span class="n">m</span><span class="p">][</span><span class="n">msk</span><span class="p">];</span> <span class="c1">//transfer data from row i-1 to i
</span>
<span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">j</span> <span class="o"><=</span> <span class="n">m</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span>
<span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">msk</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">msk</span> <span class="o"><=</span> <span class="n">full</span><span class="p">;</span> <span class="n">msk</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span>
<span class="kt">int</span> <span class="n">rit</span> <span class="o">=</span> <span class="n">msk</span> <span class="o">&</span> <span class="p">(</span><span class="mi">1</span> <span class="o"><<</span> <span class="p">(</span><span class="n">j</span> <span class="o">-</span> <span class="mi">1</span><span class="p">)),</span> <span class="n">dwn</span> <span class="o">=</span> <span class="n">msk</span> <span class="o">&</span> <span class="p">(</span><span class="mi">1</span> <span class="o"><<</span> <span class="n">j</span><span class="p">);</span> <span class="c1">//right and down plug from (i, j-1) respectively
</span>
<span class="k">if</span> <span class="p">(</span><span class="o">!</span><span class="n">rit</span> <span class="o">&&</span> <span class="o">!</span><span class="n">dwn</span><span class="p">)</span> <span class="p">{</span> <span class="c1">//case 1
</span>
<span class="n">dp</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">][</span><span class="n">msk</span> <span class="o">^</span> <span class="p">(</span><span class="mi">1</span> <span class="o"><<</span> <span class="n">j</span><span class="p">)]</span> <span class="o">+=</span> <span class="n">dp</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span> <span class="o">-</span> <span class="mi">1</span><span class="p">][</span><span class="n">msk</span><span class="p">]</span> <span class="o">%</span> <span class="n">MOD</span><span class="p">;</span> <span class="c1">//place right domino
</span>
<span class="n">dp</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">][</span><span class="n">msk</span> <span class="o">^</span> <span class="p">(</span><span class="mi">1</span> <span class="o"><<</span> <span class="p">(</span><span class="n">j</span> <span class="o">-</span> <span class="mi">1</span><span class="p">))]</span> <span class="o">+=</span> <span class="n">dp</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span> <span class="o">-</span> <span class="mi">1</span><span class="p">][</span><span class="n">msk</span><span class="p">]</span> <span class="o">%</span> <span class="n">MOD</span><span class="p">;</span> <span class="c1">//place down domino
</span>
<span class="p">}</span> <span class="k">else</span> <span class="k">if</span> <span class="p">(</span><span class="n">rit</span> <span class="o">&&</span> <span class="o">!</span><span class="n">dwn</span><span class="p">)</span> <span class="n">dp</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">][</span><span class="n">msk</span> <span class="o">^</span> <span class="p">(</span><span class="mi">1</span> <span class="o"><<</span> <span class="p">(</span><span class="n">j</span> <span class="o">-</span> <span class="mi">1</span><span class="p">))]</span> <span class="o">+=</span> <span class="n">dp</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span> <span class="o">-</span> <span class="mi">1</span><span class="p">][</span><span class="n">msk</span><span class="p">]</span> <span class="o">%</span> <span class="n">MOD</span><span class="p">;</span> <span class="c1">//case 2
</span>
<span class="k">else</span> <span class="k">if</span> <span class="p">(</span><span class="o">!</span><span class="n">rit</span> <span class="o">&&</span> <span class="n">dwn</span><span class="p">)</span> <span class="n">dp</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">][</span><span class="n">msk</span> <span class="o">^</span> <span class="p">(</span><span class="mi">1</span> <span class="o"><<</span> <span class="n">j</span><span class="p">)]</span> <span class="o">+=</span> <span class="n">dp</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span> <span class="o">-</span> <span class="mi">1</span><span class="p">][</span><span class="n">msk</span><span class="p">]</span> <span class="o">%</span> <span class="n">MOD</span><span class="p">;</span> <span class="c1">//case 3
</span>
<span class="p">}</span>
<span class="p">}</span>
<span class="p">}</span>
<span class="n">printf</span><span class="p">(</span><span class="s">"%d</span><span class="se">\n</span><span class="s">"</span><span class="p">,</span> <span class="n">dp</span><span class="p">[</span><span class="n">n</span><span class="p">][</span><span class="n">m</span><span class="p">][</span><span class="mi">0</span><span class="p">]</span> <span class="o">%</span> <span class="n">MOD</span><span class="p">);</span> <span class="c1">//final answer</span></code></pre></figure>
<h3 id="closing-remarks">Closing Remarks</h3>
<p>And that was a quick overview of Plug DP! With a firm grasp on the concepts we can easily extend this to a variety of other small grid problems, whether it be about domino tilings or counting circuits in a grid. As a small exercise, try solving the problem above when some of the given cells are blocked, or try solving it for when it does not have to be a full tiling. Anyways, that’s all for now.</p>
<p>Ciao 👋</p>Edward Xiaoyour-email@email.comSo I realized that there are literally 0 resources written in English on Plug DP, which is one of my favourite DP tricks/techniques that I know of so far. Thus, I hope this serves as a soft introduction for English speakers to this technique, and maybe sheds some light on how powerful it can be. Before we start, I would recommend having a solid understanding of bitmask DP in general in order to get the most out of this blog. Now, let’s begin. What is Plug DP? In short, Plug DP is a bitmasking technique that allows us to solve complicated problems with relatively simple states and transitions. To illustrate Plug DP in its most primitive form, let’s visit a rather classical problem: How many ways can we fully tile an \(N \times M\) grid with \(1 \times 2\) dominoes? This problem can be solved with a standard row-by-row bitmasking approach, but the transitions for that DP state is annoying and unclear at best. Instead, let’s investigate an approach that uses a slightly different state. Our state, \(dp[i][j][mask]\), will represent the number of possible full tilings of all cells in rows \(i-1\) and earlier, and the first \(j\) cells in row \(i\), with a plug mask of \(mask\). The first two dimensions are relatively straightforward, but what do I mean by “plug mask”? The Plug Mask What the state represents Let’s consider a concrete example to understand the concept of plug masks. Consider the diagram above, where the first two dimensions \((i, j) = (3, 4)\). The red line denotes the line which separates the cells we’ve already processed and the cells we have yet to consider. This line can be split into \(M+1\) segments of length 1, and each of the arrows on these segments represent a plug. The plug itself can represent a variety of things, but for our purposes here it represents whether we have placed a domino that crosses the plug (i.e. the two halves of the domino lie on separate sides of the plug). The plug will be \(1\) (toggled) if there is a domino laid over it, and \(0\) otherwise. For example, the diagram below depicts one of the tilings that has the plugs with states \([1, 0, 1, 0, 1, 0, 0, 1, 0]\) from left to right. We can obviously represent the set of states of the plugs using a bitmask of length \(M+1\), so the DP state which the tiling below belongs to is \(dp[3][4][101010010_2]\) (I’ve written the binary number in reverse here for readability. Just to be clear, the decimal equivalent of this mask is \(149\) and not \(338\)). A possible tiling represented by the binary mask 101010010 Transitions In general, we want to transition from cell \((i, j - 1)\) to cell \((i, j)\) (i.e. across each row). Notice that only 2 plugs change locations when we move horizontally, which is the main reason why Plug DP ends up being so powerful. If we number the plugs from \(0\) to \(M\), then only plugs \(j-1\) and \(j\) change locations. Specifically, \(j-1\) goes from the vertical plug in the previous state to a horizontal plug in the next, while \(j\) goes from a horizontal plug to the vertical plug. For example, the diagram below depicts the differences between the set of plugs for a state at \((3, 3)\) versus the set of plugs for a state at \((3, 4)\). The orange plugs are all shared and do not change during the transition, so we only need to consider how plugs \(3\) and \(4\) change in our transition from \((3, 3)\) to \((3, 4)\). It is convenient to note that if we \(1\)-index the columns and \(0\)-index the plugs, then plug \(j\) will always be the vertical plug when considering a state at column \(j\). Going from (3, 3) to (3, 4) So how do we transition? First, we notice that if both plugs \(j-1\) and \(j\) are toggled from the previous state then it leads to an overlap of 2 dominoes on cell \((i, j)\), so we don’t need to consider this case. Let’s handle the other 3 cases separately. Case 1: none of plug \(j-1\) and \(j\) are toggled. This means that \((i, j)\) does not have anything covering it, so we must place one end of a domino there to cover. We can either place a horizontal domino going from \((i, j)\) to \((i, j+1)\) toggling plug \(j\), or we can place a vertical domino going from \((i, j)\) to \((i+1, j)\) toggling plug \(j-1\). Note that we cannot place a domino going to \((i, j-1)\) or \((i-1, j)\) since these cells are already occupied by the definition of our state. Case 2: only plug \(j-1\) is toggled. This means that \((i, j)\) is already covered (by a domino going from \((i, j-1)\) to \((i, j)\)), so all we have to do is untoggle plug \(j-1\) and move on. Case 3: only plug \(j\) is toggled. Extemely similar to the previous case, This means that \((i, j)\) is already covered (by a domino going from \((i-1, j)\) to \((i, j)\)), so all we have to do is untoggle plug \(j\) and move on. And that’s really all there is! Now we just need to handle some special procedures and we are good to go. Going from row \(i-1\) to row \(i\) If you’ve been following along, you may be wondering how we go from one row to the next. It turns out that all we need to do is move some values from one place to another. Specifically, when we first process row \(i\), we will transfer all the values stored in \(dp[i - 1][M][mask]\) to \(dp[i][0][mask << 1]\). It may be confusing as to why we are shifting all bits to the left by 1, but the following diagram should clear things up. Shifting rows As you may notice, the vertical plug \(0\) on the next row shifts all the plug indices by 1, so we must shift all bits in the mask by 1 to compensate. Also, the vertical plugs here \(0\) and \(M\) should never be toggled since having a domino go outside the grid would be absurd, so we don’t have to worry about the bit we lose from shifting or the new bit introduced. Final details Our base case will be \(dp[0][M][0] = 1\), and you can see how this easily fits in from the previous section. The final answer will be stored in \(dp[N][M][0]\), since having any plugs toggled at that point would mean having a domino go outside of the grid. Implementation Here, you can find my implementation for the procedure described above. I take all values modulo MOD since the number of tilings grows rapidly for larger \(N\) and \(M\). The time complexity is \(\mathcal{O}(NM2^{M+1})\), which means we can solve the problem for \(N, M \le 20\) with ease. cin >> n >> m; int full = (1 << (m + 1)) - 1; //the maximum possible mask with all m+1 bits set dp[0][m][0] = 1; //base case for (int i = 1; i <= n; i++) { for (int msk = 0; msk <= full; msk++) dp[i][0][msk << 1] += dp[i - 1][m][msk]; //transfer data from row i-1 to i for (int j = 1; j <= m; j++) { for (int msk = 0; msk <= full; msk++) { int rit = msk & (1 << (j - 1)), dwn = msk & (1 << j); //right and down plug from (i, j-1) respectively if (!rit && !dwn) { //case 1 dp[i][j][msk ^ (1 << j)] += dp[i][j - 1][msk] % MOD; //place right domino dp[i][j][msk ^ (1 << (j - 1))] += dp[i][j - 1][msk] % MOD; //place down domino } else if (rit && !dwn) dp[i][j][msk ^ (1 << (j - 1))] += dp[i][j - 1][msk] % MOD; //case 2 else if (!rit && dwn) dp[i][j][msk ^ (1 << j)] += dp[i][j - 1][msk] % MOD; //case 3 } } } printf("%d\n", dp[n][m][0] % MOD); //final answer Closing Remarks And that was a quick overview of Plug DP! With a firm grasp on the concepts we can easily extend this to a variety of other small grid problems, whether it be about domino tilings or counting circuits in a grid. As a small exercise, try solving the problem above when some of the given cells are blocked, or try solving it for when it does not have to be a full tiling. Anyways, that’s all for now. Ciao 👋How I got CCO silver without solving anything2021-05-16T21:40:20-04:002021-05-16T21:40:20-04:00http://4fecta.ca//how-i-got-cco-silver-without-solving-anything<p>I would like to preface this by saying that you should not voluntarily attempt what I did at CCO if you are serious about your results. My strategy was mainly damage control from day 1, and it was a miracle I even got silver. However, you may find my first CCO experience interesting or maybe even hilarious, which is why I am making this post. Anyways, please enjoy. 🙂</p>
<h2 id="day-1">Day 1</h2>
<h3 id="p1-swap-swap-sort">P1. Swap Swap Sort</h3>
<p>The first fault in my approach at CCO. I had some initial ideas early on, scoring the first 2 subtasks at around 16 minutes. Over the next hour, I developed a solution which runs in square root log time, believing it would pass with ease due to a fatal misreading of the constraints. The solution worked well for the first three subtasks, but for some reason I couldn’t figure out kept receiving a <code class="language-plaintext highlighter-rouge">WA</code> verdict on the last batch. For around another hour, I read over my code countless times and ran multiple fast-slow scripts, but simply couldn’t find out where the error lied. After a gruesome 2 hour and 30 minutes on problem 1, I decided to take a peek at the rest of the problemset before it was too late (although it was already way too much time wasted).</p>
<h3 id="p3-through-another-maze-darkly">P3. Through Another Maze Darkly</h3>
<p>I had a quick glance over problem 2, but decided that the subtasks from problem 3 were a lot more approachable. Really, my goal here was to snatch whatever I can and rush back to problem 1 where I had the most potential points yet to be earned. A quick program that printed the path given by a random line graph revealed the pattern of \(1-x-1-y-1-...-1-N-1-N-...\), for which the first idea that came to mind was binary search. This was the smoothest subtask of day 1 for me, taking only around 20 minutes of time in total.</p>
<h3 id="p2-weird-numeral-system">P2. Weird Numeral System</h3>
<p>This problem was intimidating at first, with no clear idea on how to proceed. Again, I was simply controlling the damage of my poor problem 1 performance here, so I was only aiming for the subtask. The subtask provided the constraint that the absolute value of any allowed digit is less than the base, which intuitively meant that any change caused by a higher base couldn’t be reverted by lower bases, no matter what values we assign them. This inspired a brute force recursion in descending order of power, ensuring that the number is in the range \((-b^K, b^K)\) when we are done with the \(K\)-th power (of course, \(b\) denotes the given base here). The solution ended up running surprisingly fast (0.1 seconds), but kept getting <code class="language-plaintext highlighter-rouge">WA</code> on case 7. After around 10 minutes of debugging, I decided it was all or nothing at this point and simply slapped <code class="language-plaintext highlighter-rouge">__int128</code> into my code, which surprisingly fixed the bug and gave me the first subtask. Overall, this was around 30 minutes spent on 8 marks, which I was relatively pleased with (considering that was more than half of the points I had earned so far).</p>
<h3 id="the-struggle-with-p1-continues">The struggle with P1 continues</h3>
<p>It was only here that I decided it may be a good idea to reread the statement, and discovered that contrary to my belief that \(Q = 100\;000\), the constraints actually had \(Q = 1\;000\;000\)! A quick 1 line fix to my <code class="language-plaintext highlighter-rouge">MQ</code> constant resolved the <code class="language-plaintext highlighter-rouge">WA</code> verdict, but replaced it with the ever so agonizing <code class="language-plaintext highlighter-rouge">TLE</code> instead. As there were only 30 minutes left at this point, I decided it would be futile to search for new solutions and settled with constant optimizing my square root log. I spammed around 20 different versions of the same code with different block sizes and with/without <code class="language-plaintext highlighter-rouge">pragma</code> optimizations, but none of them made it through the last batch. In the last 10 minutes I tried to cheese the time limit by handling numbers with small frequencies separately but that was to no avail either, and the timer hit 0 with only 11 points on problem 1, a problem I dedicated over 3 hours of contest time to.</p>
<h3 id="reflections">Reflections</h3>
<p>Clearly, my strategy of tunnel visioning on problem 1 did not work out in my favour at all. Spending over 3 out of 4 hours of such an important contest for 11 points is something that would pain anyone to see, and I was quite sad over my mediocre day 1 performance. If there is one lesson to be learned out of my CCO experience this year, it would be to <em>read the constraints, and read them carefully</em>. Also, repeatedly submitting <code class="language-plaintext highlighter-rouge">WA</code> submissions or trying to fast-slow for over 30 minutes was just a waste of time, time that could have well been spent going for more partials on problem 3 or even a full solve on problem 2. Finally, it may have been wiser to try and optimize out the log factor from my code instead of spamming flimsy <code class="language-plaintext highlighter-rouge">pragma</code>s and cheeses, something that seems more than possible with 30 minutes in hindsight. Regardless, I could not redo what had already been done, and it was time to get well rested and prepare for day 2.</p>
<h2 id="day-2">Day 2</h2>
<h3 id="preparations">Preparations</h3>
<p>My mindset going into day 2 was to mainly control the damage that had been done on day 1. My lousy day 1 performance had already eliminated any chances of going for gold, so it was time to work on securing that silver. I did a mock CCO contest the day before, just to practice waking up, getting into contest mindset, and not choking or getting stuck on any particular problem for too long.</p>
<h3 id="p3-loop-town">P3. Loop Town</h3>
<p>This goes first since it was the problem I eliminated first. After reading all the problem statements right off the bat, problem 3 already seemed concerningly difficult. The best I could come up with was some 2-SAT approach based on clockwise or counterclockwise travel, but the dependencies and conditions simply did not work out. After fiddling with it for a bit longer, I decided that this was probably the killer problem of CCO 2021, and dropped it completely (of course, the first subtask being worth 12 points helped with that realization as well). Back to the other two.</p>
<h3 id="p1-travelling-merchant">P1. Travelling Merchant</h3>
<p>I invested a fair amount of time into this problem. My first impressions were “oh hey, I finally found the template free easy Tarjan’s problem” that previous CCOs all had (at least, some variation of a template problem). However, the problem quickly managed to shove my words back into my mouth as I pondered the details for around 30 minutes (hint, it wasn’t Tarjan’s at all). Keeping an open mind, I changed to an approach relying on Dijkstra’s algorithm which managed to almost pass the first batch after some debugging. As it turned out, replacing the Dijkstra with a simple BFS allowed my solution to pass subtask 1 in the exact 1 second of allotted time, of course with some flimsy break statements attached as well. I couldn’t find any easy optimizations with multisource BFS that would lead to a full solution, so I decided to move on to the next problem. I was quite shocked to learn after the contest that simply switching the BFS to a DFS and applying memoization was enough for full marks, but I guess that’s just how it is sometimes :)</p>
<h3 id="p2-bread-first-search">P2. Bread First Search</h3>
<p>For this problem, the observation of partitioning the nodes into some blocks of equal distances was immediately apparent, and a naive \(\mathcal{O}(N^3)\) dynamic programming solution soon followed. Here, perhaps slightly foolishly due to the mindset of redeeming my day 1 performance, I decided to search for a \(\mathcal{O}(N)\) greedy algorithm instead of attempting to optimize my DP to \(\mathcal{O}(N^2)\). The reasoning behind this was that I had done quite a number of difficult problems which ended up converting a partial DP solution into full marks with a greedy approach, and I figured that this must be one of those as well. To my dismay, the problem was not actually a greedy problem, and I spent the rest of day 2 searching for something that wasn’t even there in the first place.</p>
<h3 id="reflections-1">Reflections</h3>
<p>After day 2, I was quite sure my tragic performance (or so I thought) on both days would place me in the bronze medal range. The mistake of going for a solution that simply did not exist as compensation for a poor performance from before was unwise and panic-induced. However, the one thing I did manage to do well at CCO was ensuring that I didn’t miss out on trivial partials, and giving all the problems at least a slight jab before moving on to the next. To my surprise, the median score on day 2 was only 2 points, which ended up placing me in the silver medalist range.</p>
<h2 id="final-thoughts">Final Thoughts</h2>
<p>This marks the conclusion of my first experience at CCO, and how I managed to earn a silver medal without even scoring full points on a single problem. It turns out that only partial farming (unintentionally) for both days can be sufficient to cross that silver cutoff, and I am glad I was able to leave the contest with a lot more experience and ideas than before. I can’t say that I’m completely happy with how I did, but I am thankful that things didn’t go as bad as I thought. I guess this also means I have a lot more to learn and prepare before the next wave of computing competitions. Anyways, that’s it for my first blog.</p>
<p>Ciao 👋</p>Edward Xiaoyour-email@email.comI would like to preface this by saying that you should not voluntarily attempt what I did at CCO if you are serious about your results. My strategy was mainly damage control from day 1, and it was a miracle I even got silver. However, you may find my first CCO experience interesting or maybe even hilarious, which is why I am making this post. Anyways, please enjoy. 🙂 Day 1 P1. Swap Swap Sort The first fault in my approach at CCO. I had some initial ideas early on, scoring the first 2 subtasks at around 16 minutes. Over the next hour, I developed a solution which runs in square root log time, believing it would pass with ease due to a fatal misreading of the constraints. The solution worked well for the first three subtasks, but for some reason I couldn’t figure out kept receiving a WA verdict on the last batch. For around another hour, I read over my code countless times and ran multiple fast-slow scripts, but simply couldn’t find out where the error lied. After a gruesome 2 hour and 30 minutes on problem 1, I decided to take a peek at the rest of the problemset before it was too late (although it was already way too much time wasted). P3. Through Another Maze Darkly I had a quick glance over problem 2, but decided that the subtasks from problem 3 were a lot more approachable. Really, my goal here was to snatch whatever I can and rush back to problem 1 where I had the most potential points yet to be earned. A quick program that printed the path given by a random line graph revealed the pattern of \(1-x-1-y-1-...-1-N-1-N-...\), for which the first idea that came to mind was binary search. This was the smoothest subtask of day 1 for me, taking only around 20 minutes of time in total. P2. Weird Numeral System This problem was intimidating at first, with no clear idea on how to proceed. Again, I was simply controlling the damage of my poor problem 1 performance here, so I was only aiming for the subtask. The subtask provided the constraint that the absolute value of any allowed digit is less than the base, which intuitively meant that any change caused by a higher base couldn’t be reverted by lower bases, no matter what values we assign them. This inspired a brute force recursion in descending order of power, ensuring that the number is in the range \((-b^K, b^K)\) when we are done with the \(K\)-th power (of course, \(b\) denotes the given base here). The solution ended up running surprisingly fast (0.1 seconds), but kept getting WA on case 7. After around 10 minutes of debugging, I decided it was all or nothing at this point and simply slapped __int128 into my code, which surprisingly fixed the bug and gave me the first subtask. Overall, this was around 30 minutes spent on 8 marks, which I was relatively pleased with (considering that was more than half of the points I had earned so far). The struggle with P1 continues It was only here that I decided it may be a good idea to reread the statement, and discovered that contrary to my belief that \(Q = 100\;000\), the constraints actually had \(Q = 1\;000\;000\)! A quick 1 line fix to my MQ constant resolved the WA verdict, but replaced it with the ever so agonizing TLE instead. As there were only 30 minutes left at this point, I decided it would be futile to search for new solutions and settled with constant optimizing my square root log. I spammed around 20 different versions of the same code with different block sizes and with/without pragma optimizations, but none of them made it through the last batch. In the last 10 minutes I tried to cheese the time limit by handling numbers with small frequencies separately but that was to no avail either, and the timer hit 0 with only 11 points on problem 1, a problem I dedicated over 3 hours of contest time to. Reflections Clearly, my strategy of tunnel visioning on problem 1 did not work out in my favour at all. Spending over 3 out of 4 hours of such an important contest for 11 points is something that would pain anyone to see, and I was quite sad over my mediocre day 1 performance. If there is one lesson to be learned out of my CCO experience this year, it would be to read the constraints, and read them carefully. Also, repeatedly submitting WA submissions or trying to fast-slow for over 30 minutes was just a waste of time, time that could have well been spent going for more partials on problem 3 or even a full solve on problem 2. Finally, it may have been wiser to try and optimize out the log factor from my code instead of spamming flimsy pragmas and cheeses, something that seems more than possible with 30 minutes in hindsight. Regardless, I could not redo what had already been done, and it was time to get well rested and prepare for day 2. Day 2 Preparations My mindset going into day 2 was to mainly control the damage that had been done on day 1. My lousy day 1 performance had already eliminated any chances of going for gold, so it was time to work on securing that silver. I did a mock CCO contest the day before, just to practice waking up, getting into contest mindset, and not choking or getting stuck on any particular problem for too long. P3. Loop Town This goes first since it was the problem I eliminated first. After reading all the problem statements right off the bat, problem 3 already seemed concerningly difficult. The best I could come up with was some 2-SAT approach based on clockwise or counterclockwise travel, but the dependencies and conditions simply did not work out. After fiddling with it for a bit longer, I decided that this was probably the killer problem of CCO 2021, and dropped it completely (of course, the first subtask being worth 12 points helped with that realization as well). Back to the other two. P1. Travelling Merchant I invested a fair amount of time into this problem. My first impressions were “oh hey, I finally found the template free easy Tarjan’s problem” that previous CCOs all had (at least, some variation of a template problem). However, the problem quickly managed to shove my words back into my mouth as I pondered the details for around 30 minutes (hint, it wasn’t Tarjan’s at all). Keeping an open mind, I changed to an approach relying on Dijkstra’s algorithm which managed to almost pass the first batch after some debugging. As it turned out, replacing the Dijkstra with a simple BFS allowed my solution to pass subtask 1 in the exact 1 second of allotted time, of course with some flimsy break statements attached as well. I couldn’t find any easy optimizations with multisource BFS that would lead to a full solution, so I decided to move on to the next problem. I was quite shocked to learn after the contest that simply switching the BFS to a DFS and applying memoization was enough for full marks, but I guess that’s just how it is sometimes :) P2. Bread First Search For this problem, the observation of partitioning the nodes into some blocks of equal distances was immediately apparent, and a naive \(\mathcal{O}(N^3)\) dynamic programming solution soon followed. Here, perhaps slightly foolishly due to the mindset of redeeming my day 1 performance, I decided to search for a \(\mathcal{O}(N)\) greedy algorithm instead of attempting to optimize my DP to \(\mathcal{O}(N^2)\). The reasoning behind this was that I had done quite a number of difficult problems which ended up converting a partial DP solution into full marks with a greedy approach, and I figured that this must be one of those as well. To my dismay, the problem was not actually a greedy problem, and I spent the rest of day 2 searching for something that wasn’t even there in the first place. Reflections After day 2, I was quite sure my tragic performance (or so I thought) on both days would place me in the bronze medal range. The mistake of going for a solution that simply did not exist as compensation for a poor performance from before was unwise and panic-induced. However, the one thing I did manage to do well at CCO was ensuring that I didn’t miss out on trivial partials, and giving all the problems at least a slight jab before moving on to the next. To my surprise, the median score on day 2 was only 2 points, which ended up placing me in the silver medalist range. Final Thoughts This marks the conclusion of my first experience at CCO, and how I managed to earn a silver medal without even scoring full points on a single problem. It turns out that only partial farming (unintentionally) for both days can be sufficient to cross that silver cutoff, and I am glad I was able to leave the contest with a lot more experience and ideas than before. I can’t say that I’m completely happy with how I did, but I am thankful that things didn’t go as bad as I thought. I guess this also means I have a lot more to learn and prepare before the next wave of computing competitions. Anyways, that’s it for my first blog. Ciao 👋