MXEVNSUB - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3

Author: Daanish Mahajan
Tester: Anay Karnik
Editorialist: Mohan Abhyas

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

You are given an integer N. Consider the sequence containing the integers 1, 2, \ldots, N in increasing order (each exactly once). Find the maximum length of its contiguous subsequence with an even sum.

EXPLANATION:

\sum_{k=1}^{k=n} k = n*(n+1)/2
Take whole sequence if above sum is even else leave out 1 to make sum even

TIME COMPLEXITY:

\mathcal{O}(1) per testcase.

SOLUTIONS:

[details = “Editorial’s Solution”]

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define forn(i,e) for(ll i = 0; i < e; i++)

void solve()
{
	ll n;
    cin>>n;
    ll sum = (n*(n+1))/2;
    if(sum%2)
    {
        cout<<n-1<<endl;
    }
    else
    {
        cout<<n<<endl;
    }
}

int main()
{
	ll t=1;
	cin >> t;
    forn(i,t) {
    	solve();
    }
    return 0;
}
3

in case of 10 it will be , 2+3+4+5+6+7+8+9+10 = 54

1 Like
4

what if n=2 ?

5

then answer will be 1, {2}.

6

what’s wrong in this code??

#include
using namespace std;

int main() {
// your code goes here
int t;
cin>>t;
while(t!=0)
{
int n;
cin>>n;
int count=n;
int sum;
for(int i=1;i<=n;i++)
{
sum+=i;
}
if(sum%2!=0)
{
sum=sum-(n);
count–;
if(sum%2!=0)
{
count–;
cout<<count<<endl;
}
else
{
cout<<count<<endl;
}
}
else
{
cout<<count<<endl;
}
t–;
}
return 0;
}

7

Can someone help in this?
image

This shows wrong answer…

9

This solution would be the ideal solution in my opinion

t=int(input())
while(t):
  n=int(input())
  if(((n*(n+1))/2)%2==0):
    print(n)
  else:
    print(n-1)
  t-=1

You should check the sum of entire series. In that way if sum is odd just one can be removed to make it largest even sum subsequence
What you’re doing fails for numbers like 10. (Ans should be 9 but your code gives 8)!
Hope this helps even a little bit!

1 Like
10

At 10 code provides 9 as output😐

11

Brother I could see that you didn’t intialize the sum variable to 0 before using it. So when you write sum+=i you are adding it to the garbage value. Sum has garbage value(unpredictible value) in it.
Replace int sum with int sum=0;

Also you are adding extra couts i mean remove all those else statements and replace them with just single cout<<count<<endl; as this will do the job.

Also this logic is not what the question asked. I did the same logic untill i saw the editorial loll.

Happy to hear back from you brother love from India

12 
from sys import stdin
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	print (n if (n+1)//2%2==0 else n-1)

To save a multiply operation only (n+1)//2 needs to be checked for parity. Yes, I know its miniscule, but in systems running 100 billion operations every second it really helps.

14

The editorial Solution should fail if N=14.
Correct me if I am wrong?

15

You probably know it by now but it won’t as they just want you to -1 from the N if sum is odd.

16

i feel like this problem is not right becoz when n=6 it will return 5 but for the statement “maximum length of subsequences whose sum is even” 5 is not right answer 1+2+3+4+5=15 which is odd

IDK just feel like it should be discussed

2 Likes
17

the sum series goes like
1 = 1 ODD
1+2=3 ODD
1+2+3=6 EVEN
1+2+3+4=10 EVEN
1+2+3+4+5=15 ODD
1+2+3+4+5+6=21 ODD

so if n equals to a second consecutive ODD in the series, for eg, 2 or 6, we can’t just print(n-1) because the sum will still be ODD

2 Likes
18

To falsify the given solution: For 22 as input it gives 21 as output and for 21 as input it gives 20 as output. This clearly means for 22 it should give 20 only and not 21. Sum of first 22 & 21 integers 1+…+ 22 & 1+…+21 both are odd.

The correct solution should be –

#include <iostream>
using namespace std;

int main() {
    long int T,N,M;
	cin>>T;
	for(int i=0;i<T;i++){
	    cin>>N;
	    if(N<3){
	        cout<<0<<endl;
	    }
	    else{
	        if( (N%4 == 0) || ((N+1)%4 == 0) ){
	            cout<<N<<endl;
	        }
	        else if(N%4 == 1){
	            cout<<(N-1)<<endl;
	        }
	        else if(N%4 == 2){
	            cout<<(N-2)<<endl;
	        }
	    }
	}
	return 0;
}

Any suggestions are welcome. Thank you !

1 Like
19

What does contiguous subsequence mean? Does it mean just next subsequence (regardless of it being even)? I was under the impression that the statement asks for highest even-summed subsequence? What does CONTIGUOUS mean ?
@grimshinigami1 is that what you meant ?

20

best solution
thank you