Match Editorial

Match summary

The hard problem in division 1 involved both dynamic programming and a greedy aspect, and as such problems go, there were many submissions, and many of them were then successfully challenged. For the spectators, this was the only excitement during the challenge phase, as the other two problems had a very high success rate.

The final results won't really surprise anyone: Petr scored his next (already 47th!) match victory, second place went to ahyangyi and third to bmerry. Fourth place finish was enough for Vasyl[alphacom], even so his new rating exceeded 3000, and he is now one of the ten "targets".

In division 2, solving the hard problem was the key to victory. The top three places went to the only three coders with all problems solved: pcasa, ttaras, and saltA. The best newcomer, Lowe, was leading until his medium submission was challenged, which moved him into fourth place.

The Problems

Value	250
Submission Rate	652 / 739 (88.23%)
Success Rate	625 / 652 (95.86%)
High Score	Sunny_05 for 249.35 points (1 mins 27 secs)
Average Score	197.66 (for 625 correct submissions)

Imagine that we are solving the task manually. We have the old deck of cards in front of us, and a set of instructions how to insert them into the new deck.

Instead of keeping the new deck of cards as a stack, we can arrange them into a row, with the top card on the left and the bottom one on the right. Now, whenever inserting a new card, we count from the left until we find the right place where it should be inserted, place the new card there, and shift the remaining cards one position to the right.

This exact approach is easily implemented using a simple array. Note that the resulting algorithm is very similar to the simple sorting algorithm InsertSort. Java code follows.

  public String rearrange(String deck, int[] above) {
    int N = above.length;
    char[] newDeck = new char[N];
    for (int i=0; i<N; i++) {
      for (int j=i; j>above[i]; j--) newDeck[j]=newDeck[j-1];
      newDeck[above[i]]=deck.charAt(i);
    }
    String result = "";
    for (int i=0; i<N; i++) result += newDeck[i];
    return result;
  }

Exercise: Did you find this task too easy? Then find and implement a solution that is faster than quadratic in the number of cards.

Value	500
Submission Rate	453 / 739 (61.30%)
Success Rate	327 / 453 (72.19%)
High Score	darrenctwhk for 484.84 points (5 mins 3 secs)
Average Score	283.75 (for 327 correct submissions)

As with all progress bars, the actual value shown is computed as 100 * (time elapsed) / (total time). The "100 *" part converts the fraction of elapsed time into percentage.

Total time is easy to compute: 365 days for non-leap years, 366 for leap years.

Actually, the smallest unit given in the input are minutes, so it makes sense to compute both the elapsed time and the total time in minutes, so that all intermediate values are integers. (The value of the fraction remains the same regardless of the units we choose, it is only important to use the same unit both in the numerator and in the denumerator.)

A day has 24 hours, each hour has 60 minutes. Thus a non-leap year has 365*24*60 and a leap year has 366*24*60 minutes.

Now we need to compute the elapsed time. This is a bit more tricky, but the idea remains the same. We have to sum these times:

• All the days in previous months.
• Previous days in the given month.
• The time (hours and minutes) elapsed in the given day.

Java code follows.

  static String[] months = { "January", "February", "March", "April", "May", "June", "July", "August", "September", "October", "November", "December" };
  static int[] days = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
  boolean isLeap(int y) { if (y%400==0) return true; if (y%100==0) return false; if (y%4==0) return true; return false; }
  int daysInMonth(int m, int y) { if (m==2 && isLeap(y)) return 29; return days[m-1]; }
  int getMonth(String name) { for (int i=0; i<12; i++) if (name.equals(months[i])) return i+1; return 0; }

  public double percentage(String currentDate) {
    String[] tokens = currentDate.split("[ ,:]");
    int month = getMonth(tokens[0]);
    int day = Integer.parseInt(tokens[1]);
    int year = Integer.parseInt(tokens[3]);
    int hour = Integer.parseInt(tokens[4]);
    int minute = Integer.parseInt(tokens[5]);

    double daysInYear = 365; if (isLeap(year)) daysInYear += 1;
    double daysElapsed = 0;
    for (int m=1; m<month; m++) daysElapsed += daysInMonth(m,year);
    daysElapsed += day-1;
    daysElapsed += hour / 24.;
    daysElapsed += minute / 24. / 60.;
    return 100 * daysElapsed / daysInYear;
  }

