Category Archives: spoj

Spoj(CRAN02) – Roommate Agreement

0
Posted on by

http://www.spoj.com/problems/CRAN02/

I solved this problem awhile ago.But recently i discussed about this problem with a friend of mine.This made to blog about this problem.It is such an interesting problem.

The main logic  is to use prefix_sum array

Let Sum[i+1]=arr[i]+arr[i-1]+arr[i-2]+….arr[0]

Sum[L..R]=Sum[0..R]-Sum[0..L-1]. Hence Sum[L..R]=0 iff Sum[0..L-1]=Sum[0..R]

arr[ i ]  + arr [ i + 1 ]  + arr [ i + 2 ] + … + arr [ j – 1 ] + arr [ j ]   = Sum[ j + 1 ] – Sum[ i ]

thus if the subsequence from arr[ i ]…arr[ j ] sum to 0 then

0 = sum[j+1] – sum[i]

so

Sum [ j + 1 ] = Sum[ i ] ; and vice versa

Store the count of each sum in a map.

If you ponder awhile on the Sum array you will get the logic that the number of equal pairs in Sum array + number of 0’s in Sum array is the result required.

if sumcount=n number of equal pairs is n(n-1)/2 and also if  0 is encountered as a sum then count[0] is added to the ans.

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

Spoj (MAXSUB) Maximum Subset of Array

0
Posted on by

http://www.spoj.com/problems/MAXSUB/

This one though looks like a complicated problem invoiving many cases , can actually be broken down into just 3 cases

1. All numbers are negative
2. At least one number is 0 but there is no number >0
3. There is at least one number >0

In first case, the best possible sum is the largest number. The number of possibilities is the number of times that number appears in the arrray.

In second case, the best possible sum is 0. The number of possibilities is 2^K – 1 where K is the number of zeros in the array.

In the third case, the best possible sum is the sum of all positive numbers in the array. Number of possibilities is 2^K where K is the number of zeros in the array.

#include<iostream>
#include<cstdio>
#include<deque>
#include<algorithm>
#include<math.h>
#define MOD 1000000009
using namespace std;
typedef long long int L;
int main(){
int t;
L n;
scanf("%d",&t);
while(t--){
scanf("%lld",&n);
L arr[51000],sum=0LL;
L cnt=1LL;
L zeroCount=0LL;
int allNegative=1;
for(int i=0;i<n;i++){
scanf("%lld",&arr[i]);
if(arr[i]>0){
sum+=(long long)arr[i];
allNegative=0;
}
else if(arr[i]==0){
allNegative=0;
zeroCount++;
}
}
sort(arr,arr+n);
if(sum==0){//this is to check if there is no +ve num
if(allNegative==1){//if array contains only -ve numbers
sum=arr[n-1];
for(int j=n-2;j>=0;j--){
if(sum==arr[j])
cnt++;
else
break;
}
}else{//if there exist 0's
L num=1;
for(L k=0;k<zeroCount;k++){
num=(L)(num*2)%MOD;// num of subset is 2^zeroCount-1
}//decrementing 1 from 2^zeroCount since we should exclude null set according to the prob
cnt=num-1;
}
}
else{//if the array contains +ve numbers
L num=1;
for(L k=0;k<zeroCount;k++){
num=(L)(num*2)%MOD;// num of subset is 2^zeroCount
}
cnt=num;
}
cnt=cnt%MOD;
printf("%lld %lld\n",sum,cnt);
}
}
view raw maxsub.cpp hosted with ❤ by GitHub

Spoj-Aggressive cows

2
Posted on by

After a long time ,i started solving spoj problems.I came across this interesting problem

http://www.spoj.com/problems/AGGRCOW/

Here is the approach

lets have a function

f(x) which will return 1 if gap between the cow stalls can be atleast of length x( i.e. all cows can occupy the stalls which are placed x distance  from ajacent stalls)

or return 0 if the gap between the stalls cannot be of length x

iff(x) ==0 then f(y) is also 0 such that y>x . We should code a function which can check

if x is can be allowed distance between each stall.

Our task is to find the largest minimum distance between the stalls.(i.e largest value of the allowed minimum distance)

How to do that ??

Well,You can always place cows such that the minimum distance is 0, while almost always, you cannot achieve minimum distance = N-1. For each number ‘x’ between 0 and N-1, you can either place the cows with minimum distance = ‘x’ or not.
If you list whether you can place the cows with a given distance ‘x’ you have check one by one
0 – Yes
1 – Yes
2 – Yes
.
.
.
x1 – Yes
x2 – No
x2+1 – No
.
.
.
N-1 – No

Our task is to find x1

This can be done using a simple binary search!

f(0)………………………………………………………..f(N-1) will be like

1 1 1 1 1 1 1 0 0 0 0 0 0…………………………..0 0 0

we have to find the last occuring 1

let

start=0

end=n-1

mid =(start+end)/2

if f(mid)=0 then x1 occurs within start and mid

if f(mid)=1 then x1 occurs within mid+1 and end

Search accordingly using divide and conquer strategy

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

Spoj- Pizzamania

0
Posted on by

Problem code: OPCPIZZA

 http://www.spoj.com/problems/OPCPIZZA/

