CHESUB - Editorial

editorial
, , ,
45

thanks;

46

@cherry0697 why this line is neccessary?
dp[i][j] = max(dp[i][j], -inf);
and I am getting WA on using LONG_LONG_MIN instead of -(1e18)
what difference is this making?
Anyone help me with these 2 questions please.

47

In both programs, I used recursion, can anyone say what I have done wrong in c++ program.

my links :
CodeChef: Practical coding for everyone
CodeChef: Practical coding for everyone

48

Yeah, you pointed out correct. Thanks. I also got AC after changing vector dp to static array dp.

Its pathetic. They should have kept the time limit a little lenient because without this optimization, this code would have just took maybe around 1.5s. Costed me 50 points and a chance to get an under 50 rank.

Thank you very much again

1 Like
49

Can anyone tell me why i am getting tle ? Its complexity is O(nxkx2) .

Link :- https://www.codechef.com/viewsolution/47302069

50

because the time complexity should be n*k

51

Sorry for above its not k square its n into k into 2

52

I thought in short contests, people don’t have time to cheat. But these legends proved me wrong :wink:

53

the problem is when you are filling table array you are taking constant operations of 1e51e2 = 1e7 and as test case can be 1e3 so in the worst case the number of operations can be 1e10 and ideally it should be at max 1e8 for the given time constrain which is causing you tle if you change 1e5 with ‘n’ then the number of operation at worst case will be 1e51e2 = 1e7 as the sum of n over all test case is 1e5 which is ideal. your accepted code

54

Woo! Thanks a lot

55

Can anybody please check where my code goes wrong?
Here’s the submission link:
https://www.codechef.com/viewsolution/47296034

Thanks

56

Thanks a lot for such a detailed explanation , Now I understood why the third state was taken and the recursion part also.
Thanks a lot once again :slight_smile:

57

why this line is neccessary?
dp[i][j] = max(dp[i][j], -inf);
and I am getting WA on using LONG_LONG_MIN instead of -(1e18)
what difference is this making?

58

@king_rayuga
why this line is neccessary?
dp[i][j] = max(dp[i][j], -inf);
and I am getting WA on using LONG_LONG_MIN instead of -(1e18)
what difference is this making?

59

Same here I too was amused too see how hard they tried to hide their cheat!
XD

60

welcome

61

Best editorial.

1 Like
62

Hey I think we can easily reduce the space complexity to O(n) by only storing dp[i-1][j] and dp[i][j] in the same array, similarly for p array.
check my sol at CodeChef: Practical coding for everyone

image
image1053×367 28.1 KB

2 Likes
63

Time limit too tight for top down solution??

solution

64

Your solution passes for a file when N=1e5 but gives you TLE when N \le100. I mean to say that time complexity for your solution doesn’t depend on N but on T.

When the value of T is large you get a TLE verdict as your time complexity for any test file is O(T*10^5*100). Irrespective of the value of N you are always using N as 1e5. That is the reason for your TLE