Single Round Match 711 Editorials

March 25, 2017 Harshit Mehta

SRM 711 Editorials are now here. Thanks to jonathanirvings, Shizhouxing, hariom_7, stni for contributing to the Editorials. A big thanks to Egor for reviewing the submissions.
Just to remind you all, TCO17 Algorithm Rounds begin from 1st week of April. Check out the schedule here.

Below are the editorials that got submitted. You can reach out to the writers in the discussion forum.


Single Round Match 711 Round 1 – Division II, Level One SquareMaking by jonathanirvings

The optimal final length will be between min(a,b,c,d) and max(a,b,c,d). Since the constraint is small, a brute force solution will run on time. Another solution that runs in O(1) exists, but that won’t be necessary. The faster solution is left as an exercise for the reader.

C++

    
    #include <bits/stdc++.h>
    using namespace std;
    
    class SquareMaking {
        public:
        int getMinimalPrice(int a,int b,int c,int d) {
            int answer = 1000000000;
            for (int i = 1; i <= 1000000; ++i) {
                int cur = abs(i - a) + abs(i - b) + abs(i - c) + abs(i - d);
                answer = min(answer, cur);
            }
            return answer;
        }
    }
    

Single Round Match 711 Round 1 – Division II, Level Two StringTransform by hariom_7

We are given two strings which have equal lengths and we have to make some changes in first string such that we can make second string. For change in first string at location idx we can select any index which is less than idx and we can replace s[idx] by s[i] ( 0 < i < idx) if it satisfiesthe condition.

In my code I have used map for storing the characters which have already appeared in string S. Now I will traverse both the string from i = 0 to l, if both the strings contained same character at location i then make m[s[i]] true if both the characters at location are not same them we have to look upon the values of m if value of T[i] has appeared in the map then we can transform that character else we can not transform string s to T.

Solution class :

    
    // here is my solution 
    #include<bits/stdc++.h>
        class StringTransform {
    public:
        string isPossible(string s, string t) {
            int l = s.length();
            map<char,bool> m; // to store the characters
            // which are already traverse
            for ( int i = 0 ; i < l ;i++)
            {
                if ( s[i] == t[i])
                {
                    m[s[i]] = true;
                }
            else if ( m[t[i]] == false) // if char t[i] is not there in the map then return Impossible
                return "Impossible";
            else
                m[s[i]] = true ;
            }
            return "Possible"; // if all the condition satisfied return Possible
        }
    };
    

Single Round Match 711 Round 1 – Division II, Level Three TreeMovingDiv2 by Stni

Let’s use dynamic programming to solve this problem

dp[i][j]: number of ways to remove j-th edge of i-th tree

If we remove j-th edge from tree_i,
we will have to connect the two subtrees connected by the j-th edge,

    
    for all edge_k in tree_i-1,
        if end points of edge_k connects the two subtrees,
            we add the number of ways to remove edge_k from tree_i-1 to dp[i][j]
    

So the transition is dp[i][j]=dp[i][j]+dp[i-1][k]

We need to do this DP n-1 times, each time we calculate the number of ways to remove one of the edges of the first tree.

The answer to our problem is the sum of all the n-1 results. Which equals to the number of all possible ways to remove any of the edges of the first tree.

To do this, we need to use a depth-first search to get all edges in tree_i able to replace edge_k of tree_i+1

For tree_i+1, we will see if edge_j of tree_i endpoints u and v can be connected.

If they can be connected, all the edges of tree_i+1 along the search will be marked as able to be replaced by edge_j of tree_i.

Because if an edge_e on the search path is disconnected, the end points of the edge_e can still be connected by all the edges on the search path plus edge_j of tree_i. The search path plus edge_j of tree_i forms a loop, disconnection of any one of the edge make the nodes form a tree.

Total complexity is O(n^3*m)

