EQDIV - EDITORIAL

[naman_narula]

I don’t know why there is no solved example for this question.It is difficult to comprehend and think in theorems and proofs.At least an example for the ideas that constitute the solution would be helpful.

[bohdan]

There are three sample case explanation in statement, isn’t it enough?

[naman_narula]

Explanation of each concept with example that built the solution helps in understanding.That is what i was trying to convey

[bohdan]

There is example of first concept, and you need to refer to code to see how second is working. What’s more to explain?

[forwet123]

Hey @bohdan! Nice work! Can you please throw some more light on

dp[i] = (d[i-1] << cost[i] )| (dp[i-1] >> cost[i]).

What’s the intuition behind it. Thanks!

[bohdan]

We can either add current pile to the first group (thus difference increase), or to the second (decrease).

[jaynilshah]

Can u explain how this sequence can be used to prove the fact

[jay_1048576]

If you take the k-th powers of any 2^k+1 consecutive numbers and apply addition for the digit 1 in the corresponding bit of the k-th term of the sequence and subtraction for the digit 0, then the final answer will always be zero. This is by induction that the left half of the numbers cancel out the effect of the right half of the numbers.

[nitin3000]

Very nice solution Ritesh. You can get rid of the while loop to calculate the extra assignments. Basically extra will be extra = n- max_ar_length[k] / cycle_length[k]

[zephxr]

@bohdan

Let’s calculate it’s complexity. First dimension of dp will have N elements, while second should have 2∗(1^K+2^K+...+N^K) , which is O(N^{K+1})

Can anyone explain the editorial from this point to the end of the editorial in simple language.
Not able to understand anything after this.
please help!

[bohdan]

From earlier part of editorial: We can do standard knapsack-like boolean dynamic programming dp[i][j] - is it possible to distribute numbers from 1^K, 2^K, 3^K, … , i^K between two groups A[i] and B[i], such that Sum(A[i]) - Sum(B[i]) = j?
Obviously, complexity will be (as explained above) O(N^{K+1}).
What exactly can be unclear here?

[zephxr]

Thanks for replying @bohdan,

All the stuff you wrote in the reply is clear to me but its not clear to me from here:

@bohdan

So in total, we will have O(N^{K+2}) states and two transitions from each state (we can either add current number to the first group or to the second). After using bitsets, complexity will become O(N^{K+2}/64) both time and memory.

I know that memory is too high to do standard knapsack even for k=3.i didn’t got the point what we are doing in this case.

[bohdan]

What is unclear in these lines? We have O(N^{K+1}) * N = O(N^{K+2}) states, and obviously two transitions from each state, thus get complexity O(N^{K+2} / 64) after using bitsets. As for me, it is quite easily deduced from what was written above it. Try read all the editorial.

[zephxr]

I misunderstood the total time complexity as O(n^{k+1})

I calculated time complexity like this:

first dimension=N
second dimension= (1^K+2^K+...+N^K) = ({N+1})^k =O(N^k)

So, N * O(N^k) = O(N^{k+1})

please point out where i am going wrong here.

How you concluded the following two:
can you explain a bit please?

why we are multiplying 2 in the following:

@bohdan

while second should have 2∗(1^K+2^K+...+N^K) which is O(N^{K+1})

@bohdan

So in total, we will have O(N^{K+2}) states and two transitions from each state

[bohdan]

(1^K+2^K+...+N^K) = ({N+1})^k =O(N^k)
For K = 1, N = 3 you state that 1 + 2 + 3 = 4.
What? Can you please read editorial carefully before asking such weird questions?

[zephxr]

Actually i am not asking a weird question.
i read it many times but i am lacking in formulas like you pointed out.

can you correct me here?

This is the confusion i am facing,if you are not interested in telling then i have no issues in that.Thanks!