Below problem (Maximum length even Subarray) in today’s contest is accepting wrong solutions.
Just see my submission and you will know why.
https://www.codechef.com/viewsolution/50311269
So, to have even sum, the number of odd number in the series should be even, it doesn’t depend on whether ‘N’ is even or odd.
e.g.: N=26 gives odd sum but so does N=25, because both 26 and 25 have odd numbers of odd. Therefore for N=26, answer should be N-2.
Yeah, I wrote the explanation in replies.
n*(n+1) will always be even , so it will be definitely divisible by 2
but n*(n+1)/2 can be odd or even → if even print n else print n-1
Just check for N=26, for this ans is n-2, Just read my explanation above.
for n=26, remove 1… add 2+3+4…+26=even
So, n-1
For n = 26, the sum will be 351, and 351-1=350 which is even, so the logic is this:
If the sum is already even, just print n,
Else print n-1. (Imagine that you’re deleting the number “1” from the sequence, now what’s left is a contiguous subsequence)
understand this odd-1=even
even-1 = odd
so the max answer possible is n
if sum of all n numbers is odd → answer = n-1
if sum of all n numbers is even → answer= n
Yeah, now I get it. Thanks.
Thanks.