PRTITION - Editorial

PROBLEM LINK:

Practice
Contest

Author: Hasan Jaddouh
Tester: Alexey Zayakin
Editorialist: Oleksandr Kulkov

DIFFICULTY:

EASY

PREREQUISITES:

None

PROBLEM:

You’re given two integers x and N. Consider all integers between 1 and N inclusive, except x. We want to partition these integers into two disjoint sets such that the sums of numbers in this sets are equal.

QUICK EXPLANATION

Write simple brute-force which goes from N to 1 and firstly tries to take current number into lesser set. Turns out it’s fast enough.

EXPLANATION:

Sum of numbers from 1 to N is equal \tfrac{N(N+1)}{2}. If it has different parity from x then solution doesn’t exist at all. Otherwise it does with few exceptions.

To solve the problem you can write the following simple brute-force:

bool brute(int n, int x, int64_t l = 0, int64_t r = 0) {
    if(n == x) {
        ans[n - 1] = '2';
        return brute(n - 1, x, l, r);
    }
    if(n == 0) {
        return l == r;
    }
    if(l < r) {
        if(brute(n - 1, x, l + n, r)) {
            ans[n - 1] = '0';
            return true;
        } else {
            ans[n - 1] = '1';
            return brute(n - 1, x, l, r + n);
        }
    } else {
        if(brute(n - 1, x, l, r + n)) {
            ans[n - 1] = '1';
            return true;
        } else {
            ans[n - 1] = '0';
            return brute(n - 1, x, l + n, r);
        }
    }
}

This solution goes by numbers from N to 1 trying to keep l and r close to each other. Thus if first sum currently less than second one then we try to proceed adding number n to first sum, otherwise we firstly try second sum. If that didn’t lead to solution then we try another option. At first it looks like this will consume too much time but it’s not true.

You can prove by induction that |l-r|\leq n+1 at each step of algorithm for which n \geq x or n < x - 1. And only for n=x-1 it is |l-r|\leq n+2. That means that if x>2 we will have |l-r|\leq 2 for n=1. But |l-r| will always be even after this step since we ensured that l+r=\dfrac{N(N+1)}{2}-x is even at the beginning. That means that |l-r|=1 at n=1 for x>2 and greedy solution works just fine.

As for cases x=1 and x=2 we should use the fact that |l-r|\leq 6 for n=5. You can manually check that you will always find solution from this step:

  • x=1,|l-r|=0 \to \{2, 5\}, \{3,4\}
  • x=1,|l-r|=2 \to \{2, 4\}, \{3,5\}
  • x=1,|l-r|=4 \to \{2, 3\}, \{4,5\}
  • x=1,|l-r|=6 \to \{4\}, \{2,3,5\}
  • x=2,|l-r|=1 \to \{1, 5\}, \{3, 4\}
  • x=2,|l-r|=3 \to \{1, 4\}, \{3, 5\}
  • x=2,|l-r|=5 \to \{1, 3\}, \{4, 5\}

So overall it will take for you at most n+2^5 operations per testcase which is enough to solve the problem.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.

RELATED PROBLEMS:

I got AC on this problem in O(logn) by checking lots of conditions and printing specific strings:D Seems to be an overkill for the problem.


[1]


  [1]: https://www.codechef.com/viewsolution/16967937
1 Like

can it be solved in O(n) by starting filling array from backside and decreasing sum value?

Yes. It can be.

You can have a look on this solution : https://ideone.com/3gaZVa

Someone please find mistake which results in WA in one of the caseMy Code

Can somebody tell me what is the intuition behind this solution, i.e. how does one reach to this solution after reading the problem? What thought process leads to the approach of this solution?

2 Likes

A solution always exists unless N < 4 or the sum of all the numbers from 1 to N except x is odd.

Build a set adding numbers in decreasing order starting from the highest and skipping x and s - x, where s is the remaining sum of the numbers to be added to the set. If the initial value of s is greater that N (which is always true for N > 5) then when it drops to or below the current number it is guaranteed to be different from x, and it would become the last number in the set.


[1].


  [1]: https://www.codechef.com/viewsolution/17063900

Why is my greedy solution failing?
https://www.codechef.com/viewsolution/17021342

1

2 8

Answer is possible.

Thanks man!

@shivg7706

//Not enough rep to comment so writing as answer

I wasn’t able to come up with any small test case but I don’t think your program would work for a case when a[i] is x+1.

1 Like

Can anyone tell me why my solution failed!/ any testcase to fail my code.
https://www.codechef.com/viewsolution/16940105

@masterbios
your code fail on the test case
1
2 8

The “few exceptions” when the sum of all the numbers from 1 to N except x is even but no solution exists is when N < 4.

1 Like

it Can be solved in O(n) by starting filling array from backside and decreasing sum value?
My approach was–>

  1. first find sum = N*(N+1)/2
  2. if (sum - x) is odd, solution is imposible
  3. if (sum - x) is even than dividing in two equal set can be possible or impossible both
  4. find halfOfSum=sum/2
  5. iterate for i in numbers N from backside, if Number is smaller or equal to halfOfSum than A[i]=1 and halfOfSum=halfOfsum-i
    else A[i]=0
  6. check wheather halfOfSum is zero or not… if zero tham possible else not possible
  7. List item

but above code fails in such a case as x=2 n=8, so to pass such case we will repeat from step 4 but iteration will start from n-1th element this time backside… and last element will be allocated A[last]=0

Happy Coding
hemant_dhanuka
:slight_smile:

Hi, Can anyone please tell me why I could get all test cases to pass except one. I had tried it for 4 continuous days to identify my mistake but in vain. I got really frustrated at one moment of time. It will be really helpful if someone can point me the mistake or the test case for which it fails.The link to my submission is: https://www.codechef.com/viewsolution/17047046

Just for explanation of the program, I am using a boolean array to store the set to which the ith number belongs. “false” means set 0 and “true” means set 1.

Thanks in advance.

here is my submission , I don’t know what I am missing .

It would be great help if anyone could help . Thanks in advance :slight_smile:

https://www.codechef.com/viewsolution/17100333 is my submission , I don’t know what I am missing .

It would be great help if anyone could help . Thanks in advance :slight_smile:

https://www.codechef.com/viewsolution/17104754

heyy, can someone please help me with the test cases for which i might be getting the wrong answer? cant figure out, what i might be missing.

@rahuldugar I don’t think there is a need to calculate even the sum…
link to my solution
https://www.codechef.com/viewsolution/16878569
Though the solution is based on similar lines ie. printing set of strings to make separation into equal sum.