C++

    
    #include <vector>
    #include <string.h>
    using namespace std;

    const int mod=1e9+7;

    class TreeMovingDiv2{
        int m,X[100],u[51][51],v[51][51];
        vector<pair<int,int> >edges[51][51]; // edge[i][j]=(a,b)       := i-th tree has edge_b connecting node_j and node_a
        bool canBeReplaced[51][51][51];      // canBeReplaced[i][j][k] := edge_k of tree_i can be replaced by edge_j of tree_i-1
        bool dfs(int treeId, int edgeId, int cur, int des, int prev=-1){
            if(cur==des) return true;
            for(pair<int,int> edge : edges[treeId][cur]){
                int u=edge.first, id=edge.second;
                if(u==prev) continue;
                if(dfs(treeId, edgeId, u, des, cur)){
                    /*
                     In tree_treeId, end points of edge_edgeId from tree_treeId-1 can be connected by edge_id
                     */
                    canBeReplaced[treeId][edgeId][id] = true;
                    return true;
                }
            }
            return false;
        }
        long long dp[51][51];       //dp[i][j] := number of ways to remove edge_j of i-th tree
    public:
        int count(int n,vector<int>roots,vector<int>a,vector<int>b,vector<int>c){
            m = (int)roots.size();
            memset(canBeReplaced, 0, sizeof(canBeReplaced));
            for(int i=0;i<m;i++){
                X[0] = c[i];
                for(int k=1;k<=n-1;k++)X[k]=(1ll * a[i] * X[k-1] + b[i]) % mod;
                for(int j=0;j<=n-2;j++){
                    u[i][j]=(roots[i]+j+1)%n;
                    v[i][j]=(roots[i]+(X[j]%(j+1)))%n;
                    edges[i][u[i][j]].push_back(make_pair(v[i][j], j));
                    edges[i][v[i][j]].push_back(make_pair(u[i][j], j));
                }
            }
            for(int i=0;i<n;i++){
                edges[m][i]=edges[0][i];
            }
            for(int i=0;i<m;i++){
                for(int j=0;j<n-1;j++){
                    /*
                     for all edges of tree_i,
                     check if there are paths connecting (the two end points of edge_j of tree_i) in tree_i+1
                     */
                    dfs(i+1,j,u[i][j],v[i][j]);
                }
            }
            long long ans=0;
            for(int i=0;i<n-1;i++){
                memset(dp,0,sizeof(dp));
                // 1 way to remove edge_i from tree_0
                dp[0][i]=1;
                for(int j=1;j<=m;j++){
                    for(int k=0;k<n-1;k++){
                        for(int p=0;p<n-1;p++){
                            //if j-th tree has edge connecting p and k
                            if(canBeReplaced[j][p][k]){
                                /*
                                 number to remove edge_k of tree_j should added by number of ways removing edge_p from tree_j-1
                                 because if we remove edge_p from tree_k-1, we can add it to tree_j and edge_k and edge_p connected,
                                 so tree_j is still a tree
                                 */
                                dp[j][k]=(dp[j][k]+dp[j-1][p])%mod;
                            }
                        }
                    }
                }
                /*
                 answer added by number of ways to remove edge i from tree_m(tree_0),
                 which means we looped back
                 */
                ans=(ans+dp[m][i])%mod;
            }
            return (int)ans;
        }
    };

    

Single Round Match 711 Round 1 – Division I, Level One ConsecutiveOnes by jonathanirvings

Since the number of bits are small, we can try for every position of consecutive ones in m.

Suppose we are considering that the consecutive ones in m is from i-th bit to (i+K-1)-th bit. Let’s say that x is an integer where the i-th bit to (i+K-1)-th bit are 1, and the rest of the bits are 0. There are two cases :

1. The first case is when n & x == x. In this case, we can simply consider n as the final answer.

2. The second case is when n & x ≠ x. In this case, we need to keep incrementing the value of n until n & x = x. But, doing that naively will not fit the time limit. The faster way is to compute the value of n | x and change all first i bits to 0. Consider this number as the final answer.
C++

    
    #include <bits/stdc++.h>
    using namespace std;
    
    class ConsecutiveOnes {
        public:
        long long get(long long n, int k) {
            long long answer = 1LL << 52;
            for (int i = 0; i < 50; ++i) {
                if (i + k > 50) {
                    break;
                }
                long long x = (1LL << (i + k)) - (1LL << i);
                if ((n & x) == x) {
                    answer = min(answer, n);
                } else {
                    answer = min(answer, (n | x) & ~((1LL << i) - 1));
                }
            }
            return answer;
        }
    };
    

