SRM 672

Match Summary

Round Overview
Discuss this match

SetPartialOrder

We need to find if the two sets in the input are equal, disjoint or if one is a proper subset of the other. The sets are provided as arrays which may be in any order, but we can just sort them. Once you sort the two arrays, we can check if they are equals, if the sorted arrays are equal then the sets are equal (Remember order doesn’t matter in a set).

We can then find if the sets are disjoint. If there is at least one element in a that doesn’t exist in b AND there is also at least one element in b that doesn’t exist in a, then the sets are disjoint.

If the sets are neither equal nor disjoint then forcefully one is a proper subset of the other. The smaller set will be.

Since we need to check if there are elements that exist in a but not in b and vice versa then we can also use that logic to find equality, if there are no such elements the sets are equal.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
string compareSets(vector < int > a, vector < int > b) {
  bool a_lacks = false, b_lacks = false;
  for (int x: a) {
    // std::count counts the number of times x is in the vector
    if (count(b.begin(), b.end(), x) == 0) {
      b_lacks = true;
    }
  }
  for (int x: b) {
    if (count(a.begin(), a.end(), x) == 0) {
      a_lacks = true;
    }
  }
  if (!a_lacks && !b_lacks) {
    return "EQUAL";
  }
  if (a_lacks && b_lacks) {
    return "INCOMPARABLE";
  } else if (a_lacks) {
    return "LESS";
  } else {
    return "GREATER";
  }
}

Another idea is to use more set logic and find the intersection between the two sets. e.g: If the intersection is equal to a, then a is a subset of b. Combine this with perhaps using the language’s built-in sets and we can have something like this in python:

1
2
3
4
5
6
7
8
9
10
11
12
class SetPartialOrder:
  def compareSets(self, a, b):
  A = set(a)
B = set(b)
if A == B:
  return "EQUAL"
elif A == A & B: #A & B in the intersection
return "LESS"
elif B == A & B:
  return "GREATER"
else:
  return "INCOMPARABLE"

SubstitutionCipher

Since we have an example of a message and its encoded version, we can use the following logic to decode new messages: Since we know that a[i] becomes b[i] after encoding, then we can know that if we find b[i] in a new encoded message, then the original character in that position was a[i].

There’s just an additional corner case. Since we also know that all the cipher encodes and decodes are upper case English letters, and there are 26 of them. Then in case we knew the ways to encode exactly 25 of the letters, we can use that information to be able to encode the remaining one. The letter that’s missing in a will become the letter that is missing in b. We can just search for them and add them to the cipher look up table.

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
// return a letter that is not in s:
char not_in(string s) {
  // for each letter
  for (char ch = 'A'; ch <= 'Z'; ch++) {
    // if the letter appears 0 times in the string:
    if (count(s.begin(), s.end(), ch) == 0) {
      // return the letter
      return ch;
    }
  }
  return '?';
}

string decode(string a, string b, string y) {
  // a map to have a reverse lookup for all the characters in the cipher
  // so cipher[x] will be the character that becomes x after coding it.
  map < char, char > cipher;
  // save the characters we know in the lookup table
  for (int i = 0; i < a.size(); i++) {
    cipher[b[i]] = a[i];
  }
  // in case there are exactly 25 characters, then we can infer how to
  // translate the remaining one:
  if (cipher.size() == 25) {
    cipher[not_in(b)] = not_in(a);
  }

  // translate using the lookup table
  string x;
  for (int i = 0; i < y.size(); i++) {
    if (cipher.count(y[i]) == 0) {
      // we found a character we don't know how to decode:
      return "";
    }
    x += cipher[y[i]];
  }

  return x;
}

Tdetectived2

If we were the detective we would keep track both of which people we’ve already asked and everybody’s current suspicion levels. A useful observation is that we only need to keep track of who we’ve already asked. The suspicion levels for each person can be determined by just looking at who we already asked: For person i, the suspicion level will be equal to the maximum dislike among every person that was already asked. These can be inferred in O(n) time.

This is great because there are at most 18 people so there are at most 2^18 different combinations of people you already asked. In fact, since we always ask 0, the limit is 2^17. So let’s try a recurrence relation f(A) which finds the minimum time needed to interrogate k given the set A of already-asked suspects. Initially A = {0} because at the beginning we ask 0.

