SRM 684

Match Summary

Round Overview
Discuss this match

Istr

We can remove at most k letters. The question we need to answer is, for each of the removals, what is the best letter to remove? The value formula is equal to the sum of the number of times each distinct character appears in the input squared. For example in string “xxxxxyyyy”, letter “x” appears 5 times and letter “y” appears 4 times, the value is 5^2 + 4^2 = 25 + 16 = 31. What is interesting about squaring is that higher numbers contribute a lot more to the score than smaller numbers. If we remove an “x”, we reduce the value by 5, whereas if we remove a “y”, the score drops by 4, so “xxxxyyyy” has a smaller value than “xxxxxyyy” ( 4^2 + 4^2 = 32 versus 5^2 + 3^2 = 34).

In short, for each of the k steps, pick the letter that’s repeated the most and delete it. This will ensure that the final value of the string is as small as possible.

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
int count(string s, int k) {
  // for each of the k steps:
  for (int i = 0; i < k; i++) {
    // pick the letter that repeats the most in s:
    char best_ch = '?';
    int best_count = 0;
    for (char ch = 'a'; ch <= 'z'; ch++) { // for each letter ch:
      int c = std::count(s.begin(), s.end(), ch); // count occurrences of ch
      if (c > best_count) {
        // remember the best
        best_count = c;
        best_ch = ch;
      }
    }
    // erase one instance of best_ch
    s.erase(find(s.begin(), s.end(), best_ch));
  }

  // calculate the value:
  int value = 0;
  for (char ch = 'a'; ch <= 'z'; ch++) {
    int c = std::count(s.begin(), s.end(), ch);
    value += c * c;
  }

  return value;
}

DivFreed2

We can solve this using a recurrence relation. Imagine we decide that the first element in the array is i. Then the the second element can be any integer between 1 and k, inclusive that is not a divisor of i. Let’s define a function f(t, i) that returns the number of good arrays of length t that start with i:

• We know that the first element of the array is i.

• We just need to count the number of ways to fill the remaining t-1 elements. This is equal to the sum of all f(j, t-1) where j is not a divisor of i.

As a base case, when t = 1, then there is only one element in the array and it’s already known to be i, so f(1, i) is 1 for all valid i.

And the final solution is equal to the sum of f(n, i) for all valid i.

We can use iterative dynamic programming to implement this solution. It would look like this:

1
2
3
4
5
6
7
8
9
for i = 1 to k:
  f[1][i] = 1

for t = 1 to n:
  for i = 1 to k:
  f[t][i] = 0
for j = 1 to k:
  if j is not a divisor of i:
  f[t][i] = f[t][i] + f[t - 1][j]

Optimizing it out

The pseudocode above solves the problem, but is too slow in its current state. The complexity is O(n k^2), note that n <= 10, k <= 100000.

Note that numbers tend to have few divisors. The maximum number of divisors in a number smaller than 100000 is 29 (83160 has 29 divisors). We can calculate the sum of all f[t-1][j] and then subtract the f[t-1][j] for j that are divisors. This requires us to do two things:

• We need the sum of all f[t-1][j], this can be done in O(k) for each t.

• We need to quickly precalculate all the divisors of all numbers between 1 and k and save them in a table. An approach is to use a sieve. For each integer i, then we know that 2i, 3i, 4i, … are multiples of i, so i is a divisor of those numbers. For i = 1, this needs O(k) steps, but for i = 50000, it will need only one step (only 2i is smaller than or equal to k). The number of steps is exactly equal to the sum of the number of divisors for each integer between 1 and k, which even if we assume that each number had 29 divisors (which is a very exaggerated estimation) it will take only 2900000 steps in total.

Problems that ask you to return the result modulo 1,000,000,007 (or a similar number) usually do so to allow us to solve problems that have large results without actually using those large numbers in calculations. We can handle these numbers with modular arithmetic. Read this recipe for more info.

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
const int MOD = 1000000007;

