FINDABC-Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Utkarsh Gupta
Tester: Satyam, Jatin Garg
Editorialist: Devendra Singh

DIFFICULTY:

1843

PREREQUISITES:

Greedy algorithms, Bitwise XOR

PROBLEM:

Chef has 3 hidden numbers A, B, and C such that 0 \leq A, B, C \leq N.

Let f be a function such that f(i) = (A \oplus i) + (B \oplus i) + (C \oplus i). Here \oplus denotes the bitwise XOR operation.

Given the values of f(0), f(1), \dots, f(N), determine the values of A, B, and C.

It is guaranteed that at least one tuple exists for the given input. If there are multiple valid tuples of A, B, C, print any one.

EXPLANATION:

A, B, C \leq N\leq 10^5 \implies only first 18 bits can be set to 1 in A, B\: and\: C.
Also as only the sum f(i) = (A \oplus i) + (B \oplus i) + (C \oplus i) is taken into consideration for each bit from 0^{th}(least significant) bit to the 17^{th} bit only the number of set bits is important.

only the number of set bits is important.

Let countset_j represent the count of numbers in which the j^{th} bit is set to 1.

f[i] = \sum_{j=0}^{17} 2^{j}*((i & 2^j)?(3-countset_j):countset_j). Thus only the number of set bits for each bit is important to calculate the answer.

Let set be the number of integers in which i^{th} bit is set to 1 and unset be the number of integers in which i^{th} bit is set to 0.
Then set+unset=3 and set-unset= \frac{f[0] - f[2^i]}{2^i}
The number of set bits for each bit i (2^i<=N) can be calculated as \frac{(3+\frac{f[0] - f[2^i]} {2^i})}{2}.

Initialize A, B and C as 0. Now iterate over bits from most significant to least significant bit and maintain the order of elements (ascending or descending), calculate the number of set bits for each bit using the above formula, add them to the the numbers in ascending order. For example if number of set bits for a bit is 1 add it to the smallest number, if it is 2 add it to the two smaller values and so on. This greedy approach produces one of the correct answers.

This greedy approach produces one of the correct answers.

Let i^{th} bit from right be the first bit which is not same in all A,B\: and\: C. If it is present in only one number, set it in A and then whenever we have a choice of setting the bits i.e. set bit count is 1 or 2 we set them in B and C as they can never exceed A. Since an answer always exists this produces a correct answer.
If it is present in two numbers set it in A and B and then whenever we have a choice of setting the bit in one number i.e. set bit count is 1, we set it in C as it can never exceed A. When we get a choice of setting a bit in two numbers for the first time we set it in A and C and later every time in B and C
Thus, this greedy approach always produces one of the correct answers.

For details of implementation please refer to the attached solutions.

TIME COMPLEXITY:

O(N) for each test case.

SOLUTION:

Setter's solution
//Utkarsh.25dec
#include <bits/stdc++.h>
#define ll long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define vl vector <ll>
#define all(c) (c).begin(),(c).end()
using namespace std;
ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll modInverse(ll a){return power(a,mod-2);}
const int N=500023;
bool vis[N];
vector <int> adj[N];
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;
            }

            if(!(l <= x && x <= r))
            {
                cerr << l << ' ' << r << ' ' << x << '\n';
                assert(1 == 0);
            }

            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,' ');
}
int sumN=0;
void solve()
{
    int n=readInt(2,100000,'\n');
    sumN+=n;
    assert(sumN<=200000);
    int A=0,B=0,C=0;
    int f[n+1]={0};
    for(int i=0;i<=n;i++)
    {
        if(i!=n)
            f[i]=readInt(0,100000000,' ');
        else
            f[i]=readInt(0,100000000,'\n');
    }
    for(int i=0;i<20;i++)
    {
        if((1<<i)>n)
            break;
        ll x=f[0];
        ll y=f[(1<<i)];
        ll diff=y-x;
        diff/=(1<<i);
        if(diff==3)
        {
            
        }
        else if(diff==-3)
        {
            A|=(1<<i);
            B|=(1<<i);
            C|=(1<<i);
        }
        else if(diff==1)
        {
            A|=(1<<i);
        }
        else if(diff==-1)
        {
            A|=(1<<i);
            B|=(1<<i);
        }
        else
        {
            assert(false);
        }
    }
    if(A>n)
    {
        int rec=20;
        for(int i=20;i>=0;i--)
        {
            if((A&B&C&(1<<i))!=0)
                continue;
            if((A&(1<<i))==0)
                continue;
            A^=(1<<i);
            C^=(1<<i);
            rec=i;
            break;
        }
        if(B>n)
        {
            for(int i=rec-1;i>=0;i--)
            {
                if((A&B&C&(1<<i))!=0)
                    continue;
                if((B&(1<<i))==0)
                    continue;
                B^=(1<<i);
                if((A&(1<<i))==0)
                    A^=(1<<i);
                else
                {
                    C^=(1<<i);
                    if(C>n)
                    {
                        C^=(1<<i);
                        B^=(1<<i);
                        continue;
                    }
                }
                break;
            }
        }
    }
    cout<<A<<' '<<B<<' '<<C<<'\n';
    assert(max({A,B,C})<=n);
    for(int i=0;i<=n;i++)
        assert(f[i]==((A^i)+(B^i)+(C^i)));
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    int T=readInt(1,20000,'\n');
    while(T--)
        solve();
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}
Editorialist's Solution
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define pb push_back
#define all(_obj) _obj.begin(), _obj.end()
#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
ll INF = 1e18;
const int N = 1e5 + 11, mod = 1e9 + 7;
ll max(ll a, ll b) { return ((a > b) ? a : b); }
ll min(ll a, ll b) { return ((a > b) ? b : a); }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void sol(void)
{
    int n;
    vector<int> a(3, 0);
    cin >> n;
    int f[n + 1];
    for (int i = 0; i <= n; i++)
        cin >> f[i];
    for (int i = 18; i >= 0; i--)
    {
        if ((1 << i) > n)
            continue;
        sort(all(a));
        int diff = (f[1 << i] - f[0]) / (1 << i);
        if (diff == -3)
        {
            a[0] ^= (1 << i);
            a[1] ^= (1 << i);
            a[2] ^= (1 << i);
        }
        else if (diff == 1)
        {
            a[0] ^= (1 << i);
        }
        else if (diff == -1)
        {
            a[0] ^= (1 << i);
            a[1] ^= (1 << i);
        }
    }

    cout << a[0] << ' ' << a[1] << ' ' << a[2] << '\n';
    return;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    int test = 1;
    cin >> test;
    while (test--)
        sol();
}
2 Likes

