SRM 675

Match Summary

Round Overview
Discuss this match

LengthUnitCalculator

There are many ways to solve this problem. We could just hardcode each of the possible conversions, with four units there are only 16 possible conversions. We would need 16 if-then-elses to detect each case but it is doable.

Let’s look for a simple way to implement this. One method would be to pick an intermediary unit. We always convert the given amount to that unit before converting from that unit to the wanted unit. This way we only need to hard-code 8 conversions: All of those between and to the intermediary unit we picked. In fact, since it is possible that the intermediary unit matches the initial or target unit we only need 6 conversions.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
double calc(int amount, string fromUnit, string toUnit) {
  double res = amount;
  // convert to inches:
  if (fromUnit == "ft") {
    res *= 12.0;
  }
  if (fromUnit == "yd") {
    res *= 12.0 * 3.0;
  }
  if (fromUnit == "mi") {
    res *= 12.0 * 3.0 * 1760.0;
  }
  // convert from inches:
  if (toUnit == "ft") {
    res /= 12.0;
  }
  if (toUnit == "yd") {
    res /= 12.0 * 3.0;
  }
  if (toUnit == "mi") {
    res /= 12.0 * 3.0 * 1760.0;
  }
  return res;
}

We can get clever and try to implement this without such hard coding. Since the units are in succession (inches are smaller than feet, feet are smaller than yards and yards smaller than miles), we can identify which unit is smaller than the other and think of conversions as moving from smaller units to larger units or vice versa.

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
double calc(int amount, string fromUnit, string toUnit) {
  // assing an id to each unit so we know which is smaller than another
  map < string, int > unit_id = {
    {
      "in",
      0
    },
    {
      "ft",
      1
    },
    {
      "yd",
      2
    },
    {
      "mi",
      3
    },
  };

  // unit (i+1) is equal to factors[i] times unit (i). 
  vector < double > factors = {
    12.0,
    3.0,
    1760.
  };

  int a = unit_id[fromUnit];
  int b = unit_id[toUnit];
  double res = amount;
  // to move to larger units, divide:
  while (a < b) {
    res /= factors[a];
    a++;
  }
  // to move to smaller units, multiply:
  while (a > b) {
    res *= factors[a - 1];
    a--;
  }
  return res;

}

ShortestPathWithMagic

Normally in a problem where we have to find the shortest path between some vertices (cities) and weighted edges (roads) between the vertices we can use Dijkstra’s algorithm (for example). The potions make the problem special in which you can halve the length of some of the edges.

The potions don’t make the problem as special as it might first seem. In the version of the problem without potions, we move from a city a to a city b. In the real problem might use some potions. Moving from city a to city b with a potion is not the same as not using the potion. The edge cost is halved, but also the state changes. We were in city a and had r potions left, and after moving we are in city b with r-1 potions left. If we choose not to use the potion, we end up in city b with r potions left. We can consider each pair (city, number of remaining potions) as a vertex in this problem instead of just using the cities as vertices. This means we want to find the shortest path between (city 0, 0 potions) to (city 1, any number of potions) . Any number of potions is valid for the final vertex, because maybe it is not necessary to use all the potions (for example, if the number of edges in the path is smaller than the number of potions).

Once we use (city, number of remaining potions) as vertices all that remains in the problem is to implement a shortest paths algorithm . Dijkstra works well in this case. There are O(nk) vertices and each vertex has O(n) edges (n edges without using potions and n edges with potions) so the number of edges is O(n^2 k). The usual Dijkstra implementation will need O( log(nk)( nk + n^2 k) ) time.

