SRM 633

Match Summary

Round Overview

Target

Used as: Division Two - Level One:

This is an implementation problem. But there are many distinct methods. It’s interesting to find what is the simplest to implement one (for you).

The five loops

The typical solution to this problem is to code 5 loops, 4 nested in another to fill each row and column of each ring. Like in the following java 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
public String[] draw(int n) {
  char[][] m = new char[n][n];
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      m[i][j] = ' ';
    }
  }

  for (int i = 0; i < n; i += 2) {
    // fill column
    // (i,i) -> (i,n-i-1)
    for (int j = i; j < n - i; j++) {
      m[i][j] = '#';
    }
    // fill column
    // (n-i-1,i) -> (i,n-1-1)
    for (int j = i; j < n - i; j++) {
      m[n - i - 1][j] = '#';
    }
    // fill row
    // (i,i) -> (n-i-1,i)
    for (int j = i; j < n - i; j++) {
      m[j][i] = '#';
    }
    // fill row
    // (i,n-i-1) -> (n-i-1,i)
    for (int j = i; j < n - i; j++) {
      m[j][n - i - 1] = '#';
    }
  }

  // convert char[][] to String[]
  String[] res = new String[n];
  for (int i = 0; i < n; i++) {
    res[i] = "";
    for (int j = 0; j < n; j++) {
      res[i] = res[i] + m[i][j];
    }
  }
  return res;
}

Filling cell by cell

Let’s fill a matrix of n times n characters. The main challenge is to find the logic for: Given a cell position: row i, cell j, should we paint this cell or not?

What we need is to divide the board in rings. So let’s number the outer ring 0, then ring 1, ring 2, etc. In this bulls-eye pattern, even rings will be painted. So we need to know if the ring of (i,j) is even. The logic ends up becoming similar to this in python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Target:
  def draw(self, n):

  # returns true
if (i, j) should be painted:
  def painted(i, j):
  (x0, x1, y0, y1) = (0, n, 0, n) # the total square
t = 0
while ((x0 <= i < x1) and(y0 <= j < y1)):
  t += 1 #continue increasing until we find a square that doesn 't contain the cell
  (x0, x1, y0, y1) = (x0 + 1, x1 - 1, y0 + 1, y1 - 1) #reduce the size of the square
return t % 2 != 0

return tuple(''.join('#'
  if painted(i, j)
  else ' '
  for j in range(n)) for i in range(n))

Fractal

Another approach consists on noticing that given the result for `n = 1` (The smallest case):

We can build the result for `n = 5` (The second smallest case, note that only cases = 1 modulo 4 are valid)

Just take the `n=1` and first surround it by blank cells and then surround again by painted cells.

We can simplify this by imagining a result for `n = 3`

If we put things together:

So the result for `n` can be built from the result for `n-2`. Just negate the result for `n-2` (swap painted cells with unpainted ones) and then surround with #.

This extra analysis pays off because the code is simple and straight-forward:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector < string > draw(int n) {
  vector < string > res = {
    "#"
  }; //result for n = 1

  for (int i = 3; i <= n; i += 2) {
    // buld result for i, using i-2 as base
    vector < string > nw(i, string(i, '#')); //surround

    for (int x = 1; x < i - 1; x++) {
      for (int y = 1; y < i - 1; y++) { //negate
        if (res[x - 1][y - 1] == '#') {
          nw[x][y] = ' ';
        }
      }
    }
    res = nw; //save new result
  }
  return res;
}

Jumping

Used as: Division Two - Level Two:

There are different approaches to this problem. We will use one that also enables solving the division 1 version.

Set of reachable points

Imagine we care only about the first jump. What points can be reached after the first jump? If the jump has length `r`. Then of course any points in the circle of radius `r` centered at `(0,0)` can be reached in the first move:

This is useful when we want to consider two steps. In the above example, the first jump had length 3. Now imagine a second jump of length 1. Which are the points that are reachable using these two jumps? First we pick any of the points reachable in one step , the points in the circle above. Then we can center a circle of radius 1 in the picked point and those are the points reachable in the second step. We can repeat this for every point reachable in one step.

If we join all these circles together we will reach something interesting:

What we have now is a doughnut-like shape. From this we can guess that any point whose distance to `(0,0)` is between 2 and 4 is reachable using the first two steps. Any other point is not reachable.

