CHESUB - Editorial

It think this definition is not correct. According to your explanation later, it should be max score by taking first i numbers with exactly j sub-arrays with i being the last index of j^{th} segment.

Also, if the dp[i][j] is defined the way in the edi, the ans should have been directly dp[n][k] and not \max\limits_{i=1}^{n} dp[i][k] as in your solution.

Correct me if I’m wrong. @cherry0697 @cubefreak777

1 Like

I think the definition is wrong the accurate definition would be DP [ i ] [ j ] is defined as maximum score that is possible by taking the first i elements and having exactly j subarrays such that the jth subarray ends at index i . And I think answer can also be pref [n-1][k]

2 Likes

Yes you’re correct, the definition given in the editorial refers to DP_1[i][j]=\max\limits_{i=1}^{N} DP[i][j], but rest of the solution apart from the definition has been modelled according to DP[i][j] instead of DP_1[i][j]

2 Likes

Yes, he should correct it because it is misleading otherwise.

2 Likes

a loaded question that oozes dp, yes please chef

1 Like

Do correct me if I am not comprehending your point correctly but I believe you misinterpreted the meaning of the statement

DP[i][j] is defined as the maximum score that is possible by taking the first i index of the array A and having exactly j subarrays.

as

DP[i][j] is defined as the maximum score that is possible to obtain in subarray stretching from 0 to i of the array A and having exactly j subarrays.

I believe the statement does mean to convey that dp[i][j] has to have taken the first i indices meaning the i_{th} index must be included in the progression of subarrays we have considered.

If the answer being dp[n][k] were to comply with the definition now, would it not have implied the answer is “maximum score possible taking first n indices of A having exactly j subarrays”, which would contradict what the question has stated, it being- taking all indices into account isn’t necessary, which I think complies with the answer being \max \limits_{i=1}^{n} dp[i][k]. That’s why I think the word taken has been causing a fuss without meaning to rather than it being a wrong definition.

1 Like

Thanks, I corrected that part. Yet subtask 3 gives TLE.

code

I think you misinterpreting that in the correct definition of dp[i][j], the whole prefix 1...i should be present whereas that’s not the case. Only, the index i should be compulsorily present and not the full prefix.

And let’s suppose we go by your definition, then the sub-arrays in the final answer would be continuous but they can be discontinuous as well.

I didn’t say that at all… I just said that “taken” means the last index must be present because you’re considering arrays stretching from 0 to i, I said nothing about the inclusion of any of the middle in fact I said that if it did mean what you think it did then that would contradict the fact that not all elements must be present. I said the opposite of what you’re saying I said…

1 Like

Umm :thinking:

1 Like

meaning the i_{th}ith​ index (must I really add only the ith index in a comment explaining that taken is only meant in the sense that ith index must be taken and again only i nothing about the middle) must be included in the progression of subarrays we have considered.

umm times two you’re again looking at the word taken as something that means taken into the subarrays it only means upto that point thus only stressing on the inclusion of that last index.

1 Like

You clearly wrote "has to have taken first i indices".

How does taking first i indices means taking only index i compulsorily ?

DP[i][j] is defined as the maximum score that is possible by taking the first i index of the array A and having exactly j subarrays.

Also, in the above definition I see no reason why would it imply taking the i^{th} index compulsory unless mentioned.

1 Like

has to have taken first i indices into consideration for the subarrays being involved not into the subarrays being involved. Taking the first i indices into consideration can’t leave out the i-th index because it is upto i, that’s all taken means in the context that the i-th has to be present which obviously has to happen as the end element of the j-th subarray chosen (it being the last element). You are misinterpreting a word in a comment explaining that you may have misinterpreted the same word in the post :rofl:

1 Like

That’s the whole point of the taken that I’ve been trying to explain good lord its alright it may be a difficult statement with room for interpretation otherwise but it ain’t wrong the editorial meant what you said it should mean already.

1 Like

Again, I stick to words.

I seriously don’t understand how does taking first i means compulsorily taking the last i^{th} index.

It’d help if you started sticking to context more than words then I guess lolz because if you can’t see how taking i indices means having to have gone up to including the i-th one then you shouldn’t have assumed it meant taking optimal answer until i-th index when the entire explanation points to otherwise.

1 Like

PS I hope I don’t sound rude because I’m not trying to be rude it may sound weird typed out so sorry if it sounded rude or anything, its hard conveying faces over typing i guess lolz

2 Likes

No, it’s perfectly fine. You never sounded rude. :slightly_smiling_face:

Since, now we both understand the actual definition and only can’t agree on the English statement, I think we should stop at this point because otherwise the battle will go on forever.

Also, the statement has been made more clearer now (Thanks @cherry0697 ).

2 Likes

we stop at this point because otherwise the battle will go on forever

Aye if I may sprinkle my absurd humor to seal the disagreement… That’s what she said.

2 Likes

… how the solution guaranteed that if we add the ith element to the jth subaaray then subarray property will not break…it means suppose consider the jth subarray → ([…]) . Adding ith element it will become this → […,i]
is it → […,i] the subarray of the given array??