A slight complication is that the distances may not be integer (when halving a road of odd length). This might make the Dijkstra hard to implement. We can fix this by solving the problem using edges of double the real size and then halving it again once the minimum distance is found.

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
double getTime(vector < string > dist, int k) {
  int n = dist.size();
  const int INF = 10000;

  vector < vector < int >> shortest(n, vector < int > (k + 1, INF));

  // Dijkstra:

  // We can use a std::set for Dijkstra, of course a priority_queue works
  // as well, but sets allow us to remove elements which makes the algo
  // O(|V|) in memory as opposed to O(|E|), this doesn't matter in this
  // problem.
  //
  // set contains pairs (distance, vertex), this way the smallest element
  // in the set will be the one with smallest distance.
  set < tuple < int, int, int > > Q;

  // The act of pushing an element (x,r) with distance d to the Dijkstra queue
  auto push = [ & ](int d, int x, int r) {
    if (shortest[x][r] > d) {
      // distance was larger than recorded, update:
      auto it = Q.find(make_tuple(shortest[x][r], x, r));
      if (it != Q.end()) {
        Q.erase(it); //erase the previous element from the set
      }
      // update
      shortest[x][r] = d;
      Q.insert(make_tuple(shortest[x][r], x, r));
    }
  };

  // begin by pushing (0,k):
  push(0, 0, k);
  while (Q.size() != 0) {
    auto it = Q.begin();
    int d, x, r;
    tie(d, x, r) = * it;
    Q.erase(it);
    // move from (x,r) to (y, something):
    for (int y = 0; y < n; y++) {
      int dxy = (int)(dist[x][y] - '0');
      if (r > 0) {
        // use a potion
        push(d + dxy, y, r - 1);
      }
      // don't use a potion:
      push(d + 2 * dxy, y, r);

      // costs are doubled, we will need to half them later
    }
  }

  // the minimum distance to (vertex 1, some r)
  int res = INF;
  for (int i = 0; i <= k; i++) {
    res = std::min(res, shortest[1][i]);
  }
  return res / 2.0;
}

TreeAndPathLength2

We need to think of an approach that tries to build a tree with the desired specifications but without missing any kind of tree shape so that we can be sure that if we don’t find a tree with s length 2 paths we can be sure that such tree doesn’t exist.

Let’s start with the simplest tree shape and try to see what happens if we add nodes to different positions of it:

Just n-1 nodes that are direct children to the root. The only length-2 paths are between the leaves, every unordered pair of leaves makes a path so that is: s = (n-2)(n-1)/2. We can try every value of n as a starting setting and then see what happens when we add a node, then add more nodes and so and so. There are two ways to add a node in this case:

If we add the new node to one of the leaves, the number of length-2 paths increases by just 1. If we instead add the new node to the root, the number of paths increases by n-1. It’s interesting that adding a node to a leaf always increases the number of length-2 paths by 1. This is true regardless of the shape of the tree, as long as they are leaves. This can be generalized to adding i nodes as children to a leaf: If we add i nodes as children to what was previously a leaf this creates i new length-2 paths between the leaf’s parent and the new leaves. It also adds some new paths between the new leaves: (i(i-1))/2. So in total if we choose to add i nodes as children to a leaf this increases s by i + (i(i-1))/2 and n by i. Note that it doesn’t matter which of the leaves we pick, the result is the same for any leaf. The number of leaves in the tree also changes: If we previously had o leaves, the number of leaves changes to o - 1 + i, because the leaf we added nodes to stopped being a leaf but we also added i new ones. Therefore we can describe the shape of a tree by 3 integers:

• n : The current number of nodes.

• o: The number of leaves.

• s: The number of paths of length 2

Given any tree (n,o,s), we can pick any of the leaves and add i children to it. This changes the tree to : (n+1, o-1 + i, s + i + (i*(i-1))/2). We have known starting trees that we know to be valid: (j+1, j, (j(j-1))/2) to each valid tree, we can try all the values i of nodes to add to a leaf, this lets us find new valid trees. This is a depth-first search where (n,o,s) are vertices in the graph of valid trees. If any of the valid trees has the wanted values of n and s, then the answer is “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
28
29
30
31
32
33
34
35
36
37
int N, S;

bool visited[51][51][1001];