Single Round Match 711 Round 1 – Division I, Level Two OrderedProduct by Shizhouxing

Let f[n] be the answer that the length of the sequence is exactly n.

For each factor p[i]^a[i] in X, we need to divide those a[i] prime factors to n integers in the sequence. According to combinatorial mathematics, we can easily find out that the number of ways are Binom(a[i] + n – 1, n – 1). (Here Binom(i, j) is a binomial coefficient. It stands for the number of different ways to choose j elements from i elements).

Multiply numbers of ways for each factor. We will get the number of ways to divide the factors for integers more than n. But we want the answer for exactly n integers. So we should subtract number of ways such that result is for less than n integers. If there are only i integers, we have Binom(n,i) ways to choose those integer. Then we need to just subtract f[i] * binom(n,i) from our temporary answer.

Finally, add up f[1],f[2],…f[a[0]+a[1]+…+a[n-1]], and we will get the answer to the problem.

C++

    
    #include <bits/stdc++.h>
    #define rep(i, a, b) for (int i = (a); i <= (b); ++i)
    
    using namespace std;
 
    typedef long long ll;
 
    const ll mo = 1000000007;
 
    ll binom[5000][5000];
 
    class OrderedProduct
    {
        public:
        int n;
        
        ll f[10000];
        
        int count(vector  a)
        {
            binom[0][0] = 1;
            rep(i, 1, 3000)
            {
                binom[i][0] = 1;
                rep(j, 1, i)
                {
                    binom[i][j] = (binom[i - 1][j] + binom[i - 1][j - 1]) % mo;
                }
            }
            
            n = 0;
            for (auto i:a) n += i;
            
            ll ans = 0;
            
            rep(i, 1, n)
            {
                f[i] = 1;
                for (auto j:a)
                {
                    f[i] = f[i] * binom[j + i - 1][i - 1] % mo;
                }
                rep(j, 1, i - 1)
                f[i] = (f[i] - binom[i][j] * f[j]) % mo;
                ans = (ans + f[i]) % mo;
            }
            
            return (ans + mo) % mo;
        }
        
    };
    

Single Round Match 711 Round 1 – Division I, Level Three TreeMoving

Let’s first think of a solution with lower efficiency.

For graph T(k) and T((k+1) mod m), if we remove e(i) from T(k) and add it to T((k+1) mod m), and if e(j) is removed from T((k+1) mod m), we can easily check whether this is valid. We only need to check whether T((k+1) mod m) is connected after that using union-find forest. Let g[k][i][j] be true if this is valid, otherwise make it false.

Assume the edge removed from T(0) is e(r), now we can come up with a DP algorithm:

 

dp[0][r] = 1

dp[i][j] = sum(dp[i-1][k] | g[i-1][k][j] == true) (0<i<m, 0<=j<=n-2)

ans[r] = sum(dp[m-1][j] | g[m-1][j][r] == true) (0<=j<=n-2)

The final answer is ans[0]+ans[1]+…+ans[n-2].

But, this dp algorithm is too slow. We can see the complexity for a single r is O(mn^2), so the total complexity is O(mn^3) which is not enough to get passed.

Observe the problem a little bit more. We can find that if we remove e(i) from T(k) and add it to T((k+1) mod m), and assume that edge connects u and v, then in T((k+1) mod m), the edge to remove must be on the path from u to v. Otherwise, the new tree can’t be connected.

So we can do DP transferring on the tree. Now let’s make each tree rooted. For T(i), when we are at dp[i][j], we can add dp[i][j] to all dp[i+1][k] where e(k) in T(i+1) is on the path between two nodes of e(j) in T(i). If we do that for each edge one by one, it’ll still be slow. However, we can add the dp value to only two nodes of e(j) temporarily, and subtract the double dp value from the LCA(Lease Common Ancestor) of those two nodes. After we finish work for all j, go through T(i+1) from bottom to top, and add the value on each node to its ancestor. After that, you can find that we’ve added dp values from each edge of T(i) to corresponding edges in T(i+1) with only O(n) complexity. Now the total complexity reduces to O(mn^2) which is already enough to get passed.

Code

