BREAKSTICK - Editorial

PROBLEM LINK:

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

Setter: Utkarsh Gupta
Tester: Harris Leung
Editorialist: Trung Dang

DIFFICULTY:

1026

PREREQUISITES:

None

PROBLEM:

Chef has a stick of length N.

He can break the stick into 2 or more parts such that the parity of length of each part is same. For example, a stick of length 11 can be broken into three sticks of lengths {3,3,5} since each part is odd, but it cannot be broken into two sticks of lengths {5,6} since one is even and the other is odd.

Chef can then continue applying this operation on the smaller sticks he obtains, as many times as he likes.

Can Chef obtain a stick of length exactly X by doing this?

EXPLANATION:

There are two cases:

  • When X is odd, we can always perform the operation regardless of N (by simply breaking N into X and a lot of 1's).
  • When X is even, since all the parts must also be even, we need N to be even as well. When this is the case, we can also always perform the operation (by breaking N into X and a bunch of 2's).

Therefore the necessary and sufficient condition is X odd or N even.

TIME COMPLEXITY:

Time complexity is O(1) per test case.

SOLUTION:

Setter's Solution
//Utkarsh.25dec
#include <bits/stdc++.h>
#define ll long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define vl vector <ll>
#define all(c) (c).begin(),(c).end()
using namespace std;
ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll modInverse(ll a){return power(a,mod-2);}
const int N=500023;
bool vis[N];
vector <int> adj[N];
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){
            if(is_neg){
                x= -x;
            }

            if(!(l <= x && x <= r))
            {
                cerr << l << ' ' << r << ' ' << x << '\n';
                assert(1 == 0);
            }

            return x;
        } else {
            assert(false);
        }
    }
}
string readString(int l,int r,char endd){
    string ret="";
    int cnt=0;
    while(true){
        char g=getchar();
        assert(g!=-1);
        if(g==endd){
            break;
        }
        cnt++;
        ret+=g;
    }
    assert(l<=cnt && cnt<=r);
    return ret;
}
long long readIntSp(long long l,long long r){
    return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
    return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
    return readString(l,r,'\n');
}
string readStringSp(int l,int r){
    return readString(l,r,' ');
}
void solve()
{
    int n=readInt(1,1000000000,' ');
    int x=readInt(1,n-1,'\n');
    if(n%2==1 && x%2==0)
        cout<<"NO\n";
    else
        cout<<"YES\n";
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    int T=readInt(1,1000,'\n');
    while(T--)
        solve();
    assert(getchar()==-1);
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
const ll mod=998244353;
const int N=2e6+1;
int main(){
	ios::sync_with_stdio(false);
	int t;cin >> t;
	while(t--){
		ll n,x;cin >> n >> x;
		if(n%2==0 || x%2==1) cout << "YES\n";
		else cout << "NO\n";
	}
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin >> t;
    while (t--) {
        int n, x; cin >> n >> x;
        cout << (x % 2 == 1 || n % 2 == 0 ? "YES\n" : "NO\n");
    }
}
2 Likes

I don’t know if it was only me or not but from the statements it is not clear whether the problem asks all the sticks finally formed should be having the same parity or during intermediate steps.

5 Likes

He can break the stick into 2 or more parts

You are allowed to break the stick into its final forms instantly. So all that matters is the result, it is therefore irrelevant how you get to the result.

it is not clear…

you are right, but problems have to be misleading somewhere. The problem could also be straightforward and tell you, you are given 2 numbers and you print “YES” when the first is odd or the second is even, else you print “NO”.

1 Like

me to but when I was look at test case 3rd then it was clear to me