void dfs(int n, int o, int s) {
  if (!visited[n][o][s]) {
    visited[n][o][s] = true;
    // take a leaf and add children
    for (int i = 1; n + i <= N; i++) {
      int ns = s + i + i * (i - 1) / 2;
      if (ns <= S) {
        dfs(n + i, o - 1 + i, ns);
      }
    }
  }
}

string possible(int n, int s) {
  this - > N = n;
  this - > S = s;

  // the number of children for the root:
  for (int i = 1; i + 1 <= n; i++) {
    int ns = i * (i - 1) / 2;
    if (ns <= S) {
      dfs(i + 1, i, ns);
    }
  }

  for (int i = 0; i <= n; i++) {
    if (visited[n][i][s]) {
      return "Possible";
    }
  }

  return "Impossible";
}

TreeAndPathLength3

We are looking for a method that can generate the tree we want and it should be guaranteed to find a tree for each of the possible inputs (1 <= s <= 10000). The tree shape can be anything as long as the number of length-3 paths is s and the number of nodes doesn’t exceed n. We should also aim to finding a method that is as simple to implement as possible.

The limit for n is significantly smaller than the limit for s. When you think of a simple line of vertices, each new vertex adds a single length-3 path to the tree. It would need too many vertices to reach s ~= 10000. So we need to think of a shape that can implement in multiplication instead of in addition. It is possible to have a multiplication a times b in a tree shape:

In this shape, there are two center vertices connected to each other. The left vertex is connected to a other vertices and the right vertex is connected to b other vertices. The total number of length-3 paths is a times b (Every path starting with any of the a left vertices and ending with any of the b right vertices is of length-3)

This gives us a way to find trees of a + b + 2 elements that have s = ab. So for example if s = 1026, we can do a = 32 and b = 32. This won’t work when s is prime or if the only factors of s are such that one would be too large. We can’t find appropriate a and b for s = 3029, because the only factors of 3027 are 3 and 1009, b would be too large for 500 vertices.

Remember the addition. What if we had something like s = ab + c, it 's easier to find proper values of a, b and c for any s that way. In the linear tree version, we added a single length-3 path every time we added a new vertex to the line. This time there’s more places in the shape, but we can add a line of vertices and reach that same state:

The shape of the tree is similar to the one before but this time there is a line of c vertices attached to one of the b vertices that there were before. The line of c vertices does interesting things to s. There is a difference between the very first beginning of the line and the other vertices.

• There are b - 1 new length-3 paths between the start of the line, the vertex attached to the line and each of the other b-1 vertices in the right side.

• For each of the c vertices, there is also a length-3 path that starts with it and ends to its left.

In this shape, there are (a times b) + (b - 1) + c length-3 paths. However, we can generalize and imagine what happens when c = 0, when c = 0, there are only (a times b) paths. So we have this formula based on 3 numbers such that a + b + c + 2 = n <= 500 and (a times b) + (b - 1) + c = s or (a times b) = s if c = 0. For every s, there should always be at least one solution to this equation. Let’s try to prove it.

• There is a case in which s is not prime and it has two factors a, b such that ab = s and a + b + 2 <,= 500. In this case a solution exists where c = 0. This takes care of special cases like s = 1 or 2, in fact, this takes cares of all cases in which s is small. For c = 0, b = 1, then we have a solution for any s <= 498.

• So let’s worry about cases where c != 0. We have s = ab + (b - 1) + c = ab + b + c - 1 = b(a + 1) + c - 1. So s + 1 should be equal to b (a+1) + c. We can do a name change with S = s + 1 and A = a + 1. We now that S is between 2 and 10001. We need to find three integers A, b, c such that A + b + c + 1 <= 500 and Ab + c = S. We can work under the assumption that S is large (since small S are covered by the previous condition). There is a lot of freedom here, we can aim towards having A = b ~= sqrt(S) and then c ~= S - (|__sqrt(S)__|)^2, this guarantees that A, B and c will be at most sqrt(S), at most 100, which will nicely fit in the constraints for A + b + c + 1 <= 500 .

