MINSZ - Editorial

PROBLEM LINK:

Practice
Div1
Div2
Div3

Setter: Abhinav sharma
Tester: Samarth Gupta
Editorialist: Ajit Sharma Kasturi

DIFFICULTY:

EASY

PREREQUISITES:

Bitwise operations

PROBLEM:

An array A of size N is called an interesting array if N \geq 1 and A_i = 2^x -1 for some integer
1 \leq x \leq 60. We need to find one such interesting array with minimum size where the bitwise xor
of all the elements in the array is C.

EXPLANATION:

First let us analyse the binary representation of 2^x -1 . It is 1111\dots ( x times ).

Therefore, intuition suggests us that this problem can be solved constructively as follows:

Let us take an initial empty array arr and also keep track of a variable cur which denotes the current xor of all the elements of arr.

(In the below method the word positon has 0-based indexing ).

Now iterate over i from 60 to 0:

  • If both bits in cur and C at position i are the same i.e either both are set or both are unset, we need not apply any operation and continue to next i.

  • Else we need to add an element to the array in order to change to toggle the bit at position i for cur. Since we can add only numbers of the form 2^x -1, we will add 2^{i+1} - 1 to arr and update cur as cur = cur \oplus (2^{i+1} -1).

After this entire procedure is done, there is one special case left to handle. What if C =0 \hspace{1 mm} ? Then, we will end up with an empty array arr. But an interesting array must have size N \geq 1. Here, we can’t have one element with cur =0 since 2^x -1 \gt 0 for 1 \leq x \leq 60. Therefore, in this special case, we need to add any two equal elements of the form 2^x -1, (for example 1, 1) to arr.

Now, we can output the final array arr along with its size.

TIME COMPLEXITY:

O(60) for each testcase.

SOLUTION:

Editorialist's solution

#include <bits/stdc++.h>
#define ll long long int
using namespace std;

int main()
{
     int tests;
     cin >> tests;
     while (tests--)
     {
          ll C;
          cin >> C;

          ll cur_xor = 0;
          vector<ll> arr;

          for (int i = 60; i >= 0; i--)
          {
               ll bit1 = (1ll << i) & cur_xor;
               ll bit2 = (1ll << i) & C;

               if (bit1 != bit2)
               {
                    arr.push_back((1ll << (i + 1)) - 1);
                    cur_xor ^= (1ll << (i + 1)) - 1;
               }
          }

          if (arr.empty())
               arr = {1, 1};

          cout << arr.size() << endl;
          for (int i = 0; i < arr.size(); i++)
               cout << arr[i] << " ";
          cout << endl;
     }
     return 0;
}

Setter's solution
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define db double
#define el "\n"
#define ld long double
#define rep(i,n) for(int i=0;i<n;i++)
#define rev(i,n) for(int i=n;i>=0;i--)
#define rep_a(i,a,n) for(int i=a;i<n;i++)
#define all(ds) ds.begin(), ds.end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
typedef vector< long long > vi;
typedef pair<long long, long long> ii;
typedef priority_queue <ll> pq;
#define o_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 


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

    int T=1;
    ll sum = 0;
    cin >> T;
    while(T--){
        
        ll c;
        cin>>c;
        
        if(c==0){
            cout<<2<<el<<"1 1"<<el;
        }
        else{
            int prev = -1;
            ll b=0;
            vector<ll> v;
            ll c1=c;
            while(c){
                if((c&1)!=prev){
                    if(prev!=-1) v.pb((1ll<<b)-1);
                    prev = (c&1);
                }
                c>>=1;
                b++;
            }
            v.pb((1ll<<b)-1);
            sum+=v.size();
            cout<<v.size()<<el;
            for(auto h:v) cout<<h<<" ";
            cout<<el;

            ll xr = 0;
            for(auto h:v){
                xr^=h;
                //assert(h>0 && h<(1ll<<60) && __builtin_popcountll(h+1)==1);
            }
            //assert(xr==c1);
        }
    
    }
    cerr<<sum<<el;
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
    return 0;
}


Tester's solution
#include <bits/stdc++.h>
using namespace std;

