MINSZ - Editorial

editorial
, , ,
14

Recursion also works.Obviously time taken is more.

#include <bits/stdc++.h>
using namespace std;
vector<unsigned long long int> ans;

void func(unsigned long long int x)
{
    
  unsigned long long int lgvalue,finalvalue;
    if(x == 1)
    {
        ans.push_back(1);
        return;
    }
    else if(x==0)
    {
        return;
    }
    lgvalue = (unsigned long long int)log2(x)+1;
    finalvalue = (unsigned long long int)powl(2,lgvalue)-1;
    ans.push_back(finalvalue);
    
    
    return func(finalvalue-x);
    
}
void solve()
{
ans.clear();
unsigned long long int c;
cin>>c;
if(c == 0)
{cout<<2<<endl<<"1 1"<<endl;
return;}
func(c);
cout<<(unsigned long long int)ans.size()<<endl;
reverse(ans.begin(),ans.end());
for(int i =0;i<ans.size();i++ )
{
    cout<<ans[i]<<" ";
}
 cout<<endl;   
}
int main() {
   ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin>>t;
    while(t--)
    {
        solve();
    }
    



	
}
1 Like
15

I have a slightly different approach that may be more intuitive. My Code

Convert C to binary.
Eg: 25 = 11001

Now, since numbers in array can only have set bits in binary form,
Therefore, for 11001
Ans=
11111
00111
00001

Conclusion:

At positions with set bit, number of set bits in the final answers array is odd

Algorithm:

Iterate from left to right and create a non-decreasing array
In this case:
1 1 0 0 1 → 1 1 2 2 3
How? At places with set bits in C, number of set bits should be odd and at unset bits, it should be even.

Now, from 1 1 2 2 3, you can very easily generate the binary numbers that are part of the final array.
Eg:
After 11111, Remaining → 00112
After 00111, Remaining → 00001
After 00001, Remaining → 00000

Implementation suggestion:

Using bitset will make work with binary numbers much easier

4 Likes
16

One thing I noticed is, In Line 17, Newline is missing at the end.

17

Can someone tell me what is wrong with my code?

Solution: 52389257 | CodeChef

I have used long long int and also handled c==0.

18

Thank you so much

19

Thank You so much

20

Just typecast

using namespace std;
#define ll long long int
#define MOD 1000000007
#define fast                          \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);
#define pb push_back
#define mp make_pair
#define fi first
#define se second

void solve()
{
    ll c;
    cin >> c;

    if (c == 0)
    {
        cout << 2 << endl;
        cout << "1 1" << endl;
        return;
    }

    int a[60] = {0};
    int i = 1;
    while (c > 0)
    {
        a[60 - i] = c % 2;
        c = c / 2;
        i++;
    }
    int prev = 0;
    vector<ll> ans;
    for (int i = 0; i < 60; i++)
    {
        if (prev == 0)
        {
            if (a[i] == 1)
            {
                ans.pb((unsigned long long int)pow(2, (60 - i)) - 1);
                prev = 1;
            }
        }
        else
        {
            if (a[i] == 0)
            {
                ans.pb((unsigned long long int)pow(2, (60 - i)) - 1);
                prev = 0;
            }
        }
    }

    cout << ans.size() << endl;
    for (auto &x : ans)
        cout << x << " ";
    cout << endl;
}

int main()
{
    fast;
    int t;
    //t=1;
    cin >> t;
    
    while (t--)
    {
        solve();
    }
    return 0;
}
1 Like
21

Thanks man!

22

apparently a long long took its toll… can someone explain how different 1ll<<n is to 1<<n . or give reference to any article

1 Like
23

Please tell what’s wrong with the code. It is only passing one of the three test cases.
My solution : CodeChef: Practical coding for everyone

24

Because pow returns double or floating value so it may causes the problem.
Refrence: Link

25

Can you please post your code also, that will be a great help for me.

26

What am I missing in here…
https://www.codechef.com/viewsolution/52388386

27

i didnt understand editorial can anyone explain why using this approach any proof?

28

It is there in the first line

30

Just typecast your value returned by pow

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

string binary(long long n)
{
    string s = "";
    if (n == 0)
    {
        s += '0';
        return s;
    }
    while (n > 0)
    {
        long long k = n % 2;
        s += to_string(k);
        n = n / 2;
        // cout << k << s[i] << endl;
    }
    // s[i] = '\0';
    // reverse(s.begin(), s.end());
    return s;
}

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        long long n;
        cin >> n;
        string str = binary(n);
        // cout << str << endl;
        vector<long long> v;
        if (str.size() == 1 and str[0] == '0')
        {
            v.push_back(1);
            v.push_back(1);
        }
        else
        {
            int f = 1;
            for (int i = str.size() - 1; i >= 0; i--)
            {
                char k = f + '0';
                if (str[i] == k)
                {
                    long long y = (long long int)pow(2, i + 1) - 1;
                    v.push_back(y);
                    f = 1 - f;
                }
            }
        }
        cout << v.size() << endl;
        for (int i = 0; i < v.size(); i++)
        {
            cout << v[i] << " ";
        }
        cout << endl;
    }
    return 0;
}
31

I have done exactly the same.

32

I got the approach but can someone please explain that how is the size of the array minimum using this algo?

33

can anyone help me with my code ,
I found a pattern , and it works for each case , cant find anyone that fails .
Please help . Here is code
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
// your code goes here
ll t;
cin>>t;
while(t–)
{
ll c;
cin>>c;
ll twos = 2;
ll temp = twos-1;

    while(temp<c)
    {
        twos = twos*2;
        temp = twos - 1;
    }
    
//    cout<<temp<<"\n";
    ll temp2 = temp - c;
    
    if(temp2>0)
    {
        cout<<2<<"\n";
        cout<<temp2<<" "<<temp<<"\n";
    }
    else
    {
        cout<<1<<"\n";
        cout<<temp<<"\n";
    }
}
return 0;

}

34

Consider the following input.

Input

1
5

Your Output

2
2 7

A_0 viz., 2 doesn’t satisfy the condition A_i = 2^x - 1.