Tag Archives: spoj solution

Spoj (QUE1) Queue (Rookie)

1
Posted on by

problem link – http://www.spoj.com/problems/QUE1/

Vector of pairs is used to store the height and count of taller person standing before.

This problem can be solved by sorting the vector based on height.

Assign the final position for each person i in the answer array by moving them C empty positions from the index 0 where

C = count of taller person who are standing before person i

Detailed explanation is in the comments of the code below.

#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
#define MAX 10000005
typedef long long int ll;
int ans[1005];
int main(){
int t,n;
vector<pair<int,int> >arr;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
arr.resize(n);
memset(ans,0,sizeof ans);
//height
REP(i,n){
scanf("%d",&arr[i].first);
}
//count of ppl whose height is greater than the person at position i
REP(i,n){
scanf("%d",&arr[i].second);
}
//sort the vector of pairs based on the height
sort(arr.begin(),arr.end());
int greaterCount=0;
REP(i,n){
//greaterCount = count of ppl whose height is greater than the person at position i
greaterCount=arr[i].second;
REP(j,n){
//if there is no person whose height is greater than the height of current person (positioned at i) is found
//and if position j in ans array is not filled yet,then assign that person to position j
if(greaterCount==0&&ans[j]==0){
ans[j]=arr[i].first;
break;
}
//decrement the greaterCount eachtime when an unfilled answer position is found
//this implicitly means: decrement the greaterCount eachtime when a person with height greater than the current person i is found
if(ans[j]==0)
greaterCount--;
}
}
REP(i,n){
printf("%d ",ans[i]);
}
printf("\n");
}
}
view raw QUE1.cpp hosted with ❤ by GitHub

Spoj(GAMES) – HOW MANY GAMES

0
Posted on by

Brute force will give you TLE even though it will pass initial test cases.

The logic behind this problem is to represent the average score x in the form of a/b where b is minimum.

We know x=a/b . First let us bring x in the form of a/b by multiplying x with pow(10,number of digits after decimal point)

Example: x=30.25 Here we multiply x with pow(10,2) so now a=3025 and b=100

Now we have to reduce the fraction a/b to its least form.

The greatest common divisor is useful for reducing fractions to be in lowest terms. For example, gcd(42, 56) = 14, therefore,

\frac{42}{56}=\frac{3 \cdot 14 }{ 4 \cdot 14}=\frac{3 }{ 4}.

Similarly 3025/100=121*25/4*25=121/4

Now we find gcd(a,b) which is nothing but gcd(x*pow(10,numberOfDigitsAfterDecimalPoint),pow(10,numberOfDigitsAfterDecimalPoint))

FInally answer is b/gcd(a,b)

Where b = pow(10,numberOfDigitsAfterDecimalPoint)

a = x*pow(10,numberOfDigitsAfterDecimalPoint)

So ans for average score x=30.25 is 100/gcd(3025,100)=100/25=4

#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>
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
int gcd(int a,int b){
if(a<b)
return gcd(b,a);
if(b==0)
return a;
return gcd(b,a%b);
}
int main(){
int t;
scanf("%d",&t);
while(t--){
string str;
cin>>str;
int len=str.length();
int c=0;
int decimalPointFlag=0;
for(int i=len-1;i>=0;i--){
if(str[i]=='.'){
decimalPointFlag=1;
break;
}
else{
c++;
}
}
int power=0;
int number=0;
int numerator;
if(decimalPointFlag){
for(int i=0;i<len;i++){
if(str[i]!='.'){
number=number*10+str[i]-'0';
}
}
power=pow(10,c);
numerator=number;
printf("%d\n",power/gcd(numerator,power));
}
else{
printf("1\n");
}
}
}
view raw GAMES.cpp hosted with ❤ by GitHub

Spoj(MIXTURES) Mixtures – Dynamic Programming

6
Posted on by

I always love solving Harry Potter theme based problems.This one http://www.spoj.com/problems/MIXTURES/ was  fun solving.

Its based on classic DP problem Matrix Chain multiplication.

Task :

Minimize the  amount of smoke that Harry can get when mixing all the mixtures together.

Solution:

If you look into the problem statement carefully you will know that harry can mix only adjacent  mixtures together. So for example m1,m2,m3 are the mixtures he can either mix m1,m2 first or m2,m3 first.

i.e you can either split the mixture set as {m1} and {m2,m3}

OR

{m1,m2} and {m3}

Let dp[a][b]=minimum smoke produced on mixing mixtures a to b

SO its all about splitting the mixtures into 2 subsets and each of that subsets into 2 sub-subsets and so on such that smoke produced(smoke generated in mixing subsets s1 ans s2 is sum(elements in s1)%100 X sum(elements in s2)%100) is minimized. Aim of the problem  boils down to minimizing the product of the 2 mixtures to be mixed.

Hence our recurrence relation is going to be

dp[a][b]=min(dp[a][k]+dp[k+1][b]+sum(a,k)*sum(k+1,b)) for all k where a<=k<b

Here sum(a,b) defines (sum of all elements from a to b )%100

Base case is dp[i][i]=0

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

Spoj(NITT8) Dating Rishi

0
Posted on by

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

Theres a nlogn solution for this.

Store the (height,position) array as a vector of pairs

Now our aim is to maximize the friend quotient(i,e maximize both terms a and b in the formula given down)

FQ = minimum height of the 2 girls {term a}* absolute diff of the position of the 2 girls{term b}

Sort the vector based on height

 After sorting , considering each height element h of the pair (starting from the maximum. i.e is right side) as the candidate for the minimum height .Let its postion be i.

We have to maximize the difference too.(maximize b). So for each position i ( position where our candidate height h is located) find the value that is most maximum than it and store it in max1.also find the value that is most minimum that it and store it in min1.

You will find out that you have to check only the right side of the position i to find the max1 and min1 since if we go left our height value will be reduced. 

Calculate the F.Q at each iteration and store the maximum F.Q in a variable and update the variable at each stage.

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

Spoj(FARIDA) – Princess Farida

0
Posted on by

This is an interesting and easy DP problem. I solved this in less than 5 minutes.(Trust me ! Its that easy)

Let

dp[i] –> maximum coin sum till i monsters

dp[i]=max(arr[i]+solve(i+2),solve(i+1));

Case 1:

if you choose the ith monster’s coins you cannot choose the next so you
move to the i+2th monster.

Case 2:

if you do not choose the ith monster’s coins you still have a chance to choose i+1th monster’s coins.So you move to i+1th monster

[gist https://gist.github.com/anonymous/8433780]

Spoj(RPLB) Blueberries

0
Posted on by

Yet another Knapsack based problem

#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>
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
int n,W,wt[1001];
int dp[1001][1001];
int solve(int i,int w){
if(i>n)
return w;
if (dp[i][w]!=-1)
return dp[i][w];
if((wt[i]+w)<=W)
dp[i][w]=max(solve(i+2,w+wt[i]),solve(i+1,w));
else
dp[i][w]=solve(i+1,w);
return dp[i][w];
}
int main(){
int t;
scanf("%d",&t);
FOR(j,1,t+1){
scanf("%d %d",&n,&W);
FOR(i,1,n+1){
scanf("%d",&wt[i]);
}
memset(dp,-1,sizeof dp);
printf("Scenario #%d: %d\n",j,solve(1,0));
}
}
view raw RPLB.cpp hosted with ❤ by GitHub