SPLITPAIR - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: S.Manuj Nanthan
Tester: Manan Grover
Editorialist: Aman Dwivedi

DIFFICULTY:

Simple

PREREQUISITES:

Maths

PROBLEM:

You are given a positive integer N. You have to split each digit of N into either of two non-empty subsequences A or B.

Let us define a function F(X,Y)=(X+Y) \mod 2. Find out whether it is possible to find two non-empty subsequences A and B formed out of N such that F(A,B)=0.

EXPLANATION:

Remember the basic mathematics rule again:

Even + Even = Even \\ Odd + Odd = Even \\ Odd + Even = Odd

As every digit needs to be part of exactly one subsequence A or B. Then observe that the last digit of the given number will be the last digit of any subsequence. Let’s put this digit in the subsequence A.

  • Last digit of the given number is Even.

    It means that the subsequence A is going to be an even number. In order to get the remainder 0 we need to have (X+Y) as even. And for that the subsequence B needs to be also even. Now if there is any digit apart from the last digit in the given number as even we will be able to get the subsequence B also even.

  • Last digit of the given number is Odd.

    It is opposite to that of the above case. Instead of Even we will be looking for odd as the last digit is odd hence the subsequence A will be odd. As odd added to odd only will produce the sum even which will produce the remainder 0.

TIME COMPLEXITY:

O(D), where D is the number of digits in the given number

SOLUTIONS:

Author
for _ in range(int(input())):
	n=int(input())
	par=(n%10)%2
	n=n//10
	s='NO'
	while(n):
		if((n%10)%2 == par ):
			s='YES'
		n=n//10
	print(s)
Tester
#include <bits/stdc++.h>
using namespace std;

long long readInt(long long l, long long r, char endd) {
    long long x = 0;
    int cnt = 0;
    int fi = -1;
    bool is_neg = false;
    while (true) {
        char g = getchar();
        if (g == '-') {
            assert(fi == -1);
            is_neg = true;
            continue;
        }
        if ('0' <= g && g <= '9') {
            x *= 10;
            x += g - '0';
            if (cnt == 0) {
                fi = g - '0';
            }
            cnt++;
            assert(fi != 0 || cnt == 1);
            assert(fi != 0 || is_neg == false);
 
            assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
        }
        else if (g == endd) {
            assert(cnt > 0);
            if (is_neg) {
                x = -x;
            }
            assert(l <= x && x <= r);
            return x;
        }
        else {
            assert(false);
        }
    }
}
int main(){
  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  #ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
  #endif
  int t;
  t = readInt(1, 1000, '\n');
  while(t--){
    int n;
    n = readInt(10, 1000000000, '\n');
    int m = n / 10;
    bool f = false;
    while(m){
      if(m % 2 == n % 2){
        f = true;
        break;
      }
      m /= 10;
    }
    if(f){
      cout<<"YES\n";
    }else{
      cout<<"NO\n";
    }
  }
  return 0;
}
Editorialist
#include<bits/stdc++.h>
using namespace std;

void solve()
{
    int n;
    cin>>n;
    
    int last_digit = (n%10);
    last_digit %= 2;
    
    n = n/10;
    
    while(n)
    {
        if ((n%10)%2 == last_digit)
        {
            cout<<"YES"<<endl;
            return;
        }
        n = n/10;
    }
    
    cout<<"NO"<<endl;
}

int main()
{
    int t;
    cin>>t;
    
    while(t--)
        solve();

return 0;
}
2 Likes

whoever has set this question please go and learn about subsequences,
1.there is no hard and fast rule for subsequences to end with the last digit only
2.if you are considering yours way of defining subsequence please mention it properly
(" if N=104N=104, some possible values of (A,B)(A,B) can be (10,4),(14,0)(10,4),(14,0) and (1,4)")
instead of writing “some” you should have written “all”.

21 Likes

I used recursion for this question:

#include <bits/stdc++.h>
using namespace std;
#define int long long

bool fl;

void solve(string s1, string s2, string &s, int i)
{
if (i == s.size())
{
if (s1.size() > 0 && s2.size() > 0)
{
int n1 = stoi(s1);
int n2 = stoi(s2);
if ((n1 + n2) & 1 ^ 1)
fl = 1;
}
return;
}
if (!fl) {
solve(s1 + s[i], s2, s, i + 1);
solve(s1, s2 + s[i], s, i + 1);
}
}

signed main()
{
ios::sync_with_stdio(0);
cout.tie(0);
cin.tie(0);
int t ;
cin >> t;
while (t–)
{
int n, m, e, o;
fl = 0;
cin >> n;
string s = to_string(n);
solve("", “”, s, 0);
puts(fl ? “YES” : “NO”);
}
}

