Get Time
statistics_w  Match Editorial
SRM 398
Tuesday, April 15, 2008

Match summary

This match attracted 1280 competitors, 721 Div2 (78 newcomers) and 559 Div1. Div2 problem set turned out to be the easier one for Div2 coders. They faced easier Hard problem that was worth 900 points. Many of them (even 88 competitiors) solved correctly all three tasks. Div1 coders faced very easy 250 points problem and almost all of them solved it correctly, however, due to minor bugs some red coders (ex-target) like gawry and ahyangyi failed on this problem, but thanks to their excellent coding skills their rating increased. Many coders showed that they are familiar with Div1 Medium kind of problems. Some of them took it as easier and had to resubmit their solution to avoid Failed system tests. Many coders trapped with Div1 Hard and lot of early submited solutions failed.

In Div1 wywcgs first submitted Hard problem, but it came out as incorrect. After solving Medium problem ardiankp, tomekkulczynski and PaulJefferys took lead. Match is going on and submissions of Hard problem change things - PaulJefferys, nigulh, Vasyl[alphacom] (become almost a target) and Rizvanov_de_xXx took lead, but one of them had 1K problem incorrect solution. PaulJefferys showed great performance and thanks to 4 successful challenges won the match with over 200 points margin and became target. nigulh took second place, followed by Petr who resubmited 1K problem, but earned 125 points in challenge phase and took third place. Even with third place, Petr's rating decreased - amazing, isn't?

Because the problems in Div2 weren't hard, we've got very fast solutions for each of them. Thanks to 2 successful challenges dlwjdans won the match. Although newcomer ILoveWangYeMore finished challenge phase with -50 points, he won second place, followed by gpascale who was on third place.

The Problems

MinDifference rate it discuss it
Used as: Division Two - Level One:
Value 250
Submission Rate 687 / 715 (96.08%)
Success Rate 571 / 687 (83.11%)
High Score wenbin for 248.48 points (2 mins 13 secs)
Average Score 214.65 (for 571 correct submissions)

Although this is very simple problem, it can be solved in several ways.

First approach

Simple checking for the minimum over all pairs will work in O(n^2) time.

Second approach

Since O(n^2) solution could be "very slow" on some platforms, it would be very nice if we can come up with faster one. Lets look at the element A[i] and divide other elements into two groups:
  • Elements lower or equal to A[i]
  • Elements greater than A[i]
