This is the link to the editorial of the question AlokNath and sanskars,in this month's long challenge. http://discuss.codechef.com/questions/58420/sanskareditorial?sort=votes&page=2 The complexity given is O(K * pow(2,N) * N) for a single test case. Now, with given k=8 and N=21, the total instructions to be executed become 10 * 10^6 * 20 (taking k as 10 and n as 20), which gives 2*10^8 instructions. Further there are 10 test cases. How can such a huge set of instructions get executed in 1 sec. Please help. I am not able to understand this timing concept at all. asked 19 Dec '14, 03:01

I agree with you. The expected instruction will be nearly O(2*10^9), so probably I will also think before making the code of this algorithm, thinking there should be some efficient algorithm. Although I didn`t took part in the contest, but I had a look at the problems and I expected an O(2^N * K * T), which will be near to O(10^8). May be the test cases were weak that they are passing the solution, because according to given constraints there should be at least one file with 10 test cases and each test case having K=8 and n=21. answered 19 Dec '14, 13:42

The test cases didn't have cases with maximum constraints. Most probably no. of test cases was equal to 1 when n and k were large. Otherwise , my solution wouldn't pass as it takes 7 seconds for the worst case when (t,n,k) are maximum . And even the official solution takes over 7 seconds . I've checked it here : http://ideone.com/EtDTSI answered 19 Dec '14, 13:43