int count(int n, int k) {
  // A sieve to find the divisors of each integer:
  vector < vector < int > > divisors(k + 1);

  for (int i = 1; i <= k; i++) {
    for (int j = 2 * i; j <= k; j += i) {
      divisors[j].push_back(i);
    }
  }
  // The dynamic programming:
  vector < vector < long > > f(n + 1, vector < long > (k + 1));

  // base case, for t = 1, there is only one array that starts with each i
  for (int i = 1; i <= k; i++) {
    f[1][i] = 1;
  }

  for (int t = 2; t <= n; t++) {
    // the sum for the previous t:
    long sum = 0;
    for (int i = 1; i <= k; i++) {
      sum += f[t - 1][i];
    }
    sum %= MOD;

    // subtract the results for each divisor
    for (int i = 1; i <= k; i++) {
      f[t][i] = sum;
      for (int d: divisors[i]) {
        f[t][i] = (f[t][i] + MOD - f[t - 1][d]) % MOD;
      }
    }
  }

  // All possible starting values for the arrays
  long sum = 0;
  for (int i = 1; i <= k; i++) {
    sum += f[n][i];
  }
  sum %= MOD;

  return sum;
}

Autohamil

We start the process at state 0. We can choose either 1 or 0 for the first character in the string. The state 0 has two transitions one for when the character is 1 and another for when it is 0. Note how we can just make the problem about deciding which transition to use at any time. If we place a 0, it will use the first transition, else the second transition. This is true for any string position. Pick 0 or 1 for the character in that position and you will be deciding to move from the current state (vertex) to one of the two states connected to it.

We can rewrite the problem as the following: We have a directed graph where every vertex has out-degree 2 . (But loops and duplicated edges are allowed). Find if there exists a path starting at vertex (state) 0 that visits all the vertices in the graph. We can see a path as a selection of edges to pick to move from each vertex in the path to the next one. And when picking a string to be processed by the automata, we can pick 0 or 1 for each character to pick the path we chose. Note that this problem is not the same as finding a Hamiltonian Path, because the path might visit the same vertex multiple times. This makes the problem easier to do.

Coming back

What makes this task easier than finding a Hamiltonian path is the ability to come back to a vertex after visiting some other vertices. This means that we can use cycles in the graph to our advantage. If there is any cycle in the graph, then we can assume that, as long as a vertex in the cycle can be visited by a path, so can all vertices in the cycles (just visit the cycle and return to the initial vertex).

This is where the concept of strongly connected components (SCC) is useful. We can find the strongly connected components and reduce the graph to the acyclic graph of strongly connected components. A strongly connected component will contain vertex 0. This is the starting SCC. We want to find if it is possible to find a path that visits all the SCCs in the graph starting at SCC 0. This is really the same problem that we started with, but with the added benefit that there are no cycles in the graph. If there was any cycle in the graph, then all the vertices in that cycle were reduced to be part of the same SCC.

When the graph is acyclic

In the above image, the Directed Acyclic DAG that results of taking the SCCs shows that it is impossible to visit all the vertices in a single path. You start at component 0 which has two directed edges, one to component 1 and another to component 2. If you choose to go to component 1, you will be unable to go to component 2 and vice versa.

We can infer two conditions.

• All components must be reachable from component 0.

• There needs to be a path connecting all components. This time cycles are not allowed, or more accurately, are not possible.

Consider the following example:

