Match Editorial

Match summary

This SRM featured sets of an average difficulty in both divisions. In Div-I, the battle for the first place arose between Psyho, author of the fastest 900-pointer, and Petr, author of the fastest 600-pointer. Psyho was the first after the coding phase and strengthened his lead on the very beginning of the challenge phase by making +50. However, than Petr retook the lead by making two successfull challenges. Psyho didn't give up and, 4 (!!) seconds before the end of the challenge phase, he reclaimed his lead by making another successfull challenge and leaving Petr on the second place. The excellent performance allowed Psyho to get 126 rating points and become a target. Congratulations to Psyho with very nice match, his first SRM victory and becoming a target! Third place went to Petr who was behind Petr on slightly more than 200 points.

In Div-II, the first three places were taken by -AlexandeR-, Tomik and happywy. All of them solved all three problems. Newcomer DanilaVas9ev made the fastest submission on 1000-pointer, but took just 7th place because his submission on 500-pointer failed systests.

The Problems

Value	250
Submission Rate	554 / 627 (88.36%)
Success Rate	468 / 554 (84.48%)
High Score	BrainDeveloper for 245.46 points (3 mins 52 secs)
Average Score	189.29 (for 468 correct submissions)

The solution for this problem can be broken in two parts. First, let's implement the method which takes two names and calculates the probability of love between them. The implementation directly follows the problem statement:

int loveProb(String a, String b) {

  String s=a+b;

  int L=0, O=0, V=0, E=0;

  for (int i=0; i<s.length(); i++) {

    if (s.charAt(i)=='L') L++;

    if (s.charAt(i)=='O') O++;

    if (s.charAt(i)=='V') V++;

    if (s.charAt(i)=='E') E++;

  }

  return ((L+O)*(L+V)*(L+E)*(O+V)*(O+E)*(V+E)) % 100;

}

Now, having such method implemented, we can easily complete the rest of the solution:

public String findBoy(String girl, String[] boys) {

  int bestProb = -1;

  String best = "";

  for (int i=0; i < boys.length; i++) {

    int cur = loveProb(girl, boys[i]);

    if (cur > bestProb || cur == bestProb && boys[i].compareTo(best) < 0) {

      bestProb = cur;

      best = boys[i];

    }

  }

  return best;

}

Exercise. It may seem that (L+O)*(L+V)*(L+E)*(O+V)*(O+E)*(V+E) doesn't always fit within 32-bit signed integer value (each multiplier can be up to 40, so the upper bound for the whole expression is 40^6 = 4,096,000,000). If it's really true, then there can occur an overflow in loveProb method implementation provided above. Construct an example, that makes (L+O)*(L+V)*(L+E)*(O+V)*(O+E)*(V+E) overflow 32-bit signed integer value, or prove that such example doesn't exist.

Value	500
Submission Rate	264 / 627 (42.11%)
Success Rate	115 / 264 (43.56%)
High Score	niyaznigmatul for 499.00 points (1 mins 16 secs)
Average Score	313.74 (for 115 correct submissions)

Value	250
Submission Rate	438 / 486 (90.12%)
Success Rate	320 / 438 (73.06%)
High Score	SkidanovAlex for 248.24 points (2 mins 23 secs)
Average Score	191.23 (for 320 correct submissions)

In order to solve this problem, let's do some simple math. First, we need to introduce several variables:

• P - the period of calendar in years (we are looking for the smallest period);
• N - the number of days in a normal year;
• L - the number of leap years within one period.

The statement asks us to choose P, N and L in such way that each P calendar years sum to the same amount of days as P real years. It means that the average year length (in days) according to our calendar is the same as the number of days in a real year. The number of days in a real year is yearLength/dayLength. The total number of days in P calendar years is (P - L) * N + L * (N + 1) (L leap years have N + 1 days and the other years have N days). Therefore, the average year length according to the calendar is ((P - L) * N + L * (N + 1)) / P = (P*N - L*N + L*N + L) / P = (P*N + L) / P = N + L/P. So we have an equation to solve: N + L/P = yearLength/dayLength.

