You are not logged in. Please login at www.codechef.com to post your questions!

×

ANDTUPLE - Editorial

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

This question is marked "community wiki".

asked 26 Oct '14, 14:25

pkacprzak's gravatar image

5★pkacprzak ♦♦
73484390
accept rate: 12%

edited 16 Jun '15, 11:29

vicky002's gravatar image

1★vicky002 ♦♦
2561312

2

very bad editorial one hour wasted please try to be clear

(27 Oct '14, 22:10) winky2★

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

link

answered 26 Oct '14, 14:30

neo1tech9_7's gravatar image

6★neo1tech9_7
8.5k51537
accept rate: 19%

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.

link

answered 27 Oct '14, 17:08

yogeshkr0007's gravatar image

3★yogeshkr0007
111
accept rate: 0%

Answer is hidden as author is suspended. Click here to view.

answered 24 Jun '15, 15:44

lionelanand10's gravatar image

2★lionelanand10
(suspended)
accept rate: 0%

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), \text{if $N$ even}\\ f\left(\frac{N-1}{2}\right) + f\left(\frac{N - 3}{2}\right), \text{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), \text{if $N$ even}\\ g\left(\frac{N-1}{2}\right) + g\left(\frac{N - 3}{2}\right), \text{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

link

answered 25 Feb '17, 19:17

afaxnraner's gravatar image

6★afaxnraner
5665
accept rate: 25%

edited 25 Feb '17, 20:48

If n=5 and k=3, according to the formula 1+(n/2) the answer is 3. 2 of these tuples are (5,0,0) and (3,1,1). Which tuple am I missing?

link

answered 26 Oct '14, 14:32

michelangelo's gravatar image

4★michelangelo
1.1k21522
accept rate: 39%

2

(3,2,0) is also valid

(26 Oct '14, 14:33) neo1tech9_76★

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.

link

answered 26 Oct '14, 16:44

yogeshkr0007's gravatar image

3★yogeshkr0007
111
accept rate: 0%

edited 26 Oct '14, 16:45

2

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

(26 Oct '14, 19:06) pushkarmishra4★

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.

(26 Oct '14, 19:13) yogeshkr00073★

Where is max_carry initialized in above pseudo code??

Can you elaborate more on the DP solution formation. Thanks

link

answered 26 Oct '14, 23:00

vivekvelankar's gravatar image

2★vivekvelankar
1
accept rate: 0%

edited 26 Oct '14, 23:10

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.

(27 Oct '14, 16:56) yogeshkr00073★

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

link

answered 27 Oct '14, 20:25

bajaj6's gravatar image

2★bajaj6
39135
accept rate: 0%

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

link

answered 16 Dec '14, 00:37

tdk93's gravatar image

3★tdk93
3026
accept rate: 0%

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?

link

answered 16 Dec '14, 00:51

tdk93's gravatar image

3★tdk93
3026
accept rate: 0%

edited 16 Dec '14, 00:53

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×14,366
×1,754
×1,398
×331
×286
×104
×48

question asked: 26 Oct '14, 14:25

question was seen: 4,204 times

last updated: 25 Feb '17, 20:48