Tag Archives: algorithm

Codeforces #252 (Div.2) C. Valera and Tubes

0
Posted on by

Problem link: http://codeforces.com/problemset/problem/441/C

The logic is very simple. Test cases might be misleading. Each tube has to be of length>=2.

So first find the points in zig zag path of the table.(i.e move from left to right and then go the next row and move from right to left and vice versa)

Let the first k-1 tubes be of length 2. Assign 2 points from the path for each tube.

Kth tube(last tube) will have the remaining cells in the zig zag path.

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <climits>
#include <stdlib.h>
#include <stdio.h>
using namespace std;
#define REP(i,n) for(int i=0; i<n; i++)
#define FOR(i,st,end) for(int i=st;i<end;i++)
#define db(x) cout << (#x) << " = " << x << endl;
#define mp make_pair
#define pb push_back
typedef long long int ll;
int arr[305][305];
int visited[305];
int n,m,k;
int withinBoundary(int x,int y){
if(x>=0&&x<n&&y>=0&&y<m)
return 1;
else
return 0;
}
int main(){
cin>>n>>m>>k;
vector<pair<int,int> >q;
int dir=1;
int x=0,y=0;
q.pb(mp(0,0));
while(true){
y+=dir;
if(y==m){
dir*=-1;
y=m-1;
x++;
}
if(y==-1){
dir*=-1;
y=0;
x++;
}
if(x==n)
break;
q.pb(mp(x,y));
}
int j=0;
REP(i,k-1){
cout<<"2 ";
cout<<q[j].first+1<<" "<<q[j].second+1<<" "<<q[j+1].first+1<<" "<<q[j+1].second+1<<endl;
j+=2;
}
cout<<(n*m)-(2*(k-1))<<" ";
while(j<q.size()){
cout<<q[j].first+1<<" "<<q[j].second+1<<" ";
j++;
}
return 0;
}
view raw Valera and Tubes.cpp hosted with ❤ by GitHub

Given an array of length N containing integers between 1 and N, determine if it contains any duplicates in O(n) time complexity and O(1) space complexity

0
Posted on by

Since we cannot use extra space, take advantage of the fact that the array has elements only from 1 to n
and there are n elements in the array(index ranges from 0 to n-1)
So if 1 occurs make value at 0th index negative
if 2 occurs make the value at 1st index negative
if n occurs make the value at n-1th index negative
So if the same number occurs again then the value at that number index will be found negative already and
voila !Thus we found a way finding repeating number.
Algorithm
traverse the list for i= 0 to n-1 elements
{
check for sign of A[abs(A[i])] ;
if positive then
make it negative by A[abs(A[i])]=-A[abs(A[i])];
else // i.e., A[abs(A[i])] is negative
this element (ith element of list) is a repetition
}

Two nodes of a binary search tree have been incorrectly swapped. How will you efficiently restore the tree to its correct state?

2
Posted on by

An inorder traversal of BST will be in sorted order.

In the incorrect BST  2 of the nodes are swapped .
use this to your advantage and find these 2 elements in inorder traversal which violate the sorted order.This 2 elements need to  be swapped.Thats it!!

