Day 30 | Codeforces Contest 819 A and B | C++

I love the problems in this contest a lot, they are challenging and fun. Do not forget to try problems by yourself first.

Mainak and Array

Let's make some observations

1. We are only talking about a[n-1] and a[0], so if the values of these two elements remain the same, then there will be no effect on the answer

2. If we are considering a subsegment in which neither 1st index is rotated nor the last index, then it doesn't change the value of a[n-1] - a[0]

3. If we are considering a subsegment in which only the first segment is considered, then only a[0] can shift thus we will try to place the smallest value there.

4. Similarly, if only the last index is included then we will try to place the maximum element of the subsegment there.

5. If both indices are included in a segment, then only the following pairs can be at a[0] and a[n-1]

   • a[0], a[n-1] for no shift

   • a[1], a[0] for 1 shift

   • a[2], a[1] for 2 shifts

We can implement the following like this

Point 2

    int minimum_so_far = a[0];
    // If j is ending index of subsegment, starting at 0
    for(int j = 1; j < n-1; j++){
        minimum_so_far = min(minimum_so_far, a[j]);
        ans = max(ans, a[n-1] - minimum_so_far);
    }

Point 3

    // Subarray including end index
    int maximum_so_far = a[n-1];
    // If j is starting index of subsegment, ending at 0
    for(int j = n-2; j > 0; j--){
        maximum_so_far = max(maximum_so_far, a[j]);
        ans = max(ans, maximum_so_far - a[0]);
    }

Point 4

    // Full length subarray
    for(int i = 0; i < n; i++){
        int left = a[i];
        int right = a[(i + n - 1) % n];
        ans = max(ans, right - left);
    }

You can implement the complete solution like this -

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

void solve(){
    int n;
    cin >> n;
    vector<int> a(n);
    for(int &i: a)cin >> i;
    int ans = a[n-1] - a[0];
    // Subarray including starting index
    int minimum_so_far = a[0];
    for(int j = 1; j < n-1; j++){
        minimum_so_far = min(minimum_so_far, a[j]);
        ans = max(ans, a[n-1] - minimum_so_far);
    }
    // Subarray including end index
    int maximum_so_far = a[n-1];
    for(int j = n-2; j > 0; j--){
        maximum_so_far = max(maximum_so_far, a[j]);
        ans = max(ans, maximum_so_far - a[0]);
    }
    // Full length subarray
    for(int i = 0; i < n; i++){
        int left = a[i];
        int right = a[(i + n - 1) % n];
        ans = max(ans, right - left);
    }
    cout << ans << '\n';
}

int main(){
    int t;
    cin >> t;
    while(t--)solve();
}

Bitwise operations

Note - Logic gate is just Bitwise Logic Operations and just go through definitions first before we understand uses.

You know that computer actually deals with 0s and 1s called bits. Actually, operations are done on bits. On the lowest level, all the operations convert into bit logic manipulations using logic gates.

Four main gates/bitwise operations -

1. AND

2. OR

3. XOR

4. NOT

These operations are run between two bits only

Let's see their result

AND operation (both should be 1 for the result to be 1)

Bit 1	Bit 2	Result
0	0	0
0	1	0
1	0	0
1	1	1

OR operation (both should be 1 for the result to be 1)

Bit 1	Bit 2	Result
0	0	0
0	1	1
1	0	1
1	1	1

XOR operation (both should be different for the result to be 1)

Bit 1	Bit 2	Result
0	0	0
0	1	1
1	0	1
1	1	0

NOT operation (reverses bit)

Bit	Result
0	1
1	0

Bit operations on C++

Now the problem is we know how bit operations work on integers in C++

For example, calculate these

1. 12 AND 20

2. 12 OR 20

3. 12 XOR 20

4. NOT 12

To solve these, remember integer in c++ is either 16 bits, 32 bits (default), or 64 bits.

Write all the bits like this

12 is 1100 and 17 is 10001

expressing them in 32 bits become

12 = 00000000 00000000 00000000 00001100

17 = 00000000 00000000 00000000 00010100

Now just apply bits to the corresponding bit

Hence answers will be

1. 12 = 00000000 00000000 00000000 00001100 AND ( & ) 20 = 00000000 00000000 00000000 00010100 RESULT 4 = 00000000 00000000 00000000 00000100

2. 12 = 00000000 00000000 00000000 00001100 OR ( | ) 20 = 00000000 00000000 00000000 00010100 RESULT 28 = 00000000 00000000 00000000 00011100

3. 12 = 00000000 00000000 00000000 00001100 XOR (^) 20 = 00000000 00000000 00000000 00010100 RESULT 24 = 00000000 00000000 00000000 00011000

4. NOT (~) 12 = 00000000 00000000 00000000 00001100 RESULT 4294967283 = 11111111 11111111 11111111 11110011

Why does C++ shows some negative number when I try this in code?

In C++ default integers are signed integers, which are 32 bits integers but use the 32nd bit as a convention to store signs.

It will work well if you try with unsigned integers like this

#include<bits/stdc++.h>
using namespace std;
int main(){
    int a = 12;
    unsigned int b = 12;
    cout << ~a << "\n";
    cout << ~b << "\n";
}

Mainak and Interesting Sequence

This is an interesting problem.

Notice one property of XOR

A XOR A = 0

A XOR A XOR A = 0 XOR A = A

Similarly, if there are even As then it will be 0

else it will be A

Now every element needs to be at least 1, so the sum will be at least n.

So we can print (n-1) 1s and remain in the end.

But wait, n-1 must be even so XOR of 1s is 0

if n is odd then we print (n-1) 1s and print the last integer as remaining

What if n is even?

Then we can print (n-2) 1s and the last two as equal values which is remaining/2

For that remaining must be even, and since n-2 was even, thus m must be even as well

So we can go ahead and implement this

void solve(){
    int n,m;
    cin >> n >> m;
    if(m < n){
        cout << "No\n";
        return;
    }
    if(n % 2 == 0 && m % 2 == 1){
        cout << "No\n";
        return;
    }
    cout << "Yes\n";
    if(n % 2 == 1){
        int rem = m - ( n - 1 );
        for(int i = 0; i < n-1; i++)cout << "1 ";
        cout << rem << "\n";
    }
    if(n % 2 == 0){
        int last_2_rem = m - (n - 2);
        for(int i = 0; i < n-2; i++)cout << "1 ";
        cout << last_2_rem/2 << " " << last_2_rem/2 << "\n";
    }
}

Complete Submission - Submission Link

Please like and share my posts if they are helpful.