Physical Address

304 North Cardinal St.
Dorchester Center, MA 02124

Binary Inversion CodeChef Solution

Problem -Binary Inversion CodeChef Solution

This website is dedicated for CodeChef solution where we will publish right solution of all your favourite CodeChef problems along with detailed explanatory of different competitive programming concepts and languages.

Binary Inversion CodeChef Solution in C++17


#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

#define fo(n)           for(long long i = 0; i < n; i++)
#define all(v)          v.begin(),v.end() 
#define ff              first
#define ss              second
#define int             long long
#define pb              push_back
#define mkp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());
 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
 
 
void c_p_c()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}
int32_t main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    w(t){
    	int n, m;
    	cin>>n>>m;
    	vector<string>a(n);
    	fo(n)cin>>a[i];

    	vector<pii>val;
    	for(int i=0;i<n;i++){
    		int sum = 0;
    		for(int j=0;j<m;j++){
    			sum+=(a[i][j]=='0'?1:-1);
    		}
    		val.pb({sum, i});
    	}
    	vector<int>cur(n, 0);
    	string s = "";
    	sort(all(val), greater<pii>());
    	fo(n){
    		s+=a[val[i].second];
    	}
    	int one = 0;
    	for(int i=s.size()-1;i>=0;i--){
    		one+=(s[i]=='0');
    	}
    	int ans = 0;
    	fo(s.size()){
    		if(s[i]=='1'){
    			ans+=one;
    		}else{
    			one--;
    		}
    	}
    	cout<<ans<<endl;
    }
}

Binary Inversion CodeChef Solution in C++14

#include <iostream>
#include <string>
#include <ctype.h>
#include <sstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <unordered_map>
#include <numeric>
using namespace std;

typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pi;
#define pb push_back
#define MAX 200000
#define MOD 1000000007
#define nl '\n'
typedef pair<ll,ll> pi;
const ll inf = 1e9;

bool compare(string a,string b){
    int act = count(a.begin(),a.end(),'0');
    int bct = count(b.begin(),b.end(),'0');
    if(act!=bct) return act>bct;
    else return a<b;
}

void solve(){
    ll n,m;cin>>n>>m;
    vector<string> a(n);
    for(ll i=0;i<n;i++) cin>>a[i];
    sort(a.begin(),a.end(),compare);
    // for(auto el : a) cout<<el<<" ";
    // cout<<nl;
    ll ans = 0;
    vector<ll> ps(n + 1,0);
    for(ll i=n-1;i>=0;i--){
        ps[i] = ps[i + 1] + count(a[i].begin(),a[i].end(),'0');
    }

    for(ll i=0;i<n;i++){
        ll zs = 0;
        for(ll j=m-1;j>=0;j--){
            if(a[i][j]=='1'){
                ans += ps[i + 1] + zs;
            }else zs++;
        }
    }
    cout<<ans<<nl;

}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    #ifndef ONLINE_JUDGE
    freopen("input.in","r",stdin);
    freopen("output.out","w",stdout);
    #endif
    ll t; cin>>t; while(t--){solve();}
}

Binary Inversion CodeChef Solution in PYTH 3

# cook your dish here
from sys import stdin

t = int(stdin.readline().rstrip())
while t > 0:
    n, m = map(int, stdin.readline().rstrip().split(' '))
    nums = []
    for i in range(n):
        s = stdin.readline().strip()
        nums.append(s)

    nums.sort(key=lambda i: i.count('1'))
    nums = ''.join(nums)
    ones = 0
    inversions = 0
    for i in nums:
        if i == '1':
            ones += 1
        else:
            inversions += ones

    print(inversions)
    t -= 1

Binary Inversion CodeChef Solution in C

#include <stdio.h>
#include <stdlib.h>

struct arrList {
	char *arr;       // TODO: This can be made of eqaul to size of N.
	unsigned int numberOfOnes;
};

int compare (const void * a, const void * b) {
	struct arrList* aList = (struct arrList*) a;
	struct arrList* bList = (struct arrList*) b;
	
	return (aList->numberOfOnes - bList->numberOfOnes);
}


