SRM 578

Match Summary

Round Overview
Discuss this match

The problem set of SRM 578 was prepared by snuke and tozangezan. The set was full of animals, who knows may be there is some secret behind this. Total 1403 topcoders participated in the contest, 636 in Division 1 and 681 in Division 2.

The Division 2 set was consisting of ad-hoc, mathematical and Dynamic Programming Problem, while Division 1 competitors faced mathematical, Dynamic Programming and a Graph Theory problem.

In Division 1, though tourist was the fastest timer to solve 250 and 500, but unfortunately his resubmission in 1000 and an unsuccesful challenge kept him out of top 5. Top 3 places was secured by tomek, rejudge and K.A.D.R (now just 1 point lacking from 3000 rating). In Division 2, in the first appearance Endagorion won the round by around 400 point ahead from the second place holder namonakiacc and lagged by just 1 point the third place holder makanbeling. Congratulations to all of you!

DeerInZooDivTwo

Used as: Division Two - Level One:

This problem can be solved by simulation. Note that, number of deer is at most 1000 and a deer can have 0, 1 or 2 antlers. So we can loop through the number of deers having 0 antler (cnt0) and the number of deers having 1 antler (cnt1), then the number of deers having 2 antlers is simply: (N - cnt0 - cnt1 = cnt2). Now we need to check if these counts satisfy the K constraints. Number of lost antlers = cnt0*2 + cnt1*1 + cnt2*0 (Since, deers having 0 antler lost 2 antlers and so on). So if this lost antlers count is equal to K we can say that, (cnt0, cnt1, cnt2) is a valid tupple. We just need to find maximum and minimum cnt2 among valid tupples. Note that, we are not asked to return -1 or any fancy value while the given input is impossible. So impossible case will not be given. But still it is better to check the constraints to convince yourself that impossible is impossible :) Our code runs in O(N²) and which is enough to run in time for N <= 1000.

Here is a code implementing above idea:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector < int > getminmax(int N, int K) {
  int cnt0, cnt1, cnt2;
  int max_ans = -1, min_ans = -1;
  vector < int > result;

  for (cnt0 = 0; cnt0 <= N; cnt0++)
    for (cnt1 = 0; cnt1 + cnt0 <= N; cnt1++) {
      cnt2 = N - cnt0 - cnt1;

      if (cnt0 * 2 + cnt1 * 1 + cnt2 * 0 != K) continue;

      if (max_ans == -1 || max_ans < cnt2) max_ans = cnt2;
      if (min_ans == -1 || min_ans > cnt2) min_ans = cnt2;
    }

  result.push_back(min_ans);
  result.push_back(max_ans);

  return result;
}

However, there is a mathematical solution as well. If we find K antlers lost then we have 2N - K (= remaining) antlers remaining. If we want to maximize number of deers having 2 antlers then it is floor( (2N - K)/2 ). If we want to minimize it then we give 1 antler to each of the deers. If all of the antlers is distributed (remaining <= N) then we wont have any deer with 2 antlers. If we have some left over antlers (remaining > N) then we will have to give 1 extra antlers to remaining - N deers. Following is the code implementing this idea:

1
2
3
4
5
6
7
8
9
10
11
12
13
vector < int > getminmax(int N, int K) {
  vector < int > result;

  int total = 2 * N;
  int remaining = total - K;

  if (remaining <= N) result.push_back(0);
  else result.push_back(remaining - N);

  result.push_back(remaining / 2);

  return result;
}

GooseInZooDivTwo

Used as: Division Two - Level Two:

( v-cell = cell containing the character v)

Observation: We can partition all the v-cells of the given grid in such a way that, two v-cells V₁ and V₂ will be in same partition if and only if there exists v-cellU₁, U₂, … U_k so that, distance(U_i , U _i+1 ) <= dist, distance(V₁ , U₁ ) <= dist and distance(U_k, V₂ ) <= dist.

Though formally written above observation may seem quite cryptic but the idea is quite simple and intuitive.

Suppose A is a v-cell. Now if there is a goose in A then other v-cells inside the dist range (distance is manhattan distance) is forced to have goose. Similarly these will force some other cells to have goose and it will go on until we dont find any new v-cell which is forced to have goose if there is a goose in cell A. Suppose we denote these set of cells by S. Now notice that, if we have a goose in any node in S, all the nodes are forced to have goose, and the cells which are not in S are not forced to have goose. Also, if we place a goose in a cell outside S, we are never forced to place goose in any cell of S. So this set S somewhat acts independently from rest of the grid. So if we can partition all the v-cells into k sets S₁, S₂, …, S_k then we can independently decide whether the set S_ihas goose or not, decision on S_i will not effect S_j. So if there are k such sets, then we have 2^k choices.

