PRTITION - Editorial

editorial
, , , ,
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!

32

Sorry, this logic doesn’t work because obviously printing output of size n takes O(N).

33

Hey hemanth, Thanks for the idea but can you explain why starting from n - 1 th element in test the test cases like of 2, 8 always works? Sorry, i am too late to ask :slight_smile: