# Spoj HOTELS solution. Spoj Hotels Along the Croatian Coast Solution.

Category: Dynamic Programming, DP
This problem uses a technique called sliding window method or Kadane’s algorithm (Modified version is used). It is fairly easy to understand.
Logic used:
In this, you need a continuous set of hotels. To consider a set (window), we will use two pointers- One pointing to the first hotel of the window and the second pointer pointing to the last hotel of the window. It is an O(n) solution.
Now, consider two variables:
1. max_so_far  – which holds the maximum sum so far (Final ans).
2. curr_max – which holds the current sum.
1. Increment through all hotels and keep adding the cost of each hotel to curr_max until it is greater than m. (Here, this is done by incrementing end).
2. While curr_max is greater than m , increment the first pointer, which slides the window forward i.e. remove the value of that hotel. (Here, this is done by st) .
3. If curr_max>max_so_far and curr_max<=m then update max_so_far => max_so_far=curr_max.
4. As soon as curr_max=m, update max_so_far and break the loop.

### Spoj HOTELS solution code:

Here is the working code:

#include <bits/stdc++.h>
using namespace std;
#define LL long long

int main() {
ios::sync_with_stdio(false);

int n,val;
cin>>n>>val;
int arr[n];
for(int i=0;i<n;++i)
cin>>arr[i];

LL max_so_far = arr[0];
LL curr_max = arr[0];

/*Starting index*/
int st=0;

for(int i=1;i<n;++i)
{
if(curr_max+arr[i]>arr[i])
{
curr_max = curr_max+arr[i];
}
else
curr_max = arr[i];

while(curr_max>=val)
{
curr_max-=arr[st++];
if(curr_max==val)
max_so_far=curr_max;
}
max_so_far = max(curr_max,max_so_far);
}
cout<<max_so_far;
return 0;
}

# Spoj BRCKTS solution. Spoj Brackets solution.

Category : Segment Trees

In this problem, we are given a string containing parenthesis (open and closed), which requires making updates to individual parenthesis (changing an open parenthesis to closed or vice versa), and checking if the whole string represents a correct parenthesization.
Only 2 things are needed in each segment tree node:

1. The number of unmatched open parenthesis in this range.
2. The number of unmatched closed parenthesis in this range.

When we merge the counts, we need to find the minimum of the open brackets on left subtree, and closed brackets on the right subtree.

Then, we add the open and closed counts, and subtract the minimum count found above.

### Spoj BRCKTS solution code:

Here is the working code:

#include <bits/stdc++.h>
using namespace std;

struct node
{
int open;
int closed;
};

node tree[3*30005];
char arr[30005];

/*This function is used to build the
Segment Tree*/
void build(int index,int start,int end)
{
if(start == end)
{
if(arr[start]=='(')
{
tree[index].open = 1;
tree[index].closed = 0;
}
else
{
tree[index].open = 0;
tree[index].closed = 1;
}
}
else
{
int mid = (start+end)/2;
build(2*index+1,start,mid);
build(2*index+2,mid+1,end);

int change =
min(tree[2*index+1].open,tree[2*index+2].closed);
tree[index].open =
tree[2*index+1].open + tree[2*index+2].open - change;
tree[index].closed =
tree[2*index+1].closed + tree[2*index+2].closed - change;
}
}

/*This function is used to answer the queries
that are there*/
node query(int index,int start,int end,int l,int r)
{
node result;

if(start==l && end==r)
return tree[index];

int mid = (start+end)/2;
if(l>mid)
return query(2*index+2,mid+1,end,l,r);
if(r<=mid)
return query(2*index+1,start,mid,l,r);

node left = query(2*index+1,start,mid,l,r);
node right = query(2*index+2,mid+1,end,l,r);

int change =
min(left.open,right.closed);
result.open =
left.open + right.open - change;
result.closed =
left.closed + right.closed - change;
return result;
}

/*This function is used to update the value in
the Segment Tree*/
void update(int index,int start,int end,int idx,char value)
{
if(start == end)
{
if(value =='(')
{
tree[index].open = 1;
tree[index].closed = 0;
}
else
{
tree[index].open = 0;
tree[index].closed = 1;
}
}
else
{
int mid = (start + end) / 2;
if(idx <= mid)
update(2*index+1,start,mid,idx,value);
else
update(2*index+2,mid+1,end,idx,value);

int change =
min(tree[2*index+1].open,tree[2*index+2].closed);
tree[index].open =
tree[2*index+1].open + tree[2*index+2].open - change;
tree[index].closed =
tree[2*index+1].closed + tree[2*index+2].closed - change;
}
}

int main() {
ios::sync_with_stdio(false);

int n,q,val;
for(int cc=1 ; cc<=10 ; ++cc)
{
cin>>n;
cin>>arr;
cin>>q;
build(0,0,n-1);
cout<<"Test "<<cc<<":\n";
while(q--)
{
cin>>val;
if(val)
{
arr[val-1] = arr[val-1]=='('?')':'(';
update(0,0,n-1,val-1,arr[val-1]);
}
else
{
node result=query(0,0,n-1,0,n-1);
if(result.open==0 && result.closed==0)
cout<<"YES\n";
else
cout<<"NO\n";
}
}
}
return 0;
}

# Spoj KGSS solution. Spoj Maximum Sum Solution.

Category: Segment Tree

This problem asks for the maximum pair sum in each subarray and also requires updates to individual array elements. We need to store 2 things in each segment tree node:

1. The maximum value in this range.
2. The second maximum value in this range.

### Spoj KGSS solution code:

Here is the working code:

#include <bits/stdc++.h>
using namespace std;

/*Structure to store largest
and second largest value*/
struct node
{
int first;
int second;
};

node tree[3*100005];
int arr[100005];

/*This function is used to build the
Segment Tree.*/
void build(int index,int start,int end)
{
if(start==end)
{
tree[index].first = arr[start];
tree[index].second = INT_MIN;
}
else
{
int mid = (start+end)/2;
build(2*index+1,start,mid);
build(2*index+2,mid+1,end);

tree[index].first =
max(tree[2*index+1].first,tree[2*index+2].first);
tree[index].second =
min(max(tree[2*index+1].first,tree[2*index+2].second),
max(tree[2*index+1].second,tree[2*index+2].first)
);
}
}

/*This function is used to answer the queries
that  are there*/
node query(int index,int start,int end,int l,int r)
{
node result;
result.first = result.second = -1;

if(start>r || end<l )
return result;
if(start>=l && end<=r)
return tree[index];

int mid = (start+end)/2;
if(l>mid)
return query(2*index+2,mid+1,end,l,r);
if(r<=mid)
return query(2*index+1,start,mid,l,r);

node left = query(2*index+1,start,mid,l,r);
node right = query(2*index+2,mid+1,end,l,r);

result.first =
max(left.first,right.first);
result.second =
min(max(left.first,right.second),
max(left.second,right.first)
);
return result;
}

/*This function is used to update the value in
the Segment Tree*/
void update(int index,int start,int end,int idx,int value)
{
if(start == end)
{
tree[index].first = value;
tree[index].second = INT_MIN;
}
else
{
int mid = (start + end) / 2;
if(idx <= mid)
update(2*index+1,start,mid,idx,value);
else
update(2*index+2,mid+1,end,idx,value);

tree[index].first =
max(tree[2*index+1].first,tree[2*index+2].first);
tree[index].second =
min(max(tree[2*index+1].first,tree[2*index+2].second),
max(tree[2*index+1].second,tree[2*index+2].first)
);
}
}

int main() {
ios::sync_with_stdio(false);
int n,q,a,b;
char ch;

cin>>n;
for(int i=0;i<n;++i)
cin>>arr[i];
build(0,0,n-1);
cin>>q;

for(int i=0;i<q;++i)
{
cin>>ch>>a>>b;
if(ch=='Q')
{
node result = query(0,0,n-1,a-1,b-1);
cout<<result.first+result.second<<"\n";
}
else
update(0,0,n-1,a-1,b);
}
return 0;
}

# Spoj GSS3 solution. Spoj Spoj Can you answer these queries I solution.

Category: Segment Tree

This question is an extension of GSS1 , here we need to add the update function along with the existing code.

Read Spoj GSS1 solution, to understand how the solution works.

Given below is the code for update function along with the existing code. Note the similarities between the “build()” and the “update()” function.