We can also imagine this force relationship as edge. A node in a connected component forces other nodes in the same component to have goose. And in reverse, if a node does not have goose then all other nodes in that component must not have goose.

For example, let the grid be like

1
2
3
vvv
  ...
  vvv

and dist = 1. Now if we partition the cells then we will get two partitions (two components), v-cells in first row in a set S₁ and v-cells in third row in another set S₂. Now we can
have four combinations:

• S₁ has goose, S₂ has goose;

• S₁ has goose, S₂ does not have goose;

• S₁ does not have goose, S₂ has goose;

• S₁ does not have goose, S₂ does not have goose.

(Note, S_i acts like unified object, one v-cell of S_i has goose means all of them has goose.)

So if we have k partitions we have 2^K options. But among them, there is no goose in one of them. (In the above example 4th option). So our answer is: 2^K - 1. (As our problem says there must be at least one goose in the grid)

Hence our solution reduces to finding the number of v-cell sets. I think you have already figured out from the second para above that, this is simply an application of any graph search algorithm (BFS/DFS). Here is a sample implementation:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#define ABS(X)((X) > 0 ? (X) : (-(X)))

vector < string > F;
int vis[55][55];
int d, R, C;

void DFS(int r, int c) {
  vis[r][c] = 1;

  int i, j;
  for (i = 0; i < R; i++)
    for (j = 0; j < C; j++)
      if (F[i][j] == 'v' && ABS(r - i) + ABS(c - j) <= d && vis[i][j] == 0) {
        DFS(i, j);
      }
}

int count(vector < string > field, int dist) {
  int i, j;
  int cnt;

  F = field;
  d = dist;

  memset(vis, 0, sizeof(vis));

  R = field.size();
  C = field[0].size();

  cnt = 0;
  for (i = 0; i < R; i++)
    for (j = 0; j < C; j++) {
      if (vis[i][j]) continue;
      if (F[i][j] == '.') continue;
      cnt++;
      DFS(i, j);
    }

  LL ans = 1;
  for (i = 1; i <= cnt; i++)
    ans = (ans * 2) % 1000000007;

  ans = (ans - 1 + 1000000007) % 1000000007;

  return ans;
}

WolfInZooDivTwo

Used as: Division Two - Level Three:

Let us reduce the solution from brute force to Dynamic Programming solution step by step.

• Idea 1: Let’s consider brute force program first. We generate all possible wolf-not wolf pattern and check if the pattern satisfies the interval constraints. We can imagine a pattern as 0-1 string. For N = 3 one possible pattern can be: 011 means: no wolf at 0th section and wolves at 1st and 2nd section. For N sections, there can be 2^N patterns. Since N is around 300, surely this method is not going to pass.

• Idea 2: Suppose we have an interval constraint [0, 1]. That is, we must have a wolf either at 0th or 1st or both. Now, say there are N sections, and we set 0 at 0th and 1st position of pattern while generating. Since first two positions are 0, we do not need to brute force through rest of the N-2 places, as it already violated one of the constraints. So to speed up our Idea 1, after putting a 1 or 0 in a place (putting 1 means there is a wolf, and 0 means no wolf as above) we can go through all the interval constraints and see if any of them contains only 0 (it is okay to have undecided section)

• Idea 3: Note, you do not need to go through all of the intervals. Suppose you have already decided 0/1 for all the sections from 0 to i-1. Now you are putting 0/1 at ith section. After deciding which one you are putting, you can just check all the intervals that end at ith section. So what you will check is, is there at least one 1 in the intervals that end at ith section?

• Idea 4: Is it really necessary to go through all the sections in the intervals that end at ith section? This is the crucial part of our solution. Observe that, you dont need to know about all the sections before ith section, it is enough to know last 1’s place. If you know it, then you can check if the intervals (ending at i) are satisfied or not.