#include 
#define rep(i, a, b) for (int i = (a); i = (b); --i)
#define REP(i, a, b) for (int i = (a); i < (b); ++i)
#define pb(x) push_back(x)
#define mp(x, y) make_pair(x, y)
#define clr(x) memset(x, 0, sizeof(x))
#define xx first
#define yy second

using namespace std;

typedef long long ll;
typedef pair pii;
const int inf = ~0U >> 1;

const int mo = 1000000007;
int m, n;

int X[500], f[500], dp[350][350], lca[500][500], tmp[500];

int find(int x) { return (f[x] == x) ? x : (f[x] = find(f[x])); }

void add(int &x, int y)
{
	x += y;
	x %= mo;
}

struct Graph
{
	vector E[500];
	int dep[500], fa[500], f[500][20], u[500], v[500], w[500], p[500], cnt, pre[500];
	
	void dfs(int u, int _f)
	{
		fa[u] = _f;
		f[u][0] = _f;
		dep[u] = dep[_f] + 1;
		if (dep[u] > 1) p[cnt++] = u;
		
		for (auto v:E[u])
			if (v.xx != _f)
			{
				pre[v.xx] = v.yy;
				dfs(v.xx, u);
			}
	}
	
	int LCA(int x, int y)
	{
		if (dep[x] = dep[y]) x = f[x][j];
		if (x == y) return x;
		drep(j, 18, 0)
			if (f[x][j] != f[y][j]) x = f[x][j], y = f[y][j];
		return f[x][0];
	}
	
	void prework()
	{
		rep(i, 1, n) E[i].clear();
		rep(i, 0, n - 2)
		{
			E[u[i]].pb(mp(v[i], i));
			E[v[i]].pb(mp(u[i], i));
		}
		cnt = 0;
		dfs(1, 0);
		rep(j, 1, 18) 
			rep(i, 1, n)
				f[i][j] = f[f[i][j - 1]][j - 1];
	}
} G[500];

class TreeMoving
{
public:

	int count(int _n, vector  roots, vector  a, vector  b, vector  c)
	{
		n = _n;
		
		int ans = 0;
		
		m = roots.size();
		rep(i, 0, m - 1)
		{
			X[0] = c[i];
			rep(k, 1, n - 2)
				X[k] = ((ll)a[i] * X[k - 1] + b[i]) % mo;
			
			rep(j, 0, n - 1) 
				G[i].E[j].clear();	
			rep(j, 0, n - 2)
			{
				G[i].u[j] = (roots[i] + j + 1) % n + 1;
				G[i].v[j] = (roots[i] + (X[j] % (j + 1))) % n + 1;
			}
			G[i].prework();
		}
		G[m] = G[0];
		
		rep(i, 0, m - 1)
		{
			int j = (i + 1) % m;
			rep(k, 0, n - 2)
				lca[i][k] = G[j].LCA(G[i].u[k], G[i].v[k]);
		}
		
		rep(fst, 0, n - 2)
		{
			clr(dp);
			dp[0][fst] = 1;
			
			rep(i, 0, m - 1)
			{
				clr(tmp);
				rep(j, 0, n - 2)
				{
					add(tmp[G[i].u[j]], dp[i][j]);
					add(tmp[G[i].v[j]], dp[i][j]);
					add(tmp[lca[i][j]], -dp[i][j] * 2 % mo);
				}
				
				drep(j, G[i + 1].cnt - 1, 0)
				{
					int cur = G[i + 1].p[j];
					add(dp[i + 1][G[i + 1].pre[cur]], tmp[cur]);
					tmp[G[i + 1].fa[cur]] += tmp[cur];
					tmp[G[i + 1].fa[cur]] %= mo;
				}
			}
			
			add(ans, dp[m][fst]);
		}
		
		return (ans + mo) % mo;
		
	}

};

The post Single Round Match 711 Editorials appeared first on Topcoder.

Previous Article
Cheat Sheet for Algorithm Competitions at Topcoder
Cheat Sheet for Algorithm Competitions at Topcoder

If you’re a newbie at Topcoder and just getting started in the Algorithm Competition, I’m sure the website ...

Next Article
Topcoder Connect 2.0 Release
Topcoder Connect 2.0 Release

Shortly before the end of last year, we announced a major update to Topcoder Connect. We had made it easier...