As the contest ended I went to check the AC submissions for this problem and I was shocked to see all the top submissions were same . At first I thought to write a blog about this then I realized it’s better to have sleep than wasting time over this .
PS : - Codechef should also run plagiarism check after the contest ends like codeforces .
Can you explain me two things
Also please explain how you though that isstarted parameter will be needed and what it’s actually telling for that state?
Also can you please explain how you though that isstarted parameter will be needed and what it’s actually telling for that state?
isStarted: it will show that we have already started our subarray(=1) or we need to start from here(=0).
why isStarted: let’s understand if not then how we know that for which subarray we are computing or is current subarray ended or need to start new subarray or we skip current element, so for these all we need one variable which isStarted in our case to predict the state for which we are computing.
isStarted==0: means we may start our subarray from here at (i) itself which is equivalent to have already started our subarray at i . f(i, j, 1). or we may start from next f(i+1, j, 0).
isStarted==1: we already have started so we may end our current subarray here at (i) itself which is equivalent to start another subarray from next f(i+1, j+1, 0) or we continue to next element which is f(i+1, j, 1) in both case we included a[i] to current subarray so we need to add it.
it will be equivalent to a[i]*j+f(i+1, j, 1). because we included a[i] here itself so we recur for next to avoid selection of already selected element.
Hope you understood it well, if not reply for further query.
Most of them are from chandigarh university.
Return a different large negative value if it’s invalid. when c=1 it will keep returning and computing the same “infinity” and hence gives TLE.
Your AC code
(P.S. don’t blame problem setters before you analyze well)
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.
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
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.
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.
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.
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?