### Spoj GSS3 solution code:

Here is the working code:

#include <bits/stdc++.h>
using namespace std;

/*Structure that is used to
store value*/
struct node
{
int sum,prefixsum;
int suffixsum,maxsum;
};

node tree[4*50010];
int arr[50010];

/*This function is used to build the
segment tree*/
void build(int index,int start,int end)
{
if(start == end)
{
tree[index].sum = arr[start];
tree[index].prefixsum = arr[start];
tree[index].suffixsum = arr[start];
tree[index].maxsum = arr[start];
}
else
{
int mid = (start+end)/2;
build(2*index+1,start,mid);
build(2*index+2,mid+1,end);

/*Note how we use the array to access the left
and right subtree*/
tree[index].sum =
tree[2*index+1].sum + tree[2*index+2].sum;
tree[index].prefixsum =
max(tree[2*index+1].prefixsum,
tree[2*index+1].sum + tree[2*index+2].prefixsum);
tree[index].suffixsum =
max(tree[2*index+2].suffixsum,
tree[2*index+2].sum + tree[2*index+1].suffixsum);
tree[index].maxsum =
max(tree[index].prefixsum,
max(tree[index].suffixsum,
max(tree[2*index+1].maxsum,
max(tree[2*index+2].maxsum,
tree[2*index+1].suffixsum
+tree[2*index+2].prefixsum
)
)
)
);
}
}

/*This function is used to modify/update data */
void update(int index,int start,int end,int idx,int value)
{
if(start == end)
{
tree[index].sum = value;
tree[index].prefixsum = value;
tree[index].suffixsum = value;
tree[index].maxsum = value;
}
else
{
int mid = (start + end) / 2;
if(idx<=mid)
update(2*index+1,start,mid,idx,value);
else
update(2*index+2,mid+1,end,idx,value);

tree[index].sum =
tree[2*index+1].sum + tree[2*index+2].sum;
tree[index].prefixsum =
max(tree[2*index+1].prefixsum,
tree[2*index+1].sum + tree[2*index+2].prefixsum);
tree[index].suffixsum =
max(tree[2*index+2].suffixsum,
tree[2*index+2].sum + tree[2*index+1].suffixsum);
tree[index].maxsum =
max(tree[index].prefixsum,
max(tree[index].suffixsum,
max(tree[2*index+1].maxsum,
max(tree[2*index+2].maxsum,
tree[2*index+1].suffixsum
+tree[2*index+2].prefixsum
)
)
)
);
}
}
/*this function is used to return the result
for each query*/
node query(int index,int start,int end,int l,int r)
{
node result;
result.sum=result.prefixsum=INT_MIN;
result.suffixsum=result.maxsum=INT_MIN;

if(r<start || end<l)
return result;
if(l<=start && end<=r)
return tree[index];

int mid = (start+end)/2;
if (l > mid)
return query(2*index+2, mid+1, end, l, r);
if (r <= mid)
return query(2*index+1, start, mid, l, r);

node left = query(2*index+1,start,mid,l,r);
node right = query(2*index+2,mid+1,end,l,r);

result.sum = left.sum + right.sum;
result.prefixsum =
max(left.prefixsum, left.sum + right.prefixsum);
result.suffixsum =
max(right.suffixsum, right.sum + left.suffixsum);
result.maxsum =
max(result.prefixsum,
max(result.suffixsum,
max(left.maxsum,
max(right.maxsum,
left.suffixsum + right.prefixsum))));
return result;
}

int main() {
int n,m,a,b,mode;
scanf("%d",&n);

for(int i=0;i<n;++i)
scanf("%d",&arr[i]);

build(0,0,n-1);

scanf("%d",&m);

for(int i=0;i<m;++i)
{
scanf("%d%d%d",&mode,&a,&b);
if(mode)
printf("%d\n",query(0,0,n-1,a-1,b-1).maxsum);
else
update(0,0,n-1,a-1,b);
}
return 0;
}


# Spoj GSS1 solution. Spoj Can you answer these queries I solution.

Category: Segment Tree

In this question we need to print the sum such that each query:
Query(x,y) = Max { a[i]+a[i+1]+…+a[j] ; x ≤ i ≤ j ≤ y }, is satisfied.

We need to store 4 values in each node of the Segment Tree, so we use this structure.

struct node
{
int sum,prefixsum;
int suffixsum,maxsum;
};

We need to store the following 4 values:

1. Maximum sum of a subarray, starting at the leftmost index of this range.
2. Maximum sum of a subarray, ending at the rightmost index of this range.
3. Maximum sum of any subarray in this range.
4. Sum of all elements in this range.

The processing for each sum is done as follows:

node result;
result.sum = left.sum + right.sum;
result.prefixsum = max(left.prefixsum, left.sum + right.prefixsum);
result.suffixsum = max(right.suffixsum, right.sum + left.suffixsum);
result.maxsum =
max(result.prefixsum,
max(result.suffixsum,
max(left.maxsum,
max(right.maxsum,left.suffixsum + right.prefixsum))));

### Spoj GSS1 solution code:

Here is the complete code:

#include <bits/stdc++.h>
using namespace std;

/*Structure that is used to
store value*/
struct node
{
int sum,prefixsum;
int suffixsum,maxsum;
};

node tree[4*50010];
int arr[50010];

/*This function is used to build the
segment tree*/
void build(int index,int start,int end)
{
if(start == end)
{
tree[index].sum = arr[start];
tree[index].prefixsum = arr[start];
tree[index].suffixsum = arr[start];
tree[index].maxsum = arr[start];
}
else
{
int mid = (start+end)/2;
build(2*index+1,start,mid);
build(2*index+2,mid+1,end);

/*Note how we use the array to access the left
and right subtree*/
tree[index].sum =
tree[2*index+1].sum + tree[2*index+2].sum;
tree[index].prefixsum =
max(tree[2*index+1].prefixsum,
tree[2*index+1].sum + tree[2*index+2].prefixsum);
tree[index].suffixsum =
max(tree[2*index+2].suffixsum,
tree[2*index+2].sum + tree[2*index+1].suffixsum);
tree[index].maxsum =
max(tree[index].prefixsum,
max(tree[index].suffixsum,
max(tree[2*index+1].maxsum,
max(tree[2*index+2].maxsum,
tree[2*index+1].suffixsum
+tree[2*index+2].prefixsum
)
)
)
);
}
}

/*this function is used to return the result
for each query*/
node query(int index,int start,int end,int l,int r)
{
node result;
result.sum=result.prefixsum=INT_MIN;
result.suffixsum=result.maxsum=INT_MIN;

if(r<start || end<l)
return result;
if(l<=start && end<=r)
return tree[index];

int mid = (start+end)/2;
if (l > mid)
return query(2*index+2, mid+1, end, l, r);
if (r <= mid)
return query(2*index+1, start, mid, l, r);

node left = query(2*index+1,start,mid,l,r);
node right = query(2*index+2,mid+1,end,l,r);

result.sum = left.sum + right.sum;
result.prefixsum =
max(left.prefixsum, left.sum + right.prefixsum);
result.suffixsum =
max(right.suffixsum, right.sum + left.suffixsum);
result.maxsum =
max(result.prefixsum,
max(result.suffixsum,
max(left.maxsum,
max(right.maxsum,
left.suffixsum + right.prefixsum))));
return result;
}

int main() {
int n,m,a,b;
scanf("%d",&n);

for(int i=0;i<n;++i)
scanf("%d",&arr[i]);

build(0,0,n-1);

scanf("%d",&m);

for(int i=0;i<m;++i)
{
scanf("%d%d",&a,&b);
printf("%d\n",query(0,0,n-1,a-1,b-1).maxsum);
}
return 0;
}


# Spoj RPLN Solution. Spoj Negative Score solution.

Category: Segment Tree.

In this question we need to find the minimum value in the Given Range, put in another words, this question deals with Range Minimum Query.

We use the nodes of segment tree to store the minimum value of the ranges.

Segment Tree and relate theory can be read on the link.

### Spoj RPLN solution code:

Here is the working code:

#include <bits/stdc++.h>
using namespace std;

int tree[2*1000005];
int arr[1000005];