Code

First find proper values for a, b and c, using 3 nested loops. Then with the picked values, build a tree using the shape described above.

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
// construct a tree    
vector < int > construct(int a, int b, int c) {
  int n = a + b + c + 2;
  vector < int > res;
  // 0 - (a-1) each connected to n-1
  // (n-2) connected to (a ... a+b - 1)
  // (a+b-1) connected to (a+b)
  // (a+b) <-> (a+b+1) <-> ... (a+b+c-1)

  for (int i = 0; i < a; i++) {
    res.push_back(i);
    res.push_back(n - 1);
  }
  res.push_back(n - 1);
  res.push_back(n - 2);
  for (int i = a; i < a + b; i++) {
    res.push_back(n - 2);
    res.push_back(i);
  }
  for (int i = a + b; i < a + b + c; i++) {
    res.push_back(i - 1);
    res.push_back(i);
  }
  return res;
}

vector < int > construct(int s) {
  // find proper a,b and c:
  for (int a = 1; a <= 500; a++) {
    for (int b = 1; b <= 500; b++) {
      for (int c = 0; a + b + c + 2 <= 500; c++) {
        if (b * a + c + ((c > 0) ? (b - 1) : 0) == s) {
          return construct(a, b, c);
        }
      }
    }
  }
  return {};
}

LimitedMemorySeries1

We have a 1MB memory limit and a 10 seconds time limit. So let’s try to make the best of that megabyte.

The size of the array can be very large so we cannot store it in memory. However, we can iterate through all the elements of the array multiple times. With this, we can treat the queries separately. Try each q independently of the others. We only need to be able to do each query in at most 0.1 seconds (The total time limit is 10 seconds).

When dealing with large inputs an interesting work around is to think of finding an approach that needs only O(sqrt(N)) of time (or this time memory). This can sometimes be done by dividing the problem in two sub-problems, each needing O(sqrt(N)) time.

By looking at the generator algorithm and constraints, we can see that the elements of the array will all be between 0 and 1000000006, inclusive. The problem requires us to find the q-th smallest element, which will be a number between 0 and 1000000006. Let’s instead try estimating the value. For example, how about thousands? Is the number between 0 and 999, or 1000 and 1999 or 345000 and 345999?

Let’s divide the space of possible numbers in groups of M elements each. So we have the following groups: [0, M - 1], [M, 2M - 1], [2M, 3M - 1], … , [iM, (i+1)M - 1]. Can we identify which of those groups the q-th element will belong to? Let’s say the q-th element belongs to group #p. This means that the q-th element is greater than or equal to pM and less than (p+1)M. This all depends on the number of elements in the array that are smaller than pM. Let’s say the total number of elements smaller than pM is c. This means that any element greater than or equal to pM will have at least c elements before it. The q-th element needs to have exactly q elements before it. It follows that q >= c. p is the largest number for which q >= c , where c is the number of elements smaller than pM. Alternatively, if c is the number of elements smaller than pM and p_n is the number of elements between pM and (p+1)M-1m then c <= q < c + p_n. We can calculate c for each p as we iterate from p = 0 upwards. Note that the upper bound for p will be around 1000000006 / M.

Once we identify p, we know that the q-th largest element will be between pM and (p+1)M - 1. How can we find the exact value? There are now only M possible values. We can once again count the number of elements that belong to each possible value. Know that there are c elements smaller than pM and we also know how many times each of the M elements appears in the array, we can now use the same method as before to identify the exact q--th element.

To count the number of elements in each group, we need to iterate through the elements using the generator. The same happens when we need to count the number of elements equal to each of the M candidates.