An alternate solution: Some of the allowed programming languages include libraries for working with dates and times. These can be used to solve the given task for us. However, one has to be careful not to fall into the subtle trap of locale settings, time zones, daylight saving times, etc. See abi20sg's submission for a pretty short solution.

Exercise 1 (easy): Our solution above is linear in the number of months. Adjust it so that it will run in constant time.

Exercise 2 (harder): Write a program that will read three dates D1 < D2 < D3 and output the percentage of time that elapsed from the interval [D1,D3] at the moment D2. Your program should run in constant time, and be able to handle arbitrary inputs, even such where D1 and D3 are hundreds of years apart.

Value	1000
Submission Rate	71 / 739 (9.61%)
Success Rate	5 / 71 (7.04%)
High Score	Lowe for 667.34 points (22 mins 34 secs)
Average Score	528.12 (for 5 correct submissions)

This task consisted of two almost separate parts: getting the first 5 digits right, and getting the tail (last 5 non-zero digits + the number of zeroes) right.

We will start with the tail part.

First, remember that every positive integer has a unique prime factorization, and the prime factorizations multiply. That is, if p is a prime, the prime factorization of X contains p^k, and the prime factorization of Y contains p^l, then the prime factorization of XY will contain p^k+l.

What we need is to find the values a and b such that the given C has the form 2^a * 5^b * F, for some F that is not divisible by 2 or 5.

This can easily be done by processing all the numbers in the given range. For each of them we can (just using simple division) find the largest power of 2 and 5 that divides it, and then add all these powers to get a and b, respectively.

Once we have a and b, we know the number of zeroes at the end of C. How? The number of zeroes is the largest power of 10 that divides C. And as 10=2*5, that power is simply z=min(a,b).

Now we can find the last 5 non-zero digits. Finding the last 5 digits of a number X (in base 10) is equivalent to finding the value (X mod 10⁵). In our case, our number X is (C with trailing zeroes removed), that is, C/10^z. Or, equivalently, 2^a-z * 5^b-z * F.

We can compute the values a and b and the last five non-zero digits at the same time. For each number in the given range, first divide it by 2 and 5 (while possible) and increment a and b. Multiply all the remaining parts, modulo 10⁵, to get (F mod 10⁵). At the end, compute z, and then multiply the value of (F mod 10⁵) by the remaining power of 2 or 5.

Now what remains is to find the first 5 digits – that is, an approximate value of C. Simple multiplication (e.g., using doubles) is not the way to go here, as the result can be way larger than what the range of doubles supports. This can be fixed by keeping the exponent small. For example, after each multiplication, while the current result has more than 5 digits to the left of the decimal point, divide it by 10.

We will show an almost equivalent approach, based on a neat trick that can be used in situations like this one: logarithms. In this writeup, we will use the base-10 logarithm and we will denote it log().

For any integer k we have log(10^k)=k. Logarithm (with a base greater than 1) is an increasing function. Therefore for any integer X between 10^k and 10^k+1 we have k < log(X) < k+1.

Therefore logarithm can be handy to compute the number of digits of any X. More precisely, all the numbers in [10^k,10^k+1) have logarithms in [k,k+1), and their number of digits is k+1. Thus number_of_digits(X) = 1 + floor(log(X)).

Logarithms are additive. That is, log(ab) = log(a)+log(b) for any positive a,b. Thus, in our task, we can compute L=log(C) as the sum of logarithms of all numbers in the given range.

