Binary Removals
Source: codechef
Difficulty: 1572

Binary Removals
Given a
binary
string$S$of length$N$, and two integers$X$and$K$. Your task is to empty the string by performing the following operation :
In one operation, you may select any subsequence$^{\dagger}$of the string such that the number of
inversions$^{\dagger}$in the subsequence lies in the range$[0, X]$and is divisible by$K$.
Remove the selected subsequence from the string.
Your task is to determine the
minimum number of operations
required to empty the string.$^{\dagger}$A string$T$is called a
subsequence
of another string$S$if$T$can be derived from$S$by deleting zero or more characters without changing the order of the remaining characters.$^{\dagger}$An
Inversion
in a binary string$S$is a pair of indices$(i, j)$such that$i \lt j$and$S_i$= '$1$',$S_j$= '$0$'. For example, the string$S =$"$01010$" contains$3$inversions :$(2, 3)$,$(2, 5),$$(4, 5)$Input Format
The first line contains an integer$T$, the number of test cases.
For each test case:
The first line contains three integers$N$,$X$and$K$, where$N$is the length of the binary string.
The second line contains a binary string of length$N$.
Output Format
For each test case, output on a new line the minimum number of operations required to empty the string.
Constraints$1 \leq T \leq 5 \times 10^5$$1 \leq N \leq 5 \times 10^5$$1 \leq K \leq 10^9$$0 \leq X \leq 10^9$Sum of$N$over all test cases does not exceed$5 \times 10^5$.
Sample 1:
Explanation:
Test case$1$:
You can remove the complete string as it has$1$inversion.
Test case$2$:
One possible sequence of operations is as follows:$[\underline{1} 1 \underline{10} 10] \xrightarrow{\text{subsequence } 110} [110]$, number of inversions in subsequence$110$is$2$which is divisible by$2$.
Now again remove subsequence$110$to empty the string.
It can be proven that for this string there is no way to empty the string in less than$2$operations.

Sample Input:
2
2 2 1
10
6 100 2
111010

Sample Output:
1
2

C++ solution:
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")

using namespace std;
using namespace __gnu_pbds;

#define ll long long
#define f(i, n) for (ll i = 0; i < n; i++)
#define ia(a, n) \
ll a[n];     \
f(i, n) cin >> a[i]
#define iv(v,n) vector<ll> v(n); f(i,n) cin >> v[i]
#define MOD (1000000007)
#define INF 1000000000000000000LL // Infinity for ll
#define mp make_pair
#define nline '\n'
#define yes cout << "YES\n"
#define no cout << "NO\n"

template<typename T>
using os = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template<typename T>
using oms = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

// read question properly
// don't forget newlines!!!!!!
// take care about cin >> t;
// comment the optimization before debugging
// ALWAYS USE FIXED << SETPRECISION WHILE OUTPUTTING FLOATS

void solve() {
    int n,x,k;
    cin >> n >> x >> k;
    int c1 = 0;
    string s;
    cin >> s;
    ll inv = 0;
    f(i,n) {
        if(s[i] == '1') {
            c1++;
        }
        else{
            inv += c1;
        }
    }
    if(inv % k == 0 && inv <= x) {
        cout << 1 << nline;
    }
    else{
        cout << 2 << nline;
    }
}

int main() {
#ifdef PRADY
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    clock_t T = clock();
#endif

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

    long long t = 1;
    cin >> t;

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

#ifdef PRADY
    cout << "\nTime taken: " << ((float) (clock() - T)) / CLOCKS_PER_SEC << " seconds";
#endif
    return 0;
}

Go solution:
package main

import (
    "bufio"
    "fmt"
    "os"
)

type Scanner struct {
    scanner *bufio.Scanner
}

func NewScanner() *Scanner {
    scanner := bufio.NewScanner(os.Stdin)
    scanner.Split(bufio.ScanWords)
    scanner.Buffer(make([]byte, 1024), 1024*1024)
    return &Scanner{scanner: scanner}
}

func (s *Scanner) ReadInt() int {
    s.scanner.Scan()
    num := 0
    for _, ch := range s.scanner.Bytes() {
        num = num*10 + int(ch-'0')
    }
    return num
}

func (s *Scanner) ReadString() string {
    s.scanner.Scan()
    return s.scanner.Text()
}