So to sum up, you just need to know where are you now, and where did you put your last 1 before your current place. Now check all the intervals ending at your current position. If one of the intervals does not contain last 1, it means you can not put 0 at your current position and you must put 1. Otherwise you may put both 0 or 1 here. So our state is: (last, at) where last is the section index where we put last 1, and at is the index where we are currently. Now let’s worry about our initial call. We will certainly want to put 0/1 at 0th place, so our current position should be at 0, (at = 0). But what is our last? If we put last 1 at -1th section (an imaginary section) it would not have changed our answer. But it is certainly a problem to memorize our DP value (problem to index the array). One way is to consider 1-indexing instead of 0-indexing since in that case our imaginary station can be 0 and our indexing problem is solved.

Time complexity of the solution is: O(N*N + N*M). N*N for state (since last and at may have value ranging from 0 to N). N*M is a bit tricky. You can imagine it like this, for every value of last, suppose we go to all other values of at, and check all the intervals ending there. Or we may phrase it in another way, for every value of last, we check all intervals once, hence it is N*M. (N, M <= 300).

(Exercise: Can you solve it in: O(N*N + M)?)

Here is the code implementing the above idea:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
LL dp[350][350];
vector < int > V[350];
int N;

LL DP(int last, int at) {
  if (at > N) return 1;

  LL & ret = dp[last][at];
  if (ret != -1) return ret;

  ret = 0;

  int sz = V[at].size(), flag = 1, i;

  for (i = 0; i < sz; i++) {
    if (V[at][i] > last)
      flag = 0;
  }

  if (flag) ret = DP(last, at + 1);
  ret = (ret + DP(at, at + 1)) % 1000000007;

  return ret;
}

int count(int _N, vector < string > L, vector < string > R) {
  int i, a, b;
  string SL, SR;

  for (i = 1; i <= N; i++) V[i].clear();
  memset(dp, -1, sizeof(dp));

  SL = SR = "";
  for (i = 0; i < L.size(); i++) SL += L[i];
  for (i = 0; i < R.size(); i++) SR += R[i];

  istringstream iSL(SL);
  istringstream iSR(SR);

  while (iSL >> a) {
    iSR >> b;

    a++;
    b++;

    V[b].push_back(a);
  }

  N = _N;

  return DP(0, 1);
}

GooseInZooDivOne

Used as: Division One - Level One:

Before reading this, readers are suggested to go through the editorial of DIV 2 Medium which is an easier version of this problem.

The main difference between the easier version and this one is the total number of goose must be even. So now not only the number of sets is important but also the number of ***v-cell***s inside a set. But the parity of this number is only matter. If we replace a set with 3 elements with a set of 7 elements it does not change our answer. So suppose even be the number of sets having even number of elements and similarly odd.

Let odd set be a set having odd number of elements and similarly even set. And (n, r) = nCr(n, r).

Now, if we select an even set to have goose, it does not have effect on final parity of number of goose. So we can select them in X = 2^even ways (same logic as before).

Among odd sets, we need to choose even number of them, otherwise total parity will be odd. So total ways to choose odd elements = (odd, 0) + (odd, 2) + … (odd, odd - 1). Since, odd is at most 2500 we can easily precalculate the nCr value table using the recurrance (n, r) = (n - 1, r - 1) + (n - 1, r) and use it here. There is a mathematical formula though.

(odd, 0) + (odd, 2) + … (odd, odd - 1) = 2^{odd - 1}

(Proof in the comment, if you are interested.)

There is a special case, if odd = 0, then there is one way to select from odd sets, that is select none, Y = 1. Otherwise, Y = 2^{odd - 1}.

So our final answer is: X*Y. And of course we must not forget to subtract the solution having no goose in board.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
vector < string > F;
int vis[55][55];
int R, C, d;

int DFS(int r, int c) {
  int cnt = 1;

  vis[r][c] = 1;
  int i, j;
  for (i = 0; i < R; i++)
    for (j = 0; j < C; j++)
      if (F[i][j] == 'v' && ABS(r - i) + ABS(c - j) <= d && vis[i][j] == 0) {
        cnt += DFS(i, j);
      }

  return cnt;
}

int count(vector < string > field, int dist) {
  int i, j;
  int cnt, temp, odd, even;

  F = field;
  d = dist;

  memset(vis, 0, sizeof(vis));

  R = field.size();
  C = field[0].size();

  odd = even = 0;
  for (i = 0; i < R; i++)
    for (j = 0; j < C; j++) {
      if (vis[i][j]) continue;
      if (F[i][j] == '.') continue;

      temp = DFS(i, j);

      if (temp % 2) odd++;
      else even++;
    }

  if (even == 0 && odd == 0) return 0;

  cnt = even;
  if (odd) cnt += odd - 1;

  LL ans = 1;
  for (i = 1; i <= cnt; i++)
    ans = (ans * 2) % 1000000007;

  ans = (ans - 1 + 1000000007) % 1000000007;

  return ans;
}