One geek joke comes to my mind at this point:
The Flood is over and the ark has landed. Noah lets all the animals out and says, "Go forth and multiply."
A few months later, Noah decides to take a stroll and see how the animals are doing. Everywhere he looks he finds baby animals. Everyone is doing fine except for one pair of little snakes. "What's the problem?" askes Noah. "Cut down some trees and let us live there", say the snakes.
Noah does as they say. Several weeks later, Noah checks on the snakes again. Lots of little snakes, everybody is happy. Noah asks, "Want to tell me how the trees helped?"
"Certainly", say the snakes. "We're adders, so we need logs to multiply."

We now know that 10^L = C. Then, 10^L-floor(L) = C / 10^floor(L). If we divide C by a power of 10, the digits remain the same, only the decimal point shifts. In this case, L-floor(L) is in [0,1), therefore the result is in [1,10).

Using similar reasoning, 10^L-floor(L)+4 has the same digits as C, and its value is in [10000,100000). Therefore the first five digits of C can be computed as floor(10^L-floor(L)+4).

Java code follows. We use logarithms to estimate the number of digits in D. If it is small enough, we compute it exactly, otherwise we use the approaches from this writeup to get its first and last few digits.

  public String prettyPrint(int A, int B) {
    int twos=0, fives=0;
    long D=1L, MOD=(long)Math.pow(10,12);
    for (int i=A; i<=B; i++) {
      int tmp=i;
      while (tmp%2==0) { tmp/=2; twos++; }
      while (tmp%5==0) { tmp/=5; fives++; }
      D *= tmp;
      D %= MOD;
    }
    int zeroes = Math.min(twos,fives);
    twos-=zeroes; fives-=zeroes;
    while (twos-->0) { D *= 2; D %= MOD; }
    while (fives-->0) { D *= 5; D %= MOD; }

    double logProduct = 0;
    for (int i=A; i<=B; i++) logProduct += Math.log10(1.*i);
    logProduct -= zeroes;

    if (logProduct<11.5 && D<(long)Math.pow(10,10)) {
      return D + " * 10^" + zeroes;
    } else {
      logProduct = logProduct - (int)logProduct + 4;
      int first = (int)(Math.pow(10.,logProduct));
      return first + "..." + (D % 100000) + " * 10^" + zeroes;
    }
  }

Exercise: When we find the values a and b such that C = 2^a * 5^b * F, is it possible that b > a?

Value	250
Submission Rate	575 / 600 (95.83%)
Success Rate	546 / 575 (94.96%)
High Score	Burunduk1 for 247.99 points (2 mins 33 secs)
Average Score	192.96 (for 546 correct submissions)

As the class name suggests, simulation was enough to solve this task.

Approach 1: Heavy artillery. Use a map to assign turn numbers to visited states. Whenever a state appears for the second time, thanks to the map we will find this out. The difference in turn numbers of both occurrences is the length of the period.

  vector<int> step(vector<int> prev) {
    vector<int> next(1, prev.size() );
    for (int i=0; i<int(prev.size()); i++) if (prev[i]>1) next.push_back( prev[i]-1 );
    sort( next.begin(), next.end() );
    return next;
  }

  int periodLength(vector <int> heaps) {
    map< vector<int>, int> visited;
    sort( heaps.begin(), heaps.end() );
    int time = 0;
    visited[ heaps ] = time++;
    while (1) {
      heaps = step( heaps );
      if (visited.count( heaps )) return time - visited[ heaps ];
      visited[ heaps ] = time++;
    }
  }

Approach 2: Use Floyd's cycle finding algorithm.

  public int periodLength(int[] heaps) {
    ArrayList<Integer> slow = new ArrayList<Integer>();
    for (int i=0; i<heaps.length; i++) slow.add(heaps[i]);
    Collections.sort(slow);
    ArrayList<Integer> fast = slow;

    while (true) {
      slow = step(slow);
      fast = step(fast);
      fast = step(fast);
      if (slow.equals(fast)) {
        int period = 0;
        while (true) {
          slow = step(slow);
          period++;
          if (slow.equals(fast)) return period;
        }
      }
    }
  }