Imagine another step, also of radius 1. This time we can pick any point in the donought-shape and reach it in 2 steps. The third step means that any point in the circle of radius 1 centered in the point reached in 2 steps can be reached. So the union of all those possible circles will be the set of points reachable in the first 3 steps:

By now we can generalize that the set of valid points will always be determined as a range of distances. We can use an interval `[a,b]`, meaning that any distance `d : a <= d <= b` is valid. We have also approximated a way to generated the interval for `k` moves using the interval generated from the first `k-1` moves.

Imagine that after `k-1` moves, the valid interval is `[a,b]` , we have to add a new move of radius `r`. Then, according to the previous examples, the new interval will be `[a-r, b+r]`. This is usually true, but there is an exception. When the radius of the new move is too large in comparison to `a`. In the above example, consider a new move with `r = 2`, then `a = 1` cannot become `a - 2 = -1`, so the logic is no longer so useful. We can see that the maximum distance is still `b + r`, but `a - r < 0` or `r > a` so we need to think of something else.

• In this specific case, it is possible to reach point zero. Since `a > r` and `r <= b`, we can first move to a point that has distance `r` in the first `k-1` moves (in this case, `r = 2`), then we can move to point (0,0). From this it follows that all points at a distance within 0 and `b + r` are reachable.

That covers when `r <= b`, what about `r > b` ? In this case, it is useful to consider the negative distances. We had `a = 1, b = 5` in the previous case, imagine a new `r = 6`. Imagine we move to point `(-b,0)` then we can move to point `(r-b,0)` by adding `r` units in the opposite direction all because `r-b` is positive. Note that it is also possible to move to `(r-a,0)`, but `(r-b)` will be smaller or equal. Ergo, in this case the new minimum should be `(r - b)`. In the specific example, it will be possible to move to all points with a distance between 1 and 11.

This is all we need, we can build the interval of valid distances after `k` moves using the result of the first `k-1` moves. Initially, we can do `a = b = 0` as the defacto result for zero moves. Then we repeat the logic. To recap, if the previous interval was `[a,b]` and the new radius is `r`:

• The new maximum is `b + r`.

• If `r <= a`, the new minimum is `a - r`.

• If `a < r <= b`, the new minimum is `0`.

• If `r >= b`, the new minimum is `b - r`.

From this we can find the interval `[a,b]` of distances that can be traveled using all the moves. Then we can just calculate the distance from `(0,0)` to input `(x,y)`, if this distance is within the interval, it is possible to move to it.

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
string ableToGet(int x, int y, vector < int > jumpLengths) {
  int n = jumpLengths.size();
  long a = 0; // in zero steps, only point (0,0) is reachable:
  long b = 0;

  for (int i = 0; i < n; i++) {
    int r = jumpLengths[i];
    // update minimum
    if (r <= a) {
      a = a - r;
    } else if (r <= b) {
      a = 0;
    } else {
      a = r - b;
    }
    // update maximum
    b += r;
  }
  // distance must be in interval [a, b]
  // We know use Euclid's distance formula. sqrt( (x - 0)^2 + (y - 0)^2 )
  // but since everything is a integer, it migth be convenient to avoid
  // floating point calculations. 
  // a <= sqrt( x^2 + y^2 ) <= b
  // a*a <= x^2 + y^2 <= b*b
  long dx = x, dy = y;
  long r2 = dx * dx + dy * dy;

  return (a * a <= r2 && r2 <= b * b) ? "Able" : "Not able";
}

GCDLCMEasy

Used as: Division Two - Level Three:

Imagine we take any of the indexes in the sequence. The result will hold a value `x` in this index. By constraints, the possible LCM values between this `x` and some other numbers is at most 10000. We can guess that `x` is an integer from 1 to 10000. The trick to this solution is to try all values of `x` until we find one that is consistent with the results.

Imagine we picked a fixed value `x` for one of the elements of the sequence. Is it possible to fill the remaining values of the sequence in a consistent way? What does `x` tell us about the other elements? There may be some elements `y` such that we know the wanted values of `LCM(x,y)` and `GCD(x,y)`. The key to this problem is to know the following equation:

This is a known property and one of the usual ways to calculate the LCM programmatically.

Just an idea:

This means that once we fix `x`, then we can easily find the value for `y`. Now imagine that there maybe multiple other elements `y`, each with two defined conditions for GCD(x,y) and LCM(x,y), we can determine all these values.