WolfInZooDivOne

Used as: Division One - Level Two:

Before reading this, readers may go through the editorial of DIV 2 Hard which is an easier version of this problem.

In DIV 2 Hard, we had to have at least one wolf in each segment. But now we can not have more than 2 wolves in each segment. So if you are planning to keep last two wolves and current position in state then no, not possible. What about keeping three wolves then? Okay, yes that will work, when we are at a position we will check if all of these three are inside any interval ending at current position. But in such case order is: O(N^3 * M) which is a bit risky for N, M <= 300 range. So let’s go back to drawing board.

Let us imagine we are going from left to right and will consider option to place a wolf. Suppose we are placing a wolf at current position (6th cell in the diagram below).

Then we can ignore the next three cells. And again start our usual process (whether to place wolf or not) from the arrow signed cell. Note, we are certain that we can not place any wolf in these three cells. Why? Because there is an interval which already covered two wolves and we can not place any more wolf until these interval ranges are over.

So our solution is: we are going from left to right, if we place a new wolf, we will go through intervals and see which intervals got newly placed wolf and the wolf we placed just before this one. We can safely jump over them. So what we need to keep track is only the last wolf we placed before this current position and our current position as state (last, at). If we do not place wolf at our current place at then we simply call (last, at + 1). But if we place a wolf at at then, we go through all the intervals and find the intervals which has these two wolves inside, and since we are jumping over all these intervals, we are only interested in the interval which has rightmost right end. Note, it is sufficient to check against the wolves at last and at only, because according to our process we have already satisfied all the intervals ending before at. Note that, the time complexity is: O(N*N*M) which is managable for the given bound of N, M <= 300.

(Exercise: Can you solve it in O(N*M)?)

Here is the code implementing above idea:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
typedef pair < int, int > PII;

vector < PII > V;
int N;
int dp[305][305];

int DP(int last, int at) {
  if (at > N) return 1;

  int & ret = dp[last][at];
  if (ret != -1) return ret;

  ret = 0;

  //do not place a wolf, it does not violate any rule
  ret = DP(last, at + 1);

  //place a wolf, now progress 'at' to such a place so that, it does not have any scope to break any constraint.
  int sz, end, i;

  sz = V.size();
  end = at;
  for (i = 0; i < sz; i++)
    if (V[i].first <= last && at <= V[i].second) {
      if (end < V[i].second)
        end = V[i].second;
    }

  ret = (ret + DP(at, end + 1)) % 1000000007;

  return ret;
}

int count(int _N, vector < string > L, vector < string > R) {
  int i, a, b;
  string SL, SR;

  N = _N;
  memset(dp, -1, sizeof(dp));

  SL = "";
  for (i = 0; i < L.size(); i++) SL += L[i];
  SR = "";
  for (i = 0; i < R.size(); i++) SR += R[i];

  istringstream iSL(SL), iSR(SR);
  V.clear();
  while (iSL >> a) {
    iSR >> b;
    a++, b++;
    V.push_back(PII(a, b));
  }

  return DP(0, 1);
}

DeerInZooDivOne

Used as: Division One - Level Three:

Let us first solve two easier versions of this problem.

Easier Problem 1

Problem 1: Suppose there are two rooted trees, U and V, rooted at u and v respectively. Find out the maximum sized subtree rooted at u and v so that they are isomorphic. Let, this maximum size be w(u, v).

Solution of Problem 1: Let, u₁, u₂ … u_p are p children of u and v₁, v₂ … v_q are q children of v. We can find w(u_i, v_j)for 1<=i<=p and 1<=j<=q recursively. Now to find w(u, v) what we have to do is, pair one of u_i with one of v_j so that total pairing cost is maximized. Let me give an example.

Here, w(u₁, v₁) means, maximal isomorphic subtree rooted at u₁ and v₁ has size 2. And so on for other w(u_i, v_j).

