SRM 682

Match Summary

Round Overview
Discuss this match

DNASequence

This is mostly an implementation problem. We can try all possible substrings of the input string and check if each character is A,G,C or T.

We can also do the following: Instead of trying all substrings, we can just pick a starting index and increment the length until we meet the end of the string or a character that is not A, G, C or T:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int longestDNASequence(string sequence) {
  set < char > valid = {
    'A',
    'C',
    'G',
    'T'
  };
  int n = sequence.size();
  int res = 0;
  for (int i = 0; i < n; i++) {
    int t = 0;
    while ((i + t < n) && (valid.count(sequence[i + t]) == 1)) {
      t++;
    }
    res = std::max(res, t);

  }
  return res;
}

TopBiologist

The main thing to notice in this problem is that the result won’t be very long. The sequence has at most 2000 characters. If the result has 5 characters, it means that the sequence contains all 4^4 substrings of 4 characters possible. 4^4 = 256 and if we imagine 256 strings of 4 characters each, that is 1024 characters in total. Already quite high. So let’s find a formal upper bound for the length of the result.

We need to find a length s, such that it is completely impossible for a string of length 2000 to contain all possible strings of length s as a substring. Keep in mind that the substrings can overlap. So for example “AAACCC” contains AAACC and AACCC as substrings. But even if we could find a perfect way to put all the substrings in a single string a way that they overlap perfectly, each new substring we add will add at least 1 new character to the string. There are 4^6 = 4096 substrings of length 6, even if after adding the first substring with 6 characters and each of the remaining 4095 substrings added a single character, it would still need 6+4095 characters. So we can be certain that the substring we are looking for will have at most 6 characters. So using 6 as the limit is a safe bet. In fact, the system tests do include a string that contains all strings of length 5 as a substring.

Because of the 6 characters limit, there are 4 + 4^2 + 4^3 + 4^4 + 4^5 + 4^6 = 5460 candidate substrings we need to try, we can use backtracking (for example) to find all of these strings and test each of them against the string in O(|L|) time until we find one that isn’t a substring (The test would be the exact same we used in division 2 easy). 5460 * 2000 is not a big amount of operations and we can do all of this well under 2 seconds.

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
// We can be pretty certain that the result's length is at most 6:

string sequence, result;
char sol[6] = {
  '?',
  '?',
  '?',
  '?',
  '?',
  '?'
};

// backtrack to find all possible strings with length < 7, until we find one
// that isn't a substring of sequence:
void backtrack(int p) {
  if (p < result.size()) { // if p is already large no reason to continue

    // check that the string is not a substring:
    bool found = false;
    for (int i = 0; i < sequence.size(); i++) {
      int j = 0;
      while ((j < p) && (i + j < sequence.size()) && (sequence[i + j] == sol[j])) {
        j++;
      }
      if (j == p) {
        found = true;
      }
    }
    if (!found) {
      result = "";
      for (int j = 0; j < p; j++) {
        result += sol[j];
      }
    }
    // add a new character, keep backtracking.
    for (char ch: {
        'A',
        'G',
        'C',
        'T'
      }) {
      sol[p] = ch;
      backtrack(p + 1);
    }
  }
}

string findShortestNewSequence(string sequence) {
  this - > sequence = sequence;
  result = string(7, '?'); //start the result as a length 7 string
  backtrack(0);
  return result;
}

FriendlyRobot

This is a interesting dynamic programming problem. What we want to calculate is the maximum number of times the robot can return to the initial location. Note that after the first time the robot returns to the initial location, it would be after some instruction j and after doing “need” modifications. Then we can use a smaller version of the problem: Starting with instruction j+1 and assuming that the robot is once again at the starting location (0,0), what is the maximum number of times it will return to this location (using only instructions higher than or equal to j+1) if the limit for changes is: “changesAllowed” - “need”.

So if we define a function f(s, c) that finds the maximum number of times the robot returns to the initial location, for the sequence of instructions starting at instruction # s and if the maximum number of modifications is c. Then we find that, in order for the robot to return to the location after location j, we need a total of “need” modifications. The optimal number of returns if j is the earliest time the robot returns to the initial location is: 1 + f(j+1, c - “need”). We can try all values of j until we find the one with the maximum 1 + f(j+1, c - “need”) result.