int main() {
	unsigned int T = 0, N = 0, M = 0;
	int i = 0, j = 0;
	unsigned long long int curNumberOfOnes = 0, total = 0;
	
	struct arrList *totalList = NULL;
	
	scanf("%u", &T);
	
	while (T--) {
		scanf("%u %u\n", &N, &M);
		
		// There are total N strings, and each strings has the M characters
		// Allocate memory for total number of data
		totalList = malloc( N * sizeof(struct arrList) );
		
		for( i = 0; i < N; i++) {
			totalList[i].numberOfOnes = 0;
			totalList[i].arr = malloc(sizeof(char) * (M+1));
			// Take out the inidividual strings from the input
			for(j = 0; j < M; j++) {
				totalList[i].arr[j] = getchar();
				if(totalList[i].arr[j] == '1')
					totalList[i].numberOfOnes++;
			}
			
			// Get the next new line character
			getchar();
		}
		
		// Sort the strings according to the elements
		qsort(totalList, N, sizeof(struct arrList), compare);
		
		curNumberOfOnes = 0;
		total = 0;
	
		// Array is sorted now, calculate the inversion possible.
		for(i = 0; i < N; i++) {
			for(j = 0; j < M; j++) {
			    //printf("%c", totalList[i].arr[j]);
				if(totalList[i].arr[j] == '1')
					curNumberOfOnes++;
				else
					total += curNumberOfOnes;
			}
			
			//printf("\n");
		}
		
		printf("%llu\n", total);
		
		for(i = 0; i < N; i++) {
		    free(totalList[i].arr);
		}
		free(totalList);
	}
	

	return 0;
}

Binary Inversion CodeChef Solution in JAVA

