Why is my code giving TLE?

Problem link - KFOLD - https://www.codechef.com/COOK121B/problems/KFOLD.
My solution - https://www.codechef.com/viewsolution/37109035

I believe the time complexity of my code is O ( T*(N + 3K + N/2K ) ) ,
where T<=100 and K<=N <=1000 . I believe it should run within 1 sec . Please help me find out my mistake !

Edit - I commented the same thing on the main editorial of this problem but no one replied, so had to create this thread :frowning:

1
6 1
000111

Answer

Correct answer is string itself.

hey, your’s solution giving WA on the above test case, i recommend you to try out some more test cases , maybe you figure out your self what is happening.

Hey, maybe you should read the question carefully. I asked specifically about TLE and NOT WA.

When the code is indented and commented properly many would answer and also a small suggestion , since the string has only zeroes and ones, it would be better to use two simple variables to store their count instead of a map. same goes when its a string of lowercase or uppercase letters,array of length 26 will suffice. This is important because complex data structures have significant constant time opertions internally which make less time efficient sometimes.

1 Like

Consider the test input:

1
1000 1
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
2 Likes

You are doing something like res+=res. Suppose initially, res is only β€œ1”. In the first step it is appending the string β€œ1”, in the second step, it’s appending β€œ11”, in the third step, β€œ1111”,… In general, in the i-th step, it is appending a string of length 2i-1. So, even if n/(2*k) is more than 30 (which can be upto 500), it will give TLE.

1 Like

here check this link out i tried to fix your code and also commented the bugs
–>>https://www.codechef.com/viewsolution/37117122

2 Likes

Yea, i saw that statement but thought otherwise. Thanks !

Thanks for taking the time out. Really appreciate it <3

I hope you would like this from my end https://www.codechef.com/viewsolution/37117894

yes this looks much better than the previous one, no map and the code is more organized, but whenever you post your code next time in the discussion make sure to document(comments) it so that others understand the logic behind what you have written.

1 Like