CHEFPROG - Editorial

[chief_surya01]

Problem links:

[Practice] CHEFPROG Problem - CodeChef
[Codeyssey] CodeChef: Practical coding for everyone

Author:- [V Surya Kumar] chief_surya01 | CodeChef User Profile for V Surya Kumar | CodeChef
Editorialist:- [V Surya Kumar] chief_surya01 | CodeChef User Profile for V Surya Kumar | CodeChef

DIFFICULTY:- Medium
PREREQUISITES:- Binary Numbers (0r) Bit Manipulation

---

Problem

We are given with an array of integers, we can change at most K elements in the array by either inverting "no" bit or "one" bit of a number. We have to make the changes in such a way that,

• If the size of the array (N) is Even,
  the array should be lexicographically maximum.

• If the size of the array (N) is Odd,
  the array should be lexicographically minimum.

What is Inverting a bit?

If the binary representation of a number is:
→ 10101
Inverting the bit at position 4 changes the number with its binary representation as:
→ 11101
Inverting the bit at position 1 changes the number with its binary representation as:
→ 10100

What is Lexicographical Order?

Lexicographical order also known as Dictionary Order, is one way of ordering elements in such a way that:

• 123 \lt 124
• 1234 \lt 1249
• 199 \lt 911

Find the detailed meaning at this Wikipedia Link.

Explaination

We can solve the question by dividing it into two parts, i.e.

1. The first part, when we have to make the array lexicographically maximum (N is even).

As we can change at most K elements, we will choose at most K no. of elements/numbers possible starting from the left side of the array and maximise them.

• Excluding the numbers which are of the form 2^p-1 (for any natural no. p). Because the binary representation of the numbers will be in the form 1, 11, 111, 1111, 1111.... And we can’t maximise the number by changing/inverting any bit.

• For any other number, we can maximise the number by changing left most zero bit -to- one bit ( i.e most significant unset bit to set bit). For example,
  – Inverting the leftmost unset bit of 5, will make the number 7.
  – 5 → 101
  – 7 → 111
  Changing any unset bit of a number to set bit always maximises the number.

In this way, we can change the array into lexicographically maximum order by repeating the same process for at max K numbers.


2. The second part when we have to make the array lexicographically minimum (N is odd).

As we can change at most K elements, we will choose at most K no. of elements/numbers possible starting from the left side of the array and minimise them.

• For any number, we can minimise the number by changing left most one bit -to- zero bit ( i.e most significant set bit to unset bit). For example,
  – Inverting the leftmost set bit of 5, will make the number 1.
  – 5 → 101
  – 1 → 001
  Changing any set bit of a number to unset bit always minimises the number.

In this way, we can change the array into lexicographically minimum order by repeating the same process for at max K numbers.

Solution:

Editorialist’s Solution:-

// Created by surya (chief_surya01 || surya-x)
#include<bits/stdc++.h>
using namespace std;

typedef long long int ll;

#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

void lexicographically_max(ll arr[], int n, int k){
    int i=0, j, pos, counter;

    while(i<n && k){
        // Handling the except case when the element is in the 1, 11, 111...
        if( !( arr[i] & (arr[i]+1) ) ){
            i++; continue;
        }
        
        // For any other no.
        counter = 0;
        // Finding the position of left most unset bit.
        for(j=arr[i]; j>0; j=j>>1){
            if( (j&1) == 0){
                pos = counter;
            }
            counter++;
        }
        // Changing the leftmost unset bit to set bit and storing in the array itself.
        arr[i] = (arr[i] | (1<< (pos) ));
        i++; k--;
    }
}

void lexicographically_min(ll arr[], int n, int k){
    int i=0;
    ll temp;
    while(i<n && k){
        temp = arr[i];

        temp |= temp >> 1;
        temp |= temp >> 2;
        temp |= temp >> 4;
        temp |= temp >> 8;
        temp |= temp >> 16;

        temp >>= 1;
        
        // Changing the leftmost set bit to unset bit.
        arr[i] = arr[i] & temp;

        i++; k--;
    }
}

void solve(){
    int n, k, i;
    cin>>n>>k;
    ll arr[n];
    for(i=0; i<n; i++)
        cin>>arr[i];

    // calling the functions depending upon the no. of elements in the array.
    if (n%2==0){
        lexicographically_max(arr, n, k);
    }
    else{
        lexicographically_min(arr, n, k);
    }

    // Printing the array as output
    for(i=0; i<n; i++)
        cout<<arr[i]<<" ";
    
    cout<<endl;
}

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

Links to refer to learning, how to set & unset leftmost unset/set bit.

• Set the Left most unset bit
• Find most significant set bit of a number