AXNODR - Editorial

editorial
, , , ,
1

PROBLEM LINK:

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

Setter: Sandeep V
Tester: Istvan Nagy, Aryan
Editorialist: Lavish Gupta

DIFFICULTY:

Easy

PREREQUISITES:

None

PROBLEM:

Dazzler has a blank canvas and (N-1) colours numbered from 2 to N.
Let B denote the beauty of the canvas. The beauty of a blank canvas is 1.

Dazzler paints the canvas by using all the (N-1) colours exactly once. On applying the i^{th} colour (2 \leq i \leq N):

  • If i is odd, B = B \& i.
  • If i is even, B = B \oplus i.

Find the beauty of the canvas after applying all (N-1) colours.

Note: The colours are applied in ascending order. Colour number 2 is applied first. The i^{th} numbered colour is applied after (i-1)^{th} numbered colour for all i \gt 2.

Here \& and \oplus denote the bitwise AND and bitwise XOR operations respectively.

EXPLANATION:

The best way to understand what is going on, is to calculate the results for some values of N. Although we will be proving our results, the motivation behind the proofs only comes through the observation and finding out what exactly we need to prove.

Let F(N) denotes the answer when we have N colors. Let us find out the values of F(N) for some values of N.
F(2) = 3, F(3) = 3, F(4) = 7, F(5) = 5, F(6) = 3, F(7) = 3, F(8) = 11 and so on… I highly recommend to continue the process till N = 12 or 15. One thing that you can now observe is, each bit is playing it’s role independently. So, let us try to analyze how each bit is changing.

The first bit

Consider the least significant bit. Initially, this bit is set. Now, if we encounter an even number, we take the XOR of this even number with the resultant. Because this bit is unset in the even number, it remains unchanged in the resultant. If we encounter an odd number, we take AND of this odd number with the resultant. Because this bit is set in the odd number, it remains unchanged in the resultant.

In other words, the first remains unchanged, and because we have that bit set initially, this bit will remain set for all values of N.

The second bit

Let’s first try to find out when is this bit set in the resultant. If you write some values, you will find out that if N\%4 == 1, then this bit is unset, otherwise this bit remains set.

To prove this, we can use induction. As the base case, start with N = 1. In this case, the second bit is unset. Now consider that the second bit is unset for some N = 4\cdot K + 1, and try to simulate the process till 4\cdot K + 1. You will find that this bit remains unset for N \% 4 == 1, and is set for other numbers.

The general bit

Now, let’s talk about third and higher bits. Earlier, we have seen that the we are having cases on modulo 4, so let’s think in that direction only. Consider the block of 4 numbers, like \{4k, 4k + 1, 4k+2, 4k+3\}. Note that if you consider any such block, and the third or higher bit, let say i-th bit (i \geq 3), then either this bit is set in all these 4 numbers, or is unset in all these 4 numbers.

Now, one observation is, for numbers of form 4k + 3, this bit is always unset in the resultant. We can use this observation to comment about this bit in the resultant for 4k+4, 4k+5, 4k+6, 4k+7. If this bit is unset in these 4 numbers, then the bit will remain unset in the resultant as well. If this bit is set in all the 4 numbers, then we can see that if N \% 4 == 0 OR N \% 4 == 1, this bit is set in resultant, otherwise not.

Summary

So, let’s summarize our observations.

The first bits is set in the resultant for all N.
The second bit is unset if N \% 4 == 1, otherwise it is set in the resultant.
If the general bit is unset in N, it remains unset in N. If it is set in N, it becomes unset in resultant if N\%4 == 2 OR N \% 4 == 3, otherwise remains set in the resultant.

Final Answer

Using all the observations above, we have
N \% 4 == 0, ans = N+3
N \% 4 == 1, ans = N
N \% 4 == 2, ans = 3
N \% 4 == 2, ans = 3

TIME COMPLEXITY:

O(1) for each test case.

SOLUTION:

Editorialist's Solution 
#include <bits/stdc++.h>
#define ll long long
#define lld long double


using namespace std;

#define nline '\n'
void solve()
{

ll n;
cin>>n;

if(n%4==2 or n%4==3)cout<<3<<nline;
else if(n%4==0) cout<<(n+3)<<nline;
else cout<<n<<nline;
}



int main()
{   
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
       #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    freopen("Error.txt","w",stderr);
    #endif
    int t=1;
    cin >> t;

    while (t--)
    {
        solve();
    }
}