Approach 3: Just store all visited states in an array, and for each new state traverse the entire array and check whether it already occured. Thanks to how this game works, even such solutions would pass with plenty of time left.

To see that the first two approaches work in time, it is enough to note that the states of the game are simply integer partitions of the number of cards, which is at most 50. The number 50 has only 204,226 different partitions, so this is an upper bound on the number of states we have to visit until one repeats.

The fact that the third solution works in time is related to how the game behaves – it tends to reach a roughly "triangular" state (such as "1,2,3,4") quickly. The game is called Bulgarian solitaire. Follow the link for an overview of research related to this game.

Exercise: Find the absolutely worst test case, i. e., one that forces Approach 1 to visit as many states as possible. How would you make sure your case really is the worst one? (Hint: Find a way how to compute pre-period and period lengths for all states at the same time.)

Value	500
Submission Rate	356 / 600 (59.33%)
Success Rate	284 / 356 (79.78%)
High Score	bmerry for 492.10 points (3 mins 36 secs)
Average Score	345.51 (for 284 correct submissions)

The important thing to realize here is that when playing the game, the optimal decision at any moment depends only on the current set of remaining cards – and not on the current balance. This is because our goal is always the same: play the rest of the game in such a way that our expected profit from the rest of the game is maximized.

And moreover, at any moment we only have two options to choose from: either stop or play on. And we just argued that the decision whether to play or to stop depends only on the number of red and black cards that remain in the deck.

Let E(R,B) be the expected profit from a game with R red and B black cards, if we play optimally. What are the two options we have at the beginning? If we stop playing, our profit is zero. If we play on, we flip the first card. With probability R/(R+B) it is red. In this case, we gain a dollar, and are left with a game with R-1 red and B black cards. In the other case, we lose a dollar and are left with R red and B-1 black cards. Thus the expected profit if we play on is ( R * (E(R-1,B) + 1) + B * (E(R,B) - 1) ) / (R+B). If this value is positive, it is better to play, if it is negative, it is better to stop immediately.

In the previous paragraph we silently ignored the cases where one of R and B is zero. For these situations we clearly have E(R,0)=R and E(0,B)=0.

What we just got is a recurrence relation that can be used to compute any value E(R,B) in O(RB) time. The last trick needed to get a working solution was to observe that a 5000 by 5000 array of doubles is too large to fit into memory. Luckily, all values E(R+1,*) can be computed from all values E(R,*) only. Therefore we can reduce the memory requirements to O(B) by just keeping the last two rows of the array in memory.

Java code follows.

  public double getProfit(int R, int B) {
    double[][] best = new double[2][B+1];
    Arrays.fill(best[0],0);
    for (int r=1; r<=R; r++) {
      best[r%2][0]=r;
      for (int b=1; b<=B; b++)
        best[r%2][b] = Math.max(0,
            (1.*r/(r+b))*(best[ 1-(r%2) ][b] + 1)
            +
            (1.*b/(r+b))*(best[ r%2 ][b-1] - 1)
        );
    }
    return best[R%2][B];
  }

Exercise 1: Let f(B) be the smallest R such that E(R,B) is positive. How does f look like? (Note that, perhaps surprisingly, f(B)<B for most B.)

Exercise 2: How does g(R) = E(R,R) look like?

Value	1000
Submission Rate	82 / 600 (13.67%)
Success Rate	29 / 82 (35.37%)
High Score	Petr for 728.61 points (18 mins 52 secs)
Average Score	487.27 (for 29 correct submissions)

First, we'll show how to solve the case where inputValue is small.

In this case, a textbook dynamic programming approach can be used: For each amount between 1 and inputValue we will compute the smallest number of coins necessary to give change for this amount.

Additionally, we need to take care of the tie-breaking rule. Whenever there are multiple equally good ways of providing change, we should prefer the one that uses the larger coins. A simple way how to implement this rule is to process the coins in order, and remember the largest coin that could've been used in the best solution found so far.

