MINSZ - Editorial

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

Please tell what’s wrong with the code. It is only passing one of the three test cases.
My solution : Solution: 52391379 | CodeChef

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

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

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

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

It is there in the first line

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;
}

I have done exactly the same.

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

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;

}

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.

@suman_18733097 can you please help with this one?

1 Like

Can someone help, I can’t figure out which case am I missing.
Solution: 52365564 | CodeChef

for _  in range(int(input())):
    n = int(input())
    if n==0:
        ans += "1\n1 1\n"
        continue
    if (n+1)&n==0:
        ans += str(1)+"\n" + str(n)+"\n"
        continue
    num = bin(n)[2:]
    l = len(num)
    res = []
    cnt = 1
    for i in range(len(num)):
        if num[i]=="1" and (cnt)%2!=0:
            res.append(int('1'*(l-i), 2))
            cnt+=1
        elif num[i]=="0" and cnt%2==0:
            res.append(int('1'*(l-i), 2))
            cnt+=1
        elif num[i]=='0' and cnt%2!=0:
            continue
        elif num[i]=='1' and cnt%2==0:
            continue
    ans += str(len(res)) + "\n"
    for i in res:
        ans += str(i) + " "
    ans += "\n"
    
print(ans)```

Let’s understand it with an example. But before going through the example, you should know this property of the Bitwise Exclusive-OR function.

  • Let A = [A_1,\ A_2,\ A_3,\ \dots,\ A_N]. Let X = A_1 \oplus A_2 \oplus A_3\oplus \dots\oplus A_N (\oplus\ \text{denotes bitwise EX-OR operator}).

    • i^{th} bit in X is set iff the number of elements (of A) having i^{th} bit set is Odd.

Now you know this property, we’ll move into an example.

Let \text{bin(C) = 1 1 0 1 0 0 0 1}. It is given that A_i = (2^x - 1)\ \forall\ i\in [1, N].

Moving from \text{MSB} to \text{LSB}, for now, let i = 0 denote position of \text{MSB} and i = K denote position of \text{LSB}:

  • i = 0: \text{bit}[\text{i}] = 1. So, we need an Odd number of elements having this bit set. To minimise the number of elements, the number of elements having this bit set shall be 1. Given that A_i = 2^x - 1. So we will choose A_1 = (11111111)_2 = 2^8 - 1 = (255)_{10}.

    • Why can’t we choose A_1 = (2^K - 1), \text{for some}\ K \ge 9?

      • If we pick K\ge9, we have to reset other higher order bits too → requires more elements. -\ (1)
  • i = 1:\ \text{bit[i] = 0}. So, we need odd number of elements having this bit set. Notice that A_1 = (2^8 - 1) already has this bit set and it is the only element so far. Since the requirement (Odd number of elements having this bit set) is already satisfied, we proceed for next bit.

  • i = 2:\ \text{bit[i] = 0}. So, we need Even number of elements having this bit set. Our sequence so far is [(11111111)_2] → there are odd number of elements having this bit set. We have to make it even. So, we add another element A_2 = (111111)_2 = (2^6 - 1) = (63)_{10}.

    • Now A = [(11111111)_2,\ (111111)_2] = [(255)_{10},\ (63)_{10}]
  • This process continues., and at the end the sequence A becomes
    A = [(11111111)_2,\ (111111)_2,\ (11111)_2,\ (1111)_2,\ (1)_2] = [(255)_{10},\ (63)_{10},\ (31)_{10},\ (15)_{10},\ (1)_{10}].

The only step you should bother about is marked as (1): Setting up bits unnecessarily will require additional elements to reset. So, to minimise the number of elements, we make use of the property of Bitwise Exclusive-OR \oplus operation:
i^{th}\text{bit is set iff the number of elements having this bit set is Odd}.

At each step, we will greedily pick an Integer that minimises the additional elements required. The way we choose an element will impact the number of elements required in the next iteration of i.

You should also note that |A| will not exceed 60 and the input for |A| = \text{60} should be C = (101010\dots)_2,\ (|\text{bin}(c))| = 60.

My Solution using same approach
/*
* Author: Chitturi Sai Suman
*/
#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;

void solve() {
    ll N = 0;
    cin >> N;
    if(N == 0) {
        cout << "2\n1 1\n";
        return;
    }
    vector<ll> answer;
    int c = 0;
    for(int i = 61; i >= 0; i--) {
        if(((N >> i) & 1) == 1) {
            if(c % 2 == 0) {
                answer.push_back((1LL << (i + 1)) - 1);
                c++;
            }
        }
        else {
            if(c % 2 == 1) {
                answer.push_back((1LL << (i + 1)) - 1);
                c++;
            }
        }
    }
    cout << c << '\n';
    for(auto& x: answer) {
        cout << x << ' ';
    }
    cout << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 0;
    cin >> t;
    for(; t > 0; t--) {
        solve();
    }
    return 0;
}
1 Like

@viraj_008

This should have been

if n == 0:
    and += "2\n1 1\n"

instead.

That’s really silly of me!
Thanks for pointing out

Thank you so much dear

Can someone please check why the code gives SIGCONT error?
I just started out with CC, a small help would be greatly appreciated.

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

void print(vector<ll> v){
	cout << v.size() << endl;
	sort(v.begin(), v.end());
	for(ll i = 0; i < v.size(); i++){
		cout << v[i] << " ";
	}
	cout << endl;
}

int main(){
	#ifndef ONLINE_JUDGE	
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
	ll t;
	cin >> t;
	while(t--){
		vector<ll> v;
		ll c, res = 0;
		cin >> c;
		for(ll i = 60; i >= 0; i--){
			//stores the difference between c and the current bit
			ll num1 = (1 << i) & c;

			//stores the difference between the current bit and result
			ll num2 = (1 << i) & res;

			if (num1 != num2){
				v.push_back((1 << (i + 1)) - 1);
				res ^= ((1 << (i + 1)) - 1);
			}
		}
		if(v.size() == 0){
			v.push_back(1);
			v.push_back(1);
		}
		print(v);
	}	
}

Are you trying to “Run” without Providing “Custom Input”?

Either way, there’s these errors:

[simon@simon-laptop][13:36:03]
[~/devel/hackerrank/otherpeoples]>./compile-latest-cpp.sh 
Compiling adarsh500-MINSZ.cpp
Executing command:
  g++ -std=c++17 adarsh500-MINSZ.cpp -O3 -g3 -Wall -Wextra -Wconversion -DONLINE_JUDGE -D_GLIBCXX_DEBUG    -fsanitize=undefined -ftrapv
adarsh500-MINSZ.cpp: In function ‘void print(std::__debug::vector<long long int>)’:
adarsh500-MINSZ.cpp:8:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(ll i = 0; i < v.size(); i++){
                   ~~^~~~~~~~~~
Successful
[simon@simon-laptop][13:36:10]
[~/devel/hackerrank/otherpeoples]>echo "3
1
2
3
" | ./a.out
adarsh500-MINSZ.cpp:27:26: runtime error: shift exponent 60 is too large for 32-bit type 'int'
adarsh500-MINSZ.cpp:30:26: runtime error: shift exponent 60 is too large for 32-bit type 'int'
adarsh500-MINSZ.cpp:33:32: runtime error: shift exponent 33 is too large for 32-bit type 'int'
adarsh500-MINSZ.cpp:34:28: runtime error: shift exponent 33 is too large for 32-bit type 'int'
1
1 
2
1 3 
1
3 
2 Likes