Match Editorials

Match summary

This TCHS match turned out to be quite easy - out of 87 participants, 42 solved the Hard and 31 solved all three problems. Within such conditions, coding speed was the deciding factor. Young 13-year old tourist showed excellent performance and took the first place. For the second HS SRM in a row he makes the fastest submission times on *all* problems! anastasov.bg and UranusX were just a bit slower and took the second and third places, respectively.

The Problems

Value	250
Submission Rate	83 / 87 (95.40%)
Success Rate	75 / 83 (90.36%)
High Score	tourist for 249.50 points (1 mins 16 secs)
Average Score	222.24 (for 75 correct submissions)

As it often happens with DivII-Easy problems, to solve this one you just need to implement everything from the statement properly. One of the ways to do it is as follows:

1. Construct a string AZ containing all 'A'/'Z' characters from spell, in order. For example, it would be "AZAZAA" for spell=AABZCADZA.
2. Set current position to be the last character of the AZ string. Iterate through the characters of spell, from left to right. If the next character is not 'A' or 'Z', just append it to result. Otherwise, append the character from AZ at current position to result and decrease current position by 1. (In other words, current position iterates by characters of AZ from right to left and therefore includes them into result in the reversed order.)

Java implementation of this approach can look as follows:

public class MagicSpell {
  public String fixTheSpell(String spell) {
    // step 1
    String az="";
    for (int i=0; i<spell.length(); i++)
      if (spell.charAt(i)=='A' || spell.charAt(i)=='Z')
        az += spell.charAt(i);

    // step 2
    String res="";
    int pos = az.length()-1;
    for (int i=0; i<spell.length(); i++)
      if (spell.charAt(i)=='A' || spell.charAt(i)=='Z')
        res += az.charAt(pos--);
      else
        res += spell.charAt(i);
    return res;
  }
}

Value	500
Submission Rate	82 / 87 (94.25%)
Success Rate	57 / 82 (69.51%)
High Score	tourist for 498.59 points (1 mins 31 secs)
Average Score	422.43 (for 57 correct submissions)

This problem allows for many different approaches. Let's present 3 of them.

1. Memoization. Let F(X) be the smallest number of digits required to obtain the product X. Obviously, we need to find F(N). There's a following simple reccurrence to calculate F(X). If X < 10, then F(X) = 1 (one digit is enough). Otherwise, iterate through all digits d from 2 to 9 (it never makes sense to use digit 1 because it doesn't change the product of digits), inclusive, such that X is divisible by d and try to use d as a first digit of our number. If d is a first digit, then the product of the rest must be X/d and it requires F(X/d) digits to fill the rest. Therefore, F(X) = min{F(X/d) + 1} by all d, 2 ≤ d ≤ 9, such that X is divisible by d.

Having such a reccurrence, we have two ways to evaluate it. The first is to create a table F of size N and to calculate values F[1], F[2], ..., F[N], in order. Unfortunately, N can be as large as 10^9 what makes this approach impossible. The other approach is to use recursion with memoization. Let's estimate the number of states that will be visited if we calculate F(N) in such way. Note that digits from 2 to 9 have only primes 2, 3, 5 and 7 in their factorization. Therefore if N = 2^A * 3^B * 5^C * 7^D * n, each recursive call will be made for a number representable as 2^a * 3^b * 5^c * 7^d * n, where 0 ≤ a ≤ A, 0 ≤ b ≤ B, 0 ≤ c ≤ C, 0 ≤ d ≤ D. It means that the number of recursive calls is at most (A+1)*(B+1)*(C+1)*(D+1) ≤ (29+1)*(18+1)*(12+1)*(10+1) = 81,510. So the number of visited states is not very large and memoization approach will easily run in time.

Java implementation of this approach follows.

import java.util.*;

public class ProductOfDigits {
  Map memo = new HashMap();

  int solve(int N) {
    if (N<10) return 1;
    if (memo.containsKey(N)) return memo.get(N);
    int res = 1000;
    for (int i=2; i<=9; i++)
      if (N%i==0) res = Math.min(res, solve(N/i)+1);
    memo.put(N, res);
    return res;
  }

  public int smallestNumber(int N) {
    return solve(N) == 1000 ? -1 : solve(N);
  }
}

2. Case analysis. This approach works in O(1), but is somewhat harder to come with. Let's represent N as 2^A * 3^B * 5^C * 7^D * n. If n > 1, then N is not representable as a product of digits (all digits have only primes 2, 3, 5, 7 in their factorization). Let's assume that n = 1. There's only one digit divisible by 7 -- it's 7 itself. Similarly, only 5 itself is divisible by 5. Therefore to obtain 5^C * 7^D we have only one choice -- to include C 5s and D 7s into our number.

Now let's find the best way to obtain 2^A * 3^B.

Lemma. If B > 1, then there's an optimal solution that contains digit 9.

Proof. Suppose there's no optimal solution that contains 9. Then we have at least one of the following possibilities.

• The optimal solution contains 3 and 3. In this case we can replace these two 3s by one 9 and obtain a solution with a smaller number of digits. Contradiction.
• The optimal solution contains 3 and 6. We can replace them by 2 and 9 thus obtaining an optimal solution that contains 9. Contradiction.
• The optimal solution contains 6 and 6. We can replace them by 4 and 9. Contradiction.

End of proof.

