ANDTUPLE - Editorial

bit
dynamic-programming
easy-medium
editorial
ltime17
memoization
recursion

#1

PROBLEM LINK:

Practice
Contest

Author: Piyush Kumar
Tester: Minako Kojima
Editorialist: Pawel Kacprzak

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

Bits, Recursion, DP, Memoization

PROBLEM:

You are given two integers N and K, where n ≤ 1018 and k = 3 or 4. The task is to count number of k-tuples a1, a2, …, ak where a1 + a2 + … + ak = n
and for each i = 0, …, k - 1, ai ^ ai+1 = ai+1. We call the first condition the pairwise condition and the second the sum condition.

QUICK EXPLANATION:

In order to fulfil the pairwise condition, you can notice that there are only 4 (k = 3) or 5 (k = 4) valid combinations for every bit of a tuple elements.

Based on that fact, you can use recursion starting from the leftmost bit of n and try to cover 1’s with possible valid combinations of corresponding bits of elements a tuple. If you decide to not cover a particular 1 with a weight b, you carry it to the next position and try to cover 2 ones with a weight b - 1 instead.

EXPLANATION:

For k = 3 there exists a very simple solution (see Alternative solution), but the below method is general and works for any k, even bigger than 4.

Without a loss of generality we assume that k = 3. The solution for k = 4 is analogous.

We say that a tuple is valid if the pairwise condition is fulfilled.

Let’s consider the i-th bit. There are only 4 combinations of bits at position i in a valid tuple:

       1  2  3  4    
a_1:   0, 1, 1, 1    
a_2:   0, 0, 1, 1    
a_3:   0, 0, 0, 1    

You can see that any tuple formed by values in above columns is a valid tuple and moreover any other tuple is invalid.

In order to fulfil the sum condition, i.e. a1 + a2 + a3 = n, we can use recursion starting from the leftmost bit of n and try to cover 1’s in the binary representation of n with the above combinations. Any 1 at position i can be covered by elements of a tuple at position i or later. Let’s define a recursive function:

solve(b, carry) := number of valid tuples covering both: the rightmost b bits of n 
and a value carry * 2^b. 

Let’s see an example for n = 3:

bit      2 1 0
n = 2    1 0 1

We start with b = 2 i.e. from the leftmost bit and call solve(2, 0), because there is no carry at the beginning. We see there is a 1here, so we have to cover it in a tuple. In order to do that, we can use the second combination from the above table and add solve(1, 0) to the result or decide to cover that bit later and add solve(1, 2) to the result covering a bit with a weight 2 with 2 bits with weight 1. Let’s consider the second situation. There is a 0 at position 1, so we have to cover only carried bits. We can use the third combination from the table to cover all of them or the second one to cover only one or the first one to decide to cover them later. Depending on our choice, we call the next recursion.

The bases case of recursion is when there are no more bits to cover, so when b = -1. In this situation, we return 1 if carry = 0 otherwise we return 0

In my solution, maximal carry is 4 * 64 in a case where k = 4, because n does not have more than 64 bits and we have exactly 4 elements in a tuple, so there are no more than 4 * 64 positions where we can put a 1, but with a more precise analysis, you can use a smaller maximal carry.

In order to avoid computing the result form solve(b, carry) many times, we use memoization to store already computed results.

Pseudo code

solve(b, carry)
    if(b == -1)
        return (carry == 0)
    if(carry > max_carry)
        return 0
    if(mem**[carry] is already computed)
        return mem**[carry]
    new_carry = carry
    if(n & (1LL << b)) 
        new_carry++
    for(d = 0; d <= min(carry, k); ++d)
        mem**[carry] += solve(b - 1, 2 * (new_carry - d))
    return mem**[carry]

Time complexity

O(64 * 64 * k) for one test case.

Alternative Solution:

For k = 3 there exists a simple formula that the result is 1 + (n/2). You can see a tester solution for more details.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.

RELATED PROBLEMS:


#2

Is there a proof for the alternative solution of k = 3 ??


#3

It seems quite obvious there exists O(1) solution for k=4 as well and also for greater k (though very tough to find for greater k by mere observation).
@ piyush/minako/pawel:: does anyone of you have the constant time solution/formula for k=4.


#4

Where is max_carry initialized in above pseudo code??

Can you elaborate more on the DP solution formation.
Thanks


#5

EXPLAINATION OF DP SOLUTION::
solve(X,Y)==> no. of ways to put Y 1s in total in the k binary number`s Xth bit.

Basically what is done here is that say when we are on Nth bit , and also we have the new_carry which is the no. of 1s we need to put in total in this Nth bit of k binary numbers .

d is the number of bits we succeeded in putting in Xth position so remaining got carried further. The carried further is twice of not done at previous position because the place value is halved for the next digit, so for missing to put 3 1s we need to put 6 1s in next position.
Base case is used after last place i.e. after b=0.


#6

can someone please explain what does this mean
“Let’s consider the i-th bit. There are only 4 combinations of bits at position i in a valid tuple:…” and also what it that matrix a_1,a_2,a_3 …???

Thanks


#7

Why are we initilaizing recursion from the left bit? Wouldn’t starting from right be more intuitive and easier to code?


#8

Let’s see an example for n = 3:
bit 2 1 0
n = 2 1 0 1

This might be a stupid ques but
since n = 3 shouldn’t bits be 11 instead of 101 as mentioned above?


#9

Here’s a much easier solution.

Case k == 3: Lets call the function, that returns the number of and-tuples of size three, f. So we want to compute f(N). First we look at the last bit of N. If the last bit is 0, it has to be generated in two ways: The last bits of the tuple has to be (0, 0, 0) or (1, 1, 0). Notice that (1, 0, 1) would not valid, because it violates the definition of the and-tuple. There are exactly f\left(\frac{N}{2}\right) and-tuples are there with the last bits (0, 0, 0) and there are exactly f\left(\frac{N - 2}{2}\right) and-tuples with the last bits (1, 1, 0). And if the last bit is 1, we the last bits of the and-tuple has to be (1,0,0) or (1,1,1). This gives us the formula:

f\left(N\right) = \begin{cases} f\left(\frac{N}{2}\right) + f\left(\frac{N - 2}{2}\right), ext{if $N$ even}\\ f\left(\frac{N-1}{2}\right) + f\left(\frac{N - 3}{2}\right), ext{if $N$ odd} \end{cases}

with start values f(0) = f(1) = 1.

Case k == 4: The solution is pretty identical. The only difference is that we have three cases if the last digit of N is 0.

g\left(N\right) = \begin{cases} g\left(\frac{N}{2}\right) + g\left(\frac{N - 2}{2}\right) + g\left(\frac{N - 4}{2}\right), ext{if $N$ even}\\ g\left(\frac{N-1}{2}\right) + g\left(\frac{N - 3}{2}\right), ext{if $N$ odd} \end{cases}

To make this recursive definition fast, we apply DP using a map to store already computed values.
Link to implementation: Submission 12928359


#10

what makes you think that there necessarily exits a O(1) formula for k=4?


#11

since the formula is from pattern here.
analysing the reason of of existence of pattern for k=3 , there must exist a pattern for k=4 due to exactly similar reason , and for k>4 as well.


#12

max_carry is the maximal carry that can be possibly covered in further bits , it is less than 4*64.
this condition is used so that whenever the function makes a call in last loop for a carry greater than max. possible then 0 is returned , saving lots of time,actually preventing the recursion from running forever.


#13

very bad editorial one hour wasted please try to be clear