So to maximize w(u, v) we will want to match u_is and v_js in such a way that sum of the matching is maximum. In this example it is: w(u₂, v₂) + w(u₁, v₃) = 9. And we also have the root u and v. So total maximum cost is 10. This will be the value of w(u, v). This matching problem is a classical problem and can be solved by Weighted Bipartite Matching(WBPM) or by Mincost flow algorithm.Now let us proceed to the second easier version of the problem.

Easier Problem 2

Problem 2: Suppose there are two trees, U and V. Find out the maximum sized subtree of U and V so that they are isomorphic.

Solution of Problem 2: If we know the solution of Problem 1, we can easily solve Problem 2. We simply select one node from tree U, another from tree V and make rooted tree considering selected nodes as root. Now we run our solution of Problem 1 on these rooted trees. In this way if we run for all pair of nodes from these two trees, and take their maximum, we will get maximum size of isomorphic subtree of U and V which solves our Problem 2.

Back to original Problem

Now we are ready to come back to our problem. Our problem asks, we have to find two vertex disjoint maximum sized isomorphic subtree in the given tree. To solve it, we can delete every edge of the given tree and run our solution to Problem 2 to solve our original probelm.

Since we are solving the entire problem recursively, we will face same Problem 2 several times. So to speed up, we can store the answer to subproblems.

The implementation of the above idea is given below. Here, weighted bipartite matching algorithm is used but the details of the matching algorithm is removed to present the main part of the solution.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
WeightedBipartiteMaxMatching G;

vector < int > V[55];
int n;
int color[55];
int f[52][52][52][52];

void dfs(int u, int parent, int col) {
  int i, sz, v;

  color[u] = col;
  sz = V[u].size();
  for (i = 0; i < sz; i++) {
    v = V[u][i];
    if (v == parent) continue;
    dfs(v, u, col);
  }
}

int check(int a, int pa, int b, int pb) {
  int & ret = f[a][pa][b][pb];
  if (ret != -1) return ret;

  ret = 1;

  int sza, szb, i, j, x, y;

  sza = V[a].size();
  szb = V[b].size();

  x = 0;
  for (i = 0; i < sza; i++)
    if (V[a][i] != pa) x++;
  y = 0;
  for (i = 0; i < szb; i++)
    if (V[b][i] != pb) y++;

  for (i = 0, x = 0; i < sza; i++)
    if (V[a][i] != pa) {
      x++;

      for (j = 0, y = 0; j < szb; j++)
        if (V[b][j] != pb) {
          y++;
          check(V[a][i], a, V[b][j], b);
        }
    }

  G.setN(MAX(x, y));
  G.clear();
  for (i = 0, x = 0; i < sza; i++)
    if (V[a][i] != pa) {
      x++;

      for (j = 0, y = 0; j < szb; j++)
        if (V[b][j] != pb) {
          y++;
          G.add_edge(x, y, check(V[a][i], a, V[b][j], b));
        }
    }

  return ret = 1 + G.WBPM();
}

int calc() {
  int i, j, now, ret = 0;
  int x, y;

  for (i = 1; i <= n; i++)
    for (j = 1; j <= n; j++)
      f[i][0][j][0] = -1;

  for (i = 1; i <= n; i++)
    for (j = 0; j < V[i].size(); j++)
      for (x = 1; x <= n; x++)
        for (y = 0; y < V[x].size(); y++) {
          f[i][V[i][j]][x][V[x][y]] = -1;
        }

  //     memset(f, -1, sizeof(f)); <- it makes runtime 1.997s. Above reduces to 291ms

  for (i = 1; i <= n; i++)
    if (color[i] == 1)
      for (j = 1; j <= n; j++)
        if (color[j] == 2) {
          now = check(i, 0, j, 0);
          ret = MAX(ret, now);
        }

  return ret;
}

int getmax(vector < int > a, vector < int > b) {
  int i, j, now, ans = 0;

  n = a.size() + 1;

  for (i = 0; i < n - 1; i++) a[i]++, b[i]++;

  for (i = 0; i < n - 1; i++) {
    for (j = 1; j <= n; j++)
      V[j].clear();

    for (j = 0; j < n - 1; j++)
      if (j != i) {
        V[a[j]].push_back(b[j]);
        V[b[j]].push_back(a[j]);
      }

    dfs(a[i], b[i], 1);
    dfs(b[i], a[i], 2);

    now = calc();
    ans = MAX(ans, now);
  }

  return ans;
}

You may follow stjepan’s implementationin the match or cgy4ever’s solution at practice room to see a solution by mincost flow.