Bug in MXEVNSUB problem

help
,
1

My issue

Below appears to be a valid solution. But When I check it manually it doesn’t look valid.
CodeChef aproves it as a good one but look:

Lets check sums of series for given N:
N=1 Sum=1 ->Odd
N=2 Sum=3 ->Odd
N=3 Sum=6 ->Even
N=4 Sum=10 ->Even
N=5 Sum=15 >Odd
N=6 Sum=21 >Odd
N=7 Sum=28 ->Even
N=8 Sum=36 ->Even

So this code should not pass, because it gives below output for this case:
N:1 lenth:0 Sum:0
N:2 lenth:1 Sum:1
N:3 lenth:3 Sum:6
N:4 lenth:4 Sum:10
N:5 lenth:4 Sum:10
N:6 lenth:5 Sum:15
N:7 lenth:7 Sum:28
N:8 lenth:8 Sum:36

So for n=2 it should be 0, and for n=6 solution is 4 not 5, because sum series for N=5 equals 15 so it is odd.

My code

#include <iostream>
using namespace std;

int main() {
	// your code goes here
	int t,n,temp;
	cin>>t;
	while(t--)
	{
	   cin>>n;
	   temp = n*(n + 1) / 2;
	   if(temp % 2 !=0)
	   cout<<n - 1<<endl;
	   else
	   cout<<n<<endl;
	}
	return 0;
}

Problem Link: CodeChef: Practical coding for everyone

2

@camillowski
For n=2
its sum is 1+2 =3
which is odd.
but when i’ll remove starting 1 it gives me 2 only which is even .
That’s how its possible and it will work for all other cases too where u got (n*(n+1))/2 as odd sum.

3

OK, but the problem statement says “…Consider the sequence containing the integers 1,2,…,N 1,2,…,N in increasing”
So it is not from 2 but from 1.

Moreover example one also takes all three numbers into consideration:

“Example case 1:** The optimal choice is to choose the entire sequence, since the sum of all its
elements is 1+2+3=61+2+3=6, which is even.”

Applying your way of thinking in the example we should also take only 2 and 3 which would give us 5 which is odd, so example would not pass.

4

@camillowski
actually the question says u have to find the maximum length of the subarray that result in even sum .
The subarray the said to be the part of the array that can be made by erasing some integers from the back or from the front .
Now if u have cleared the definition of subarray lets take some ex:-
for n=2
maximum length wound be 2 but its sum is 1+2 =3(which is odd) so i pick a subarray of length 1 from [1 ,2] which is 2 itself and its sum is even.
now for n=3
its maximum length for which the sum is even is 3 itself.
so if u got the intuition by now u will get it that if the sum of all numbers till n which will be (n*(n+1))/2; is even then answer will be n itself and if its odd then we can drop the 1 from it and pick rest elements which will be a subarray of length n-1 .

I hope u will get it now . Let me know in case u have more doubts.

1 Like
5

Yes, now I understand your point of view. I see that my mistake was an assumption that the sequence MUST start from 1. I got misled by word “contiguous”. Also examples they gave were a bit tricky.

Thank you dpcoder_007 for you time spent explaining me the solution. I’m very grateful for that and I wish you a good evening.

1 Like