Match Editorial

Match summary

This match attracted 1301 participants - 561 in Division I and 740 in Division II. Both divisions featured quite easy problemsets. The easy problem in Div-I was quite straightforward, 600-pointer required some insight to solve and 900-pointer was an exercise on using binary indexed trees. Petr was pretty fast and gained his 48th match victory even after scoring -25 during the challenge phase. His concurrents were quite close behind - ahyangyi with the fastest 600-pointer submission scored just 18.96 points less than Petr and took the second place. ACRush was the fastest on 900-pointer, but he had to resubmit the 600-pointer and lose many points because of this. With 125 points during the challenge phase he was able to claim the third position.

The winning receipt in Div-II was fast solving the Hard problem and having a couple of challenges. rudiso won the match exactly in this way. [G][U]nawan was the fastest on the Hard problem, but without any challenges it was only enough to claim the second spot. The third place was taken by lilu0355.

The Problems

Value	250
Submission Rate	662 / 740 (89.46%)
Success Rate	594 / 662 (89.73%)
High Score	dolphin.orca for 248.43 points (2 mins 15 secs)
Average Score	200.30 (for 594 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	554 / 740 (74.86%)
Success Rate	371 / 554 (66.97%)
High Score	Alex_KPR for 495.60 points (2 mins 41 secs)
Average Score	369.20 (for 371 correct submissions)

Value	250
Submission Rate	554 / 561 (98.75%)
Success Rate	474 / 554 (85.56%)
High Score	bmerry for 249.35 points (1 mins 27 secs)
Average Score	220.63 (for 474 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<Integer, Integer> memo = new HashMap<Integer, Integer>();

  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	900
Submission Rate	159 / 740 (21.49%)
Success Rate	30 / 159 (18.87%)
High Score	[G][U]nawan for 578.92 points (24 mins 11 secs)
Average Score	444.36 (for 30 correct submissions)

It's not hard to see that the required set doesn't exist in the following 2 cases:

• M is greater than the total amount of roads;
• the set of all roads is not connected.

If we don't have any of these 2 cases, a connected set of M roads can be constructed as follows. First find any spanning tree (it contains N-1 roads) and then add any M-N+1 free roads to this tree. However, there's one problem -- we've constructed an arbitrary connected set of M roads, but in fact we need to construct such set with the highest priority.

To find the set with the highest priority, let's make two fixes to the presented approach. First, find the spanning tree with the highest priority and then, add free roads with the highest priority. The second part (adding free roads) is trivial and to solve the first one it's convenient to use Kruskal's algorithm. That is, we assign each vertex into a separate component and check roads in the decreasing order of priority. If a road connects 2 cities from different components, we add it to the tree and merge these components together, otherwise we skip it.

Java implementation of this approach follows.

public class BestRoads {
  public int[] numberOfRoads(String[] roads, int M) {
    // initialization
    int N = roads.length;
    char[][] c = new char[N][N];
    for (int i=0; i < N; i++) c[i] = roads[i].toCharArray();

    // Kruskal's algorithm
    int[] id = new int[N];
    for (int i=0; i < N; i++) id[i] = i;
    int compCnt = N;
    int[] deg = new int[N];
    for (int i=0; i < N; i++)
      for (int j=i+1; j < N; j++) {
        if (c[i][j] == 'N' || id[i] == id[j]) continue;
        int idi = id[i], idj = id[j];
        M--; compCnt--;
        c[i][j] = 'N'; c[j][i] = 'N';
        deg[i]++; deg[j]++;
        for (int t=0; t < N; t++) if (id[t] == idi) id[t] = idj;
      }

    // the set of all roads is not connected
    if (compCnt > 1) return new int[] {};

    // adding free roads
    for (int i=0; i < N; i++)
      for (int j=i+1; j < N; j++)
        if (c[i][j] == 'Y' && M > 0) {
          M--;
          c[i][j] = 'N'; c[j][i] = 'N';
          deg[i]++; deg[j]++;
        }

    // M is greater than the total number of roads
    if (M != 0) return new int[] {};

    // return result
    return deg;
  }
}

Value	600
Submission Rate	239 / 561 (42.60%)
Success Rate	106 / 239 (44.35%)
High Score	ahyangyi for 554.99 points (8 mins 13 secs)
Average Score	349.02 (for 106 correct submissions)

Let's describe the state of our character by three parameters: (current strength, current intellect, current free points). Here free points are those points that the character obtained and not yet has distributed to his parameters. Initial state of the game is (1, 1, 0). The following two simple observations are crucial to solving the problem:

1. If our current parameters allow to complete a mission, it always makes sense to complete it. That is almost obvious, we lose nothing and gain more free points.
2. Current free points are uniquely determined by current strength and intellect. Let the current state be (S, I, P). By the previous observation we can easily calculate the number of gained points: it's the sum of points[i] by all missions that we are able to complete with strength S and intellect I. Out of these gained points, exactly S+I-2 needed to raise strength and intellect to S and I. All the other points are free and this number can be uniquely determined.

The second observation allows us to present the state as (current strength, current intellect). Now it's clear that the character's algorithm looks basically as follows:

Set strength=1, intellect=1, free points=0;
While True
  Complete all possible missions that are not completed yet
  If there is no free points, break
  Make a decision: increase strength or intellect by 1
End While

Our goal is to make decisions in such way that allows to complete the maximum number of missions. Note that this number is also uniquely determined by our final strength and intellect, so in fact it's enough to find which pairs (strength, intellect) the character can achieve and which he can't. After this, we can just choose the pair (strength, intellect) which is possible to achieve and which allows to complete the maximum number of missions.

Let can(S, I) be true, if it's possible to achieve strength S and intellect I. Let's also freePnt(S, I) be the number of free points the character has if he achieved strength S, intellect I and completed all possible missions. When discussing the second observation, we gave the way to calculate freePnt(S, I). To calculate can(S, I), we can use the following reccurrence:

Can(1, 1) = true
Can(S, I) = true, if:
  a) S > 1, freePnt(S-1, I) > 0 and can(S-1, I)
or
  b) I > 1, freePnt(S, I-1) > 0) and can(S, I-1)