func calculateInversions(s string) int {
    zeros := 0
    inversions := 0
    
    for i := len(s) - 1; i >= 0; i-- {
        if s[i] == '0' {
            zeros++
        } else {
            inversions += zeros
        }
    }
    
    return inversions
}

func minOperations(n, x, k int, s string) int {
    totalInversions := calculateInversions(s)
    
    if totalInversions <= x && totalInversions%k == 0 {
        return 1
    }
    
    return 2
}

func solve(scanner *Scanner, writer *bufio.Writer) {
    t := scanner.ReadInt()
    
    for i := 0; i < t; i++ {
        n := scanner.ReadInt()
        x := scanner.ReadInt()
        k := scanner.ReadInt()
        s := scanner.ReadString()
        
        result := minOperations(n, x, k, s)
        fmt.Fprintln(writer, result)
    }
}

func main() {
    scanner := NewScanner()
    writer := bufio.NewWriter(os.Stdout)
    defer writer.Flush()
    
    solve(scanner, writer)
}

Java solution:
/**
 * @author Abhisek Singh (Zyroßeast)
 * 
 */

import java.io.DataInputStream;
import java.io.IOException;

public class Main {

   /**
    * Main logic for the program.
    * 
    * @param args Not Used anywhere
    * @throws IllegalArgumentException If any Error happens while processing data.
    * 
    */
    public static void main(String[] args) throws IllegalArgumentException {
        initializeIO();
        try {
            int __ = nextInt(), i, n, x, k, ones;
            long inversions;
            StringBuilder sb = new StringBuilder();
  
            while(__ -- > 0) {
                n = nextInt(); x = nextInt(); k = nextInt();
                next(sb);
                
                for(inversions = i = ones = 0; i < n; i++) {
                    if(sb.charAt(i) == '0') {
                        inversions += ones;
                    } else {
                        ones++;
                    }
                }
                
                outData.append(inversions <= x && inversions % k == 0 ? 1 : 2).append('\n');
            }
        
        } catch(IllegalArgumentException iae) {
            close();
            throw iae;
        }
        
        close();
    }
    
    
    
    
    
    
    
    
    
    
   /* The methods below are used for low level IO operations
    that will be used in the program. */
     
   /** InputStream with implemented buffering for faster input */
    private static DataInputStream dis;
   /** Buffer for input */
    private static byte[] buffer;
   /** Variables for reading buffer */
    private static int bytesRead, bufferPos;
   /** Unsynchronized Mutable String to store Output */
    private static StringBuilder outData;
    
   /**
    * Initializes the IO objects.
    * To be called before using IO methods.
    * 
    */
    private static void initializeIO() {
        dis = new DataInputStream(System.in);
        buffer = new byte[1 << 16];
        read();
        
        outData = new StringBuilder();
    }
    
   /**
    * Closes IO objects after execution.
    * 
    */
    private static void close() {
        try {
            System.out.print(outData);
            dis.close();
        }
        catch(IOException e) {
        }
    }
    
   /** To store next byte in buffer for Operations. */
    private static byte c;
   /** To store if a integer type data is negative or not. */
    private static boolean neg;
    
   /**
    * @throws IllegalArgumentException If the next input data is not an integer type.
    * 
    * @return The next Integer data from the input data
    * 
    */
    private static int nextInt() throws IllegalArgumentException {
        skipWhiteSpace();
        int temp = 0;
        
        neg = (c == '-');
        if(neg) {
            read();
        }

        do {
            if(!isDigit()) {
                throw new IllegalArgumentException();
            }
            
            temp = temp * 10 + c - '0';
            read();
        } while(!(c == '\n' || c == ' ' || c == '\r') && (c != -1));
        
        return neg ? -temp : temp;
    }
    
   /**
    * @param n The size of the array.
    * @throws IllegalArgumentException If the next input data is not an integer type.
    * @return The Integer array with the specified number of elements.
    * 
    */
    private static int[] nextIntArr(int n) throws IllegalArgumentException {
        int[] arr = new int[n];
        for(int i = 0; i < n; i ++) arr[i] = nextInt();
        return arr;
    }
    
