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

Правка en4, от Noble_Mushtak, 2022-07-25 04:20:35

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 write it up both because I want to share it with others and because I feel like explaining a solution can help myself remember it better.

First, notice that, since every leg of the triangle $$$a\oplus b, a\oplus c, b\oplus c$$$ is the XOR of the other two legs in the triangle, and it is well-known that $$$x+y\geq x\oplus y$$$ for all positive integers $$$x, y$$$, the triangle is degenerate if and only if $$$x+y=x\oplus y$$$ for some legs $$$x, y$$$ of the triangle, i.e. $$$x+y < x\oplus y$$$ is not a possibility. I will be using this assumption implicitly throughout my solution.

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

For the rest of the post, let $$$lastVal$$$ be the value of $$$b_{i-1}\cdots b_0$$$, mod $$$998244353$$$. It is easy to compute $$$lastVal$$$ for all $$$i$$$ using a simple for loop, adding $$$2^i$$$ wherever $$$b_i$$$ is set in the binary string.

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

In this case, since the $$$i$$$th bit of all of $$$a,b,c$$$ are $$$0$$$, it is obvious that $$$a,b,c < n$$$, so $$$a,b,c$$$ are just arbitrary $$$i$$$-bit numbers. Let $$$d=a\oplus b$$$ and $$$e=a\oplus c$$$. Then, the legs of the triangle have lengths $$$d, e, d\oplus e$$$. Again, $$$d$$$ and $$$e$$$ are just arbitrary $$$i$$$-bit numbers, since $$$a,b,c$$$ are arbitrary $$$i$$$-bit numbers. Overall, there are $$$2^i\cdot 2^i$$$ possible values of $$$(d, e)$$$, and there are three cases where the triangle is degenerate:

  • $$$d+e=d\oplus e$$$: This happens when $$$d$$$ and $$$e$$$ are disjoint, i.e. there is no $$$j$$$ where both $$$d$$$ and $$$e$$$ have their $$$j$$$th bit set to $$$1$$$. There are $$$3^i$$$ possibilities where this could occur, because there are $$$3$$$ possibilities for each bit: each of the $$$i$$$ bits are either in $$$d$$$, in $$$e$$$, or in neither.
  • $$$d+(d\oplus e)=e$$$: This happens when $$$d$$$ is a subset of $$$e$$$, i.e. there is no $$$j$$$ where $$$d$$$ has its $$$j$$$ th bit set but $$$e$$$ does not have its $$$j$$$ th bit set. There are $$$3^i$$$ possibilities where this could occur, because there are $$$3$$$ possibilities for each bit: each of the $$$i$$$ bits are either in $$$d$$$, in both $$$d$$$ and $$$e$$$, or in neither.
  • $$$e+(d\oplus e)=d$$$: This happens when $$$e$$$ is a subset of $$$d$$$, similar to above case, there are $$$3^i$$$ possibilities where this could occur.

Now, we need to account for the intersections of these cases:

  • Both $$$d$$$ and $$$e$$$ are disjoint and $$$d$$$ is a subset of $$$e$$$ when $$$d=0$$$ -> $$$2^i$$$ possibilities
  • Both $$$d$$$ and $$$e$$$ are disjoint and $$$e$$$ is a subset of $$$d$$$ when $$$e=0$$$ -> $$$2^i$$$ possibilities
  • $$$d$$$ is a subset of $$$e$$$ and $$$e$$$ is a subset of $$$d$$$ when $$$d=e$$$ -> $$$2^i$$$ possibilities

Finally, all three cases occur at the same time when $$$d=e=0$$$ -> $$$1$$$ possibility

Thus, total number of pairs $$$(d,e)$$$ which lead to a degenerate triangle is: $$$4^i-3^i-3^i-3^i+2^i+2^i+2^i-1=4^i-3\cdot 3^i+3\cdot 2^i-1$$$

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

Without loss of generality, assume $$$a$$$ has $$$i$$$ th bit set to 1 and $$$b$$$ and $$$c$$$ have $$$i$$$ th bit set to 0. (We'll multiply the answer from this case by $$$3$$$ at the end to account for this arbitrary choice.)

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

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

Теги #dp, #bitmasks, #xor

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en15 Английский 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 Английский Noble_Mushtak 2022-07-25 05:21:59 0 (published)
en13 Английский Noble_Mushtak 2022-07-25 05:20:29 913
en12 Английский Noble_Mushtak 2022-07-25 05:15:50 40
en11 Английский Noble_Mushtak 2022-07-25 05:14:25 2535
en10 Английский Noble_Mushtak 2022-07-25 05:04:05 355
en9 Английский Noble_Mushtak 2022-07-25 04:51:55 691
en8 Английский Noble_Mushtak 2022-07-25 04:47:42 1088
en7 Английский Noble_Mushtak 2022-07-25 04:39:17 2329
en6 Английский Noble_Mushtak 2022-07-25 04:29:52 1572
en5 Английский Noble_Mushtak 2022-07-25 04:22:39 392
en4 Английский Noble_Mushtak 2022-07-25 04:20:35 33
en3 Английский Noble_Mushtak 2022-07-25 04:20:04 2129
en2 Английский Noble_Mushtak 2022-07-25 04:10:49 673
en1 Английский Noble_Mushtak 2022-07-25 04:06:38 1682 Initial revision (saved to drafts)