The idea of this reccurrense is easy: to obtain strength S and intellect I, we must be able to either obtain strength S-1 and intellect I and then increase strength by 1, or to obtain strength S and intellect I-1 and then increase intellect by 1.

Java implementation of this approach is presented below.

public class StrengthOrIntellect {
  public int numberOfMissions(int[] strength, int[] intellect, int[] points) {
    boolean[][] can = new boolean[1001][1001];
    int[][] freePnt = new int[1001][1001];
    int res=0;
    for (int S=1; S<=1000; S++)
      for (int I=1; I<=1000; I++) {
        freePnt[S][I] = 2 - S - I;
        int missionCnt = 0;
        for (int x=0; x < strength.length; x++)
          if (strength[x] <= S || intellect[x] <= I) {
            freePnt[S][I] += points[x];
            missionCnt++;
          }
        can[S][I] = (S == 1 && I == 1 ||
                     S > 1 && can[S-1][I] && freePnt[S-1][I]>0 ||
                     I > 1 && can[S][I-1] && freePnt[S][I-1]>0);
        if (can[S][I]) res = Math.max(res, missionCnt);
      }
    return res;
  }
}

Value	900
Submission Rate	157 / 561 (27.99%)
Success Rate	69 / 157 (43.95%)
High Score	ACRush for 870.42 points (5 mins 16 secs)
Average Score	522.28 (for 69 correct submissions)

In order to solve this problem, we need a structure that stores the information about some array A[1..N] of integers, initially filled by zeros, and is able to perform two types of operations:

1. Set A[pos] := A[pos] + value (where value and pos are given and value can be of arbitrary sign).
2. Calculate sum(A, l, r) = A[l] + A[l+1] + ... + A[r-1] + A[r] (where l and r are given).

We need this structure to perform both operations in time O(log N). The way to achieve this is to use Binary Indexed Trees (BIT). For those not familiar with BITs, please look at the following tutorial.

In our solution we will use two BITs indexed 1..L. The first one is called cnt and cnt[i] is the number of currently planted trees having a coordinate i (we increase all coordinates by 1 to fit them into interval [1..L]). The second tree is called dst and dst[i] = cnt[i] * i. In other words, dst[i] is the sum of coordinates of all trees planted at point i.

Suppose we want to plant a tree at point x[i] and wish to calculate its price in a fast way. There are CL = sum(cnt, 1, x[i]-1) trees located to the left of x[i]. Each of these tree with coordinate x₀ is located on distance x[i] - x₀ from our tree. So, the sum of all distances is CL * x[i] - sum(all x₀) = CL * x[i] - sum(dst, 1, x[i]-1). Similarly, there are CR = sum(cnt, x[i]+1, L) trees located to the right of x[i] and the sum of distances for them is sum(dst, x[i]+1, L) - CR * x[i]. So the total price of the tree can be calculated as follows:

price = x[i] * (sum(cnt, 1, x[i]-1) - sum(cnt, x[i]+1, L)) +
        sum(dst, x[i]+1, L) - sum(dst, 1, x[i]-1)

After the price is calculated, we just need to update cnt and dst: cnt[x[i]] := cnt[x[i]] + 1, dst[x[i]] := dst[x[i]] + i. The overall complexity of this approach is O(N * logL), which is fine to fit within the time limit.

public class ProductOfPrices {
  long[] sumDst = new long[200001];
  long[] sumCnt = new long[200001];

  // BIT operations implementation
  void add(long[] s, int pos, int value) {
    while (pos <= 200000) {
      s[pos] += value;
      pos |= pos - 1;
      pos++;
    }
  }

  long getSum(long[] s, int pos) {
    long res = 0;
    while (pos > 0) {
      res += s[pos];
      pos &= pos - 1;
    }
    return res;
  }

  long getSum(long[] s, int l, int r) {
    if (l > r) return 0;
    return getSum(s, r) - getSum(s, l - 1);
  }

  public int product(int N, int L, int X0, int A, int B) {
    int[] x = new int[N];
    x[0] = X0 % L;
    for (int i=1; i < N; i++)
      x[i] = (int)(((long)x[i-1] * (long)A + (long)B) % L);

    long res = 1;
    add(sumDst, x[0] + 1, x[0] + 1);
    add(sumCnt, x[0] + 1, 1);
    for (int i=1; i < N; i++) {
      long price = (long)(x[i] + 1) * (getSum(sumCnt, 1, x[i]) -
                                       getSum(sumCnt, x[i]+2, L))
                   - getSum(sumDst, 1, x[i]) + getSum(sumDst, x[i]+2, L);
      price %= 1000000007;
      res = (res * price) % 1000000007;
      add(sumDst, x[i] + 1, x[i] + 1);
      add(sumCnt, x[i] + 1, 1);
    }

    return (int)res;
  }
}