There’s a different approach i found.
CHECK MY APPROACH : CodeChef: Practical coding for everyone
I just made a recursive program to find best solution and the found pattern in the solution. But for k =4, i couldn’t figure out some numbers.
1 Like
It is not different, it is the same, just with hardcoding everything ( I guess your recursion is either bruteforce or similar to dp).
1 Like
Can you please provide me proof of why the answer would be 0 or 1 for large value of N (N>2^(k+1))
This sequence may be used to find how can the Kth powers of any 2K+1 consecutive numbers be divided into two groups such that both the groups have equal sum.
This is exactly what is written in editorial.
1 Like
can you please explain the algorithm in detail?
I did the same ;D
1 Like
The dp solution is intuitive. Although I could not solve, but people have simply used patterns.
Like for k=1, there is a pattern of length 4, with minimum difference in pattern 1 0 0 1
Similarly k=2, had a pattern of length 8, with difference with minimum pattern 1 0 0 1 for n>5 and the repeat for any number >16 would be. Answer of (n-8)+ pattern.
Similary k=3 had a pattern of 16 length and it repeated after 28 and k=4 had a pattern of 32 length.
How did you calculate for K = 4?
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?
Difficulty Level : Medium.
Okay …
What’s wrong? It must be either medium or easy-medium by all estimations.
1 Like
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 
1 Like
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
1 Like
Or you can used __in128. But at all, 32-bit data types was enough.
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.
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.
3 Likes
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.
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.