Insertion Sort Advanced Analysis

Insertion Sort is a simple sorting technique which was covered in previous challenges. Sometimes, arrays may be too large for us to wait around for insertion sort to finish. Is there some other way we can calculate the number of times Insertion Sort shifts each elements when sorting an array?

If kkii is the number of elements over which the iithth element of the array has to shift, then the total number of shifts will be kk11 +k+k22 +...+k+...+kNN.

Input Format

The first line contains the number of test cases, TT. TT test cases follow. The first line for each test case contains NN, the number of elements to be sorted. The next line contains NN integers (a[1]a[1], a[2]a[2], ..., a[N]a[N]).

Output Format

Output TT lines containing the required answer for each test case.

Constraints

1≤T≤151≤T≤15
1≤N≤1000001≤N≤100000
1≤a[i]≤10000000

Sample Input

2 
5 
1 1 1 2 2 
5 
2 1 3 1 2

Sample Output

0 
4  

Explanation
The first test case is already sorted, therefore there's no need to shift any element. In the second case, it will proceed in the following way.

Array: 2 1 3 1 2 -> 1 2 3 1 2 -> 1 1 2 3 2 -> 1 1 2 2 3
Moves:   -        1       -    2         -  1            = 4

solution: :

 #include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int read(int * p, int k) {
    int nrt=0;
    while(k>0) {
        nrt += p[k];
        k -= (k&(-k));
    }
    return nrt;
}

void update(int * p, int k) {
    while(k<=10000000) {
        p[k] ++;
        k += (k&(-k));
    }
}

int assign(int k, int * p, int existing) {
    int n = read(p, k); // sum of counts of number which is not bigger than k
    update(p, k);
    return existing-n;
}
int main() {
     int test=0;
    cin>>test;
    for(int i=0; i<test; i++) {
        int n=0;
        long sum=0l;
        cin>>n;
        int *p = new int[10000001]; // array is too big for stack
        for(int j=0; j<10000001; j++) {
            p[j]=0;
        }
      
        for(int j=0; j<n; j++) {
            int k=0;
            cin>>k;
            sum += assign(k, p, j);
        }
        cout<<sum<<endl;


delete[] p;
    }
    return 0;
}

Make it Anagram

Alice recently started learning about cryptography and found that anagrams are very useful. Two strings are anagrams of each other if they have same character set (and frequency of characters) and same length. For example strings "bacdc" and "dcbac" are anagrams, while strings "bacdc" and "dcbad" are not.

Alice decides on an encryption scheme involving 2 large strings where encryption is dependent on the minimum number of character deletions required to make the two strings anagrams. She need your help in finding out this number.

Given two strings (they can be of same or different length) help her in finding out the minimum number of character deletions required to make two strings anagrams. Any characters can be deleted from any of the strings.

Input Format

Two lines each containing a string.

Constraints

1 <= Length of A,B <= 10000
A and B will only consist of lowercase latin letter.

Output Format

A single integer which is the number of character deletions.

Sample Input #00:

cde
abc

Sample Output #00:

4

Explanation #00:

We need to delete 4 characters to make both strings anagram i.e. 'd' and 'e' from first string and 'b' and 'a' from second string.



solution::
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int a[256];
int b[256];
int main()
{
    string s1,s2;
    cin>>s1>>s2;
    int flag=0,sum=0;
    for (int i = 0; i < s1.length(); i++)
    {
        a[s1[i]]++;
    }
    for (int i = 0; i < s2.length(); i++)
    {
        b[s2[i]]++;
    }
    for (int i = 96; i < 127; ++i)
    {
        if(a[i]!=b[i])
        {
            sum+=abs(a[i]-b[i]);
            //break;
        }
    }
    cout<<sum;
    cout<<endl;
    return 0;
}
 

Degree of Dirtiness

 Problem Statement
There are N toilets in a row indexed from 1 to N. At a time, 2 people enter the washroom. The degree of dirtiness of each toilet is 0 initially and it increases by 1 after it is used each time. The 1st person occupies the 1st toilet with the lowest degree of dirtiness moving from 1 to N. The 2nd person occupies the toilet with the lowest degree of dirtiness moving from N to 1. The next two people enter the toilet when the first two people have left. Find the index of toilet and degree of dirtiness for the Mth person.
Note In case M is odd, the last person walks into the washroom alone and occupies the least dirty toilet moving from 1 to N

Input Format

The first line contains T, the number of test cases. Each test case consists of one line containing N, the number of toliets, and M, the person to enter the toilet, seperated by space.

Output Format

The index of the toilet used by M and its degree of dirtiness D

Sample Input

3 
10 3 
5 8 
4 26


Sample Output
2 0 
4 1 
4 6 

Explanation
In the second test case,
for the first two persons, positions are 1 _ _ _ 2, degree of dirtiness 0 0 0 0 0 (dirtiness is 0 since they are the first to use it)
for person 3 and 4, positions are _ 3 _ 4 _ , degree of dirtiness 1 0 0 0 1
for 5 and 6, positions are _ _ 5 _ 6, degree of dirtiness 1 1 0 1 1
for 7 and 8, positions are 7 _ _ 8 _, degree of dirtiness 1 1 1 1 2 so the answer is 4,1

 solution::

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

int main() {

    int t,n,m,c,i,min1,min2,r,pos,dirt;
 scanf("%d",&t);
 while(t--)
 {
  scanf("%d %d",&n,&m);
  int d[n];
  for(i=0;i<n;i++)
  {
   d[i]=0;
  }
  for(c=0;c<m;c=c+1)
  {
   if(c==m-1)
   {
    if(c%2==0)
   {
    min1=d[0];
    r=0;
    for(i=0;i<n;i++)
    {
     if(d[i]<min1)
     {
      min1=d[i];
      r=i;
     }
    }
    pos=r+1;
    dirt=d[r];
   }
   else if(c%2!=0)
   {
    min2=d[n-1];
    r=n-1;
    for(i=0;i<n;i++)
    {
     if(d[i]<=min2)
     {
      min2=d[i];
      r=i;
     }
    }
    pos=r+1;
    dirt=d[r];
   }
  }
  else
  {
   if(c%2==0)
   {
    min1=d[0];
    r=0;
    for(i=0;i<n;i++)
    {
     if(d[i]<min1)
     {
      min1=d[i];
      r=i;
     }
    }
    d[r]++;
   }
   else if(c%2!=0)
   {
    min2=d[n-1];
    r=n-1;
    for(i=0;i<n;i++)
    {
     if(d[i]<=min2)
     {
      min2=d[i];
      r=i;
     }
    }
    d[r]++;
   }  
  }
 }
   printf("\n%d %d",pos,dirt);
 }
 return 0;
}