For each of those `y` elements, we have a new conundrum. There may be elements `z` such that the values of `LCM(y,z)` and `GCD(y,z)` are known. This will help us determine the value for `z`. Then we can do the same with the values of `z`

Imagine what will happen if we find two conflicting stories, we determined that `x_i` has a value, but after moving through other conditions we found a completely distinct value for `x_i`. This is a contradiction. In case of a contradiction, the value we picked for `x` was invalid.

This logic can be translated to a Depth-first search (DFS). Imagine a graph, each element of the sequence is a node and each pair of conditions is an edge. We start with `x` and its fixed value. Then we try all the neighbors of `x`, find their values `y` and then continue the DFS with `y` and so and so, filling the elements’ values and looking for contradictions. Like this:

1
2
3
4
5
6
7
8
9
10
11
12
DFS(x, value) {
    if (memory[x] == -1) {
      // didn't know the value
      memory[x] = value;
      for y in neighbors(x) {
        yvalue = (calculate value of y using the LCM / GCD equation)
        DFS(y, yvalue)
      }
    } else if (memory[x] != value) {
      // found a contradiction
      CONTRADICTION = true
    }

Unconnected graphs

We found that just fixing the value for an element `x` will generate the values of all the remaining elements. This is not always true. Sometimes the equations do not make a single connected component. The approach is to just treat each connected component separately, for each component, try each possible value for just one of the elements.

Complexity

For each connected component, we repeat a DFS 10000 times. Running a DFS in each connected component is `O(V + E)` where `V` is the number of vertices and `E` the number of edges. This means `O(n + m)` in this problem. There are `n` variables (vertices) and `m` conditions (edges). Complexity is equivalent to `O(V + E) ` 10000 times.

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
int gcd(int a, int b) {
  while (b != 0) {
    tie(a, b) = make_tuple(b, a % b);
  }
  return a;
}
int lcm(int a, int b) {
  return (a / gcd(a, b)) * b;
}

string possible(int n, vector < int > A, vector < int > B, vector < int > G, vector < int > L) {
  // save edges in a list, each edge is stored as (B[i], G[i], L[i]) for A[i]
  vector < list < tuple < int, int, int >>> g(n);
  for (int i = 0; i < A.size(); i++) {
    for (int j = 0; j < 2; j++) {
      g[A[i]].push_back(make_tuple(B[i], G[i], L[i]));
      swap(A[i], B[i]);
    }
  }
  vector < int > value(n, -1);
  for (int i = 0; i < n; i++) {
    if (value[i] == -1) {
      // In each step, make sure to set all variables in this
      // connected component to -1: calling cleanDFS(x) will do that
      function < void(int) > cleanDFS = [ & ](int x) {
        if (value[x] != -1) {
          value[x] = -1;
          for (auto edge: g[x]) {
            int y, g, l;
            tie(y, g, l) = edge;
            cleanDFS(y);
          }
        }
      };
      bool onegood = false; //at least one good xi value
      for (int xi = 1; xi <= 10000; xi++) {
        cleanDFS(i);
        bool good = true;

        // setDFS(x,a) does a DFS throughout the component, finding
        // new values and checking for contradictions.

        function < void(int, int) > setDFS = [ & ](int x, int a) {
          if (value[x] == -1) {
            value[x] = a;
            for (auto edge: g[x]) {
              int y, g, l;
              // each edge is in format (y, g, l):
              tie(y, g, l) = edge;

              // LCM(a,b) = a * b / GCD(a,b)
              // l = a * b / g
              // b = (l * g) / a;
              int p = l * g;
              if (p % a == 0) {
                int b = p / a;
                if (lcm(a, b) == l && gcd(a, b) == g) {
                  // continue the DFS:
                  setDFS(y, p / a);
                } else {
                  good = false;
                }
              } else {
                good = false;
              }
            }
          } else if (value[x] != a) {
            good = false;
          }
        };
        setDFS(i, xi);
        if (good) {
          onegood = true;
          break;
        }
      }
      if (!onegood) {
        // no good result for this component
        return "Solution does not exist";
      }
    }
  }
  return "Solution exists";
}

;

PeriodicJumping

Used as: Division One - Level One:

A good first step is to understand how we can tell if it is possible to reach the target point after `k` steps. The analysis in the division 2 version of the problem shows that after any number of moves, all points with a distance to `(0,0)` within a range `[a,b]` are reachable, and we also know how to find `a` and `b`.

The logic we can try is to iteratively try each new step in the cycle, update `a` and `b` until the distance `x` from `(0,0)` is valid. An issue with this is that the number of required moves can be very large. For example, imagine a case with only length-1 jumps and `x = 1000000000`, we would need to simulate `1000000000` jumps which would be expensive.

Double-steps

The trick is to take advantage of the cyclical nature of the sequence of jump lengths. Repetitions are good and useful, try it with just two equal moves: `{z, z}`. If we use the analysis you will find that any distance in interval `[0, 2z]` is valid. You can move from `(0,0)` to `(0,z)` and then back to `(0,0)` or `(0,2z)` and this is enough to prove that both distance 0 and `2z` are valid. Since the set of valid distances is always a interval, all distances between `0` and `2z`, inclusive are valid.

This extends to repeated sequences of moves, so imagine that the total sum of lengths in a cycle is `Z`. This means that it is possible to move from `(0,0)` to `(0,Z)` by using all the steps in the cycle. If we repeat the cycle again, the longest distance we can travel is, again, `Z`. So we can move to `(0,2Z)` and `(0,0)`, showing that all distances from `0` to `2Z` are valid.

There is more, imagine we repeat a cycle `2i` times. If the sum of all the jumps in a single cycle is `S`, then we can conclude that after `2i` times, we can move to any distance between `0` and `2 i S`, inclusive.

So this is the idea, find the largest `i` such that `2 i S <= x`. We can do this with a division: `i <= x/(2S)`. This means that we do not need to simulate the first `2iN` moves, because we can easily find `a = 0, b = 2S`. We can then simulate the remaining moves until `x` is reachable. What is the maximum number of moves we might need to simulate? After `2 (i+1)N` moves, all distances from 0 to `2(i+1)S` will be reachable, and `2iS <= x < 2(i+1)S`, because `2iS` is the maximum distance `<= x`. After `2N` moves, the point `x` will be guaranteed to be reachable. So we only need to simulate at most `2N` moves.

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
int minimalTime(int x, vector < int > jumpLengths) {
  x = abs(x);
  // Distance by 2 cycles:
  long s = 0;
  for (int y: jumpLengths) {
    s += 2 * y;
  }
  int n = jumpLengths.size();
  int i = (int)(2 * (x / s) * n); // start by moving as many 2-cycles as possible
  long a = 0; // then the interval is from 0 to x - x % s
  long b = x - x % s; // interval [a,b]
  while (!(a <= x && x <= b)) {
    int r = jumpLengths[i % n];
    // update minimum:
    if (r <= a) {
      a = a - r;
    } else if (r <= b) {
      a = 0;
    } else {
      a = r - b;
    }
    // update maximum
    b += r;

    i++; // next jump          
  }
  return i;
}

DoubleTree

Used as: Division One - Level Two:

As is usual in tree problems it is convenient to root the trees. In this case the root would be the first label we pick for the solution (and would be the root in both trees). We do not know in advance which vertices will be included in the optimal pick, so we should try solving for each picked root separately and then return the best score among all roots.

After a root label is picked, both trees will be rooted. Imagine the root is `r` and we decide to include a label `x` in the set. Since the set of labels must make a connected subtree in both trees, this means that all the nodes in the two paths (both trees) between the root `r` and `x` must be included in the solution. Then for every `y` that is between `r` and `x` in any of the trees, we have to make sure the whole path between `y` and `r` in the other tree is included and so and so…

The issue is that thinking in whole paths will complicate things too much. An idea that can greatly simplify this problem is to just say: “If we include `x`, then the parents `y` and `z` of `x` in both rooted trees must also included.”. This is really the same condition as before, but simplified so that the inclusion of a new vertex only implies the inclusion of two other vertices. It is true: If we include the parent of `x`, then we must also include the grandparent of `x` and its parent and so and so until reaching the root; hence this condition is sufficient to make the whole path from `x` to `r` included.

Reframing the problem

Given two rooted trees, decide to include or not a label.

• If a label `x` is included, you earn score[x] points.

• If label `x` then the parent of `x` in tree 1: `y` must also be included.

• If label `x` then the parent of `x` in tree 2: `z` must also be included.

Minimum cut

We have many decisions and deciding something forces us to decide something else. We should get creative in thinking for approaches and eventually we might ask : Can we use minimum cut to solve this problem?

The first issue is that Minimum cut is a minimization problem. But imagine a special version of minimum cut in which the costs to remove edges are negatives of the scores in the original problem. Then minimizing the result in this problem would maximize the original score. It is worth noting that, because the costs score[x] may be negative, negative numbers in the costs is is an issue we had to deal with anyway.

How would we represent the problem of including / not including a node as a minimum cut? We can create a binary. There is an edge connecting the source to node `x` and an edge connecting `x` to the sink. For a cut, we need to remove at least one of the edges, so the decision is in which of the edges will be removed. If score[x] is the score, then an option costs -score[x] points (include it) and the other option costs 0 points. These would be the costs of the edges.

In this image, we have a node `A` , including this node gives `a` points, so there is an edge with cut cost 0 and an edge with cost `-a`.

We’d like to implement the condition: “If we include A, then we must include B”. So we need to imagine that `B` has a similar story:

Cutting the `-a` edge should somehow force us to cut the `-b` edge as well (note that `-a` and `-b` are not necessarily negative). Cutting the above `0` edge, should still allow us to decide anything about the edges related to `B`. This is the idea:

If we cut `-a` instead of just the above `0`, then we will be forced to cut `-b`, because the infinite edge between `A` and `B` makes a new path that goes through the `-b` cost edge possible.

Negative edges

If we want to reduce minimum cut to maximum flow , then we need to deal with the possibility of negative capacities. We should come up with a way to convert the problem to one with all costs positive.

The idea is to add a cost `M` to all the edges. `M` should be a very large value. So large that we are guaranteed that for each vertex, we will only increase the cost by `M` in addition to the “real” cost. Note that we also need `M` not to be very large, because large capacities will complicate the flow implementation. The maximum vertex score is 1000, so in fact `M = 1001` is large enough.

After all of that, we can subtract `(n-1)M` from the maxflow result. This will yield the minimum cut considering the possibly negative costs. Negating this cut cost is the total score of the optimal pick using `r` as a root. Remember to add score[r] too, it has been implicitly added when we picked it as the root.

Code

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
const int M = 1001;

// Not included: A network class that represents a flow network (to solve max flow
// which is equivalent to minimum cut)
// Methods:
// addVertex() creates a new vertex in the network and returns an identifier int
// addEdge(u,v,c) : creates an edge from u to v with capacity c
// maxFlow() : Returns the maximum flow in that network.

int maximalScore(vector < int > a, vector < int > b, vector < int > c, vector < int > d,
  vector < int > score) {
  int n = score.size();
  int best = 0;
  for (int x = 0; x < n; x++) {
    unique_ptr < MaxFlow::network > g(new MaxFlow::network());
    for (int i = 0; i < n; i++) {
      g - > addVertex();
    }
    g - > source = g - > addVertex();
    g - > sink = g - > addVertex();

    // do the DFS usign the tree represented by u, v
    auto doDFS = [ & ](const vector < int > & u,
      const vector < int > & v) {
      function < void(int, int) > dfs = [ & ](int i, int parent) {
        for (int j = 0; j < n - 1; j++) {
          int k = -1;
          if (u[j] == i) {
            k = v[j];
          } else if (v[j] == i) {
            k = u[j];
          }
          if (k != -1 && k != parent) {
            if (i != x) {
              // Add an infinite capacity edge connecting
              // a label to its parent in this tree.
              g - > addEdge(k, i, MaxFlow::INF);
            }
            dfs(k, i);
          }
        }
      };
      dfs(x, -1);
    };
    doDFS(a, b); //Do the DFS for tree 1
    doDFS(c, d); //Do the DFS for tree 2

    for (int i = 0; i < n; i++) {
      if (i != x) {
        g - > addEdge(g - > source, i, M);
        g - > addEdge(i, g - > sink, M - score[i]);
      }
    }
    int mf = g - > maxFlow();
    best = std::max < int > (best, M * (n - 1) - mf + score[x]);
  }
  return best;
}

GCDLCM

Used as: Division One - Level Three:

Prime factorizations

In many number theory problems it is useful to consider numbers from the perspective of their prime factorization. In this case, we have the LCM and GCD, imagine two numbers `a = 18 = 2*3^2` and `b = 15 = 3*5`. The LCM is: `90 = 2*3^2*5` and the GCD is : `3`. The cool thing is that for each prime factor `p`, such that its exponent in the factorization of `a` is `q` and its exponent in the factorization of `b` is `r`, we have that the exponent of that prime number in the factorization of the LCM will be `max(q,r)` and the exponent in the GCD will be `min(q,r)`.

Consider a condition like: `GCD(A,B) = C`. We can factorize `C` and for each prime factor `p`, we will have a condition of the kind: `GCD(A_p, B_p) = C_p`, where `A_p, B_p` and `C_p` are the exponents of the prime number in each respective number. LCM conditions create similar groups of conditions but using `max()`.

Note that each possible prime factor makes a set of conditions that is independent of the others so we can solve each of these groups separately. If all the sets of conditions are valid, then the test case is valid.

Therefore, for each relevant prime number `p` we will repeat a problem in which there are various conditions of the kind `min(A,B) = C` or `max(A,B) = C`. Relevant prime numbers are those that appear at least once as a factor of the LCMs or GCDs in the input conditions. There are at most 200 of those numbers and their upper bound is 1000000000. The maximum number of distinct numbers contributed by a single number <= 1000000000 is 9 ( The product of the 10 smallest primes is larger than 1000000000). So we can imagine an upper bound of 9*200 relevant prime numbers. In reality, the upper bound will be far smaller, but this estimate is good enough. We just need an `O(n^2)` solution to solve the new subproblem of the set of min() or max() conditions.

min() / maX() conditions

We found a new subproblem. We have many conditions in one of the following two forms:

Is there a combination of values that is consistent with all those conditions?

Two cases

Imagine a condition:

`a` or `b` would need to be equal to `c`. But if `a` is equal to `c`, then `b` needs to be greater than or equal to `c`. So we have an OR between two conditions:

Similarly, `max(a,b) = c` becomes:

SAT

In total we will have a condition of the kind: `(A and B) or (C and D)`. This is repeated for each of the initial conditions. So we have a chain of conditions of the form `(A and B) or (C and D)` that must all be true. Each of the small conditions `A`, `B`, `C`, `D`… may contradict with other conditions so we may need to add extra expressions to ensure a mutual exclusion. We can use a single big boolean AND expression combining all conditions. Finding if it is possible to satisfy this is the boolean satisfability problem. Which is difficult to solve in the general case.

2-SAT

The 2-SAT variation of the satisfability problem would be much better. We would be interested in big conjunction of expressions of the kind `A or B`. We currently have conditions of the kind `(A and B) or (C and D)`. The trick is to just consider each `(A and B)` sub-condition a single truth value. So when we say `)X or Y)`, `X` is actually a pair of conditions `(A and B)` , (and the conditions represent things like `X_0 = c, X_1 > c`).

So each of the min() / max() conditions will generate a condition in the form `(X or Y)`. And we are very close to be able to use 2-SAT. The only extra thing to consider is the statements that are mutually exclusive.

Mutual exclusion

Each variable participating in the big condition `(A or B) and (C or D) and …` actually represents a pair of conditions like `( (X_0 = c) and (X_1 >= c) )`. The same variables `X_0` or `X_1` may be used in other conditions. So imagine a pair of conditions that cannot be simultaneously true:

These two conditions cannot simultaneously be true. So we should a conditions that ensure mutual exclusion: `S ==> ~T` . “If `S` is true, then `T` must forcibly be false.” . Note that `T ==> ~S` is an equivalent condition.

There are various ways two conditions `S` and `T` may be mutually exclusive. Maybe one states `X_i = 5` and the other `X_i < 3`. Or one states `X_i <= 5` and the other `X_i >= 10`. etc.

Complexity analysis

There are `m <= 200` conditions of the kind `min(a,b) = c` or `max(a,b) = c`. Each of these conditions becomes an expression `A or B`. Two statements each with a truth value. Each of these statements becomes 2 vertices (the statement and its negation) in the graph we use to solve 2-SAT by finding the Strongly Connected Components. This means `8m` vertices. Tarjan’s algorithm for the SCC needs `O(|V| + |E|)` time. `V` is the number of vertices and `E` the number of edges. There are `O(m)` vertices (specifically `4m`). The number of edges is `O(m^2)`. There are `O(m^2)` possible mutual exclusions. This yields an `O(m^2)` complexity for the approach.

Code

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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
vector < list < int >> g;

bool contradiction(int a, int b, int c, char t_ab,
  int d, int e, int f, char t_de) {
  // if t_ab == 'm':
  //     X : (a == c) ^ (b >= c)
  // else:
  //     X : (a == c) ^ (b <= c)

  // if t_de == 'm':
  //     X : (d == f) ^ (e >= f)
  // else:
  //     X : (d == f) ^ (e <= f)

  if ((a == d) && (c != f)) {
    return true;
  }
  if (a == e) {
    if (t_de == 'm') {
      if (c < f) {
        return true;
      }
    } else {
      if (c > f) {
        return true;
      }
    }
  }
  if (b == d) {
    if (t_ab == 'm') {
      if (f < c) {
        return true;
      }
    } else {
      if (f > c) {
        return true;
      }
    }
  }
  if (b == e) {
    if (t_ab == 'm' && t_de == 'M') {
      // b >= c , b <= f
      if (c > f) {
        return true;
      }
    } else if (t_ab == 'M' && t_de == 'm') {
      // b <= c,  b >= f
      if (f > c) {
        return true;
      }
    }
  }

  return false;

}

bool forPrime(string type,
  const vector < int > & A,
    const vector < int > & B,
      const vector < int > & C) {
  int m = A.size();
  // m disjunctions (A v B) ^ (C v D) ^ (...
  // Each disjunction brings 2 statements.
  // Each statement is two vertices in the graph (normal and negation)
  g.resize(4 * m);
  for (auto & x: g) {
    x.clear();
  }
  for (int i = 0; i < m; i++) {
    // each of the m conditions is like (X v Y) or ~X -> Y
    int x = 2 * i, y = 2 * i + 1;
    // add ~x -> y
    g[2 * x + 1].push_back(2 * y);
    g[2 * y + 1].push_back(2 * x);

    // min(A[i],B[i]) = C[i]
    // X == ( (A[i] = C[i]) ^ (B[i] >= C[i]) )
    // Y == ( (A[i] >= C[i]) ^ (B[i] = C[i]) )  

    // look for exclusions
    for (int j = i + 1; j < m; j++) {
      int z = 2 * j, w = 2 * j + 1;
      // Z == ( (A[j] = C[j]) ^ (B[j] >= C[j]) )
      // W == ( (A[j] >= C[j]) ^ (B[j] = C[j]) )

      // does x contradict z ?
      if (contradiction(A[i], B[i], C[i], type[i], A[j], B[j], C[j], type[j])) {
        // x -> ~z
        g[2 * x].push_back(2 * z + 1);
        g[2 * z].push_back(2 * x + 1);
      }

      // does y contradict z ?
      if (contradiction(B[i], A[i], C[i], type[i], A[j], B[j], C[j], type[j])) {
        // y -> ~z
        g[2 * y].push_back(2 * z + 1);
        g[2 * z].push_back(2 * y + 1);
      }

      // does x contradict w ?
      if (contradiction(A[i], B[i], C[i], type[i], B[j], A[j], C[j], type[j])) {
        // x -> ~z
        g[2 * x].push_back(2 * w + 1);
        g[2 * w].push_back(2 * x + 1);
      }

      // does y contradict w?
      if (contradiction(B[i], A[i], C[i], type[i], B[j], A[j], C[j], type[j])) {
        // y -> ~z
        g[2 * y].push_back(2 * w + 1);
        g[2 * w].push_back(2 * y + 1);
      }
    }
  }
  // find the SCCs (Using Tarjan's algorithm, 
  //if i and i^1 exist in the same SCC, return false.
  // Code for SCC not included.
  return true;
}

string possible(int n, string type, vector < int > A, vector < int > B, vector < int > C) {
  set < int > relevantPrimes;
  for (int x: C) {
    int y = x;
    for (int p = 2; p * p <= y; p++) {
      if (y % p == 0) {
        relevantPrimes.insert(p);
        while (y % p == 0) {
          y /= p;
        }
      }
    }
    if (y != 1) {
      relevantPrimes.insert(y);
    }
  }
  int m = type.size();
  string mtype(m, '?');
  vector < int > mA(m), mB(m), mC(m);
  for (int p: relevantPrimes) {
    // solve min/max problem for a given prime number p.
    for (int i = 0; i < m; i++) {
      int y = C[i];
      int r = 0;
      while (y % p == 0) {
        r++;
        y /= p;
      }
      // the prime exponent is r = 0
      mA[i] = A[i];
      mB[i] = B[i];
      mC[i] = r;
      if (type[i] == 'G') {
        mtype[i] = 'm';
      } else {
        mtype[i] = 'M';
      }
    }
    if (!forPrime(mtype, mA, mB, mC)) {
      return "Solution does not exist";
    }

  }
  return "Solution exists";
}