/*this function is used to build the
Segment Tree. We used o-indexed array
to store the tree*/
void build(int node,int start,int end)
{
if(start == end)
{
tree[node] = arr[start];
}
else
{
int mid = (start+end)/2;
build(2*node+1,start,mid);
build(2*node+2,mid+1,end);
tree[node] = tree[2*node+1]>tree[2*node+2]?tree[2*node+2]:tree[2*node+1];
}
}

/*This function is used to query the Segment Tree
to find the minimum of the given range*/
int query(int node,int start,int end,int l,int r)
{
if(start>r || end<l)
return INT_MAX;

/*If completely inside*/
if(start>=l && end<=r)
return tree[node];

/*If partially inside*/
int mid = (start+end)/2;
int p1 = query(2*node+1,start,mid,l,r);
int p2 = query(2*node+2,mid+1,end,l,r);
if(p1>p2)
return p2;
else
return p1;
}

int main() {

int n,q,a,b,t,caseCount=0;
scanf("%d",&t);
while(t--)
{
caseCount++;
scanf("%d%d",&n,&q);

for(int i=0;i<n;++i)
scanf("%d",&arr[i]);

build(0,0,n-1);
printf("Scenario #%d:\n",caseCount);
for(int i=0;i<q;++i)
{
scanf("%d%d",&a,&b);
printf("%d\n",query(0,0,n-1,a-1,b-1));
}
}
return 0;
}

# Spoj MSCHED solution. Spoj Milk Scheduling Solution.

Category: Greedy Algorithm

This question is the direct application of the Job Sequencing Problem.

We need to maximise the milk that we get, at the same time taking care of the deadlines.

Here we use a vector of STL pair<> to keep the corresponding deadlines and gallons of milk together.
We then use the STL sort function, with a user defined comparison function.
This comparison function returns a “true” value if the first argument comes before the second argument in the sorted output.
We using the function sort the cows on the basis of milk production, if the production is same, then we sort on the basis of lower deadline.
We then use a slot[] array, to keep track if the corresponding processing slot has been used or not.

### Spoj MSCHED solution code:

Here is the working code:

#include <bits/stdc++.h>
using namespace std;

/*Function used for user-defined sorting,
return true if first argument should
come before second argument in the
sorted output*/
bool comp(pair<int,int> a,pair<int,int> b)
{
if(a.first != b.first)
return a.first > b.first;
return a.second < b.second;
}

int main() {
ios::sync_with_stdio(false);

int n,a,b;
cin>>n;

/*Making pairs of deadline and
milk produced for each cow*/
vector<pair<int,int> > v;
for(int i=0;i<n;++i)
{
cin>>a>>b;
v.push_back(make_pair(a,b));
}
/*STL sort*/
sort(v.begin(),v.end(),comp);

bool slot[n]={0};
int ans=0;

/*Job sequencing*/
for(int i=0;i<n;++i)
for(int j=min(n,v[i].second)-1;j>=0;--j)
{
if(!slot[j])
{
slot[j]=true;
ans += v[i].first;
break;
}
}
cout<<ans<<"\n";
return 0;
}

# Spoj GERGOVIA solution. Spoj Wine trading in Gergovia solution.

Category: Greedy Algorithm

This question is based on Greedy approach.
Since every element is needed to become zero so just keep on accumulating the total work .

Suppose the first element is non-zero then it must be transferred to the next element so whether it is positive or negative you have to transfer it all. And the work will be absolute value of the transferred element.
In this way you just need to sum it up till the last term and you will get the total work.

### Spoj GERGOVIA solution code:

Here is the working code:

#include <bits/stdc++.h>
using namespace std;

int main() {
ios::sync_with_stdio(false);

int t,n;
long long work=0;
cin>>n;
while(n)
{
work=0;
int arr[n];
for(int i=0 ; i<n ; ++i)
cin>>arr[i];
for(int i=1 ; i<n ; ++i)
{
arr[i] += arr[i-1];
work += abs(arr[i-1]);
}
cout<<work<<"\n";
cin>>n;
}
return 0;
}

# SPOJ ABSP1 SOLUTION. SPOJ abs(A-B) I SOLUTION.

In this question, for solution in one iteration, we need to calculate all the terms corresponding to each position of array in one step.
This can be done if initially we find the sum of all the elements.

Algorithm:

1. Find sum of all the elements. (this is done while input-ing them).
2. For each element apart from the last, do the following.
1. Subtract that element from sum.
Now sum contains sum of all elements towards right of the present element.
2. Add to “answer” the difference (sum – (n-i-1)*arr[i])  where i is used for iteration and n is the number of elements.
This is done as for each element to the right of the present element we need to add the corresponding difference, since the sum of all elements to the right is in “sum”, we just need to subtract the present value (n-(i+1)) times.
3. Output the “answer”.

### Spoj ABSP1 solution code:

Here is the working code:

#include <bits/stdc++.h>
using namespace std;
#define LL long long

int main() {
ios::sync_with_stdio(false);

int t,n;
cin>>t;
LL sum=0,ans=0;

while(t--)
{
sum=0;
ans=0;
cin>>n;
LL arr[n];
for(int i=0;i<n;++i)
{
cin>>arr[i];
sum += arr[i];
}
for(int i=0;i<n-1;++i)
{
sum -= arr[i];
ans += sum-(n-i-1)*arr[i];
}
cout<<ans<<"\n";
}

return 0;
}

# Spoj GEEKOUNT Solution. Spoj EVEN COUNT Solution.

Category: Maths, AdHoc, Formula

We have to find the count of such numbers, between 2 given numbers, whose product of digits is even. Any number, in which any one digit is even, will come in this category. We will find all those numbers whose product of digits is odd and subtract them from total numbers between two given numbers. We will calculate required numbers from 1 to first number and lets call it num1, then from 1 to second number and lets call it num2 , then num2-num1 will be the answer.

Suppose we consider any n digit number. Then the number of numbers with exactly n digits and all digits odd will be 5 raised to power n. So, the number of numbers from 1 digit to n digits with all digits odd will be sum of all powers of 5 raised to power 1 upto n ie. 51 +52 +53 +…….+5n.

The above formula of 5 gives the ans as 999..9(n times). But what about the case when the number is neither the smallest, nor the largest n digit number.

So if we are a general n digit number, then we will use formula to calculate the required number of numbers upto n-1 digits and use the following approach to calculate the number of n digits numbers, smaller than given number, for which product of digits is odd.

The number of such numbers will be equal to sum of the numbers of product of half of corresponding digit and 5^ [length-position-1] and this digit will be from left digit to right digit. However, this process will stop when we encounter an even digit because from there we will not get any number where all digits will be odd.

Do the same for second number.

Subtract n1 from n2 and subtract this result from the difference between the given 2 numbers to obtain the required answer.

Let us take an example. Suppose we have to calculate till 57981. So, from 10000 to 50000, our counting will be only from 10000 to 19999 and 30000 to 39999, so and the number will be equal to same which we found for 4-digit numbers. Then we will shift our counter from 5 to 7 in our number 57981. Now, our target will be from 1000 to 1999, 3000 to 3999, 5000 to 5999, and our answer will be same as we found for 3 digit numbers. Process terminates as we encounter 8 as after it, no more numbers with all digits odd. (Source: Internet)

### Spoj GEEKOUNT solution code:

Here is the working code:

#include <bits/stdc++.h>
using namespace std;

/*This function gives the number of numbers
whose porduct of digits is even*/
int evenProd(int a)
{
int ans=0,flag=0;
int temp=a,Power=0;
int digit[11];

/*Converting the number to
digits and adding 5^0 to
5^(n-1) to the result*/
while(temp/10!=0)
{
digit[Power++]=temp%10;
temp/=10;
ans+=pow(5,Power);
}
digit[Power]=temp%10;

/*Working till 1st even digit*/
while(Power>0)
{
if(digit[Power]%2==0)
{
ans+=(digit[Power]/2)*pow(5,Power);
flag=1;
break;
}
else
{
ans+=(digit[Power]/2)*pow(5,Power);
flag=0;
}
Power--;
}
if(!flag)
{
ans+=((digit[Power]+1)/2);
}
return (a-ans);
}

int main() {
ios::sync_with_stdio(false);

int t,a,b;
cin>>t;
while(t--)
{
cin>>a>>b;
cout<<evenProd(b)-evenProd(a-1)<<"\n";
}
return 0;
}