There is a path that joins all the components, but there are multiple ways to go from the top component to the bottom one. If you pick the direct ones, you will not be able to go to the middle components. The solution to avoid issues like this is to use the topological sort of the graph. Then always try to visit the top-most component that has not visited yet. If you cannot find a path with this method, then it is impossible to do so. The following is an example of how complicated and long the resulting code is:

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
string check(vector < int > z0, vector < int > z1) {
  // create the graph from input, adjacency matrix:
  int n = z0.size();
  vector < vector < int > > a(n, vector < int > (n, 0));

  for (int i = 0; i < n; i++) {
    a[i][z0[i]] = 1;
    a[i][z1[i]] = 1;
  }

  // Floyd-Warshall to quickly get which vertices are reachable from which starting points:
  auto d = a;
  for (int k = 0; k < n; k++) {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        d[i][j] = (d[i][j] || (d[i][k] && d[k][j]));
      }
    }
  }

  // if a vertex u is reachable from vertex v and vice versa, then they
  // belong to the same SCC, use that information to build a SCC graph:
  vector < int > node_compo(n, -1);
  int t = 0;
  for (int i = 0; i < n; i++) {
    if (node_compo[i] == -1) {
      node_compo[i] = t++;
      for (int j = 0; j < n; j++) {
        if (d[i][j] && d[j][i]) {
          node_compo[j] = node_compo[i];
        }
      }
    }
  }

  vector < set < int > > g(t), rg(t);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      int u = node_compo[i];
      int v = node_compo[j];
      if ((u != v) && a[i][j]) {
        g[u].insert(v);
        rg[v].insert(u);
      }
    }
  }

  // topsort the SCC graph:
  vector < int > top_sort(t);
  vector < bool > added(t, false);
  for (int i = 0; i < t; i++) {
    int pick = -1;
    for (int j = 0; j < t; j++) {
      if (!added[j]) {
        int cnt = 0;
        for (int k: rg[j]) {
          if (!added[k]) {
            cnt++;
          }
        }
        if (cnt == 0) {
          pick = j;
        }
      }
    }
    if (pick == -1) {
      return "Does not exist";
    } else {
      top_sort[i] = pick;
      added[pick] = true;
      cout << "[";
      for (int i = 0; i < n; i++) {
        if (node_compo[i] == pick) {
          cout << i << " ";
        }
      }
      cout << "]" << endl;
    }
  }

  if (top_sort[0] != 0) {
    return "Does not exist";
  }
  // check the path:
  for (int i = 1; i < t; i++) {
    if (g[top_sort[i - 1]].count(top_sort[i]) == 0) {
      return "Does not exist";
    }
  }
  return "Exists";
}

A simpler way

There is a much simpler way to solve this problem. For each pair of components, they need to be connected in either direction. So given two components u and v, there needs to be a path from u to v OR from v to u. This condition is necessary and sufficient. The only way in which we would be unable to build a path if this condition was true is if there was any cycle between the components, but if there was a cycle, they wouldn’t be separate SCCs.

This can be implemented without building the SCCs graph. All vertices must be reachable from vertex 0. And all pairs of vertices must be connected in one direction or the other.

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
string check(vector < int > z0, vector < int > z1) {
  // create the graph from input, adjacency matrix:
  int n = z0.size();
  vector < vector < int > > a(n, vector < int > (n, 0));

  for (int i = 0; i < n; i++) {
    a[i][z0[i]] = 1;
    a[i][z1[i]] = 1;
  }

  // Floyd-Warshall to quickly get which vertices are reachable from which starting points:
  auto d = a;
  for (int k = 0; k < n; k++) {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        d[i][j] = (d[i][j] || (d[i][k] && d[k][j]));
      }
    }
  }
  for (int i = 0; i < n; i++) {
    if (i != 0 && !d[0][i]) {
      return "Does not exist";
    }
    for (int j = 0; j < n; j++) {
      if ((i != j) && !d[i][j] && !d[j][i]) {

        return "Does not exist";
      }
    }
  }
  return "Exists";
}

CliqueParty

k-smoothness and the minimum/maximum elements

The condition for a set to be k-smooth is complicated in its current state, you need to consider all pairs of elements in the set. It really helps to see the condition in a different way. Consider it in terms of the minimum and maximum elements of the set. Let min(S) be the minimum element and max(S) the maximum: Since they are elements of the set then max(S) <= k min(S) must be true. What is interesting is that this condition is not only necessary, it is sufficient. After all, k-smooth just means that the distance between any two elements of the set is never too high and if the distance between the minimum element and the maximum element is not too high then the other distances will also be small enough (all other distances will be even smaller).

Minimum and maximum differences

The problem requires us to pick a subset S, then for the subset we find all pair-wise distances between distinct elements and add them to a new set D that must be k-smooth. From the previous section comes that if the minimum distance in D is m then the maximum distance cannot exceed km.

There are only O(n^2) possible minimum distances m when picking elements for D. We can try all of them. Then we have to solve the question: What is the maximum number of elements we can pick to add to D so that the minimum distance between two of them is at least m and the maximum distance is at most km? If this condition is true, then D will be k-smooth.

Since the maximum difference cannot exceed km, this means that we have a constraint. If the minimum element of D is a[r], then no element can be larger than a[r] + km. We can try all candidates for the minimum element a[r]. This is inside the O(n^2) loop that tries all minimum distances m. So in total we will try O(n^3) situations.