What we need now is to find a way to find the minimum number of instruction modifications for instructions between s and j so that the robot reaches the initial location after execution instruction j. This objective is not always possible. As a first step, simulate the instructions, the robot will reach a new position (x,y) after using those instructions. The horizontal distance between 0 and x is |x| and the vertical distance |y|. Modifying a single instruction has plenty of potential: Imagine x and y are both positive, this means we should modify only up or right instructions:

• If we modify a right instruction into a left instruction, x is reduced by 2.

• If we modify a right instruction into a down instruction, x is reduced by 1 and y is reduced by 1.

• If we modify an up instruction into a down instruction, y is reduced by 2.

• If we modify an up instruction into a left instruction, x is reduced by 1 and y is reduced by 1.

Each modification reduces either both the horizontal and vertical distances by 1 or one of them by 2. This works the same in all cases. So if the distance sum is |x|+|y|, each modification will reduce it to |x|+|y|-2. This means that if we use “need” instructions, the distance sum can become |x|+|y|-2"need". So the number of modifications we need is : (|x|+|y|) / 2 and this only works when |x|+|y| is even. If |x|+|y| is odd, nothing we can do will fix it. Note that if (x,y) is already (0,0), the number of modifications is 0. With this number of modifications, we can complete the dynamic programming:

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
int findMaximumReturns(string instructions, int changesAllowed) {
  int n = instructions.size();
  int f[301][301];

  for (int c = 0; c <= changesAllowed; c++) {
    f[n][c] = 0;
  }

  for (int s = n - 1; s >= 0; s--) {
    for (int c = 0; c <= changesAllowed; c++) {
      f[s][c] = 0;
      // simulate:
      int x = 0, y = 0;
      for (int i = s; i < n; i++) {
        switch (instructions[i]) {
        case 'L':
          x--;
          break;
        case 'R':
          x++;
          break;
        case 'U':
          y++;
          break;
        case 'D':
          y--;
          break;
        }
        //  |x| + |y| must be even:
        if ((abs(x) + abs(y)) % 2 == 0) {
          // the number of needed modifications:
          int need = (abs(x) + abs(y)) / 2;
          if (need <= c) {
            f[s][c] = std::max(f[s][c], 1 + f[i + 1][c - need]);
          }
        }
      }
    }
  }

  return f[0][changesAllowed];
}

SmilesTheFriendshipUnicorn

There’s a variety of approaches to this level. An idea is to first start with a simpler problem: Figure out a way to find a path of 4 distinct vertices, we’ll name them a -> b -> c -> d. Once we find such a path, we just need to find an extra vertex i, connected to either extreme. Assuming we enumerate all possible 4-length simple paths, we can just look for i connected to a, it needs to be the first i that is distinct to a, b, c and d, this means that if we iterate through the vertices adjacent to a, we will need to try at most 5 such vertices. So the number of steps needed will be equal to at most 5 multiplied by the number of simple paths of length 4.

Simple paths of length 4

A simple path of length 4 consists of 3 edges: a -> b, b -> c and c -> d. There are at most M = 2000 edges in the graph, so one idea is to try all the O(M^2) possible pairs of edges ( a -> b, c -> d), for each of them, confirm that (b -> c) also exists, this can be done in O(1) if we precalculated an adjacency matrix. Then we can confirm we have a line a -> b -> c -> d , the last step is to confirm that all of the vertices are distinct. This is an O(M^2) approach to find simple paths of length 4. So we find the fifth vertex in at most 5 steps which means that the approach is O(M ^ 2).

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
string hasFriendshipChain(int N, vector < int > A, vector < int > B) {

  vector < vector < bool >> adj(N, vector < bool > (N));
  vector < vector < int >> g(N);

  set < pair < int, int > > edges;
  int M = A.size();
  for (int i = 0; i < M; i++) {
    edges.insert({
      A[i],
      B[i]
    });
    edges.insert({
      B[i],
      A[i]
    });
    adj[A[i]][B[i]] = true;
    adj[B[i]][A[i]] = true;
    g[A[i]].push_back(B[i]);
    g[B[i]].push_back(A[i]);
  }

  // pairs of edges:
  for (auto x: edges) {
    for (auto y: edges) {
      int a = x.first, b = x.second;
      int c = y.first, d = y.second;

      if (adj[b][c]) {
        // a - b - c - d. exists
        if (
          (a != b && a != c && a != d) &&
          (b != c && b != d) &&
          (c != d)
        ) {
          for (int i: g[a]) {
            if (i != a && i != b && i != c && i != d) {
              return "Yay!";
            }
          }
        }
      }
    }
  }
  return ":(";
}