Let's reduce the fraction yearLength/dayLength. Set yearLength' = yearLength/d, dayLength' = dayLength/d, where d is the greatest common divisor of yearLength and dayLength. Then the equation from the previous paragraph can be written as (N*P + L) / P = yearLength' / dayLength'. Now, since the fraction in the right part is irreducible, it becomes clear that the minimum possible value of P is dayLength'. It's left to show that this value for P is feasible, i.e. to provide the correct values for N and L, but it's easy to do: N = yearLength' DIV dayLength' and L = yearLength' MOD dayLength'. These values will work because (N*P + L) / P = ((yearLength' DIV dayLength')*dayLength' + yearLength' MOD dayLength') / dayLength' = yearLength' / dayLength'.

The implementation is really easy and straightforward. We just need to calculate dayLength / gcd(dayLength, yearLength):

public class DesignCalendar {

  int gcd(int a, int b) {

    while (a>0 && b>0)

      if (a>b) a%=b; else b%=a;

    return a+b;

  }



  public int shortestPeriod(int dayLength, int yearLength) {

    return dayLength / gcd(dayLength, yearLength);

  }

}

Value	1000
Submission Rate	100 / 627 (15.95%)
Success Rate	17 / 100 (17.00%)
High Score	DanilaVas9ev for 769.15 points (16 mins 38 secs)
Average Score	560.63 (for 17 correct submissions)

This problem is solved using brute force, i.e. by checking all possibilities. The basic idea is simple: we need to iterate through all subset of K letters, check for each of them how many words it allows to read and return the maximum. However, inefficient implementation of this approach will lead to time out. There can be up to C(26, 13) = 26! / (13! * 13!) = 10,400,600 possible subsets and checking each of them requires iterating through each letter of each word (at most 50*15 = 750 operations). Overall, it gives 10,400,600 * 750 = 7,800,450,000 operations, what is obviously way too much.

To obtain working solution, let's apply two optimizations:

1. We certainly should teach letters 'a', 'n', 't', 'i', 'c', otherwise our students won't be able to read even a single word. Therefore, if K < 5, we can return 0, and if K > 5, we teach 'a', 'n', 't', 'i', 'c' and then iterate through all possible subsets of K - 5 letters among the rest of 21 letters. This reduces the number of possible subsets to C(21, 10) = 21! / (10! * 11!) = 352,716. So this optimization makes our solution work faster in almost 30 times.
2. It's convenient to represent the subsets of letters by 26-bit masks. The i-th bit in mask is set if and only if the i-th letter in alphabet is present in the subset represented by mask. This allows for faster checking whether a subset of letters represented by subsetMask is enough to read the word represented by wordMask. The mask for a subset of unknown letters can be calculated as 2²⁶ - 1 - subsetMask. It's possible to read the word if and only if there's no unknown letter which is present in the word, that is, if wordMask & (2²⁶ - 1 - subsetMask) = 0. So instead of iterating through all the characters of the word, we can perform this simple check and save running time.

With these 2 optimization, in the worst case our solution will require 352,716 * 50 = 17,635,800 checks, what is still pretty much, but enough to fit within 2 seconds time limit. Java implementation of this approach follows:

public class Teaching {

  int K;

  int[] wordMask;

  int res = 0;



  // recursive method for checking subsets

  // pos is the index of letter we are currently at

  // have is the number of taken letters

  // mask is the mask of taken letters

  void go(int pos, int have, int mask) {

   // if the subset is completely formed

   if (pos == 26) {

     // if the number of taken letters is not K, skip the subset

     if (have != K) return;



     // calculate how many words we can read

     int cnt = 0;

     for (int i=0; i < wordMask.length; i++)

       if ((wordMask[i] & ((1<<26)-mask-1)) == 0) cnt++;



     // update maximum if needed

     if (cnt > res) res = cnt;

     return;

   }



   // if the letter is none of 'a', 'n', 't', 'i', 'c', try skipping it

   if ("antatica".indexOf((char)((int)'a'+pos)) == -1) go(pos+1, have, mask);

   

   // try learning the letter

   go(pos+1, have+1, mask + (1<<pos));

  }



  public int count(String[] words, int K) {

    // precalculate the masks for all words

    wordMask = new int[words.length];

    for (int i=0; i<words.length; i++)

      for (int j=0; j<words[i].length(); j++)

        wordMask[i] |= (1 << (words[i].charAt(j) - 'a'));



    this.K = K;



    // start recursive checking of all subsets

    go(0, 0, 0);



    return res;

  }

}

Value	600
Submission Rate	276 / 486 (56.79%)
Success Rate	127 / 276 (46.01%)
High Score	Petr for 530.06 points (10 mins 36 secs)
Average Score	321.74 (for 127 correct submissions)

The key idea for solving this problem is the following lemma which provides a very simple way to calculate d(x).

Lemma. If x>0, then d(x) = (x%9 == 0 ? 9 : x%9).

Proof. First, note that 10^n % 9 = (10 % 9)^n % 9 = 1^n % 9 = 1. Now let n = (a_k a_{k-1} ... a_1 a_0)₁₀. Then n % 9 = (a_k * 10^k + a_{k-1} * 10^{k-1} + ... + a_1 * 10 + a_0) % 9 = (a_k * (10^k % 9) + a_{k-1} * (10^{k-1} % 9) + ... + a_1 * (10 % 9) + a_0 * (1 % 9)) % 9 = (a_k + a_{k-1} + ... + a_1 + a_0) % 9. So each number has the same remainder modulo 9 as the sum of its digits. When calculating d(x), we repeatedly change number by sum of its digits until it becomes less than 10. As number modulo 9 always remains the same during the process, the result is x%9 if x is not divisible by 9. If x is divisible by 9, we have two potential choices - 0 and 9. But it's easy to see that sum of digits of positive number is always a positive number, so the right choice is 9.

Corollary. d(mul*x) = d(d(mul) * d(x)).

It follows from the corollary, that without loss of generality, we can assume that 1 ≤ mul ≤ 9 (otherwise just replace mul by d(mul)). Consider the sequence d(1), d(mul), d(mul^2), ..., used in the algorithm we need to implement. As each next element depends only on previous one, very soon this sequence becomes periodical with very small period:

mul = 1: [1];
mul = 2: [1, 2, 4, 8, 7, 5];
mul = 3: 1, 3, [9];
mul = 4: [1, 4, 7];
mul = 5: [1, 5, 7, 8, 4, 2];
mul = 6: 1, 6, [9];
mul = 7: [1, 7, 4];
mul = 8: [1, 8];
mul = 9: 1, [9].

Quite surprising, but the sequence of coordinates, produced for a fixed mul and K=1,2,3,..., is also periodical:

mul = 1: [(0, 0), (0, 1), (1, 1), (1, 0)];
mul = 2: [(0, 0), (0, 1), (2, 1), (2, -3), (-6, -3), (-6, 4), (-1, 4), (-1, 3), (-3, 3), (-3, 7), (5, 7), (5, 0)];
mul = 3: (0, 0), (0, 1), [(3, 1), (3, -8), (-6, -8), (-6, 1)];
mul = 4: [(0, 0), (0, 1), (4, 1), (4, -6), (3, -6), (3, -2), (10, -2), (10, -3), (6, -3), (6, 4), (7, 4), (7, 0)];
mul = 5: [(0, 0), (0, 1), (5, 1), (5, -6), (-3, -6), (-3, -2), (-1, -2), (-1, -3), (-6, -3), (-6, 4), (2, 4), (2, 0)];
mul = 6: (0, 0), (0, 1), [(6, 1), (6, -8), (-3, -8), (-3, 1)];
mul = 7: [(0, 0), (0, 1), (7, 1), (7, -3), (6, -3), (6, 4), (10, 4), (10, 3), (3, 3), (3, 7), (4, 7), (4, 0)];
mul = 8: [(0, 0), (0, 1), (8, 1), (8, 0)];
mul = 9: (0, 0), [(0, 1), (9, 1), (9, -8), (0, -8)].

To obtain this data, you can write an easy program that prints first 100 members of each sequence and manually check for repeats within the printed coordinates. We see that period length is either 4 or 12, and pre-periodic part can contain 0, 1 or 2 elements. Based on this knowledge, it's easy to write a program to solve the problem:

public class LocateTreasure {

  public String location(int K, int multi) {

    // if K is large, then make it smaller

    if (K >= 12) {

      // K can be taken modulo 12, because the period length is

      // 12 or 4 (a divisor of 12)

      K %= 12;

      // K can fall within pre-periodic part after taking

      // modulo 12, so add 12 for safety

      if (K <= 2) K += 12;

    }



    // calculate K-th member of the sequence

    // K can be at most 14 here

    int x = 0, y = 0;

    int[] dx = new int[] {0, 1, 0, -1};

    int[] dy = new int[] {1, 0, -1, 0};

    int d = 1;

    for (int step=0; step<K; step++) {

      x += dx[step%4] * d;

      y += dy[step%4] * d;

      d *= multi;

      while (d>9) d-=9;

    }



    // return the result

    return x+" "+y;

  }

}

Value	900
Submission Rate	56 / 486 (11.52%)
Success Rate	32 / 56 (57.14%)
High Score	Psyho for 713.12 points (15 mins 24 secs)
Average Score	516.30 (for 32 correct submissions)

Let's first describe how to solve the problem using brute force. Let's build all possible p-sequences recursively. Our method count will take two parameters - an integer prev, describing the number we've put onto the previous position in the builded sequence (we can use some special value BEG to indicate the first position of the sequence when there's no previous position), and an array of integers left, describing all the integers that haven't been put yet into the sequence. The method count will return the number of ways to complete the sequence by all numbers from left to obtain p-sequence. The algorithm is simple: we iterate through all numbers X from left such that X - prev is not divisible by p (in case left = BEG we just iterate through all numbers from left) and sum the results of calls to count(X, left/X), where left/X is an array left with element X being removed. Each such call corresponds to extension of the builded sequence by number X and condition (X - pref) % p != 0 ensures that we check only p-sequences. In case when left is empty, there's exactly one way to obtain p-sequence – do nothing, so we return 1. The answer for the whole problem is count(BEG, S).

