CHEFODD - Editorial

editorial
,
1

PROBLEM LINK:

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

Author: souradeep1999
Tester and Editorialist: iceknight1093

DIFFICULTY:

1486

PREREQUISITES:

None

PROBLEM:

Given N and K, determine whether it’s possible to partition the integers \{1, 2, \ldots, N\} into exactly K groups such that:

  • Each group contains \geq 2 integers.
  • The sum of each group is odd.

EXPLANATION:

First off, note that we want to form K groups with \geq 2 integers each.
This means we need at least 2K integers in the first place; so if N \lt 2K the answer is immediately No.
Now let’s analyze when N \geq 2K.

We have x = \left\lceil \frac{N}{2} \right\rceil odd integers and y = \left\lfloor \frac{N}{2} \right\rfloor even integers to work with.
Note that we’ll have x = y if N is even, and x = y+1 if N is odd.
Also, N \geq 2K means x, y \geq K.

The sum of each group must be odd, which means each group should contain an odd number of odd integers. The even integers don’t affect the parity of the sum, so they can be distributed however we like.

Since x, y \geq K, let’s first put one odd and one even integer into each group.
Now, each group has odd sum and \geq 2 elements; we just need to figure out whether the other elements can be distributed properly while maintaining this property.

We’re left with x-K odd integers, which need to be distributed among the K groups.
To keep the sum of each group odd, note that even group must receive an even number of these x-K integers.
In particular, this means x-K itself must be even; and it’s not hard to see that this condition is also sufficient (if x-K is even, give all x-K odd integers to the first group and we’re done).

So, when N \geq 2K, the answer is Yes if x-K is even and No otherwise.

TIME COMPLEXITY

\mathcal{O}(1) per test case.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    n, k = map(int, input().split())
    if n < 2*k: print('No')
    else: print('Yes' if ((n+1)//2 - k)%2 == 0 else 'No')
1 Like
2

Why this code is giving me wrong answer?
Main idea = group 1 odd and 1 even in (k-1) bucket
if k bucket contains k odd numbers of odd elements answer is Yes

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

#define ull unsigned long long
#define ll long long

void solve(){
    ull n,k;
    cin>>n>>k;
    if(k > 2*n) {cout<<"NO\n"; return;}
    ull no_of_even = n/2, no_of_odd = n/2 + n%2;
    ll no_of_even_rem = no_of_even - k+1;
    ll no_of_odd_rem = no_of_odd- k+1;
    if(no_of_odd_rem%2 == 1) {cout<<"YES\n";}
    else cout<<"NO\n";
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int t;
    cin>>t;
    while(t--){;
        solve();
    }
    return 0;
}
1 Like
3

Can anyone please tell me, why it is not working, I’m stuck here for a long time

4

This should be if (2*k > n).

1 Like
5

Why this code is giving error ?
Main idea - assigning 1 even and 1 odd to (k-1) and then checking how many odd numbers is remaining .

/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        
        while (T-->0){
            int n = sc.nextInt();
            int k = sc.nextInt();

            int evenNumbers = (int) ((double) n/2);
            int oddNumbers = n - evenNumbers;
            
            int oddLeft = oddNumbers - (k-1);

            if (k*2<=n){
                if (oddLeft%2!=0) System.out.println("YES");
                else System.out.println("NO");
                
            }
            
            else System.out.println("NO");
            
        }
	}
}
6

Where is the mistake of this code? Please help me for test case: 2

void solve()
{
int a, b;
cin >> a >> b;
if (a < 2 * b) cout << “NO\n”;
else {
if (!((((a + 1) / 2 - b)) & 1)) cout << “YES\n”;
else cout << “NO\n”;
}
}

7

N and K can be very large, you should be using long and not int.
I’m also not very sure about type-casting to double, which might introduce floating-point errors. Instead of (double) n/2 you can just directly do n/2 since that rounds down anyway.

@mddinislam you have the same issue, use long long instead of int.

2 Likes
8

Hi @iceknight1093
My python code is giving wrong answer when using math.ceil instead of (n+1)//2.
Is it a problem with my implementation, if yes then what best practice do you suggest to decide when to use ceil?

from math import ceil
for i in range(int(input())):
    n, k = map(int, input().split())
    myodd = ceil(n/2)
    if myodd>= k and k*2<=n:
        myodd -= k
        if myodd%2==0:
            print('YES')
            continue
    print('NO')
9

Thank you, But I already did it & my submission is succeed.

10

I recommend not using ceil/floor (or any other functions that depend on floating-point numbers, such as sqrt) unless you really know what you’re doing.
See this blog for alternatives (it’s technically for C++, but the first 3 points are language-independent)

1 Like
11

Can someone please help me find the reason for wrong answer. I figured this solution during the contest yesterday but for some reason it results in wrong answer

#include
using namespace std;

int main() {
// your code goes here
int t;
cin>>t;
while(t>0)
{
int n,k;
cin>>n>>k;
if(n<k*2)
cout<<“NO”<<endl;
else
{
int e,o;
if(n%2==0)
{
e=n/2;
o=n/2;
}
else
{
e=n/2;
o=n/2+1;
}
o-=k;
if(o%2==0)
cout<<“YES”<<endl;
else
cout<<“NO”<<endl;
}

  t--;

}
return 0;
}

12

i did the same mistake in contest… used int in place of long long. :pensive: :pensive: