Match summary

In Division 1, the problems were much easier than those in SRM 333. We didn't have to wait long for the first submissions, with many coders scoring around 240 points on the easy problem. The remaining two problems also didn't stop the top competitors for long. After the first 20 minutes of the coding phase bmerry took the lead, thanks to the fastest submission of the hard followed by tomek the fastest solution of the medium problem. After only 5 minutes, however, the situation began to change. tomek climbed to first place with all three submissions after 27 minutes of the match had gone by. However he ended up in second place at the end of coding, with krijgertje taking over his spot in first place.

The hard problem was a little below average, in terms of difficulty, and the idea for it was pretty standard. Because of that, more than 100 coders were able to submit all three problems by the end of the coding phase.

During the challenge phase tomek gained 125 point with three successful challenges on the easy problem and overcame krijgertje, who took second place. lovro finished third, thanks to four challenges on the easy problem.

In Division 2, only a dozen coders were able to solve more than two problems. First place was taken by Argentinian newcomer lucasr. lucasr solved all three problems and successfully challenged two other coders' solutions. After this SRM lucasr moved to Division 1 with 1900 rating points. monoid came in second in Division 2, followed by Rahenri in third.

The Problems

SupermarketDiscount

Used as: Division Two - Level One:

Value 250

Submission Rate 588 / 638 (92.16%)

Success Rate 397 / 588 (67.52%)

High Score danielf for 246.71 points (3 mins 17 secs)

Average Score 196.62 (for 397 correct submissions)

Generally, in real life, it's hard to optimize purchases in order to get the maximal discount. Fortunately, we have a very simple sales rule and only three girls who do not want to split up goods across multiple transactions. In our case the girls have only three possibilities: pay separately, pay together or combine purchases for two of three girls. There are three ways to select two of three girls, so we have five possibilities in total. Here is the sample Java solution.

    int discounted(int x) {
        return x >= 50 ? x-10 : x;
    }

    int minAmount(int[] goods) {
        int ans = Integer.MAX_VALUE;
        ans = Math.min(ans, discounted(goods[0]) + discounted(goods[1]) + discounted(goods[2]));
        ans = Math.min(ans, discounted(goods[0]+ goods[1]) + discounted(goods[2]));
        ans = Math.min(ans, discounted(goods[0]+ goods[2]) + discounted(goods[1]));
        ans = Math.min(ans, discounted(goods[2]+ goods[1]) + discounted(goods[0]));
        ans = Math.min(ans, discounted(goods[0]+ goods[1] + goods[2]));
        return ans;
    }

KnightTour

Used as: Division Two - Level Two:

Value 500

Submission Rate 481 / 638 (75.39%)

Success Rate 406 / 481 (84.41%)

High Score n1b for 478.57 points (6 mins 3 secs)

Average Score 330.02 (for 406 correct submissions)

The solution for this problem is pretty straightforward. We just need to emulate the knight's trip through the given path and check whether it is really a valid re-entrant knight's tour or not. Here is rrox's Java code, which nicely shows this idea:

public class KnightTour { 
  boolean vis[][]; 
   
  boolean valid(String a, String b) { 
    int la = a.charAt(0) - 'A'; 
    int na = a.charAt(1) - '1'; 
    int lb = b.charAt(0) - 'A'; 
    int nb = b.charAt(1) - '1'; 
    if (vis[la][na]) return false; 
    vis[la][na] = true; 
    int dl = Math.abs(la - lb); 
    int dn = Math.abs(na - nb); 
    return (dl == 1 && dn == 2) || (dl == 2 && dn == 1); 
  } 

  public String checkTour(String[] a) { 
    vis = new boolean[6][6]; 
    boolean ok = true; 
    for (int i = 0; i < a.length; i++) { 
      ok &= valid(a[i], a[(i+1) % a.length]); 
      System.out.println("Round " + i + ": " + ok); 
    } 
    return ok ? "Valid" : "Invalid"; 
  } 
}

ExtendedHappyNumbers

Used as: Division Two - Level Three:

Value 1000

Submission Rate 76 / 638 (11.91%)

Success Rate 12 / 76 (15.79%)

High Score jaro3000 for 624.00 points (25 mins 33 secs)

Average Score 468.15 (for 12 correct submissions)

Used as: Division One - Level Two:

Value 500

Submission Rate 175 / 487 (35.93%)

Success Rate 138 / 175 (78.86%)

High Score Petr for 455.15 points (9 mins 6 secs)

Average Score 290.60 (for 138 correct submissions)

First of all, let's find the upper limit for a number that can be reached in the sequence N, S_K(N), S_K(S_K(N)) and so on, where N is not greater than 1 million and K is not greater than 6. It is easy to see that this upper limit is less than 4*10⁶ because S₆ for any number below 4*10⁶ is not greater than 3⁶ + 6*9⁶ = 3189375.

Now, let's begin to solve the problem. The naive solution is to take each number N from A to B, inclusive, and build the sequence N, S_K(N), S_K(S_K(N)) and so on, until some number in this sequence appears twice. After that there will be no new values in the sequence because its elements begin to repeat. We can find the minimal element in this (already built) sequence's prefix, and it will be the answer for the N.

Unfortunately, this naive solution works too slowly. Its performance can be improved a lot, however. During the computation of the answer for the number N we can simultaneously compute and store answers for S_K(N), S_K(S_K(N)) and so on. After that, if we need a number with a previously computed answer, we can just return this value without any hesitation.

You can use Petr's C# code as a reference.

EncodedSum
Used as: Division One - Level One:

Value 250

Submission Rate 399 / 487 (81.93%)

Success Rate 233 / 399 (58.40%)

High Score JongMan for 244.24 points (4 mins 23 secs)

Average Score 171.70 (for 233 correct submissions)

This is a fairly easy problem for Division One, and doesn't require much effort to solve and code. Nevertheless, many coders wrote a naive solution and were beaten in the challenge phase.

The naive solution is as follows: Try all possible assignments between letters and digits and take the one that leads to the best result. For the fixed assignment we can calculate the total sum by iterating along all given summands. Clearly, this solution is not fast enough, but even small improvements allow it to fit to the time limit.

Let's interpret each integer, which needs to be summed as follows (where n is the length of current integer):

Letter₀ * 10^n-1 + Letter₁ * 10^n-2 + ... + Letter_n-1 * 10⁰,

After that we can combine the items around each letter from 'A' to 'J'. Now, if we know the assignment between letters and digits, we can calculate the total sum by 10 operations. This is much faster than without pre-calculation. This optimization was good enough to pass system tests -- see JongMan's solution as an example.

You can move forward, however, and create A solution without iterations of all possible assignments at all. The main idea is that, after the optimization described above, you can easily state your preferences about the values of the letters. The only thing you should worry about is a zero digit that cannot be assigned to some of the letters.

Terrorists

Used as: Division One - Level Three:

Value 900

Submission Rate 149 / 487 (30.60%)

Success Rate 102 / 149 (68.46%)

High Score Abednego for 891.70 points (2 mins 44 secs)

Average Score 673.86 (for 102 correct submissions)

In this problem you are required to find a sum of the edges of a minimal cut in the given graph. According to the max-flow min-cut theorem a sum of the edges of a minimal cut that separates two vertexes v1 and v2 equals to the maximum flow in the given graph with v1 and v2 as a source and a sink respectively. For any cut in the graph the town 0 will be separated from some other town. So, to solve the problem we can fix the town 0 as a source and try all other towns as a sink. The minimal of the obtained result will be the answer for the original problem.

You can view kia's solution with this idea here.

By Andrew_Lazarev
TopCoder Member