/* package codechef; // don't place package name! */
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;
import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
    public static class Reader {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;
 
        public Reader()
        {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }
 
        public Reader(String file_name) throws IOException
        {
            din = new DataInputStream(
                new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }
 
        public String readLine() throws IOException
        {
            byte[] buf = new byte[64]; // line length
            int cnt = 0, c;
            while ((c = read()) != -1) {
                if (c == '\n') {
                    if (cnt != 0) {
                        break;
                    }
                    else {
                        continue;
                    }
                }
                buf[cnt++] = (byte)c;
            }
            return new String(buf, 0, cnt);
        }
 
        public int nextInt() throws IOException
        {
            int ret = 0;
            byte c = read();
            while (c <= ' ') {
                c = read();
            }
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
 
            if (neg)
                return -ret;
            return ret;
        }
 
        public long nextLong() throws IOException
        {
            long ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }
 
        public double nextDouble() throws IOException
        {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
 
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
 
            if (c == '.') {
                while ((c = read()) >= '0' && c <= '9') {
                    ret += (c - '0') / (div *= 10);
                }
            }
 
            if (neg)
                return -ret;
            return ret;
        }
 
        private void fillBuffer() throws IOException
        {
            bytesRead = din.read(buffer, bufferPointer = 0,
                                 BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }
 
        private byte read() throws IOException
        {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }
 
        public void close() throws IOException
        {
            if (din == null)
                return;
            din.close();
        }
    }
    static class FastReader { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader( 
                new InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) { 
                try { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException e) { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() { return Integer.parseInt(next()); } 
  
        long nextLong() { return Long.parseLong(next()); } 
  
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() 
        { 
            String str = ""; 
            try { 
                if(st.hasMoreTokens()){ 
                    str = st.nextToken("\n"); 
                } 
                else{ 
                    str = br.readLine(); 
                } 
            } 
            catch (IOException e) { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    } 
    public static int gcd(int a,int b)
    {
        if(b==0)
        return a;
        return gcd(b,a%b);
    }
   
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		//Reader s=new Reader();
		//Scanner s=new Scanner(System.in);
		FastReader s=new FastReader();
		StringBuilder sb=new StringBuilder();
		int t=s.nextInt();
		while(t-->0)
		{
            int n=s.nextInt();
            int m=s.nextInt();
            long inv=0;
            int a[]=new int[n];
            for(int i=0;i<n;i++)
            {
                String st=s.nextLine();
                int c=0;
                for(int j=0;j<st.length();j++)
                {
                    if(st.charAt(j)=='1')
                    c+=1;
                    else
                    inv+=c;
                }
                a[i]=c;
            }
            Arrays.sort(a);
            int cz=0;
            for(int i=n-2;i>=0;i--)
            {
                cz+=m-a[i+1];
                 inv+=a[i]*cz;
            }
            System.out.println(inv);
		}
		System.out.println(sb);
	}
}

Binary Inversion CodeChef Solution in PYPY 3

tl= int(input())
while(tl):
    tl=tl-1
    n,m=map(int,input().split())
    a1=[]
    ainv=[]
    for j in range(n):
        s=str(input())
        inv=0
        su=0
        c1=0
        for i in reversed(range(m)):
            if s[i]=='0':
                inv=inv+1
            else:
                su=su+inv
                c1=c1+1
        c0=m-c1
        a1.append(c1)
        ainv.append(su)
    a1.sort()
    sofin=sum(ainv)
    ans=0
    ex0=0
    for i in reversed(range(n)):
        ans=ans+a1[i]*(ex0)
        ex0=ex0+m-a1[i]
    fans=sofin+ans
    print(fans)

Binary Inversion CodeChef Solution in PYTH

t = int(raw_input())
for i in range(t):
	st = raw_input().split()
	N = int(st[0])
	M = int(st[1])
	A = []
	for k in range(N):
		st = raw_input().strip()
		tot = 0
		n = 0
		for x in st:
			if x == '0':
				tot += n
			else:
				n += 1
			# endif
		# endfor x
		A.append([n,tot])
	# endfor k
	A.sort()
	tot = 0
	n = 0
	for x in A:
		tot += x[1] + n*(M-x[0])
		n += x[0]
	# endfor x
	print tot
# endfor i

Binary Inversion CodeChef Solution in NODEJS

process.stdin.resume();
process.stdin.setEncoding('utf8');

// your code goes here
let input = '';
let current = 0;

process.stdin.on('data', (data) => {
    input += data;
});
process.stdin.on('end', () => {
    input = input.split('\n');
    main();
});

const readLine = () => input[current++];

const cmp = (s1, s2) => (s1.match(/1/g) || []).length - (s2.match(/1/g) || []).length;

const calcMinInversions = (n, m, newStr) => {

    let minInversions = 0;
    let ones = 0;

    for(let i = 0 ; i < newStr.length ; i++) {
        if(newStr[i] === '1') ones++;
        else minInversions += ones;
    }
    
    return minInversions;
};

const main = () => {
    const t = +(readLine());
    for(let i = 0 ; i < t ; i++){
        const [N, M] = readLine().split(' ').map(Number);
       
        let stringArray = [];
        for(let i = 0 ; i < N ; i++) stringArray[i] = readLine();
        stringArray = stringArray.sort(cmp);
       
        let newStr = '';
        for(let j = 0 ; j < N ; j++) newStr += stringArray[j];
        
        console.log(calcMinInversions(N, M, newStr));
    } 
};

Binary Inversion CodeChef Solution in GO 

package main

import (
	"bufio"
	"bytes"
	"fmt"
	"os"
	"sort"
)

func main() {
	reader := bufio.NewReader(os.Stdin)

	tc := readNum(reader)
	var buf bytes.Buffer
	for tc > 0 {
		tc--
		n, m := readTwoNums(reader)
		S := make([]string, n)
		for i := 0; i < n; i++ {
			S[i], _ = reader.ReadString('\n')
		}
		res := solve(n, m, S)
		buf.WriteString(fmt.Sprintf("%d\n", res))
	}

	fmt.Print(buf.String())
}

func readInt(bytes []byte, from int, val *int) int {
	i := from
	sign := 1
	if bytes[i] == '-' {
		sign = -1
		i++
	}
	tmp := 0
	for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
		tmp = tmp*10 + int(bytes[i]-'0')
		i++
	}
	*val = tmp * sign
	return i
}

func readNum(reader *bufio.Reader) (a int) {
	bs, _ := reader.ReadBytes('\n')
	readInt(bs, 0, &a)
	return
}

func readTwoNums(reader *bufio.Reader) (a int, b int) {
	res := readNNums(reader, 2)
	a, b = res[0], res[1]
	return
}

func readThreeNums(reader *bufio.Reader) (a int, b int, c int) {
	res := readNNums(reader, 3)
	a, b, c = res[0], res[1], res[2]
	return
}

func readNNums(reader *bufio.Reader, n int) []int {
	res := make([]int, n)
	x := 0
	bs, _ := reader.ReadBytes('\n')
	for i := 0; i < n; i++ {
		for x < len(bs) && (bs[x] < '0' || bs[x] > '9') && bs[x] != '-' {
			x++
		}
		x = readInt(bs, x, &res[i])
	}
	return res
}

func readUint64(bytes []byte, from int, val *uint64) int {
	i := from

	var tmp uint64
	for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
		tmp = tmp*10 + uint64(bytes[i]-'0')
		i++
	}
	*val = tmp

	return i
}

func solve(n, m int, S []string) int64 {
	p := make([]Pair, n)
	for i := 0; i < n; i++ {
		var cnt int
		for j := 0; j < m; j++ {
			if S[i][j] == '1' {
				cnt++
			}
		}
		p[i] = Pair{cnt, i}
	}

	sort.Sort(Pairs(p))
	var res int64
	var zeros int64
	for i := n - 1; i >= 0; i-- {
		k := p[i].second
		for j := m - 1; j >= 0; j-- {
			if S[k][j] == '1' {
				res += zeros
			} else {
				zeros++
			}
		}
	}

	return res
}

type Pair struct {
	first  int
	second int
}

type Pairs []Pair

func (ps Pairs) Len() int {
	return len(ps)
}

func (ps Pairs) Less(i, j int) bool {
	return ps[i].first < ps[j].first
}

func (ps Pairs) Swap(i, j int) {
	ps[i], ps[j] = ps[j], ps[i]
}
Binary Inversion CodeChef Solution Review:

In our experience, we suggest you solve this Binary Inversion CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Binary Inversion CodeChef Solution.

Find on CodeChef

Conclusion:

I hope this Binary Inversion CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

Cognitive Class Answer

CodeChef Solution

Microsoft Learn

Related Posts

Leave a Reply

Your email address will not be published. Required fields are marked *