First of all, we do an O(n^2) loop to find the suspicion levels of each of the people we haven’t asked yet. Then we consider only those with the maximum suspicion level, when there are many of them, we need to pick one. The one with that would minimize the total time before we ask k:

• If k is among the people with the maximum suspicion level, we should interview them and the mystery ends. The result is 1.

• Else we calculate for each person with maximum suspicion level, what would happen if we interview them. If we interrogate i then the number of additional interviews before k is: f( A uuu {i}), to which we add the interview to i: 1 + f(A uuu {i}). So we should pick the minimum 1 + f(A uuu {i}) among every i with maximum suspicion level.

We can use memoization for f(A) if we represent A by a bitmask of n bits. There are O(2^n) possible states and in each one we need an O(n ^2) loop to calculate the suspicion levels. This is repeated for each killer k. For a total of O(k * 2^n n^2) time complexity.

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
int n;
vector < string > s;

int memo[18][1 << 18];

int f(int k, int mask) {
  int & res = memo[k][mask];
  if (res == -1) {
    int susp = -1;
    int best_time = 0;

    // get suspicions.
    // for the maximum suspicion, remember the minimum time
    for (int i = 1; i < n; i++) {
      if (!((1 << i) & mask)) {
        int su = 0;
        for (int j = 0; j < n; j++) {
          if ((1 << j) & mask) {
            su = std::max < int > (su, s[j][i] - '0');
          }
        }
        int t = 1 + ((i == k) ? 0 : f(k, mask | (1 << i)));
        if (su > susp) {
          // new maximum suspicion
          susp = su;
          best_time = t;
        } else if ((su == susp) && (best_time > t)) {
          // update minimum time
          best_time = t;
        }
      }
    }
    res = best_time;
  }
  return res;
}

int reveal(vector < string > s) {
  // init memo table with -1s
  memset(memo, -1, sizeof(memo));
  this - > s = s;
  n = s.size();

  int res = 0;

  for (int i = 0; i < n; i++) {
    res += i * f(i, 1);
  }
  return res;
}

Procrastination

Let’s start thinking of a simple simulation to keep track of the employees that get assigned to task n as i advances. Whenever n % i = 0 or n % i = 1, then the task changes hands, either moving from current n to n+1 or to n-1. You should notice that once i becomes larger than current n, it will become impossible for the task to change hands ever again, because we need n > i according to the statement, so we can stop the simulation then.

1
2
3
4
5
6
7
i = 2
while i <= n:
  if n % i == 0:
  n = n + 1
else:
  n = n - 1
i = i + 1

This simple simulation is O(n), which would be too expensive for n <= 10^10. We can improve this by noticing that n only changes when i is a divisor of n or n-1. So imagine we were able to quickly get the next smallest divisor of a number n that comes after i. We could skip i to the next divisor of n or n-1 (whichever happens earlier).

This leads us to the issue of getting the next divisor of n greater than or equal a lower bound a. A simple way is to use division trials. We can get all divisors of n in O(sqrt(n)) time. (For each divisor d of n, n is equal to d * (n / d) and either d or n / d will be less than or equal to sqrt(n) ). If we can extract all divisors of n in O(sqrt(n)) time, we can extract all those divisors and find the smallest one that is at least a.

However, that approach is still too expensive. It’s difficult to know how many values of i will be visited and doing an O(sqrt(n)) algorithm for each of them will turn out to be expensive even for one of the example cases.

A quick workaround is to notice that n will not vary significantly, although it will sometimes increase or decrease, it will take to stay within a reduced range. It might be difficult to prove formally, but the idea is that it is just improvable to have a situation in which n keeps increasing too many times without decreasing that much (or vice versa). For example, if we increase n too much, we will reach a situation in which n is prime and thus n-1 will have more divisors available. Same in the other direction. You will find that in practice the number of distinct n values visited is very small, in the system tests provided it doesn’t go beyond 13. If we assume that the number of distinct n values will be small, then the same n values will be checked over and over again, so we can save resources by using a cache so that the divisors of each value of n are only calculated once. We will still need some execution time to search the proper divisor among all saved divisors of n, but the number of divisors is significantly smaller than O(sqrt(n)), in fact, for n <= 10^10, the maximum number of divisors is 1344

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
map < long, set < long >> divisor_cache;

