FENWITER - Editorial

editorial
, , , ,
1

PROBLEM LINKS

Practice
Contest

DIFFICULTY

easy

PREREQUISITES

binary indexed tree, knowledge of binary base system and bitwise operations

PROBLEM

The question asks you to find the number of iterations required in a query operation on a binary indexed tree, aka Fenwick tree.

Let A be the array of integers of size n. In binary indexed tree, you store an additional array BIT as follows - BIT[i] denotes sum of A[j] + A[j + 1] | \dots + A[i], where j = i \, \& \, (i + 1).

The query operation for finding sum of A_0 + A_1 + \dots + A_i can be performed as given in the below pseudo code.


    def query(i):
        let sum = 0
        while (i >= 0):
            sum += BIT[i]
            let j = i & (i + 1)
            i = j - 1;

The query index i is given in a special way. Index i is obtained by concatenating three strings a, b, c in the following way - a + n * b + b. Here n is an integer, which denotes that string b is concatenated n times.

QUICK EXPLANATION

Number of iterations required in query for a fixed i will be total number of 1’s in the binary representation of i - number of 1’s in the suffix of i + 1. These quantities can be found easily with some simple logic.

EXPLANATION

Understanding the i \& (i + 1) operation

Let us first understand the operation i \& (i + 1). We enumerate first few values of it.

i = 0, \, 0 \, \& \, 1 = 0
i = 1, \, 1 \, \& \, 2 = 01 \, \& \, 10 = 00 = 0
i = 2, \, 2 \, \& \, 3 = 10 \, \& \, 11 = 10 = 2
i = 3, \, 3 \, \& \, 4 = 011 \, \& \, 100 = 000 = 0
i = 4, \, 4 \, \& \, 5 = 100 \, \& \, 101 = 100 = 4
i = 5, \, 5 \, \& \, 6 = 101 \, \& \, 110 = 100 = 4
i = 6, \, 6 \, \& \, 7 = 110 \, \& \, 111 = 110 = 6
i = 7, \, 7 \, \& \, 8 = 0111 \, \& \, 1000 = 0000 = 0
i = 8, \, 8 \, \& \, 9 = 1000 \, \& \, 1001 = 1000 = 8

From first look, it seems that for i = 1, 3, 7 the values of j are all zeros. The numbers 1, 3, 7 contain only digit 1 in their binary representation. This is not a coincidence. If i contains all 1’s, then (i + 1) will be 1 following by zeros. Now, you can see that i \, \& \, (i + 1) will be zero.

Let us understand what this operation does in general. Let binary representation of i be x11.. s.t. x is some binary number whose last bit is 0, and let number of trailing 1’s in i be y.

i = x11..11

Binary represention of i + 1 will be (x + 1)00.., where number of zeros will be equal to number of trailing ones in zero (i.e. equal to y).

i + 1 = (x + 1)00..00

Now i \, \& \, (i + 1) will be (x \& (x + 1))000...

i \, \& \, (i + 1) = 
                                                x      11..11
                                            & (x + 1)  00..00

Note (x \& (x + 1)) will be x \& x = x, as x ends up with bit 0.

                                                x      11..11
                                            &   x      00..00
                                            =   x      00..00

So, we get i \, \& \, (i + 1) = x00..00.

Understanding the operation (i \, \& \, (i + 1)) - 1

Now let us see what will be (i \, \& \, (i + 1)) - 1. It will be x00..00 - 1. It becomes (x - 1) 11..11.

So if i = (x - 1) 11..11, then value of i after next iteration will be (x - 1) 11..11

Finding number of iterations in a query

Let us see what happens when you go to x - 1 from number x, where x ends up zero. Let the x be y000 where y ends up 1. Then x - 1 will be (y - 1)111, i.e. the last 1 of x is reset to 0 and all the digits followed by this gets converted to 1’s.

Hence, in each iteration, the prefix of 1’s at the end stays the same. The last 1 bit in the remaining initial part gets converted to zero, follwed by all the digits equal to 1, i.e. the length of suffix of 1’s keeps on increasing till all the bits become equal to 1. After that the next value of i will be become -1.

Example:

10010011
100\textbf{011}11
\textbf{0111}1111
\textbf{1}1111111
-1 \text{ (iteration stops)}

So, we see that number of iterations required in query for a fixed i will be total number of 1’s in the binary representation of i - number of 1’s in the suffix of i + 1.

Solving the final problem

The final problem asks us to solve the question for i such that binary representation of i is obtained by concatenating a + n * b + b where a, b, c are binary strings.

Let s = a + n * b + c.

So we want to find total number of 1’s in s, length of suffix of 1’s in s for solving the problem.

Total number of 1’s in s will be cnt_a + n \cdot cnt_b + cnt_c where cnt_a, cnt_b, cnt_c denote the count of 1s in a, b, c respectively.

Length of suffix of 1’s can also be found as follows. Let suf_a, suf_b, suf_c denote the count of suffix of 1s in a, b, c respectively. Let suf_s denotes length of suffix of 1’s in s. We can find suf_s by the following pseudo code.

if suf_c < len_c, then suf_s = suf_c
else if suf_b < len_b, then suf_s = suf_b + suf_c
else suf_s = suf_a + n * suf_b + suf_c

Time complexity of the above solution will be \mathcal{O} (|a| + |b| + |c|).

EDITORIALIST’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.

2 Likes
2

The setter’s and the tester’s solution aren’t visible. Kindly look into it. Thank you.

3

Please correct this line in problem statement Index ii is obtained by concatenating three strings a,b,c in the following way - a + n ∗ b + b . Here nn is an integer, which denotes that string bb is concatenated nn times.

It should be a + n ∗ b + c

4

@dpraveen @admin. Can you please explain this part of code in the editorialist solution

if (cs == 0) ans++;
else if (cs < strlen(c)) ans -= cs - 1;
else if (bs < strlen(b)) ans -= cs + bs - 1;
else ans -= cs + n * bs + as - 1;

Why are we adding ans++ for cs==0 and -1 for all other cases?.

Understood… (tot 1s’ in i) - (len of suffix 1s in i) +1 in the result expression.

5

What is number of 1’s in the suffix of i+1 ??