Match Editorial

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

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

• Elements lower or equal to A[i]
• Elements greater than A[i]

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;
    
    Arrays.sort(a);
    // 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

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])
            break;
    
    for (int i = idx + 1; i < 10001; i++)
        if (used[i]){
            ret = Math.min(ret, i - idx);
            idx = i;
        }
        
    return ret;
}

Exercise

• 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.

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)

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);
}    

Exercise

• 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.

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);
                    break;
                }
            if (j == -1){
                s = inf;
                break;
            }
        }
        if (s < sum)
            sum = s;
    }
    if (sum == inf)
        return -1;
    return sum;
}

Exercise

• 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.

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.

    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;
                else{
                    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;
                    else{
                        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;
}

Exercise

• 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?

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]

            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
            

                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]

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
loop
return "POSSIBLE"

Exercise

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