Another solution for problem 1003H (Extended)

Revision en2, by ko0g, 2025-02-10 14:37:31

Hello Сodeforces,

Recently the Div. 4 round was held with quite balanced and beautiful problems. I especially liked Problem H, where I accidentally overkilled the solution. I want to share with you a solution I came up with that supports range queries in $$$O(n + q \log n)$$$.

1. Some observations

Firstly, one should notice that value of $$$f(b)$$$ equals to ( number of $$$i$$$ : $$$b_{i} \neq b_{i+1}$$$ for $$$(1 \leq i < |b|)$$$ ) $$$+$$$ $$$1$$$. For binary strings, that means $$$f(b) = (\text{number of "10"}) + (\text{number of "01"}) + 1$$$.

Secondly, when there are update-queries mentioned in the problem, one should consider using some data structures.

2. Main idea

Suppose we have two binary strings $$$L$$$ and $$$R$$$ and we know the answer for each of them. Now our goal is to figure out how we can combine them to get the answer for the full string.

All subsequences can be represented as follows:

  1. Subsequence starts with "0" and ends with "0" — $$$0\dots0$$$
  2. Subsequence starts with "0" and ends with "1" — $$$0\dots1$$$
  3. Subsequence starts with "1" and ends with "0" — $$$1\dots0$$$
  4. Subsequence starts with "1" and ends with "1" — $$$1\dots1$$$

Let's store $$$2$$$ variables for each type of subsequences: the sum of the $$$f(b)$$$ over all subsequences — $$$S$$$ and the number of all subsequences — $$$C$$$.

3. Combining parts

Firstly, we will combine number of subsequences of each type.

To get $$$\color{red}{0} \dots \color{blue}{0}$$$ we should combine:

  1. $$$\color{red}{0} \dots0$$$ and $$$0\dots \color{blue}{0}$$$
  2. $$$\color{red}{0} \dots0$$$ and $$$1\dots \color{blue}{0}$$$
  3. $$$\color{red}{0} \dots1$$$ and $$$0\dots \color{blue}{0}$$$
  4. $$$\color{red}{0} \dots1$$$ and $$$1\dots \color{blue}{0}$$$

Hence,

$$$ C(0 \dots 0) = C_{L}(0 \dots 0) + C_{R}(0 \dots 0)$$$ $$$+$$$
$$$+$$$ $$$( C_{L}(\color{red}{0} \dots 0) \cdot C_{R}(0 \dots \color{blue}{0})) + ( C_{L}(\color{red}{0} \dots 0) \cdot C_{R}(1 \dots \color{blue}{0}))$$$ $$$+$$$
$$$+$$$ $$$( C_{L}(\color{red}{0} \dots 1) \cdot C_{R}(0 \dots \color{blue}{0})) + ( C_{L}(\color{red}{0} \dots 1) \cdot C_{R}(1 \dots \color{blue}{0}))$$$

The same principle applies for the rest of the types.

Secondly, we will combine sum of subsequences of each type.

There are two cases:

$$$ f(L+R) = \begin{cases} f(L) + f(R) & \text{if last element of } L \neq \text{first element of } R \\ f(L) + f(R) - 1 & \text{if last element of } L = \text{first element of } R \end{cases} $$$

Hence, the sum of $$$f(b)$$$ over all $$$0 \dots 0$$$ is:

$$$S(0 \dots 0) = $$$
$$$ = S_{L}(0 \dots 0) \cdot C_{R}(0 \dots 0) + C_{L}(0 \dots 0) \cdot S_{R}(0 \dots 0) - \color{red}{C_{L}(0 \dots 0) \cdot C_{R}(0 \dots 0)} +$$$
$$$ + S_{L}(0 \dots 1) \cdot C_{R}(1 \dots 0) + C_{L}(0 \dots 1) \cdot S_{R}(1 \dots 0) - \color{red}{C_{L}(0 \dots 1) \cdot C_{R}(1 \dots 0)} + $$$
$$$+ S_{L}(0 \dots 1) \cdot C_{R}(0 \dots 0) + C_{L}(0 \dots 1) \cdot S_{R}(0 \dots 0) + $$$
$$$ + S_{L}(0 \dots 0) \cdot C_{R}(1 \dots 0) + C_{L}(0 \dots 0) \cdot S_{R}(1 \dots 0)$$$

The contribution of each subsequence from the $$$L$$$ is $$$S_{L} \cdot C_{R}$$$ and vice versa. Note that we $$$\color{red}{\text{substract}}$$$ contribution of all subsequences $$$C_{L} \cdot C_{R}$$$ in case edge-elements are equal.

The same principle also applies for the rest of the types.

Tags divide and conquer, data structures, div4, segment tree

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en7 English ko0g 2025-02-11 10:10:38 152
en6 English ko0g 2025-02-10 21:48:54 169
en5 English ko0g 2025-02-10 14:50:03 80 (published)
en4 English ko0g 2025-02-10 14:47:16 241
en3 English ko0g 2025-02-10 14:46:32 693
en2 English ko0g 2025-02-10 14:37:31 1966 Tiny change: '}{0}))$.\n' -> '}{0}))$.\n\nThe same principle applies for the rest of the types.'
en1 English ko0g 2025-02-10 14:13:47 2310 Initial revision (saved to drafts)