# SRM 718 Editorials

[toc]

## Div II - Easy - RelativeHeights

In this problem you are given the heights of ‘n’ towers. You are required to choose n-1 of the towers and rank them according to their heights (ranks range between 0 to n-2). So, there would be C(n,n-1) choices. Of these you need to print out the choices that have unique rank ordering. To be more specific, if the rank orderings, for some example sequence, are as follows:

{0,2,3,1,4}
{4,3,2,1,0}
{3,4,1,2,0}
{0,2,3,1,4}
{2,4,1,0,3}
{3,4,1,2,0}

Of the above six possibilities, only 4 orderings look unique and the answer is thus 4.
You can follow a brute force method for this problem.

Pseudo Code:

For each tower
    Rank all the other towers according to their heights.
    Push this rank profile into a set 
Return the size of the set

My implementation is as follows:

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
class RelativeHeights
{
	public:int countWays(vector <int> h)
	{
		int hsiz=h.size();
		set<vector<int>> s;
		for(int i=0;i<hsiz;i++)
		{
			int pos=0;
			vector<pair<int,int>> mp;
			vector<int> ind(hsiz-1);
			for(int j=0;j<hsiz;j++)
			{
				if(i!=j)
				mp.push_back(make_pair(h[j],pos++));
			}
			sort(mp.begin(),mp.end());
			reverse(mp.begin(),mp.end());
			for(int k=0;k<hsiz-1;k++)
			ind[mp[k].second]=k;
			
			s.insert(ind);
		}	
		return s.size();
	}
};

## Div II - Medium - InterleavingParenthesisDiv2

We will use dp to solve this problem. Now consider dp[i][j] as total ways of interleaving for first ‘i’ characters of string s1 & ‘j’ characters of string s2. Now it’s pretty easy to see that the last character of this string of length i + j will either be ith character of string s1 or jth character of string s2. Therefore the transitions of dp will be

dp[i][j] = dp[i - 1][j] + dp[i][j - 1] (check for i = 0 & j = 0)

That’s pretty much it. Just check few cases like in the end total ‘(‘ characters should match ‘)’ characters and any intermediate dp state should have more ‘(‘ characters than ‘)’ if not that dp value will correspond to zero.

Java Code :

public class InterleavingParenthesisDiv2 {
    public int mod = 1000000007;
    public int countWays(String s1, String s2) {
        int n = s1.length(), m = s2.length();
        int[] p1 = new int[n+1], p2 = new int[m+1];
        for (int i = 1; i <= n; i++) p1[i] = p1[i-1] + (s1.charAt(i-1) == '(' ? +1 : -1);
        for (int i = 1; i <= m; i++) p2[i] = p2[i-1] + (s2.charAt(i-1) == '(' ? +1 : -1);
        int[][] dp = new int[n+1][m+1];
        dp[0][0] = 1;
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                if (p1[i] + p2[j] < 0) {
                    dp[i][j] = 0;
                    continue;
                }
                if (i>0) dp[i][j] += dp[i-1][j];
                if (j>0) dp[i][j] += dp[i][j-1];
                dp[i][j] %= mod;
            }
        }
        return p1[n] + p2[m] == 0 ? dp[n][m] : 0;
    }
}

## Div II - Hard - ChainCity

The solution of this problem is binary search.
In each step of binary search, we will find how many transporters required if all buildings must be at most X/2 distances away from nearest transporter.
Note that X is a center value of binary search range.
If all buildings are at most X/2 distances away from nearest transporter, we can move from any building to another building at most X distances.
Because, start building to nearest transporter is at most X/2, and destination from nearest transporter is at most X/2.
So, total cost must be at most X.
If less than or equal to k transporters required, X is possible answer and update the binary search range.
If more than k transporters required, X is impossible answer and also update the search range.
To find how many transporters required, just build a transporter from left to right if current building is more than X/2 distances away from nearest transporter.

Example)
dist = {3, 5, 4}
k = 2

Buildings are at 0, 3, 8, 12

step 1) Range is [0, 12(= 3 + 5 + 4)], X = (0 + 12) / 2 = 6

- Building at 0 is not covered because no transporter is built.
So, build transporter at 3(= 0 + 6 / 2) and the transporter is covers from 0 to 6.
We don't need to care about left buildings of current building. Because we build transporter from left to right.
So, build transporter at 3 is most efficient choice in this situation.

- 3 is covered because transporter is at 3
- 8 is not covered. So, build transporter at 11(= 8 + 6 / 2) and covers from 8 to 14.
- 11 is covered by transporter at 11.

- Need 2 transporter to cover all buildings.
So, 6 is possible answer.
New range is [0, 6].

step 2) Range is [0, 6], X = 3
- Build transporter at 1.5 and [0, 3] is covered.
Note that we can build transporter at anywhere.
- 3 is covered.
- 8 is not covered. So, build transporter at 9.5 and covers from 8 to 11
- 12 is not covered. build transporter at 13.5

- Need 3 transporter to cover all buildings.
So, 3 is impossible answer.
New range is [4, 6]

step 3) Range is [4, 6], X = 4 ((int)4.5)
- Build transporter at 2 and covers from 0 to 4
- 3 is covered
- 8 is not covered. build transporter at 10 and covers from 8 to 12
- 12 is covered

- Need 2 transporter and 4 is possible answer.
- new range is [4, 4]
- 4 is answer of this case.

Complexity:
D := distance between first building and last building
N := number of buildings

Time Complexity : O(NlogD)
- logD : cost of binary search
- N : cost to judge
Space Complexity : O(N)
- N : size of distances array

public class ChainCity {
    public int findMin(int[] dist, int k) {
        int[] pos = convert(dist);
        return solve(pos, k);
    }

    private int[] convert(int[] dist) {
        int[] pos = new int[dist.length + 1];
        int cur = 0;
        for (int i = 0; i < dist.length; i++) {
            pos[i] = cur;
            cur += dist[i];
        }
        pos[dist.length] = cur;
        return pos;
    }

    private int solve(int[] pos, int k) {
        int l = 0, r = pos[pos.length-1];
        while (l < r) {
            int c = (l + r) / 2;
            if (isPossible(c, k, pos)) {
                r = c;
            } else {
                l = c + 1;
            }
        }
        return r;
    }

    private boolean isPossible(int x, int k, int[] pos) {
        int coverTo = -1;
        for (int p : pos) {
            if (p > coverTo) {
                k--;
                coverTo = p + x;
            }
        }
        return k >= 0;
    }
}

## Div I - Easy - InterleavingParenthesis

This is a straightforward dynamic programming problem. We need to count the number of strings which satisfy the following two conditions:

* contains an equal number of left and right parentheses
* at no point in the string does the number of right parentheses exceed the number of left parentheses

Let dp[i][j] be of the number of ways to combine the first i characters of s1 and the first j characters of s2 into a string such that the second condition is satisfied. If there are more right parentheses than left parentheses among the first i characters of s1 and the first j characters of s2, then we set dp[i][j]=0, because the second condition will be violated. Otherwise, we set dp[i][j]=dp[i-1][j]+dp[i][j-1], taking mod 10^9+7 as necessary.

Finally, we must check if the first condition holds when we use all characters from both strings. If it does, the answer is dp[s1.length()][s2.length()]. Otherwise, the answer is 0.

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for (int i=a; i<b; i++)
#define F0R(i, a) for (int i=0; i<a; i++)

const int MOD = 1000000007;

class InterleavingParenthesis {
    public:
        int dp[2501][2501], cum1[2501], cum2[2501];
        int countWays(string s1, string s2) {
            F0R(i,2501) F0R(j,2501) dp[i][j] = 0;
            F0R(i,2501) cum1[i] = cum2[i] = 0;
            
            F0R(i,s1.length()) {
                cum1[i+1] = cum1[i];
                if (s1[i] == '(') cum1[i+1] ++;
                else cum1[i+1] --;
            }
            F0R(i,s2.length()) {
                cum2[i+1] = cum2[i];
                if (s2[i] == '(') cum2[i+1] ++;
                else cum2[i+1] --;
            }
            dp[0][0] = 1;
            F0R(i,s1.length()+1) F0R(j,s2.length()+1) if (cum1[i]+cum2[j] >= 0) {
                if (i > 0) dp[i][j] = (dp[i][j]+dp[i-1][j]) % MOD;
                if (j > 0) dp[i][j] = (dp[i][j]+dp[i][j-1]) % MOD;
            }
            if (cum1[s1.length()]+cum2[s2.length()] == 0) return dp[s1.length()][s2.length()];
            return 0;
        }
};