Skip to content

Instantly share code, notes, and snippets.

@rahularity

rahularity/AggresiveCows.cpp

Created August 3, 2020 12:31
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save rahularity/d1b2791a2f8f9337aa1e280f67a7d20b to your computer and use it in GitHub Desktop.
Save rahularity/d1b2791a2f8f9337aa1e280f67a7d20b to your computer and use it in GitHub Desktop.
Download ZIP
Algorithms and Data Structure Revision
Raw
AggresiveCows.cpp
/*
Read the problem statement from here: https://www.spoj.com/problems/AGGRCOW/
*/
#include<bits/stdc++.h>
using namespace std;
bool isPossible(int arr[], int n, int interval, int C){
C--;
int start = arr[0];
for( int i=1 ; i<n ; i++ ){
if(arr[i]-start >= interval){
C--;
start = arr[i];
}
if(C == 0) return true;
}
return false;
}
int main() {
int t;
cin>>t;
while(t--){
int N,C;
cin>>N>>C;
int* arr = new int[N];
for( int i=0 ; i<N ; i++ ){
cin>>arr[i];
}
sort(arr, arr+N);
int ans;
int begin=1;
int end = arr[N-1];
int mid = 0;
while(begin<=end){
mid = begin + (end-begin)/2;
//cout<<"mid is : "<<mid<<endl;
//cout<<"ispossible : "<<isPossible(arr, N, mid, C)<<endl;
if(isPossible(arr, N, mid, C)){
begin = mid+1;
ans = mid;
}else{
end = mid-1;
}
}
cout<<ans<<endl;
}
}
Raw
InversionCount.cpp
/*
Let A[0 ... n-1] be an array of n distinct positive integers.
If i < j and A[i] > A[j] then the pair (i, j) is called an inversion of A.
Find number of inversion counts
*/
long long merge(int a[], int left, int mid, int right){
long long count =0;
int i=left;
int j=mid;
int k=0;
int temp[right-left+1];
while(i<mid && j<=right){
if(a[i] <= a[j]){
temp[k++] = a[i++];
}else{
temp[k++] = a[j++];
count += mid-i;
}
}
while(i<mid){
temp[k++] = a[i++];
}
while(j<=right){
temp[k++] = a[j++];
}
for(i=left,k =0 ; i<=right ; i++, k++){
a[i] = temp[k];
}
return count;
}
long long mergeSort(int a[], int start, int end){
long long inv_count=0;
while(start<end){
int mid = start + (end-start)/2;
long long leftInversions = mergeSort(a,start, mid);
long long rightInversions = mergeSort(a, mid+1, end);
long long currentInversions = merge(a, start, mid+1, end);
return leftInversions + rightInversions + currentInversions;
//return inv_count;
}
return inv_count;
}
long long solve(int A[], int n)
{
return mergeSort(A,0,n-1);
}
Raw
LastIndexOfANumber.cpp
/*
Given an array of length N and an integer x,
you need to find and return the last index of integer x present in the array.
Return -1 if it is not present in the array.
Do it Recursively. Indexing in the array starts from 0.
*/
int lastIndex(int input[], int size, int x) {
if(size == 0){
return -1;
}
int smallAns = lastIndex(input+1, size -1, x);
if ( input[0] == x){
if(smallAns == -1){
return 0;
}
else{
return smallAns +1;
}
}
return smallAns == -1 ? -1 : smallAns+1;
}
Raw
MergeSort.cpp
/*
MERGE SORT
*/
#include<bits/stdc++.h>
using namespace std;
void merge(int arr[], int start, int mid, int end){
int temp[end-start+1];
int k=0;
int i=start;
int j=mid+1;
while(i<=mid && j<=end){
if(arr[i] <= arr[j])
temp[k++] = arr[i++];
else
temp[k++] = arr[j++];
}
while(i<mid){
temp[k++] = arr[i++];
}
while(j<=end){
temp[k++] = arr[j++];
}
for( int p=start, k=0 ; p<=end ; p++){
arr[p] = temp[k++];
}
}
void merge-sort(int arr[], int start, int end){
while(start < end){
int mid = start + (end-start)/2;
merge-sort(arr, start, mid);
merge-sort(arr, mid+1, end);
merge(arr, start, mid, end);
}
}
Raw
Murder.cpp
/*
Inversion Count Application.
Once detective Saikat was solving a murder case.
While going to the crime scene he took the stairs and saw that a number is written on every stair.
He found it suspicious and decides to remember all the numbers that he has seen till now.
While remembering the numbers he found that he can find some pattern in those numbers.
So he decides that for each number on the stairs he will note down the sum of all the numbers previously seen on the stairs which are smaller than the present number.
Calculate the sum of all the numbers written on his notes diary.
*/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll merge(int* a, int start, int mid, int end){
int* temp = new int[end-start+1];
int i=start;
int j = mid+1;
int k=0;
ll sum=0;
while(i<=mid && j<=end){
if(a[i] < a[j]){
sum += (end-j+1)*a[i];
temp[k++] = a[i++];
}else{
temp[k++]=a[j++];
}
}
while(i<=mid){
temp[k++] = a[i++];
}
while(j<=end){
temp[k++] = a[j++];
}
for(int p=start, k=0 ; p<=end ; p++,k++){
a[p] = temp[k];
}
delete []temp;
return sum;
}
ll mergeSort(int* a, int start, int end){
ll small_output1=0, small_output2=0, small_output3=0;
if(start < end){
int mid = start + (end-start)/2;
small_output1 = mergeSort(a, start, mid);
small_output2 = mergeSort(a, mid+1, end);
small_output3 = merge(a, start, mid, end);
}
return small_output1 + small_output2 + small_output3;
}
int main() {
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int* a = new int[n];
for(int i=0 ; i<n ; i++){
cin>>a[i];
}
cout<<mergeSort(a, 0, n-1)<<endl;
delete []a;
}
}
Raw
NumberOfDigits.cpp
/*
return the number of digits present in a number recursively.
*/
int count(int n){
if(n/10 == 0)
return 1;
return count(n/10) + 1;
}
Raw
Power.cpp
/*
Find x^n recursively
*/
#include<bits/stdc++.h>
using namespace std;
int power(int x, int n){
if(n==0)
return 1;
return x * power(x,n-1);
}
Raw
Print Numbers.cpp
/*
print numbers from 1 to n in increasing order recursively.
Learning: understanding how the recursive callback can be used.
*/
#include<bits/stdc++.h>
using namespace std;
void print( int n ){
if( n==1 )
cout << n << " ";
print(n-1);
cout << n << " ";
}
Raw
QuikSort.cpp
/*
QUIKSORT ALGORITHM
*/
void swap(int& a, int& b){
int temp = a;
a=b;
b=temp;
}
int partition(int a[], int start, int end){
int pivot = a[end];
int i=start-1;
int j;
for(j=start; j<=end ; j++){
if(a[j] < pivot){
i++;
swap(a[i], a[j]);
}
}
a[end] = a[++i];
a[i] = pivot;
return i;
}
void quick_sort(int a[], int start, int end){
if(start < end){
int pivot = partition(a, start, end);
quick_sort(a, start, pivot-1);
quick_sort(a, pivot+1, end);
}
}
void quickSort(int input[], int size) {
quick_sort(input, 0, size-1);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment