EQDIV - EDITORIAL

[echo_abhinav]

take first 20 heaps and find all possible |A-B|(about 10^5) and store in hash table. try to find the same |A-B| in the remaining (n-20) heaps and here n is from 21 to 64 and when brute forcing (n-20) heaps to match with the first 20 heaps it was quite fast as most of the numbers were in close to 2^(n-20) (when read in binary) (basically 111111111…10101)

Looks like it is easier to get a match for the first 20 bits because the remaining (n-20) bits you can control the sign of big numbers which can easily give you the |A-B| you got in the first 20 bits

What about you?

[semantycs]

Difficulty Level : Medium.

Okay …

[bohdan]

What’s wrong? It must be either medium or easy-medium by all estimations.

[basant07]

i left the question when i saw max N is 10^6 and k=4.
so max is (10^6)*4=10^24 beyond my limits

[carre]

x^4 - (x-1)^4 = (x^2 - (x-1)^2) * (x^2 + (x-1)^2)

To deal with large number you can just work with difference of consecutive numbers

[bohdan]

Or you can used __in128. But at all, 32-bit data types was enough.

[sudipandatta]

OEIS links -
Squares - A001422
Cubes - A001476
4th Powers - A046039

just generate these series using this algorithm -

MAX is the maximum number that cannot be represented as a sum of distinct squares or cubes or 4th powers respectively. You will find it in given links above.
MAX for k=2 is 128, k=3 is 12758 and k=4 is 5134240.

Create an array with MAX boolean values . Initially set arr[0] = true, all others = false because 0 is the only sum of fourth powers less than 1^k. Then for i = 1, 2, 3, … as long as i^k<=MAX, let p = i^k. Then let j = MAX, MAX-1, … down to p, and for each j set arr[j] to true if arr[j−p] is true.

Then just find the total sum of the series upto N using formulas lets say SUM. Set X=SUM/2.
Run a while loop decreasing X by 1 every turn until arr[X]==true.(Note :- if X> size of array then it is true)
Now X will be one groups sum and another groups sum will be SUM-X (Say Y).
Now run a loop i=N,N-1,…,1. If (arr[X - i^k]==true) then ans[i]=1 and X-=i^k else ans[i]=0.

You will need to use bigint.

This will still give you WA on 3 and 4. You have to make a small tweak. Try it yourself.
Here’s my solution - CodeChef: Practical coding for everyone (Go down to the main function upper part is just bigint library)
The algorithm actually takes 0.01s to generate the series but the time is mainly taken by bigint.

[david_s]

In solving EQDIV I did not run up against any memory or size constraints. I observed the pattern that any 2^(K+1) consecutive piles can be distributed greedily to obtain a balanced distribution. I calculate the 32-bit pattern for K = 4 greedily, and then use a portion of the pattern for smaller K.

Before I describe the algorithm, note that I prepare 2 arrays of length 2^(K+2), one containing each I^K and the other the sum of all J^K for J from 1 to I for each I.

Define M = 2^(K+1), and R = N%M. I prepare an initially undefined cache of the best distribution of the first N + R piles for each R, and the corresponding difference in their sums.

For N < M, I do not cache the result, but instead calculate the best distribution by the function described below.

For N > M, I first copy the repeating pattern to define the distribution of piles from R+1 to N. I then use the cached result for the first R + N piles for this R if it exists. If the cache for this R does not exist I calculate it by the following function.

Function to evaluate best sequence for first few piles, up to 64.

Input: R

Input: Array of length R or R + N. If R + N, last N values are set to repeating distribution.

Output: Smallest difference in sums, and Array fully defined.

First distribute the first R piles greedily, working down from the largest. If the resulting difference is 0 or 1, this is the solution.

Otherwise attempt to find a better distribution by searching a binary tree of possible distributions, working down from the last item in the input array. At each level the pile may be assigned either way. To save unnecessary searching, check if (a) a better distribution is impossible even when all the smaller piles are assigned the other way, or (b) a better distribution is obtained when all the smaller piles are assigned the other way. If (b), and the better distribution results in a difference of 0 or 1, there is no need to search further, else remember the smaller difference and continue searching.

You can see my solution at CodeChef: Practical coding for everyone
which received 100 points in 0.07 seconds.

[godly_display]

@bohdan

What about total complexity of solution? Obviously, first part is O(N)O(N)O(N) per testcase. Second part can be done just once as precalculation. But it’s complexity still is O(MK+2/64)O(M^{K + 2} / 64)O(MK+2/64), where MMM = 2K+22^{K + 2}2K+2. This will be fast enough for KKK <= 333. However, for KKK = 444 we need will have M=64M = 64M=64, thus total complexity will be ~64564^5645, which is actually too much. But we can observe that we can actually reduce size of second dimension of dpdpdp - setting it’s size to some value 2∗S2 S2∗S means that we are searching for such a solution, that all A[i]−B[i]A[i] - B[i]A[i]−B[i] are in range [−S;S][-S; S][−S;S]. You can experiment with this a little bit and ensure that actually SSS = 2∗107210^72∗107 will be enough.

I am not getting this point. Can someone please explain how this is implemented? When I tried to find the solution for n>30 for k=4 using dp, my computer almost froze.

[nishant403]

I did this problem without using any kind of patterns. I don’t have proof of correctness, but proof by AC.

For a given K, I calculate all possible sums using first 34 elements by subset sum DP (coin change type) . Then I store it as absolute difference and a mask of used elements in sorted manner.
(Answer for N < 34 is also stored while calculating this)

Now for a given N, I greedily iterate from N to 35 and each time assign the heap to the one with the lower sum. So till now , partition have say X and Y candies , so I lower_bound on absolute(X-Y) to find nearest difference I can make using 34 elements.

Code : CodeChef: Practical coding for everyone

[bohdan]

Why not refer to implementation given at the end of editorial?

[rahulmysuru7]

take t=8, n=9 to 16,the answers should be 1,1,0,0,1,1,0,0. But ur code will get 1,3,4,3,3,1,0,0

[shreyash_sohan]

bro can u explain your crd3game code in crdgame editorial post @l

[vruttant1403]

ohh got it thanks a lot.

[lanukk]

Sure.

[rajawatlks]

This is one of the best problem i tried in this contest

[sid_tyu_123]

WHY I AM GETTING WRONG ANSWER FOR K=2. I HAVE USED RECURSION IN THIS.
PLEAE SUGGEST SOME MEASURES.IT WILL BE VERY HELPFUL FOR ME TO KNOW THAT WHAT IS WRONG IN MY CODE.
https://www.codechef.com/viewsolution/37889269

[abhi2498]

So basically editorial has done it with tricky maths whereas some people just randomly applied bruteforce for some cases and saw a pattern directly.
for N < 2^(K+1) they just stored it in hard coded strings and rest is all pattern.

[lamda_cdm_10]

That should have been your clue that this problem has some trick inside it!!

[rachit02]

programming competition