Singham and his friends are fond of pizza. But this time they short of money. So they decided to help each other.They all decided to bring pizza in pairs. Our task is to find the total number of pairs possible which can buy pizza, given the cost of pizza. As pizza boy dont have any cash for change, if the pair adds upto more money than required, than also they are unable to buy the pizza. Each friend is guaranteed to have distinct amount of money. As it is Singham’s world, money can also be negative ;).
Input:
The first line consist of t(1<=t<=100) test cases.In the following 2*t lines, for each test case first there is n and m, where n(1<=n<=100000) is number of Singham’s friend and m is the price of pizza.The next line consist of n integers, seperated by space, which is the money each friend have.
The value of m and money is within the limits of int in C,C++.
Output:
A single integer representing the number of pairs which can eat pizza.
Example
Sample Input:
2
4 12
9 -3 4 3
5 -9
-7 3 -2 8 7
Sample Output:
1
1
Time Limit: 3s

Singham and his friends are fond of pizza. But this time they short of money. So they decided to help each other.They all decided to bring pizza in pairs. Our task is to find the total number of pairs possible which can buy pizza, given the cost of pizza. As pizza boy dont have any cash for change, if the pair adds upto more money than required, than also they are unable to buy the pizza. Each friend is guaranteed to have distinct amount of money. As it is Singham’s world, money can also be negative ;).

Input:

The first line consist of t(1<=t<=100) test cases.In the following 2*t lines, for each test case first there is n and m, where n(1<=n<=100000) is number of Singham’s friend and m is the price of pizza.The next line consist of n integers, seperated by space, which is the money each friend have.

The value of m and money is within the limits of int in C,C++.

Output:

A single integer representing the number of pairs which can eat pizza.

Example

Sample Input:

2

4 12

9 -3 4 3

5 -9

-7 3 -2 8 7

Sample Output:

1

1

/*Hint:
Sort all the n friends' money .
Do a modified search to find the count of pairs whose money sum equals the pizza price.(in other words
finding the number of pairs in the array whose sum equals pizza price )
*/
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int findPair(int data[], int length, int sum)
{
int c=0;
if(length < 1 )
return c;
int ahead = length - 1;
int behind = 0;
while(ahead > behind)
{
long long curSum = data[ahead] + data[behind];
if(curSum == sum)
{
c++;
behind++;
ahead--;
}
else if(curSum > sum)
ahead --;
else
behind ++;
}
return c;
}
int main(){
int t,m,n;
scanf("%d",&t);
while(t--){
scanf("%d %d",&n,&m);
int arr[n];
for(int i=0;i<n;i++){
scanf("%d",&arr[i]);
}
sort(arr,arr+n);
cout<<findPair(arr,n,m)<<endl<<endl;
}
}
view raw pizzamania.cpp hosted with ❤ by GitHub

SPOJ SBANK problem

0
Posted on by

This spoj problem may seem difficult in the beginning, but all that is required is a good knowledge of STL in C++. It simply required obtaining the account number from the user and storing it in a map. After this, just iterate through the map and print the values.

[gist https://gist.github.com/niviusha/5944486]

Spoj-Prime generator (PRIME1)

0
Posted on by

Peter wants to generate some prime numbers for his cryptosystem. Help him! Your task is to generate all prime numbers between two given numbers!

http://www.spoj.com/problems/PRIME1/

Determining the prime numbers efficiently can be a very tedious task. To crack this problem, one has to be aware of the segmented sieve of erastosthenens. First, lets take a look into what sieve of erastosthenes is. It is a technique in which the multiples of prime numbers in a range are crossed out, leaving behind only the prime numbers. To use this method, you need to define a range of values. The illustration of this sieve in this Wikipedia page should give a great insight. Segmented sieve is applied when the range of numbers is very large. In this, the range is broken down (segmented) and then sieve of erastosthenes is applied to each range. The code snippet for PRIME1 is:

#include<iostream>
using namespace std;
#include<cstdio>
#include<cmath>
#include<cstring>
#include<vector>
typedef long long ll;
void segseive( ll l, ll r){
ll limit = sqrt(r), diff = limit+1, arr[diff],i,j, seivearr[1000], start, num, set;
memset(arr, 0 , sizeof(arr));
vector<ll> primes;
vector<ll>::iterator it;
arr[0] = arr[1] = 1;
for( i = 0; i <= limit; i++){
if( !arr[i] ){
primes.push_back(i);
for( j = i+i; j<=limit; j+= i){
arr[j] = 1;
}
}
}
for( i=l; i<=r; i+= 1000){
start = i;
memset(seivearr, 0 , sizeof(seivearr));
for(it = primes.begin(); it != primes.end(); it++){
num = *it;
set = num - (start %num);
if( start%num ==0 && start>num)
seivearr[0] = 1;
for( j = set ; j<1000 && start + j<=r; j+= num){
if( start+j <= num)
continue;
seivearr[j] = 1;
}
}
for( j = 0; j< 1000 && j+start <= r; j++){
num = j+start;
if( !seivearr[j] && num != 0 && num != 1)
printf("%lld\n", start+j);
}
}
cout<<endl;
}
int main(){
ll l, r;
int t;
for( scanf("%d", &t); t; t--){
scanf("%lld%lld", &l, &r);
segseive(l,r);
}
return 0;
}
view raw PRIME1.cpp hosted with ❤ by GitHub

Here I have first applied the normal sieve to determine the prime numbers up to the square root range and then used the segmented sieve to determine the required numbers. Notice that I am not storing the resulting prime numbers and just printing them. This is because number of numbers is too large and thus has a high probability of leading to segmentation fault if they are stored and then printed.

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