Given m, the minimum distance between two elements of D and a[r], the minimum element of D what is the maximum number of elements we can add? Note that no element can be larger than a[r] + km. The inclusion of a[r] means that we cannot add any element smaller than a[r] + m, because it would mean that the added element is smaller than a[r] (breaking the condition that a[r] is the minimum) or it would break the requirement that the distances be larger than m. So the next element to add should be larger than a[r] + m. If we add any element x as the second-smallest element, it will make us unable to add any new elements smaller than x + m, so the smaller x is , the less restrictions we will have. In other words, we should always add the smallest element possible. We begin with d_0 = a[r], then we pick d_1 as the smallest element that is larger than d_0 + m, then d_2 should be the smallest element larger than d_1 + m and so and so until the elements become so large that we cannot add them without breaking the rule that they should be at most a[r] + km. Searching for these elements will take O(n) time for a total complexity of O(n^4).

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
int maxsize(vector < int > a, int k) {
  int n = a.size();
  sort(a.begin(), a.end());
  int res = 1;
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      long mindif = abs(a[i] - a[j]);
      // the minimum difference between two elements of S is mindif
      long maxdif = k * mindif;

      for (int r = 0; r < n; r++) {
        // a[r] is the smallest element in this case
        int c = 1;
        int p = r;
        for (int s = r + 1; s < n; s++) {
          // always pick the smallest element allowed:
          if (a[s] >= a[p] + mindif) {
            if (a[s] - a[r] <= maxdif) {
              p = s;
              c++;
            }
          }
        }
        res = std::max(res, c);
      }
    }
  }

  return res;
}

DivFree

Unlike the division 2 version, we can’t use that straightforward dynamic programming approach directly (The constraints are such that complexities like O(nk) or O(n^2) or O(k^2) are out of the question) . Although there are a couple of methods that rely on the way that recurrence behaves. For example, many numbers when calculating f(n,i) are repeated for different values of i. It turns out that the multiset exponents of the prime factorization of i are what determine the result for f(n,i) and there are not as many such multisets for k <= 50000.

Let’s try an approach that is easier to think about and prove.

The bad sequences

To avoid the straightforward dynamic programming approach , we should try a different perspective. When a problem asks to count valid sequences, sometimes it’s easier to count the invalid ones first. To calculate all possible sequences, we can take k ^ n. We just need to count the number of bad sequences: “bad”(n) and subtract it from k ^ n: “good”(n) = k^n - “bad”(n).

Let’s define a bad sequence. A bad sequence is any sequence of n elements between 1 and k, inclusive in which there is a pair of consecutive elements s[i], s[i+1] such that s[i] is a proper divisor of s[i+1].

Inclusion-exclusion

Let’s try and find a way to calculate “bad”(n). For n <= 1, we can see that there are no bad sequences because there are no pairs of adjacent elements. Let’s try n > 1:

• There are “bad”(n-1) bad sequences of n-1 elements, appending any integer from 1 to k should generate a bad sequence of n elements: k * “bad”(n-1). This should count all the bad sequences that have the bad pairs in the first n-1 elements.

• Some other bad sequences were good in the first n-1 elements but became bad when the last element was added. “good”(n-2) + “bad_pairs”(k)

“bad_pairs”(k) would calculate the number of pairs (x,y) where x is a proper divisor of y. So we have sequences like:

? ? ? ? ? ? ? ? ? ? ? 1 2

The last two elements make a bad pair.

But there is a problem with “good”(n-2) + “bad_pairs”(k). The logic is that we add two elements, (x,y), but what if, when adding x, the sequence became a bad sequence of n-1 elements? We intended to count the number of good sequences of n-1 elements that became bad, but this logic includes also some bad sequences of n-1 elements. We should subtract these cases: -“good”(n-3) + “bad_triples”(k). This time, “bad_triples”(k) counts the number of triples (x,y,z) such that x is a proper divisor of y and y is a proper divisor of z.

That subtraction introduces a new issue which can be solved by adding +“good”(n-4) + “bad_four_tuples”(k). This is the inclusion-exclusion principle, we will later have to subtract +“good”(n-5) + “bad_five_tuples”(k) and so and so. The general formula should look like this:

