You are not logged in. Please login at www.codechef.com to post your questions!

×

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.

asked 19 Dec '14, 03:01

k3k33's gravatar image

3★k3k33
1112
accept rate: 0%


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.

link

answered 19 Dec '14, 03:11

xellos0's gravatar image

7★xellos0
5.9k54292
accept rate: 10%

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

(19 Dec '14, 03:28) k3k333★

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.

link

answered 19 Dec '14, 13:42

the65bit's gravatar image

4★the65bit
1.1k101328
accept rate: 13%

edited 19 Dec '14, 13:44

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

link

answered 19 Dec '14, 13:43

fauzdar65's gravatar image

2★fauzdar65
29114
accept rate: 21%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×204
×141

question asked: 19 Dec '14, 03:01

question was seen: 3,457 times

last updated: 19 Dec '14, 13:44