   /**
    * @throws IllegalArgumentException If the next input data is not an integer type.
    * 
    * @return The next Long data in the input data
    * 
    */
    private static long nextLong() throws IllegalArgumentException {
        skipWhiteSpace();
        long temp = 0;

        neg = (c == '-');
        if (neg) {
            read();
        }
        
        do {
            if(!isDigit()) {
                throw new IllegalArgumentException();
            }
            
            temp = temp * 10L + c - '0';
            read();
        } while(!(c == '\n' || c == ' ' || c == '\r') && (c != -1));

        return neg ? -temp : temp;
    }

   /**
    * @param n The size of the array.
    * @throws IllegalArgumentException If the next input data is not an long type.
    * @return The Long array with the specified number of elements.
    * 
    */
    private static long[] nextLongArr(int n) throws IllegalArgumentException {
        long[] arr = new long[n];
        for(int i = 0; i < n; i ++) arr[i] = nextLong();
        return arr;
    }
    
   /**
    * @throws IllegalArgumentException If the next input data is not float or integer.
    * 
    * @return The next Double data in the input stream.
    * 
    */
    private static double nextDouble() {
        skipWhiteSpace();
        double temp = 0.0d;
        
        neg = (c == '-');
        if(neg) {
            read();
        }
        
        if(c != '.') {
            do {
                if(!isDigit()) {
                    throw new IllegalArgumentException();
                }
            
                temp = temp * 10.0d + c - '0';
                read();
            } while(c != '.' && !(c == '\n' || c == ' ' || c == '\r') && (c != -1));
        }
        
        if(c == '.') {
            double div = 1.0d;
            read();
            
            while(!(c == '\n' || c == ' ' || c == '\r') && (c != -1)) {
                if(!isDigit()) {
                    throw new IllegalArgumentException();
                }
            
                temp = temp * 10.0d + c - '0';
                div *= 10.0d;
                read();
            }
            
            temp /= div;
        }
        
        return neg ? -temp : temp;
    }

   /**
    * @param n The size of the array.
    * @throws IllegalArgumentException If the next input data is not an double type.
    * @return The Double array with the specified number of elements.
    * 
    */
    private static double[] nextDoubleArr(int n) throws IllegalArgumentException {
        double[] arr = new double[n];
        for(int i = 0; i < n; i ++) arr[i] = nextDouble();
        return arr;
    }
    
   /**
    * Checks if a byte is number or not.
    * 
    */
    private static boolean isDigit() {
        return (c >= '0' && c <= '9');
    }
  
   /** Stores the initial length of the given StringBuilder in the following functions. */
    private static int length;
   
   /**
    * Writes the remaining data from the current line from the input data in the given StringBuilder.
    * 
    * @param sb StringBuilder object in which the data will be stored.
    * @throws IllegalArgumentException If there is no byte left in input data.
    * @return The StringBuilder object after refilling it.
    *
    */
    private static StringBuilder getLine(StringBuilder sb) throws IllegalArgumentException {
        sb.setLength(0);
        
        while(c != -1) {
            if(c == '\n' || c == '\r') {
                break;
            }
            
            sb.append((char)c);
            read();
        }
        
        if(sb.length() == 0) {
            throw new IllegalArgumentException();
        }
        
        return sb;
    }
    
   /**
    * Writes the next line from the current line from the input data in the given StringBuilder.
    * 
    * @param sb StringBuilder object in which the data will be stored.
    * @return The StringBuilder object after refilling it.
    *
    */
    private static StringBuilder nextLine(StringBuilder sb) {
        skipLine(); getLine(sb);
        return sb;
    }
    
   /**
    * Appends the next word from the input data in the given StringBuilder
    * 
    * @param sb StringBuilder object in which the data will be stored.
    * @throws IllegalArgumentException If there is no byte left in input data.
    * @return The StringBuilder object after filling it.
    *
    */
    private static StringBuilder addNext(StringBuilder sb) throws IllegalArgumentException {
        skipWhiteSpace();
        length = sb.length();
        
        while(c != -1) {
            if(c == ' ' || c == '\n' || c == '\r') {
                break;
            }
            
            sb.append((char)c);
            read();
        }
        
        if(sb.length() == length) {
            throw new IllegalArgumentException();
        }
        
        return sb;
    }
    
