I got the ideal but lost with implementations
I am seriously irritated with soo many immediate submissions of CHESUB question. I got a -119, from being 5 star to 4 star because of too many cheaters above me in div1 ,me getting rank 180s. Now, these people won’t be penalized anyway for a long time. And even when they are penalized, my rating changes in not gonna change. This thing is just sad.
@admin ,
It’s a humble request from my side to do as codeforces does, like removing cheaters after each contest and provide the rating changes, which will make it more fair and reduce the number of cheaters in codechef. This mass copying via youtube/telegram groups has created a huge bad name for codechef and also reduces the value of codechef. Thank you.
7 Likes
This problem is very nice and definitely deserves an appreciation.
But its idea is taken from standard problem of maximum sum subarray and extended it to K subarrays maximum sum. so, many can have same type of solution.
Here is my solution ,It might benefit anyone. CodeChef: Practical coding for everyone
1 Like
I think your logic deserved AC.
Here’s your AC Code : # 47294178.
I just replaced the vector dp with static array dp and it worked. Same thing has happened to me on different OJs (and on this problem, yes again while upsolving), but that’s for old problems where time constraints were too strict.
That happens because vector are dynamic in nature and allocate some extra space than required which cause TLE. I’ve read it somewhere on a cf post and you can find more on it on google.
@nikiitp18 @rising_stark Maybe you guys are getting TLEd due to the same.
I hope someone from the panel can enlighten us on this.
4 Likes
can someone help me to find the issue in the below code? I am getting WA for 2 cases in subtask 3.
https://www.codechef.com/viewsolution/47291535
Can u pls explain this thing in more detail??
My Code also got AC after this change.
You are accounting for the base condition when i == n and j == k, what must happen when your k subarrays are completed before i == n.
if (j > k) return 0;
Your AC Code w/ some changes: # 47296000
Your AC Code: # 47296280
The above case that i mentioned might be wrong, sorry for that.
But i have an explanation.
Let’s say you have assigned -inf to dp initially and are returning the same.
Let’s say for any dp(i,j) i get sum as 0, but i dont have K partitions yet.
That means this configuration is invalid and code is gonna return -inf.
so what gets returned is 0+(-inf) = -inf.
Now your code will see this as a “not-calculated” value and every time you require this during recursion it will recalculate. which causes the TLE.
How to fix this?
Let’s say i have assigned dp to -1e18, and i return -1e15 when case is invalid.
now max sum = 1e11 and min sum=-1e11 (due to problem constraints)
let’s add it to what I return. that is s1=-1e15+(-1e11), s2=-1e15+1e11
In both cases, we get a sum that is greater than -1e18.
Therefore you can be sure that if dp(i,j) is NOT -1e18 then it has been computed, and otherwise not computed.
1 Like
I have also used 3 state dp,
dp[i][cnt][ptr] → i for index of array, cnt for subarray number and ptr for knowing if any element is included in subarray or not (0 → if no element included in cnt subarray and 1-> if atleast one element included in cnt subarray)
Recursion with memoisation
Solution: 47251528 | CodeChef
Thank you so much for finding out the reason for TLE. This is the first time I encountered this thing of static vs dynamic because, on CF or atcoder, I generally code multidimensional dp in this way only and there I never got TLE due to this reason.
1 Like
Can someone find error in my recursion? Only one case in subtask 3 is not passed.
https://www.codechef.com/viewsolution/47300231
arree baap re 
bhai itne saare cheaters …
bro how did u find these and how are they getting these solutions are they cheating from a higher rated user… and will they get banned?
thanks;
@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.
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
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
Can anyone tell me why i am getting tle ? Its complexity is O(nxkx2) .
because the time complexity should be n*k
Sorry for above its not k square its n into k into 2
I thought in short contests, people don’t have time to cheat. But these legends proved me wrong 