Alok Nath Sanskar problem

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/sanskar-editorial?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.

Why do you assume all cases are large? For example, in the last input file, there were some cases with K=1.

Moreover, the constant factor for this algorithm is smaller than usual (due to bitwise operations and such), so that kind of complexity seems perfectly okay to me.

O-notation means “how the time taken by the algorithm depends on input parameters, if they’re large, worst case, ignoring constants”. It’s not the runtime, only an estimate of it. The number of operations can be 10^9 or 10^7 depending on what your code does, possible breaks, slow parts like reallocation or flushes, etc. But the best thing you can do if you don’t have a better idea is submitting and actually checking how much time your code takes - maybe it’ll be good enough.

3 Likes

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.

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 : EtDTSI - Online C++0x Compiler & Debugging Tool - Ideone.com

Can you tell what constant factor are you talking about which you said is smaller than usual??