long get_divisor(long n, long a) {
  // Did we get the divisors of n before?
  if (divisor_cache.count(n) == 0) {
    // We didn't, get them:
    set < long > divs;
    divs.insert(n);
    for (long p = 2; p * p <= n; p++) {
      if (n % p == 0) {
        divs.insert(p);
        divs.insert(n / p);
      }
    }
    // save in cache
    divisor_cache[n] = divs;

  }
  // find the best divisor:
  for (long x: divisor_cache[n]) {
    if (x >= a) {
      return x;
    }
  }
  return n;
}

long findFinalAssignee(long n) {
  long i = 2;
  while (i < n) {
    if (n % i <= 1) {
      if (n % i == 0) {
        n++;
      } else {
        n--;
      }
      i++;
    } else {
      long x = get_divisor(n, i + 1);
      long y = get_divisor(n - 1, i + 1);
      // skip:
      i = std::min(x, y);
    }
  }
  return i;
}

A more solid approach:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
long findFinalAssignee(long n) {
  long i = 2;
  // until i > sqrt(n):
  for (i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      n++;
    } else if (n % i == 1) {
      n--;
    }
  }
  // from n / i downwards:
  for (i = n / i; i > 1; i--) {
    if (n % i == 0) {
      n++;
    } else if (n % i == 1) {
      n--;
    }
  }
  return n;
}

The first values of i that could be divisors of n or n-1 are all less than or equal to sqrt(n). What is interesting is that after wards there are also O(sqrt(n)) positions that can be divisors, and they mirror the previous search. As a simple example, imagine n doesn’t change, with n = 100, we will first find divisors like 2, 5, 10. There are more divisors we can get by dividing 100 by the previous divisors: 100 / 10 = 10, 100 / 5 = 20, 100 / 2 = 50, and they are also the next divisors in order. First i will travel to i = 11, where the first loop stops, then it will restart at 100 / 11 and then keep decreasing. Increasing n by 1 will not cause disruption because the divisors can be divisors of n-1. This reverse loop is also O(sqrt(n)).

AlmostEulerianGraph

Eulerian Graphs

Whenever we talk about graphs that have an Eulerian cycle, it’s useful to keep in mind their known properties. Namely, an undirected graph will contain an Eulerian cycle if and only if all the vertices have even degree. An even number of edges connecting the vertex to other vertices. By the problem statement, we also want the graph to be connected. So when we talk Eulerian Graphs we talk about connected graphs where every vertex has even degree.

Even degree graphs

How would we count the number of Eulerian Graphs of n labeled vertices? The question wants us to count Almost-Eulerian Graphs which includes Eulerian Graphs. Understanding how to count Eulerian graphs should help us. We need the graph to be connected AND have even degrees in each vertex. We can first count the number of graphs (connected or not) that have even degrees: e(n).

Consider a graph that has n-1 vertices and some edges. What happens when we add a single vertex x? Then there are n-1 edges that may be added or not. It’s interesting that for each previously existent node i. Vertex i can have odd or even degree, it doesn’t matter, because if i had odd degree, we can just add edge (i,x) and it will become even. If i had even degree, then we make sure not to add edge (i,x) and the degree of i will stay the same. Because of this reason, the number of graphs of n vertices that have even degree in every vertex is equal to the total number of graphs of n-1 vertices. That is, for each of the ((n-1)(n-2))/2 edges we can add to a graph of n-1 vertices, we pick if the edge EXISTS or DOESN’T EXIST, ((n-1)(n-2))/2 independent decisions each with 2 options. The result is: e(n) = 2^(((n-1)(n-2))/2).

Disconnected even degree graphs

But if we want the number of connected Eulerian graphs, we need to subtract from e(n) the number of even degree graphs that are disconnected. Let’s name that number d(n). e(n) - d(n) will be the Number of connected Eulerian graphs. How can we calculate d(n)?