Over all elements from the first group the maximal one will produce the minimal difference with A[i]. Similarly, over all elements from the seconds group the minimal one will produce the minimal difference with A[i]. Actually, instead of comparing A[i] to all elements from the list, we should compare it to only two elements. After this conclusion, it is obvious that sorting the list A is key to the solution. In sorted list, each element should be compared with its left and right neighbour. Implementation in Java of this approach:
public int closestElements(int A0, int X, int Y, int M, int n){
    int ret = 1000000000;
    int a[] = new int[n];
    a[0] = A0;
    // generate list
    for (int i = 1; i < n; i++)
        a[i] = (a[i - 1] * X + Y) % M;
    // in sorted list, min difference is between some two neighbour elements
    for (int i = 1; i < n; i++)
        ret = Math.min(ret, Math.abs(a[i] - a[i - 1]));
    return ret;

Time complexity of this algorithm is O(n log(n)). ILoveWangYeMore's solution is short and clear.

Third approach

Let's go on and find even faster solution, the one that depends on M and for the maximal n and M is faster than Second approach. Note that if each element (except A[0] = A0) of the list is calculated by modulo M then it must fail between 0 and M-1, inclusive. So, we have at most M+1 different numbers that are in the range 0 .. Max(M-1, A0). According to the constraints, any number is between 0 and 10000, inclusive. Let's make an array flag of 10001 booleans (0 .. 10000) and mark flag[i] = true if i appears in the list. If flag[i] was already set on true return 0. Else, go through the array flag and calculate difference between two neighbour elements that are set on true and return the minimal difference. Time complexity of the algorithm is O(Max(M, A0) + n). Implementation in Java of this approach:
public int closestElements(int A0, int X, int Y, int M, int n){
    // maximal number of different elements is 10001
    boolean used[] = new boolean[10001];
    Arrays.fill(used, false);
    int ret = 1000000000;
    int a = A0;
    used[a] = true;
    // generate list
    for (int i = 1; i < n; i++){
        a = (a * X + Y) % M;
        if (used[a])
            return 0;
        used[a] = true;
    // find value with minimal index
    int idx;
    for (idx = 0; ; idx++)
        if (used[idx])
    for (int i = idx + 1; i < 10001; i++)
        if (used[i]){
            ret = Math.min(ret, i - idx);
            idx = i;
    return ret;


  • Think of the following problem: Suppose that 1 <= n <= 10^18, everything else is as in the main problem and you are already given the list A. Memory is not contrained.
    We could disccuss about the solution on the forum.

CountExpressions rate it discuss it
Used as: Division Two - Level Two:
Value 500
Submission Rate 471 / 715 (65.87%)
Success Rate 428 / 471 (90.87%)
High Score ILoveWangYeMore for 491.07 points (3 mins 50 secs)
Average Score 322.70 (for 428 correct submissions)
Used as: Division One - Level One:
Value 250
Submission Rate 548 / 559 (98.03%)
Success Rate 528 / 548 (96.35%)
High Score Gumx for 248.53 points (2 mins 11 secs)
Average Score 207.87 (for 528 correct submissions)

This task is pretty straighforward. It doesn't involve any special knowledge. Almost each brute-force solution would pass. One way to solve the task is first to generate all possible positions for x. Then for each fixed position of x and y try all the possibilites for operators. Time complexity of this algorithm is constant, about O(2^4 * 3^3).
Shorter and simpler solution is to replace generating all possible positions of x with several recurent calls. Bellow is solution of tester ivan_metelsky

int a, b, val;

int rec(int ca, int cb, int cur) {
    if (ca==2 && cb==2) return (cur==val ? 1 : 0);
    int res=0;
    if (ca<2) res += rec(ca+1, cb, cur+a) + rec(ca+1, cb, cur-a) + rec(ca+1, cb, cur*a);
    if (cb<2) res += rec(ca, cb+1, cur+b) + rec(ca, cb+1, cur-b) + rec(ca, cb+1, cur*b);
    return res;

public int calcExpressions(int a, int b, int val) {
    this.a=a; this.b=b; this.val=val;
    return rec(1, 0, a) + rec(0, 1, b);
For a short and fast iterative solution take a look at vlad89's solution here.


  • Try to solve the task if operator precedence is defined.
  • Add operators '/' (real division), '\' (integer division) and '^' (power) and then solve the task.
  • Change task in the following way :"In each expression x and y, each of them must be used at least once, but can be used at most k times. k (1 <= k <= 4) is given." Try to solve this task.

MatchString rate it discuss it
Used as: Division Two - Level Three:
Value 900
Submission Rate 226 / 715 (31.61%)
Success Rate 104 / 226 (46.02%)
High Score dlwjdans for 852.28 points (6 mins 47 secs)
Average Score 541.34 (for 104 correct submissions)

This task was a greedy one. The key to the solutions was to check all possible positions of matchString. Once you figure out that, the problem becomes very easy. Let maxlen be the length of the longest word from matchWords and lp be the furthest possible position where matchString should be placed - that means if there is a solution at lp+m position, m > 0, then there is the solution at the position lp. Let's show lp=maxlen. Suppose it is not truth, and there is some pos=maxlen+m optimal position. Then each word must be placed between the position pos-maxlen+1 and the position pos. But pos-maxlen+1=maxlen+m-maxlen+1=m+1 which means that each word is shifted at least m times. If we shift each word m times, arrangement is the same as we didn't make those m shifts at all. So, m shifts are sufficient in this case and lp=maxlen.
When you put matchString at some position, each word matchWords[i] shift as less as you need in order to overlap corresponding letter in matchWords[i] with matchString letter at the position i. Bellow is solution in Java:

    public int placeWords(String matchString, String[] matchWords){
    int n = matchString.length();
    int inf = 1 << 20;
    int sum = inf;
    // find the last possible position of matchString
    int lp = 0;
    for (int i = 0; i < n; i++)
        lp = Math.max(lp, matchWords[i].length());

    String word;
    // try for each position
    for (int pos = 0; pos < lp; pos++){
        int s = 0;
        // for fixed position of matchString, calc position of elements in matchWords
        for (int i = 0; i < n; i++){
            word = matchWords[i];
            // this calc we can do greedy. start from the last possible character of matchWords el
            // and move to the begging of the element. if you find some position that can
            // make solution remember it, else just continue with next position of matchString
            int lidx = Math.min(pos, word.length() - 1), j;
            for (j = lidx; j > -1; j--)
                if (word.charAt(j) == matchString.charAt(i)){
                    s += (pos - j);
            if (j == -1){
                s = inf;
        if (s < sum)
            sum = s;
    if (sum == inf)
        return -1;
    return sum;
You can take a look at delicato's solution here.
Time complexity of described algorithm is O(maxlen^2*n), where n is number of puzzle words. With simple precalculating time complexity can be reduced to O(maxlen*n). Let c be i-th letter of matchString. For each position j, 0<=j<matchWords[i].length(), calc the last occurence of the letter c in the first j letters of matchWords[i]. With this information, instead to each time calculate where is the last occurence of some letter, you can get the answer in constant time. As reference you can take a look at my solution in the practice room.


  • Try to solve the task if you should return int[], where i-th element represents number of places i-th word was shifted - sum of shifts still have to be minimal. In case of tie return int[] with first element minimal; in case of tie return int[] with two first element minimal etc.

CountPaths rate it discuss it
Used as: Division One - Level Two:
Value 500
Submission Rate 349 / 559 (62.43%)
Success Rate 256 / 349 (73.35%)
High Score hesibo for 474.85 points (6 mins 36 secs)
Average Score 297.96 (for 256 correct submissions)

This is modification of well-known dynamic programming problem. Let special field i be field given by (fieldrow[i], fieldcol[i]).
Let DP[i][j][k][len] be number of differents path of length len from position (1, 1) to the position (i, j) with the last visited special field k. The problem statement says that position (i, j) could be reached only from the positions (i-1, j) and (i, j-1), so number of different paths from (1, 1) to (i, j) depends only on number of different paths from (1, 1) to (i-1, j) and (1, 1) to (i,j-1), so first calc DP[i-1][j] and DP[i][j-1] and then DP[i][j].
Let's define recursive relation for position (i, j):

  • (i, j) is special field:
    DP[i][j][k][len] = DP[i-1][j][0][len-1] + DP[i][j-1][0][len-1] + DP[i-1][j][1][len-1] + DP[i][j-1][1][len-1] + ... + DP[i-1][j][k-1][len-1] + DP[i][j-1][k-1][len-1]
    If (i, j) is special field and path from (1, 1) to (i, j) has len special fields as part of it, then paths from (1, 1) to (i-1, j) and (1, 1) to (i, j-1) must have len-1 special fields.
  • (i, j) is not special field:
    DP[i][j][k][len] = DP[i-1][j][k][len] + DP[i][j-1][k][len]. In this case nothing has changed except for position. If number of special fields from position (1, 1) to (i, j) contains len special fields and as part of it contains path from (1, 1) to (i-1, j) then that path from (1, 1) to (i-1, j) must contain len special fields. It is similary for last visited special field.
And one more thing should be explained: let set A contains all diferent paths from (1, 1) to (i-1, j) and set B contains all different path from (1, 1) to (i, j-1), then it is obvious that A union B contains all different paths because at least the last visited field of each path from set A (field at position (i-1, j)) is different from the last visited field of each path from set B (field at the position (i, j-1)). Bellow is implementation in Java:
    public int[] difPaths(int r, int c, int[] fieldrow, int[] fieldcol){
    int mod = 1000007;
    int n = fieldrow.length;
    int ret[] = new int[n + 1];
    // dp[i][j][k][l] - positions (i, j), with last visited field k, length l
    // if l = 0, it will be considered that k = 0, although k doesn't exists
    int dp[][][][] = new int[r + 1][c + 1][Math.max(n, 1)][n + 1];
    int pos[][] = new int[r + 1][c + 1];
    for (int i = 0; i <= r; i++){
        Arrays.fill(pos[i], -1);
        for (int j = 0; j <= c; j++)
            for (int k = 0; k < n; k++)
                Arrays.fill(dp[i][j][k], 0);
    for (int i = 0; i < n; i++)
        pos[fieldrow[i]][fieldcol[i]] = i;
    dp[1][0][0][0] = 1;
    for (int i = 1; i <= r; i++)
        for (int j = 1; j <= c; j++){
            // l = 0
            if (pos[i][j] == -1)
                dp[i][j][0][0] += (dp[i - 1][j][0][0] + dp[i][j - 1][0][0]) % mod;
            for (int l = 1; l <= n; l++)
                if (pos[i][j] == -1)
                    for (int k = 0; k < n; k++)
                        dp[i][j][k][l] += (dp[i - 1][j][k][l] + dp[i][j - 1][k][l]) % mod;
                    int cp = pos[i][j];
                    if (l == 1)
                        dp[i][j][cp][l] += (dp[i - 1][j][0][0] + dp[i][j - 1][0][0]) % mod;
                        for (int k = 0; k < cp; k++)
                            dp[i][j][cp][l] += (dp[i - 1][j][k][l - 1] + dp[i][j - 1][k][l - 1]) % mod;
    for (int l = 0; l <= n; l++){
        ret[l] = 0;
        for (int k = 0; k < Math.max(n, 1); k++){
            ret[l] += dp[r][c][k][l];
            ret[l] %= mod;
    return ret;

It seems that some memoization solutions for this problem was too slow, so be careful. Also, solution will probably timeout if at each step for some field you check whether it is special field or not. It is better to cacl that information once and store somewhere. This algorithm gives time and space complexity n^4. For clean and fast solution you can take a look at ainu7's solution here.


  • With number of special fields below 10 and if return is sum of path of all lenghts, could that problem be solved as combinatorial one?

MyFriends rate it discuss it
Used as: Division One - Level Three:
Value 1000
Submission Rate 119 / 559 (21.29%)
Success Rate 24 / 119 (20.17%)
High Score nigulh for 833.26 points (13 mins 16 secs)
Average Score 538.88 (for 24 correct submissions)

This problem can be divided into four parts. First two parts contain proofs that number of friends for each kid (used as array f in the parts) is unique. First and third part give algorithm that is used to obtain array f. Forth part shows how this task can be transformed into graph problem and gives one solution for the final answer - "POSSIBLE" or "IMPOSSIBLE". Now let's examine each part in details.

First part
Let f[i] be number of kid i's friends, S the sum of friends of all kids and SSF sum of all sumFriends[i] from the input. Then statements for some kid i could be written as

            J_i: sumFriends[i] = S - f[i] - f[(i+k)%n]
Let's sum all J_i
            SSF = n*S - (f[0] + f[1] + ... + f[n-1]) - (f[(0+k)%n] + f[(1+k)%n] + ... + f[(n-1+k)%n]  <=>
            SSF = n*S - S - S <=>
            SSF / (n-2) = S
This is part where we check if return could be "IMPOSSIBLE" - SSF must be divisible by n-2. Let's go on and transform J_i:
J_i: S - sumFriends[i] = f[i] + f[(i+k)%n] - let C[i] be S - sumFriends[i]
We know S and we know sumFriends[i], so we know f[i]+f[(i+k)%n]. Now we should check that f[i]+f[(i+k)%n] >= 0 holds for every i.

Second part
Suppose that (i+p*k)%n=(i+q*k)%n and 0<=p<=q<n/GCD(n, k). Lets transform that into (q*k-p*k)%n=((q-p)*k)%n=0. We have two options
1. q - p = 0 => q = p
2. (q - p)*k = r*LCM(n, k) = r*k*n / GCD(n, k) => (q-p) = r*n / GCD(n, k), but 0 <= p < q < n/GCD(n, k), so this option is impossible.
We proved that in case above p = q - call it Proof 1.

Define Seq_i as list: i, (i+k)%n, (i+2*k)%n, ..., (i+m*k)%n; where (i+m*k)%n is first index that already exists in Seq_i for some (i+r*k)%n, r < m. Such r must exists because Seq_i is finite. It is also true that m <= n/GCD(n, k). Let's proove that m = n/GCD(n, k).
m = n/GCD(n, k) is the highest value of m, because i=(i+k*n/GCD(n, k))%n.
Suppose m<n/GCD(n, k) and there exists some p such that (i+p*k)%n=(i+m*k)%n, 0<=p<m, but according to the Proof 1 it is impossible, so m=n/GCD(n, k) => (i+m*k)%n=i.
That means indexes of each Seq_i form a cycle and all Seq have the same length - the length n/GCD(n, k). For each Seq_i and Seq_j we should proove that either Seq_i is same as Seq_j or they don't have common elements. Although it is very obvious, let's make short proof.
Suppose that
Seq_i: i, (i+k)%n, (i+2*k)%n, ..., (i+c1*k)%n,..., (i+m*k)%n
Seq_j: j, (j+k)%n, (j+2*k)%n, ..., (j+c2*k)%n,..., (j+m*k)%n
and (j+c2*k)%n = (i+c1*k)%n. But that means ((j-i)+(c2-c1)*k)%n = 0. Because Seq_j is cyclic we can always choose such j that c1 = c2 and then we have (j-i)%n=0, 0<=i,j<(n-1) => i=j.

We can conclude that number of different lists Seq is equal to n/(n/GCD(n, k))=GCD(n, k) and each list has odd number of elements (n is an odd number, so n/GCD(n, k) is an odd number, too).

Third part
In order to make it easier for reading and understanding, let gr=n/GCD(n, k)-1.
Consider particular list Seq_i that actually represents independent system of equations. From the first part we can write:
                J_i: f[i]         + f[(i+k)%n]    = C[i]
        J_((i+k)%N): f[(i+k)%n]   + f[(i+k*2)%n]  = C[(i+k)%n]
      J_((i+k*2)%N): f[(i+k*2)%n] + f[(i+k*3)%n]  = C[(i+k*2)%n]
     J_((i+k*gr)%n): f[i]         + f[(i+k*gr)%n] = C[(i+k*gr)%n]
Sum left and right sides:
J_((i+k*gr)%n) - J_i + J_((i+k)%n) - J_((i+2*k)%n) + J_((i+3*k)%n) - ... + J_(i+k*(gr-1)) =
C[i+k*gr] - C[i] + C[(i+k)%n] - C[(i+2*k)%n] + C[(i+3*k)%n] - ... + C[i+k*(gr-1)] =
2 * f[(i+k*gr)%n]

Now we can calculate f[(i+k*gr)%n], then f[(i+k*(gr-1))%n], ..., and finally f[i]. If we do this for all Seqs, we will get all f[i].
We can take this way of suming in order to get f[i] because number of equations in the system is odd. In case it is even the sum will be 0.
At each part you are dividing something, check whether it is possible to divide and get integer without reminder as the result. Also check whether number of friends of some kid is non-negative number and less than number of all kids. If these conditions are not satisfied, return "IMPOSSIBLE".

NOTE: All three parts could be replaced by Gaussian elimination. However, in this case we should guess that the solution is unique.

Forth part
When we get f[i], each kid can be represented as vertex and there will be edge between two kids iff those kids are friends. So, the question becomes: "If you are given degrees of all vertices in the graph, return whether such graph exists."
To give the answer, we can use Havel-Hakimi algorithm. Here is short description of the algorithm:
init array deg[i] <- f[i]
repeat this n times
    sort array deg in ascending order
    take the highest one, let it be deg[n-1]
    deg[n-1] <- 0
    for n-1-f[n-1] <= i <= n-2
        if deg[i] is 0 return "IMPOSSIBLE"
        else deg[i] <- deg[i]-1
return "POSSIBLE"
You can take a look at fero's solution here which seems very clear.


  • Solve the task if n is even. What condition should be satisfied so that values f[i] have unique solution?

By boba5551
TopCoder Member