In a similar way we can prove that if A > 2, then there's an optimal solution that contains digit 8. Therefore we can safely include floor(A/3) 8s and floor(B/2) 9s in our solution and what's left is only to solve the case when A ≤ 2 and B ≤ 1. In this case there are only 6 possibilities: 1 requires 0 digits (having 1 means that we've already obtained the required product using 5s, 7s, 8s and 9s), 2, 3, 4 and 6 require 1 digit and 12 requires 2 digits. Here it's important to not forget about the following corner case: if N is initially 1, it requires 1 digit instead of 0.

This solution can be implemented in Java in the following way.

public class ProductOfDigits {    
  public int smallestNumber(int n) {
    if (n==1) return 1;
    int res = 0;
    int n2 = 0;
    int n3 = 0;
    while (n%2==0) {
      n/=2;
      n2++;
    }
    while (n%3==0) {
      n/=3;
      n3++;
    }
    while (n%5==0) {
      n/=5;
      res++;
    }
    while (n%7==0) {
      n/=7;
      res++;
    }
    if (n>1) return -1;

    res+=n3/2;
    n3%=2;
    res+=n2/3;
    n2%=3;
    if (n3+n2==3)
      res+=2;
    else if (n3+n2>0)
      res++;

    return res;
  }
}

3. Greedy. It appears that the following greedy algorithm works correctly. Iterate through digits 9 to 2, in decreasing order. For each digit, use it until N is divisable by it. The algorithm has very simple implementation and intuitively seems to be correct, however, as always with greedy algorithms, one needs to be very accurate and it's better to prove the correctness formally.

public class ProductOfDigits {
  public int smallestNumber(int N) {
    if (N == 1)
      return 1;
    int p = 0;
    for (int i = 9; i >= 2; i--)
      while (N % i == 0) {
        p++;
        N /= i;
      }
    return (N > 1) ? -1 : p;
  }
}

Excercises.

1. Suppose the problem would be stated not in decimal system, but in system with base B. That is, you need to find the smallest amount of numbers, each between 1 and B-1, inclusive, such that their product is N. Will the same greedy algorithm as in approach 3 work correctly for every value of B? In case of negative answer, what is the smallest value of B for which it doesn't work correctly?

2. Solve the following generalized version of the problem: find the smallest integer X such that the product of its digits in decimal notation is exactly N.

Value	1000
Submission Rate	63 / 87 (72.41%)
Success Rate	42 / 63 (66.67%)
High Score	tourist for 972.16 points (4 mins 50 secs)
Average Score	711.94 (for 42 correct submissions)

Let's consider a simplified version of the problem, where we can assign different programs to different robots. In this version, if two robots start in different connected components of the maze, we certainly can't bring them to the same cell. And for all robots starting in the same connected component, they can be moved into the same position. To do this, just choose an arbitrary cell from the component and assign a program to each robot that makes him move the path from his starting position to the chosen cell. So, in order to solve this version, we need to find connected components using BFS or DFS and to choose the component which contains the maximum amount of 'R' cells. This amount will be the answer.

Now what changes when we return to the original problem? The answer may seem surprising at the first glance. Absolutely nothing changes. Still, robots from different components can't be brought into the same cell and all robots from the same component can be moved into the same position. The first fact is still obvious, but the second one is far from being obvious. Coders have two different ways of dealing with the second one. They can experiment with several examples and just trust that this is always true. Or they can come with a formal proof. Of course, the second way is safer, but at the same time it's harder and requires more thinking time.

Let us give a simple and nice proof of this fact (the idea of the proof belongs to Gluk, the problem writer).

Theorem. If two robots start from cells A and B and there's a path between these cells, then there's a program that moves both robots into the same cell.

Proof. Let L be the length of the shortest path between A and B. It's enough for us to find a procedure that allows to shorten the length of the shortest path between the robots on at least one cell. Then we can just apply this procedure at most L times and the length of the shortest path between the robots will be 0, i.e. they will be in the same cell.

The required procedure can work as follows. Let's make both robots move a shortest path from A to B. One of the robots (that starts at A) will certainly not encounter a wall during these moves. The other robot can encounter a wall, but as only his next move leads to a wall, the shortest distance between the robots becomes at least one cell smaller (the first robot comes a cell closer, while the second one stays in place), so we can stop the procedure immediately after this. If the other robot also never encounters a wall, it's possible that the length of the shortest path is still the same. If this is the case, let's make again both robots move a shortest path between them (note that this path is still the same as from A and B). Repeat moving the shortest path until the second robot encounters a wall. Note that this procedure can't last forever, because the maze is finite and each time we move robots along the shortest path between them, we shift both of them on the same vector A->B. End of proof.

Java implementation that uses DFS is provided below.

public class ProgrammingRobots {
  int N, M;
  int[] dx = new int[] {-1,1,0,0};
  int[] dy = new int[] {0,0,-1,1};
  boolean[][] used;
  int cnt = 0;

  void dfs(String[] maze, int i, int j) {
    used[i][j]=true;
    if (maze[i].charAt(j)=='R') cnt++;
    for (int t=0; t<4; t++)
      if (i+dx[t]>=0 && i+dx[t]<N && j+dy[t]>=0 && j+dy[t]<M &&
          maze[i+dx[t]].charAt(j+dy[t]) != '#' && !used[i+dx[t]][j+dy[t]])
        dfs(maze, i+dx[t], j+dy[t]);
  }

  public int numberOfRobots(String[] maze) {
    this.N=maze.length; this.M=maze[0].length();
    used = new boolean[N][M];
    int res = 0;
    for (int i=0; i<N; i++)
      for (int j=0; j<M; j++)
        if (maze[i].charAt(j) != '#' && !used[i][j]) {
          cnt = 0;
          dfs(maze, i, j);
          if (cnt>res) res=cnt;
        }
    return res;
  }
}