Tag Archives: spoj solution

Spoj(EDIST) – Edit Distance -Dynamic Programming

0
Posted on by

 

2013-12-13 19.26.29

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

Consider the string SAT .We need to convert it into SAIT

there are 3 possibilities as seen in the picture

So the recursive rule goes like this

dp[i,j]=edit distance for strings of length i and j

dp[i,j]= min(dp[i-1,j-1]+(X[i-1]!=Y[j-1]),dp[i-1,j]+1,dp[i,j-1]+1)

Here X and Y are strings with 0 based index i.e  X[i-1] denotes ith character in X

With the base conditions

dp[0,j]=j //just insertions

dp[j,0]=j //just deletions

#include<iostream>
#include<string.h>
using namespace std;
char str1[2001];
char str2[2001];
int dp[2001][2001];
int main(){
int t;
cin>>t;
while(t--){
cin>>str1>>str2;
int d1,d2,d3,i,j,len1,len2;
len1=strlen(str1);
len2=strlen(str2);
for( i=0;i<=len1;i++)
dp[i][0]=i;
for( j=1;j<=len2;j++)
dp[0][j]=j;
for( i=1;i<=len1;i++){
for( j=1;j<=len2;j++){
d1=((str1[i-1]==str2[j-1])?0:1)+dp[i-1][j-1];//substitution-->if last character same dont do anything(0) else replace last char(1
d2=dp[i][j-1]+1; // convert (s+ch1) to (t+ch2) by inserting in ch2. so dp (s+ch1,t)+1 +1 for ch2 insertion
//insertion-->str2 of j-1 length is converted to
d3=dp[i-1][j]+1;//deletion -->convert (s+ch1) to (t+ch2) by deleting ch1 from s.so dp[s,t+ch2]+1 +1 for ch1 deletion
//finding minimum of 3
if(d1<d2&&d1<d3)
dp[i][j]=d1;
else{
if(d2<d3)
dp[i][j]=d2;
else
dp[i][j]=d3;
}
}
}
cout<< dp[len1][len2];
cout<<endl;
}
}
view raw EDIST.cpp hosted with ❤ by GitHub

Spoj (SUBS) – String it out

0
Posted on by

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

There is  a very interesting algorithmic approach for this problem

(Thanks to topcoder forum from where i got this idea)

To find the maximum power using which X can be expanded such that X is a subsequence in Y

highest possible power = length_of_Y/length_of_X

lowest power= 0

Now using binary search find the maximum valid power whose value is in the range [0,highest possible power]

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

Spoj (DSUBSEQ) – Distinct Subsequences

0
Posted on by

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

Consider the string “ABCD”

Let dp[i] = { number of subsequences possible from string[1…i]}

Note : we are considering 1 based string array

what are all the possible subsequences

dp[0] = 1   { }

dp[1]= 2   { } ,A

dp[2] = 4  { } ,A ,B ,AB

dp[3] = 8  { } ,A ,B ,AB ,C ,AC,BC,ABC

dp[4] = 16 { } ,A ,B ,AB ,C ,AC,BC,ABC,D,AD,BD,ABD,CD,ACD,BCD ,ABCD

So do we get some kind of pattern ?

yes!

dp[i]= dp[i-1]*2

(sum of all subseq till string[1…i-1] + sum of subseq till string[1…i-1] concatenated with character string[i])

There one more case we have to consider

if we have duplicate characters in the string then our subsequence will also be duplicated

To prevent that have a last[ ] array to store position of string[i] which occured before

last[string[i]]= last occurence of string[i]

substract subsequence count occured till position (last[string[i]]-1) since it is repeated again

so the correct recursion rule is

dp[i]=dp[i-1]*2;

if(last[string[i]]>0)

dp[i]=(dp[i]-dp[last[string[i]]-1]);

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- 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-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.