Hi Friends,
I want to understand the time limit of codechef, for the above problem it is stated as 1sec. Algorithm provided in the editorial runs in O(K * 2^N * N) per test case. So for entire test case, it needs T * O(K * 2^N * N) = 10 * 8 * 2 ^ 21 * 21 = 3523215360, approx ~ 3 * 10 ^9.
Doesn’t the editorial solution exceeds the time limit. Please clarify ?. What is meant by 1 sec time limit in codechef ?.
hey hi…
first check this out mysolution with 10^9 iteration
and its passing codechef server.
Now i’ll tell you the possible reason. Well acc. to me processor comes into consideration, when you are running a loop of large number, there is a branch prediction algorithm running in processor, which at each step predict whether the condition is true or false and fill the pipeline accordingly. so in large for loop, static prediction comes into picture and thus process consumes cycle and process data fast.
But when we actually make an algorithm, it contains branches and function, relative pointers, memory stack, so many cycles are wasted or say consumed in this thats why there is a difference in time limit for different codes with same complexity
Generally a program with a*10^8 will pass server on codechef in one sec. where a is some constant. if your program structure is best suitable for processor, a can me greater than 10.
so this was a general case. Now in this problem sanskar , i was also in dilemma before submitting solution with this complexity, so maybe testcases are designed keeping in mind the constant, or keeping value of k low when n is max.
even if we see the solution, my justification about this is it uses a loop, maybe suitable and faster for processor 
M sorry if i wasn’t helpful. but i read all this and discussed this with my friends somewhere in past, and i believe its kinda true 
Hi, It was helpful indeed. New learning for me “Branch predictor”. I was in a notion that codechef only allows 10^8 operation per sec. I know topcoder allows 10^9 operation per sec. I don’t have reputation points to upvote your answer :p. But thank you it was helpful +1. But I find even simple backtracking solution have passed right?.
your welcome 
actually backtrack is also having same complexity 2^N , but difference is in stack … you might see the difference in time for both solution, i guess backtrack will be slower with same complexity
and my solution was also a bruteforce , it was kind a backtrack, What i did was, just find a case where sum (arr[i] + arr[j] +. … ar[x] ) == average… and then apply backtracking on remaining array indexes not selected is last select… in this way i’ll have k sets if its valid