Brother i implemented correct solution but iterate over o … (max_bit) i got wrong answer
Going from max_bit … 0 i got accepted
Why??
I see other soln and i just revrese my loop from high to low then it aceepted
:((((( Plz explain

can anyone please explain more clearly …

1 Like

Yep , it won’t work when you go from lower to higher bits.
If you see 1000 (8) > 111 (7) , that is the individual contribution of 4th bit is greater than the combined contribution of all the remaining 3 bits. [2 ^ x > 1 + 2 + 4 + ... 2 ^ (x - 1) ].

We should consider significant bits first from left to right as we should at each bit ensure that all of our numbers remain smaller than n by assigning the smaller number that bit.

Say we have n = 1011 , a = 0 , b = 0 , c = 0
We go from 4th bit to the 1st bit and at every bit we start to build a prefix of a , b , c in their binary representation and at any step if we made all the numbers smaller than n we can actually assign the remaining bits in any order the reason being mentioned above that the contribution of a bit is greater than the combined contribution of all the bits to its right so whatever bits we assign the numbers won’t get bigger than n.

But if we go from lower to higher bits , it is possible that we made any of a , b , c bigger than than n. Hope that gives you some idea about why this thing works .

2 Likes

brother can you help and explain this solution more clearly

1 Like

Anyone please explain it more clearly … :frowning:

1 Like

Can anyone please explain the reason of moving from higher to lower with any contradicting example. For me going from lower to higher is looking good only, because we are always keeping A,B,C sorted
For ex: lets work in 3 bits here(0th,1th,2th)
right To left: let no of setBit in 0th pos is 1: so our A,B,C are:
001 000 000
no of SetBit at 1th pos is 2: so A,B,C are:
001 010 010
no of setBit at 2th pos is 2: so A,B,C are:
101 110 010
Largest no acheived in this is (110=6)
And if we move from left to right we will get the same largest number…

1 Like

Suppose we have N = 10, number of bits set for each J = {2, 2, 1, 2}. A combination of A,B,C which won’t pass is {15, 11, 0} = {1111, 1011, 0}. Another which won’t pass is {11, 8, 7} = {1011, 1000, 111}. You need some way of getting to {10, 9, 7} = {1010, 1001, 111}

can you please explain more ?

Go through the explanation in the image and zoom it sufficient enough to understand each and every thing mentioned.

5 Likes

@tushar_kumar1
@awasthi007 and anyone who wanted to understand this thing …

1 Like

which also means that when the difference of (set-unset) = (-1), then set that bit in the smallest number.
But in the editorialist’s solution, we are setting this bit in the two smallest numbers. Why?

In my solution i have subtracted f[1<<i] from f[0], logic is still the same.

1 Like

oops… my bad. :disappointed_relieved:

thank u @letsdosmtgdiff

Try this case
1
4
11 12 13 14 7

Expected Values : A=4 B=4 C=3
Your Code’s Values: A=5 B=4 C=2

Let me know if this works for you…

1 Like

Same here.

How do you practice for these types of question ? :sob: :cry:

I think before doing these kind of ques, we should know how to find bitwise XOR operation .

same , I did the same approach while on contest but it sill gives me wa : Solution: 68756358 | CodeChef
please check the submission and help me