k * “bad”(n-1) + sum_(i=2)^(i<=n)( (-1)^i * “good”(n - i) * “divseq”(i))

We generalized counting pairs, tuples, etc into calculating “divseq”(i) which is the number of sequences of i elements such that each element is a proper divisor of the next element. So for each j: s[j] is a proper divisor of s[j+1]. (-1)^i means that it should be positive when i is even and negative when i is odd.

Note that calculating “good”(n) depends on “bad”(n), so this recurrence relation still requires dynamic programming. It appears O(n^2) is the upper bound. Assuming we also precalculate “divseq”(n)`.

There is a limit for divisor sequences

It turns out that the formula in the previous section is good enough to solve the problem. We just need an additional observation. “divseq”(n) is the number of sequences of integers in which each integer is a proper divisor of the next integer. So if we start with a value for s[0] , the next value is s[1] = i_1 s[0], where i_1 is a integer greater than 1. Then s[2] = i_2 s[1], and so and so. The key is that each element in the sequence is at least twice as large as the previous element. Since k is the upper limit for the elements in this sequence, then the largest sequence possible we could imagine has ~log_2(k) elements: For example, when k = 1024, this sequence would be: 1,2,4,8,16,32,64,128,256,512,1024. Even with k = 50000, the maximum number of elements is 20. This means that for n > 20, “divseq”(n) = 0. Back to the formula:

k * “bad”(n-1) + sum_(i=2)^(i<=n)( (-1)^i * “good”(n - i) * “divseq”(i))

When “divseq”(i)) is 0, then the whole term is 0, so we can actually cut the upper bound:

k * “bad”(n-1) + sum_(i=2)^(i<=min(n, log_2(k)))( (-1)^i * “good”(n - i) * “divseq”(i))

We only need to calculate that sum for up to 20 elements. This means that the approach is actually O(n log(k)), which is excellent. All we need to do now is to calculate “divseq”(i):

Divisor sequence

We will use dynamic programming: f(n, i) calculates the number of divisor sequences of n elements such that the last element is i. It follows that f(n, i) = sum( f(n-1, d) ) for all d that are proper divisors of i. We can find the divisors in a similar fashion to the sieve in the division 2 version.

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
const int MOD = 1000000007;

int dfcount(int n, int k) {
  const int LOG_K = 20;

  // powers of k, useful
  vector < long > powk(n + 1);
  powk[0] = 1;
  for (int i = 1; i <= n; i++) {
    powk[i] = (k * powk[i - 1]) % MOD;
  }

  // divseq[n] : number of sequences of n elements in which every element
  //             is a proper divisor of the next one 
  vector < long > divseq(LOG_K + 1);

  // dp[n][i] : number of sequences of n elements in which every element
  //            is a proper divisor of the next one and
  //            the sequence ends with i.
  vector < vector < long > > dp(LOG_K + 1, vector < long > (k + 1, 0));
  for (int j = 0; j <= k; j++) {
    dp[1][j] = 1;
  }
  for (int i = 2; i <= LOG_K; i++) {
    for (int d = 1; d <= k; d++) {
      for (int j = 2 * d; j <= k; j += d) {
        // d is a proper divisor of j
        dp[i][j] += dp[i - 1][d];
      }
    }
    divseq[i] = accumulate(dp[i].begin(), dp[i].end(), 0) % MOD;
  }

  vector < long > good(n + 1);
  vector < long > bad(n + 1);
  bad[0] = 0;
  good[0] = 1;
  for (int i = 1; i <= n; i++) {
    bad[i] = (bad[i - 1] * k) % MOD;
    // inclusion-exclusion:
    for (int j = 2; j <= i && j <= LOG_K; j++) {
      long sign = 1;
      if (j % 2 == 0) {
        sign = 1; // positive sign
      } else {
        sign = MOD - 1; // negative sign
      }
      // add p*q*r
      long p = sign, q = good[i - j], r = divseq[j];
      bad[i] += (((p * q) % MOD) * r) % MOD;
    }
    bad[i] %= MOD;
    good[i] = (powk[i] + MOD - bad[i]) % MOD;
  }
  return good[n] % MOD;

}