PRTITION - Editorial

editorial
, , , ,
12

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: CodeChef: Practical coding for everyone

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.

13

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:

14

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.

15

@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.

16

I thought of the following solution. Plz can someone tell me if it is valid and can be implemented without getting a tle:

  1. Find the sum and check if it is possible to divide the numbers into two sets of equal sums.
  2. If possible, then we start with an array of numbers from 1 to n.
  3. We put the first and last numbers in one set and the second and second last numbers in second set and we skip the number x.
  4. We maintain two sum counts for each set. We check after the above division if thw two sums are equal or not.
  5. If equal we have the division. If not then, there are 2 cases. We calculate the difference between the required sum and the set with the smaller sum. If the number equal to the difference is present in the set then we can add it in the set. If not then we find the number from the smaller set to be swapped with a number in the larger set.
17

You can step almost directly to the right place to split the set by calculating the triangular number closest above the partition totals. Then with only a small adjustment of one to three elements, you can get a qualifying partition without intermediate calculation.

Kudos to the test case writer for finding “4 4” to break my first submission - the partition total is 3, which is less than 4 (my test) but not less than the highest remaining element. D’oh.

My submission

18

Yes. It can be.

You can have a look on this solution : 3gaZVa - Online C++0x Compiler & Debugging Tool - Ideone.com

19

1

2 8

Answer is possible.

20

Thanks man!

21

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
22

CodeChef: Practical coding for everyone 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:

23

@vaibhavahuja1 You made a very silly mistake. Your output string has spaces between the digits.

For input,

1

4 12

your output is:
1 1 0 2 0 1 1 0 0 1 1 0

24

Somebody please help me. PLEASE!!

25

How did you came up with this solution? How did you made all those cases separately?

26

you call case “8 11” impossible - it isn’t, eg. 10000012011

1 Like
27

For the exceptional cases when N - x is even,
The greedy solution of going from N to 1 and addint the current number to set with lesser sum works for most of the cases except when x=1 and N>=6 and N=2 and N>=7. So for that you can manually assign number from 1 to 6 and apply greedy solution to remaining.

Link to my solution for reference:
https://www.codechef.com/viewsolution/27820247

28

thnks brother

29

/******************************************************************************

                          Online C++ Compiler.
           Code, Compile, Run and Debug C++ program online.

Write your code in this editor and press “Run” button to compile and execute it.

*******************************************************************************/

#include <bits/stdc++.h>

using namespace std;

void solve()
{
long x,n; cin>>x>>n;
long a[n];
long sum = (n*(n+1))/2;
//cout<<sum;
if((sum-x) %2 !=0) cout<<“impossible”<<"\n";
if((sum-x) %2 == 0) {
long sum_half = sum/2;
if(n==8 && x==2) cout<<“12011010”<<"\n";
else
{
for(long i=n;i>=1;i–) {
// cout<<"AA "<<sum_half<<endl;
if(i==x) a[i] = 2;
else if(i <= sum_half)
{
a[i] = 1;
sum_half=sum_half-i;
// cout<<"X "<<sum_half<<endl;
}
else a[i]= 0;

        }
      //  cout<<sum_half<<endl;
            if(sum_half!=0) cout<<"impossible"<<"\n";
            else {
                    for(long i=1;i<=n;i++)
                    cout<<a[i];
                    
                    cout<<"\n";
                  }
    }
}

}

int main()
{
int t; cin>>t;
while(t–)
{
solve();
}
}
HELP ME OUT PLEASE I GOT WA?******

30

@eugalt can you explain why are you skipping s - x also?

31

Hello
Sorry for re-awaking this thread but I want to know how this above logic works!