Solution to #810 Div. 1 Problem C: XOR Triangle

Revision en1, by Noble_Mushtak, 2022-07-25 04:06:38

I think the editorial for Round#810 is not out yet, and I found a solution for 810C: XOR Triangle which I thought was interesting, even if my solution is probably more complicated the intended solution, so I wanted to share it here.

Let's say the binary string in the test case is $$$b_{N-1} \dots b_0$$$ (yes, rightmost bit is labelled $$$b_0$$$, because it is the least significant bit). The first idea behind my solution is that you can solve it using DP, where you loop from right to left in the binary string and compute the answer for $$$n=b_i\dots b_0$$$ for all $$$i=0$$$ to $$$N-1$$$, where $$$N$$$ is the length of the given binary string. That is, you compute the answer for every $$$n$$$ which is a suffix of the binary string in the given test case.

Now, let's say we are trying to find the answer for $$$n=b_i\cdots b_0$$$. If $$$b_i=0$$$, then the answer is just whatever the last answer for $$$n=b_{i-1}\cdots b_0$$$ was, which we already know from the previous DP answer. Otherwise if $$$b_i=1$$$, we have to do some work.

If $$$b_i=1$$$, I split the answer into four cases:

  1. Number of triples where exactly 0 of $$$a,b,c$$$ have their $$$i$$$ th bit set to 1
  2. Number of triples where exactly 1 of $$$a,b,c$$$ have their $$$i$$$ th bit set to 1
  3. Number of triples where exactly 2 of $$$a,b,c$$$ have their $$$i$$$ th bit set to 1
  4. Number of triples where exactly 3 of $$$a,b,c$$$ have their $$$i$$$ th bit set to 1

Case where 0 numbers have $$$i$$$ th bit set to 1

Case where 1 numbers have $$$i$$$ th bit set to 1

Case where 2 numbers have $$$i$$$ th bit set to 1

Case where 3 numbers have $$$i$$$ th bit set to 1

Tags #dp, #bitmasks, #xor

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en15 English Noble_Mushtak 2022-07-26 03:21:12 15 Tiny change: 'means $c$ is a subset of $f\set' -> 'means $c$ contains all of $f\set'
en14 English Noble_Mushtak 2022-07-25 05:21:59 0 (published)
en13 English Noble_Mushtak 2022-07-25 05:20:29 913
en12 English Noble_Mushtak 2022-07-25 05:15:50 40
en11 English Noble_Mushtak 2022-07-25 05:14:25 2535
en10 English Noble_Mushtak 2022-07-25 05:04:05 355
en9 English Noble_Mushtak 2022-07-25 04:51:55 691
en8 English Noble_Mushtak 2022-07-25 04:47:42 1088
en7 English Noble_Mushtak 2022-07-25 04:39:17 2329
en6 English Noble_Mushtak 2022-07-25 04:29:52 1572
en5 English Noble_Mushtak 2022-07-25 04:22:39 392
en4 English Noble_Mushtak 2022-07-25 04:20:35 33
en3 English Noble_Mushtak 2022-07-25 04:20:04 2129
en2 English Noble_Mushtak 2022-07-25 04:10:49 673
en1 English Noble_Mushtak 2022-07-25 04:06:38 1682 Initial revision (saved to drafts)