long long readInt(long long l, long long r, char endd) {
    long long x=0;
    int cnt=0;
    int fi=-1;
    bool is_neg=false;
    while(true) {
        char g=getchar();
        if(g=='-') {
            assert(fi==-1);
            is_neg=true;
            continue;
        }
        if('0'<=g&&g<='9') {
            x*=10;
            x+=g-'0';
            if(cnt==0) {
                fi=g-'0';
            }
            cnt++;
            assert(fi!=0 || cnt==1);
            assert(fi!=0 || is_neg==false);
 
            assert(!(cnt>19 || ( cnt==19 && fi>1) ));
        } else if(g==endd) {
            if(is_neg) {
                x=-x;
            }
            assert(l<=x&&x<=r);
            return x;
        } else {
            assert(false);
        }
    }
}
string readString(int l, int r, char endd) {
    string ret="";
    int cnt=0;
    while(true) {
        char g=getchar();
        assert(g!=-1);
        if(g==endd) {
            break;
        }
        cnt++;
        ret+=g;
    }
    assert(l<=cnt&&cnt<=r);
    return ret;
}
long long readIntSp(long long l, long long r) {
    return readInt(l,r,' ');
}
long long readIntLn(long long l, long long r) {
    return readInt(l,r,'\n');
}
string readStringLn(int l, int r) {
    return readString(l,r,'\n');
}
string readStringSp(int l, int r) {
    return readString(l,r,' ');
}
 
void readEOF(){
    assert(getchar()==EOF);
}
long long pws[61];
void pre(){
    pws[0] = 1;
    for(int i = 1 ; i <= 60 ; i++)
        pws[i] = pws[i-1]*2;
}
vector<int> dig(long long x){
    vector<int> vec;
    while(x)
        vec.push_back(x%2), x /= 2;
    return vec;
}
vector<long long> solve(vector<int> dig){
    vector<long long> ans;
    ans.push_back(pws[dig.size()] - 1);
    int f = 1;
    while(dig.size()){
        if(dig.back() == f)
            dig.pop_back();
        else{
            ans.push_back(pws[dig.size()] - 1), f = 1 - f;
        }
    }
    return ans;
}
int solve(long long x){
    if(x == 0)
        return 0;
    int ans = solve(x/2);
    return (ans + (ans + x)%2);
}
int main() {
	// your code goes here
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int t;
	t = readIntLn(1, 1e5);
	int sum = 0;
	pre();
	while(t--){
	    long long x = readIntLn(0, (1ll << 60) - 1);
	    if(x == 0){
	        sum += 2;
	        assert(sum <= 1e6);
	        cout << 2 << '\n';
	        cout << "3 3" << '\n';
	        continue;
	    }
	    vector<long long> ans = solve(dig(x));
        int count = solve(x);
        assert(ans.size() == count);
        long long j = 0;
        for(auto ele : ans)
            j ^= ele;
        assert(j == x);
        sum += count;
        assert(sum <= 1e6);
        cout << count << '\n';
	    for(auto j : ans)
	        cout << j << " ";
	    cout << '\n';
	}
	readEOF();
	return 0;
}


Please comment below if you have any questions, alternate solutions, or suggestions. :slight_smile:

2 Likes

I did the same and took care of the specialcase . Can anyone tell me which testcase/edgecase am I missing ?
My code

1 Like

Can someone help me with my code, idk what is wrong in it. [Code](https://www.codechef.com/viewsolution/52382138)

In Line 30 , typecast pow(2ll,z) to unsigned long long , then everything should work fine ig.

I believe using long long instead of int should fix the problem

Can any one tell me what is mistake in my codel

Solution: 52368341 | CodeChef

just pow(2ll,i) to (1<<i) works . Why this happened ? It hurts :frowning:

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

I am not getting for which type of test cases my code is giving wrong answer. Your HELP will be much appreciated.

Same question, I had even tested pow function for 2^60 before using :neutral_face:

Corner case: C == 0
Ans:
2
1 1
length of array should be >=1

1 Like

Consider the TestCase :
1
8796093022208

Required Output:
2
17592186044415 8796093022207

Your Ouput:
2
4095 2047

Spolier

Use Long Long int instead of Int

Spoiler

Handle this testcase

Input:
1
0

Output:
2
1 1
2 Likes

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

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

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

Can someone tell me what is wrong with my code?

Solution: 52389257 | CodeChef

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

Thank you so much

Thank You so much

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

Thanks man!