Just modify inorder traversal function as follows
[gist https://gist.github.com/vishnujayvel/5879942 ]

Finding K minimum elements from an array in O(n)

0
Posted on by

Quicksort has so many applications.One of them is to find the K minimum elements from a array in O(n) times.

How does quicksort’s O(nlogn) becomes O(n).Well,we need not sort the K minimum elements in order.we just want to find it. So we execute the partition till K becomes pivot position

[gist https://gist.github.com/vishnujayvel/5879546 ]

Spoj Herding – Flood fill algorithm

0
Posted on by

I recently came across an interesting algorithm called  flood fill algorithm.It is used in computer graphics to fill connected same colored pixels with

a replacement color.

The algorithm goes like this

Flood-fill (node, target-color, replacement-color):
 1. If the color of node is not equal to target-color, return.
 2. Set the color of node to replacement-color.
 3. Perform Flood-fill (one step to the west of node, target-color, replacement-color).
    Perform Flood-fill (one step to the east of node, target-color, replacement-color).
    Perform Flood-fill (one step to the north of node, target-color, replacement-color).
    Perform Flood-fill (one step to the south of node, target-color, replacement-color).
 4. Return.


using this algorithm lets solve a spoj problem-HERDING
http://www.spoj.com/problems/HERDING/



    

      

        

  

    
    


        



  


  

        

          
          #include<iostream>
        

        

          
          using namespace std;
        

        

          
          

        

        

          
          char grid[1000][1000];
        

        

          
          int flag[1000][1001]={0},r,c;
        

        

          
          int count=0,prev_count=0;
        

        

          
          

        

        

          
          void floodfill(int i,int j){
        

        

          
                  if(i>=0&&j>=0&&i<r&&j<c)
        

        

          
          	if(flag[i][j]==0){
        

        

          
          		flag[i][j]=count;
        

        

          
          		
        

        

          
          		switch(grid[i][j]){
        

        

          
          			case 'E':floodfill(i,j+1);
        

        

          
                               break;
        

        

          
                     case 'W':floodfill(i,j-1);
        

        

          
                               break;
        

        

          
                     case 'N':floodfill(i-1,j);
        

        

          
                              break;
        

        

          
                     case 'S':floodfill(i+1,j);
        

        

          
                              break;
        

        

          
                     
        

        

          
                  }
        

        

          
                  flag[i][j]=count;
        

        

          
          	}
        

        

          
          	else{
        

        

          
          		count=flag[i][j];
        

        

          
          		return;
        

        

          
          	}
        

        

          
          	    
        

        

          
          }
        

        

          
          

        

        

          
          int main(){
        

        

          
          	cin>>r>>c;
        

        

          
          	for(int i=0;i<r;i++)
        

        

          
          	 cin>>grid[i];
        

        

          
          	 for(int i=0;i<r;i++){
        

        

          
          	 	for(int j=0;j<c;j++){
        

        

          
          	 		if(flag[i][j]==0){
        

        

          
          

        

        

          
          	 			count=prev_count+1;
        

        

          
          	 			floodfill(i,j);
        

        

          
          	 			if(prev_count<count)
        

        

          
          	 			    prev_count++;
        

        

          
          	 			
        

        

          
          	 		}
        

        

          
          	 	}
        

        

          
          	 }
        

        

          
          	 cout<<prev_count<<endl;
        

        

          
          }
        

        

          
          

        

  





    


  




      

      

        view raw
        
          herdings.cpp
        
        hosted with ❤ by GitHub

Randomized Quicksort

0
Posted on by

We know how efficient quicksort algorithm is.its efficiency is O(nlogn)

By randomly selecting a pivot element it is found that the number of swaps reduces further.

To generate a random pivot use rand() function .

#include<iostream>
#include<stdlib.h>
using namespace std;
void swap(int &a,int &b){
int temp=a;
a=b;
b=temp;
}
int partition(int arr[],int low,int high){
int left,right,pivot;
int r=low+(rand()%(high-low+1));
swap(arr[r],arr[low]);
pivot=arr[low];
left=low;
right=high;
while(left<right){
while(arr[left]<=pivot)
left++;
while(arr[right]>pivot)
right--;
if(left<right)
swap(arr[left],arr[right]);
}
arr[low]=arr[right];
arr[right]=pivot;
return right;
}
void quicksort(int arr[],int low,int high){
if(low<high){
int p=partition(arr,low,high);
quicksort(arr,low,p-1);
quicksort(arr,p+1,high);
}
}
int main(){
int arr[]={34,1,2,89,56,23};
quicksort(arr,0,5);
for(int i=0;i<5;i++){
cout<<arr[i]<<" ";
}
}
view raw randomizedquicksort.cpp hosted with ❤ by GitHub

 

 

Given an unsorted array of nonnegative integers, find a continous subarray which adds to a given number.

0
Posted on by

Algorithm
1)This approach is similar to the problem “checking whether a pair exists in an array
with specific sum S”.
This is what we are going to do.Have a start and end pointer which intially points to
arr[0] and a variable currentSum=arr[0]
2)Now increase end pointer such that currentSum>S .Now we can try finding a subarray having
sum=S within this subarray ending with end pointer.
3)Now to adjust currentSum to S we need to increase the start pointer which in turn reduces
currentSum’s value.If currentSum becomes smaller than S you have to go back to step 2.
4)At one point of time currentSum might become S.if theres no subarray with such sum then
start will be eventually equal to end.
5)Now start your quest from new starting point start+1 and ending point end+1
Time complexity- O(n)

[gist https://gist.github.com/vishnujayvel/5869743 ]