So let’t talk about time and memory requirements. To find the number of elements in each of the groups of size M, we will need an array of around 1000000006 / M elements. Then to find the number of elements equal to each of the M candidates, we need an array of size M. If M is small then 1000000006 / M will be large and vice versa. We need the two values to be balanced, so we can instead use M ~= sqrt(1000000006) (For simplicity, let’s use M = 32000. So now we have a guarantee. We need two arrays and each will be of size 32000. The memory in MB used by two arrays of 32000 four byte values is: 2 * 32000 * 4 // 1024 // 1024 ~= 0.24 which should be appropriate.

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
long getSum(int n, int x0, int a, int b, vector < int > query) {
  // There are two situations in which we need to iterate through all
  // the elements using the generator. We could implement the generator
  // twice, or we can use lambdas. Okay... Lambdas don't make the code
  // intuitive, but they do simplify things. There is a non-lambda version
  // below.

  // first, create a function for_each_num that takes a function f.
  // f is a function that takes a integer, it will be called for each
  // generated element 
  auto for_each_num = [ & ](std:: function < void(int) > f) {
    int x = x0;
    for (int i = 0; i < n; i++) {
      f(x); // call the supplied function
      x = (int)((x * (long) a + b) % 1000000007);
    }
  };

  // interestingly, using two vector<int>s would use too much memory.
  // There's some overhead in the std::vector implementation
  int partition_count[32000];
  fill(partition_count, partition_count + 32000, 0);
  int partition_numbers[32000];

  // for each of the generated elements, find its 32000 element section
  // and increment its count:
  for_each_num([ & ](int x) {
    partition_count[x / 32000]++;
  });
  long sum = 0;
  for (int q: query) {
    // find the partition:
    int acum = 0;
    int p = -1;
    int before = 0;
    for (int i = 0; i < 32000; i++) {
      if (acum <= q && q < acum + partition_count[i]) {
        p = i;
        before = acum;
      }
      acum += partition_count[i];
    }

    fill(partition_numbers, partition_numbers + 32000, 0);
    // for each generated element, if it's in the wanted partition
    // increment the count of numbers equal to that element:
    for_each_num([ & ](int x) {
      if (p * 32000 <= x && x < (p + 1) * 32000) {
        partition_numbers[x - p * 32000]++;
      }
    });
    // use the same trick to find the exact element:
    acum = before;
    int r = -1;
    for (int i = 0; i < 32000; i++) {
      if (acum <= q && q < acum + partition_numbers[i]) {
        r = p * 32000 + i;
      }
      acum += partition_numbers[i];
    }
    sum += r;
  }

  return sum;
}

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
long getSum(int n, int x0, int a, int b, vector < int > query) {
  // interestingly, using two vector<int>s would use too much memory.
  // There's some overhead in the std::vector implementation
  int partition_count[32000];
  fill(partition_count, partition_count + 32000, 0);
  int partition_numbers[32000];

  // for each of the generated elements, find its 32000 element section
  // and increment its count:
  int x = x0;
  for (int i = 0; i < n; i++) {
    partition_count[x / 32000]++;
    x = (int)((x * (long) a + b) % 1000000007);
  }

  long sum = 0;
  for (int q: query) {
    // find the partition:
    int acum = 0;
    int p = -1;
    int before = 0;
    for (int i = 0; i < 32000; i++) {
      if (acum <= q && q < acum + partition_count[i]) {
        p = i;
        before = acum;
      }
      acum += partition_count[i];
    }

    fill(partition_numbers, partition_numbers + 32000, 0);
    // for each generated element, if it's in the wanted partition
    // increment the count of numbers equal to that element:
    x = x0;
    for (int i = 0; i < n; i++) {
      if (p * 32000 <= x && x < (p + 1) * 32000) {
        partition_numbers[x - p * 32000]++;
      }
      x = (int)((x * (long) a + b) % 1000000007);
    }

    // use the same trick to find the exact element:
    acum = before;
    int r = -1;
    for (int i = 0; i < 32000; i++) {
      if (acum <= q && q < acum + partition_numbers[i]) {
        r = p * 32000 + i;
      }
      acum += partition_numbers[i];
    }
    sum += r;
  }

  return sum;
}