SuccessfulMerger

Mostly a tree

We can see the road network as a graph. Each road is an edge between two vertices (cities). We have exactly n edges in the graph and the graph is connected.

There is a rule that dictates that if a graph has exactly n-1 edges and is connected, then the graph is a tree. So we can assume that the input graph is a tree with an added edge. In this problem, this extra edge might even be a repeated edge between two cities or a loop. When adding this extra edge, we create a single cycle in a graph that didn’t have any cycles before that edge was added. Because loops and repeated edges are allowed, the cycle can be composed of a single vertex, or two vertices. The following are some examples of what we can expect as an input:

A valid capital

How would a proper final graph look like? All simple paths between any two of the remaining cities must go through the capital city, which can be any city we pick. The answer is that all final graphs must have a star structure. All cities who are not the city connected directly to the city and that should be their only edge:

It must be one of these stars, because if the arms contained more than one city , then the simple paths would not need to go through the capital.

Remember the initial tree might have one cycle and there is an interesting way to have a valid graph that contains a cycle. It must be a two-vertices cycle, acting as yet another arm for the star structure.

What we can avoid to remove

A merger between two cities is the same as removing one city and then all the edges connecting the city become new edges connecting pairs of cities that were previously connected by the city itself. We are looking to the minimum number of cities to remove.

There is one city that we shouldn’t remove : The capital. There are also some cities that we should never need to remove: Those who can be the arms at the end. Cities with degree 1.

There is a special case, sometimes, it is possible to also leave two of the cities that belonged to the cycle. Pick one of the cities in the cycle as the capital and leave another one on. The condition is that this other city should have no edges to cities outside the cycle. This allows us to have a whole arm composed of two repeated edges - a cycle of two.

In short, there are 3 kinds of cities that we can leave in the final graph:

• Any city with degree 1.

• A city that belongs to the original cycle and is not adjacent to any city that doesn’t.

• The capital. To minimize the number of removed cities, we should pick a capital distinct to the two previous kinds of cities.

This allows us to solve the problem using a simple algorithm. We need to detect which cites belong to the cycle. This can be done with a Depth-first search (DFS). Then count the number of cities k with degree 1 and check if there is any city in the cycle that is only adjacent to other cities in the cycle. The minimum number of removed cities is: n - k - 1 or n - k - 2 if we find that special cycle city.

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
vector < list < int >> g;
vector < int > dfs_color;
vector < int > parent;

list < int > cycle_members;

void dfs(int x, int par) {
  if (dfs_color[x] == 0) {
    dfs_color[x] = 2;
    parent[x] = par;
    int c = 0;
    for (int y: g[x]) {
      if (y == par) {
        c++;
        if (c == 2) {
          // the cycle is a duplicate edge
          // we need to handle this in a special way because of
          // how the graph is saved, we ignore the edge between
          // x and the parent when iterating, but if there's
          // two of those edges, we can't ignore the other one.
          cycle_members.push_back(x);
          cycle_members.push_back(y);
        }
      } else {
        dfs(y, x);
      }
    }
    dfs_color[x] = 1;
  } else if (dfs_color[x] == 2) {
    //we found the cycle.
    int y = par;
    while (true) {
      cycle_members.push_back(y);
      if (y == x) {
        break;
      }
      y = parent[y];
    }
  }
}

int minimumMergers(vector < int > road) {
  int N = road.size();
  dfs_color.resize(N);
  parent.resize(N);
  g.resize(N);
  // prepare the graph
  for (int i = 0; i < N; i++) {
    g[i].push_back(road[i]);
    g[road[i]].push_back(i);
  }
  dfs(0, -1);

  // initially we would assume to delete all vertices minus the capital.
  int res = N - 1;
  for (int i = 0; i < N; i++) {
    if (g[i].size() == 1) {
      // if degree is 1, we are allowed not to delete this one 
      res--;
    }
  }
  for (int x: cycle_members) {
    bool good = true;
    for (int y: g[x]) {
      if (count(cycle_members.begin(), cycle_members.end(), y) == 0) {
        good = false;
      }
    }
    if (good) {
      // one of the vertices in the cycle is only connected to other
      // vertices in the cycle, we can leave it as well. But at most one
      res--;
      break;
    }
  }

  return res;
}