I don’t understand why you are only seeing the last digit parity and comparing to find that same parity exist in other digits too or not. You had given the example in the question was also including (14 , 0) for 104 where 0 is not the last digit. so we had gone through the idea that if the digit have any two odd numbers or any two even numbers then answer should be YES otherwise NO.
question makers please try to be clear with your ques and also the example given in the question of 104 contradicts your solution explanation.

8 Likes

Can someone check why this doesn’t work?
And why are we considering the last digit to check. If we are able to find two even or two odd digits, we’ll be able to create two subsequences that satisfy the condition.

void solve() {
    ll n;
    cin >> n;

    // we'll be able to create two even or two odd numbers
    if(n >= 100) {
        cout << "YES" << endl;
        return;
    }
    
    ll countEven = 0, countOdd = 0;
    while(n > 0) {
        int digit = n % 10;
        if(digit % 2 == 0) {
            countEven++;
        }
        else {
            countOdd++;
        }
        n /= 10;
    }

    // if we can create two even or two odd numbers
    if(countEven == 2 || countOdd == 2) {
        cout << "YES" << endl;
    } 
    else {
        cout << "NO" << endl;
    }
}
3 Likes

I am not getting why we only need to consider the parity of last digit. This contradicts with the example-- 104.
Example- consider numbers 333750,750,570,3750 . According to your code, these numbers can not be considered as answers.
But, according to the example in the question these numbers should be considered as answers such as subsequences of 333750 can be taken as (303,375) .so, it is an answer.
similarly, (7,5) can be taken for 750 and 570 .so, all of these numbers are answer.
But, your code is showing “No”.
so, question makers please give a clear example with questions.

3 Likes

Can you tell me why this solution is not passing all the test cases? Because according to the given example in the problem we can split the number any which way, so if we check that the number has at least two even or/and two odd digits, it must return YES (odd + odd = even, even + even = odd).

#include <bits/stdc++.h>
#define ll long long
using namespace std;

int main()
{
int t;
cin >> t;
while (t–)
{
int n;
cin >> n;

    int even_cnt = 0;
    int odd_cnt = 0;
   while(n != 0)
   {
       int d = n%10;
       if(d%2 == 0)
       {
           even_cnt++;
       }
       else {
           odd_cnt++;
       }

       n = n/10;
   }

   if(even_cnt >= 2 || odd_cnt >= 2) cout << "YES" << endl;
   else cout << "NO" << endl;
}

}

1 Like

#include
using namespace std;

int main() {
// your code goes here
int t;
cin>>t;
while(t–){
int n,p=0,q=0;
bool entry=false;
cin>>n;
q=n;
while(n<100 && n!=0){
int a=n%10;
p+=a;
n=n/10;
}
if(q<100){
if(!(p&1))
cout<<“YES\n”;
else
cout<<“NO\n”;
}
else{
cout<<“YES\n”;
}
}
return 0;
}

Anybody suggest me what is wrong in it. I took num>=100 as because 3 digit or more as at least either 2 odd digit or 2 even digit

coutEven>=2 || countOdd>=2. this will work

Even this would not work I had done the same thing in the contest and got WA.

1 Like

but 14 has 4 which is the last digit

Exactly.

you cannot go backwards while splitting numbers,i.e you can only append numbers from the front or skip them.for example 552,you cannot make 25,5 . thats what he meant to say i guess.he should have written all instead of sum

This question needed some more examples so that it would be more clear according to the question we just had to count the number of odds and evens in the number and if either of those is 2 then simply return yes else no. i did this question in log(n/2) time and still it failed some testcases

its not working bcz of first condition. if n=112 you cannot split which holds the given condition. possible splits (1,12) (12,1) (11,2)

“You are given a positive integer N. You have to split each digit of N into either of two non-empty subsequences A or B.”

You need to find subsequences 303 is not a subsequence of 333750

I used the same logic but it failed. Actually, the no. of odd/even digits can be more than two and still the sum will be even. But also in that case,(>=2 instead of ==2), only one test case passed.

Fails for test case 181.

Brainstorming for hours what could go wrong and then this silly editorial!
Quite frustrating.

Here is my code below

#include <iostream>
using namespace std;

int main() {
	int t;
	cin>>t;
	while(t--) {
	    long long int n;
	    int ecount=0, ocount=0;
	    cin>>n;
	    while(n!=0) {
	        int t=n%10;
	        if(t%2==0) ecount++;
	        else ocount++;
	        n/=10;
	    }
	    if(ecount>=2 || ocount>=2) cout<<"YES"<<endl;
	    else cout<<"NO"<<endl;
	}
	return 0;
}

basically what I did is just counted no of even and odd digit. if No of odd digit and No of even digit are greater than 2 I can make an even no.
But I can’t get an AC for this solution. Can you please help me through? I can’t get on which case my code broke!