Why is my code giving TLE?

help
1

Problem link - KFOLD - CodeChef: Practical coding for everyone.
My solution - CodeChef: Practical coding for everyone

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:

2

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.

3

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

4

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
5

Consider the test input:

1
1000 1
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
2 Likes
6

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
7

here check this link out i tried to fix your code and also commented the bugs
–>>CodeChef: Practical coding for everyone

2 Likes
8

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

9

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

10

I hope you would like this from my end CodeChef: Practical coding for everyone

11

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