   /**
    * Writes the next word from the input data in the given StringBuilder
    * 
    * @param sb StringBuilder object in which the data will be stored.
    * @return The StringBuilder object after refilling it.
    *
    */
    private static StringBuilder next(StringBuilder sb) {
        sb.setLength(0);
        addNext(sb);
        return sb;
    }
    
   /**
    * Skips any prevailing space or empty lines.
    * 
    */ 
    private static void skipWhiteSpace() {
        while((c == '\n' || c == ' ' || c == '\r') && (c != -1)) {
            read();
        }
    }
   
   /**
    * Skips any prevailing space.
    * 
    */
    private static void skipSpace() {
        while(c == ' ' && c != -1) {
            read();
        }
    }
     
   /**
    * Skips a line from the input stream.
    * 
    */
    private static void skipLine() {
        while(c != '\n' && c != '\r' && c != -1) {
            read();
        }
        
        while(c != -1 && (c == '\n' || c == '\r')) {
            read();
        }
    }
    
   /**
    * Skips a word from the input stream.
    * 
    */
    private static void skipWord() {
        while(c != '\n' && c != ' ' && c != '\r' && c != -1) {
            read();
        }
        
        read();
    }
    
   /**
    * Refills the buffer with new data.
    * 
    */
    private static void fillBuffer() throws IOException {
        bytesRead = dis.read(buffer, bufferPos = 0, buffer.length);
        
        if(bytesRead == -1) {
            buffer[0] = -1;
        }
    }
   
   /**
    * Reads the next byte from the input data and stores it in {@link c}
    * 
    */
    private static void read() {
        if(bufferPos >= bytesRead) {
            try {
                fillBuffer();
            }
            catch(IOException e) {
            }
        }
        
        c = buffer[bufferPos ++];
    }
}

JavaScript solution:
// Function to calculate inversions in a string
function calculateInversions(s) {
    let zeros = 0;
    let inversions = 0;

    // Traverse the string in reverse order
    for (let i = s.length - 1; i >= 0; i--) {
        if (s[i] === '0') {
            zeros++;
        } else {
            inversions += zeros;
        }
    }

    return inversions;
}

// Function to determine minimum operations
function minOperations(n, x, k, s) {
    const totalInversions = calculateInversions(s);

    // Check the conditions for the minimum operations
    if (totalInversions <= x && totalInversions % k === 0) {
        return 1;
    } else {
        return 2;
    }
}

// Reading input
const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

let inputLines = [];
rl.on('line', (line) => {
    inputLines.push(line.trim());
}).on('close', () => {
    const t = parseInt(inputLines[0], 10); // Number of test cases
    const results = [];

    let lineIndex = 1;
    for (let i = 0; i < t; i++) {
        const [n, x, k] = inputLines[lineIndex].split(' ').map(Number);
        const s = inputLines[lineIndex + 1];
        lineIndex += 2;

        results.push(minOperations(n, x, k, s));
    }

    // Output results
    console.log(results.join('\n'));
});

Python solution:
# cook your dish here
import sys

def count_inversions(s):
    count = 0
    ones = 0
    for c in s:
        if c == '1':
            ones += 1
        else:
            count += ones
    return count

def main():
    input = sys.stdin.read().split()
    ptr = 0
    T = int(input[ptr])
    ptr += 1
    res = []
    for _ in range(T):
        N = int(input[ptr])
        X = int(input[ptr+1])
        K = int(input[ptr+2])
        ptr +=3
        s = input[ptr]
        ptr +=1
        t = count_inversions(s)
        if 0 <= t <= X and t % K == 0:
            res.append('1')
        else:
            res.append('2')
    print('\n'.join(res))

if __name__ == '__main__':
    main()

Ruby solution:
def count_inversions(s)
  count = 0
  ones = 0
  s.each_char do |c|
    if c == '1'
      ones += 1
    else
      count += ones
    end
  end
  count
end

def main
  input = $stdin.read.split
  ptr = 0
  test_cases = input[ptr].to_i
  ptr += 1
  results = []
  test_cases.times do
    n = input[ptr].to_i
    x = input[ptr + 1].to_i
    k = input[ptr + 2].to_i
    ptr += 3
    s = input[ptr]
    ptr += 1
    t = count_inversions(s)
    if t >= 0 && t <= x && t % k == 0
      results << '1'
    else
      results << '2'
    end
  end
  puts results.join("\n")
end

main