The trouble here is that we need to distinguish between two cases. On one hand, if we have a coin worth 25, we need the information that we can pay the sum 25 using a single coin. On the other hand, if 25 is what we want change for, we need the best way how to pay it using more than one coin.

The easiest solution is to store both values: bestPay[x] will be the best way to pay the sum x, while bestChange will be the best way that uses more than one coin.

    int N = outputValues.size(), B = outputValues[N-1], MAX = B*B + B + 47;
    vector<int> bestPay(MAX), bestPayCoin(MAX), bestChange(MAX), bestChangeCoin(MAX);
    for (int i=0; i<MAX; i++) { bestPay[i]=i; bestPayCoin[i]=0; bestChange[i]=i; bestChangeCoin[i]=0; }
    for (int c=1; c<N; c++) {
      for (int i=outputValues[c]; i<MAX; i++) {
        if (bestPay[i] >= bestPay[ i-outputValues[c] ] + 1)
          bestPay[i] = bestPay[ i-outputValues[c] ] + 1,
          bestPayCoin[i] = c;
      }
      for (int i=outputValues[c]+1; i<MAX; i++) {
        if (bestChange[i] >= bestPay[ i-outputValues[c] ] + 1)
          bestChange[i] = bestPay[ i-outputValues[c] ] + 1,
          bestChangeCoin[i] = c;
      }
    }

Now, using this information, we can easily simulate the process described in the problem statement. Note that to avoid timeouts we can not proceed one coin at a time. Instead, we will proceed one coin type at a time.

Let the array coinCounts[] contain the counts of coins after we exchanged the original banknote. Then the simulation can look as follows:

    long long result = 1;
    for (int q=N-1; q>0; q--) {
      result += coinCounts[q];
      remains = outputValues[q];
      coinCounts[ bestChangeCoin[remains] ] += coinCounts[q];
      remains -= outputValues[ bestChangeCoin[ remains ] ];
      while (remains) {
        coinCounts[ bestPayCoin[remains] ] += coinCounts[q];
        remains -= outputValues[ bestPayCoin[ remains ] ];
      }
    }

The last remaining issue is the fact that the input banknote can be huge. It seems obvious that if the initial banknote is large enough, at least one largest coin will be used in the optimal payment. We will now show and prove what does "large enough" mean.

Note that the proof was not necessary. Coders could've just guessed that such a boundary exists, and implement a solution that does the dynamic programming until it almost reaches the time limit. Such solutions, if done properly, did pass.

Lemma: If we have a set of N integers, some non-empty subset of it has a sum divisible by N.

Proof: Let the numbers be a₁, a₂, ..., a_N. Consider the prefix sums: a₁, a₁+a₂, ..., a₁+...+a_N If some of them is divisible by N, we are done. If not, two of them have to give the same remainder mod N, and then their difference is a subset divisible by N.

Theorem: We have several coin types, and the largest of them has value B. If we have to pay a sum S ≥ B(B-1) using the smallest possible number of coins, then at least one coin with value B will be used.

Proof by contradiction: Assume the contrary. Thus every optimal way of paying S involves only coins worth B-1 or less. Pick one such way. As S ≥ B(B-1), this means that at least B coins were used. By our lemma, there is a non-empty subset of these coins with sum divisible by B. If we throw away these coins and replace them by the same amount in coins worth B each, we get a way of paying B using less coins than before. And thus we get a contradiction.

Corollary: For any S ≥ B(B-1) an optimal algorithm to pay S is "output a coin worth B, and then pay S-B optimally".

This means that for a huge inputValue we can output enough largest coins to decrease the remaining sum to less than B(B-1), and then use the dynamic programming table to pay the rest optimally. As B≤1000, it is enough to have the DP table up to one million, which fits nicely into both the time and the memory limit.

Exercise: How tight is the "one million" bound? For B=1000, find the coin set that maximizes the largest sum that can only be paid optimally without using coins worth B.