The described method count works nicely, but it's awfully slow. One useful method that allows to speed up recursion is memoization, i.e. ensuring that method is called exactly once for every combination of its input parameters by saving the results of all calculations in some data structure. However, with the approach we've just described, values of the input parameters don't tend to repeat often, so it doesn't directly help here. So our goal is to modify input parameters in such way that memoization can be used. Let's make several observations:

1. The order of elements in left doesn't matter, so we can always assume that it's sorted in non-descending order.
2. The only condition used in the definition of p-sequence is (s1 - s2) % p != 0 for every two consecutive elements s1 and s2. This can be rewritten as s1 % p != s2 % p. From this point of view, it directly follows that instead of actual number X we can store just X % p in left. For example, if p=3, instead of left ={0, 2, 7, 13, 15} we can store left={0, 0, 1, 1, 2} (15 % 3 = 0 % 3 = 0, 13 % 3 = 7 % 3 = 1, 2 % 3 = 2). It's worth nothing that the same numbers in left must now be treated as if they were distinct, because they are actually just the same reminders modulo p of several distinct numbers.
3. The next transformation that can be applied to left is grouping the same elements. For example, we can transform left = {0, 0, 1, 1, 2} into left = {(2, 0), (2, 1), (1, 2)}, where (2, 0) means a group of 2 zeros, (2, 1) means a group of 2 ones and (1, 2) means a group of one 2 (in other words, first integer in a group denotes the number of occurences of the second integer). Now, observe that from the point of view of method count, there's no actual difference between, for example, a group of seven 3's and a group of seven 5's. In other words, second integer in each group can be omitted. So, left = {0, 0, 1, 1, 2} can be transformed into left = {2, 2, 1}, what means that some integer occurs 2 times, some other integer also occurs 2 times and some third integer occurs 1 time. Finally, it's still useful to assume that left is sorted in non-descending order, so left = {0, 0, 1, 1, 2} must be transformed into left = {1, 2, 2}. After this transformation, the meaning of parameter prev slightly changes: instead of giving the value of the previous element of the builded sequence it can give the index of the group (in left) from which the previous element of the builded sequence was taken.

After we apply these 3 observations, left will always contain a partition of some number less than or equal to N = length of S. There are at most 28,628 partitions of numbers ≤ 30, and there are at most 31 possible values for parameter prev (at most 30 positions in left and one special value for BEG). Overall, there are at most 28,628 * 31 = 887,468 combinations of input parameters' values for method count. Note that this bound is not strict, and in actual cases the number of appeared combinations is much less – 10,275 in the worst possible case. So now we can successfully apply memoization to method count to obtain working solution.

For an example implementation of this approach, you can check Petr's submission. Note that in his code parameter prev (it's called numForbidden) there) has a bit different meaning – instead of the index of the group from which the previous element was taken, it gives the current number of elements in this group.