Let’s put our focus on a single vertex, let’s say 0. If the graph is disconnected, there will be multiple connected components in the graph. One of the connected components will include 0. The size of this connected component can be 1, 2, 3, … n-1. Let’s count the number of even degree graphs where the connected component that includes 0 has size k. First of all, we need to select k vertices out of the n available that will be part of the component, we know that 0 is already one of them, so we need to pick the remaining k-1 vertices out of the n-1 vertices that are not 0. There are ((n-1),(k-1)) ways to do this assignment (Where ((n),(k)) is the binomial coefficient). The k vertices in 0’s connected component will all have even degree, and they make a connected component, so there are e(k) - d(k) ways to set up the edges in this component. The remaining n-k vertices will also have edges of their own. The n-k vertices could make more than one connected component, so the number of edges will be e(n-k), because they just need to have even degrees but not necessarily connected. Ergo the number of disconnected graphs when 0 is in a component of size k is: ((n-1),(k-1))(e(k) - d(k))e(n-k). The total number of graphs is the sum for each k:

d(n) = sum_(k=1)^(k<n)(((n-1),(k-1))(e(k) - d(k))e(n-k))

And this is the solution. We can precalculate all the relevant binomial coefficients in O(n^2) time using Pascal’s triangle. Then note that d(n) calls all d(k) and k < n , so we can just iteratively first calculate d(0), then d(1), d(2), … d(n) using the previous precalculated result.

Almost Eulerian Graphs

Since we know that it is not complicated to count Connected Eulerian Graphs, how about using that knowledge to count the Almost Eulerian ones? Almost Eulerian Graphs are modifications of an Eulerian graph. Some edge (u,v) has been added or removed from an Eulerian Graph. The Eulerian Graph initially had even degrees in all its vertices. If we add or remove an edge (u,v), this means that u and v will become the only two vertices with odd degree. Take an Almost Eulerian Graph that is not Eulerian, this means it has two vertices u and v with odd degrees. There is always an unique Eulerian graph that can be restored from this, since u and v have odd degrees, then we need to either add or delete edge (u,v). Since for every Almost Eulerian Graph, there is exactly one Eulerian Graph that originated it, then we can generate unique Almost Eulerian Graphs from each Eulerian Graph we find. Given each of the e(n) - d(n) Eulerian graphs we counted, there are (n(n-1))/2 edges that can be modified to make a new Almost Eulerian graph. For each edge (u,v), if the edge exists in the Eulerian graph, remove it or else add it. This means that there are (n(n-1))/2 options for new Almost Eulerian graphs that can be made from each Eulerian graph. Add also the Original Eulerian Graph itself and the formula is:

( e(n) - d(n) ) * ( ( n(n-1))/2 + 1)

Code

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

// x raised to the y-th power modulo MOD:
long mod_pow(long x, int y) {
  // exponentiation by squaring
  long r = 1;
  while (y > 0) {
    if (y % 2 == 1) {
      r = (r * x) % MOD;
    }
    x = (x * x) % MOD;
    y /= 2;
  }
  return r;
}

int calculateGraphs(int n) {
  // Pascal's triangle
  vector < vector < long >> C(n + 1, vector < long > (n + 1));
  for (int i = 0; i <= n; i++) {
    C[i][0] = 1;
    for (int j = 1; j <= i; j++) {
      C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
    }
  }

  vector < long > e(n + 1), d(n + 1);
  for (int i = 0; i <= n; i++) {
    // formula for e[i]
    e[i] = mod_pow(2, ((i - 1) * (i - 2)) / 2);

    // formula for d[i]
    d[i] = 0;
    for (int k = 1; k < i; k++) {
      long p = C[i - 1][k - 1];
      long q = (e[k] - d[k] + MOD) % MOD;
      long r = e[i - k];
      d[i] += (p * ((q * r) % MOD)) % MOD;
    }
    d[i] %= MOD;
  }
  // There are e[n] - d[n] Eulerian graphs, multiply by n(n-1)/2
  long p = (e[n] + MOD - d[n]) % MOD;
  long q = n * (n - 1) / 2 + 1;
  return (int)((p * q) % MOD);
}