May 25, 2017 2017 TCO Algorithm Round 2A Editorials

TCO17 Round 2A Editorials are now published. Thanks to our very own cgy4ever for writing interesting problems and the detailed editorials. You may discuss the editorials in the discussion forum.
Round 2A is the first contest in TCO2017 that is open to every coder including the top rated ones(the ones who got a bye in round 1). Interestingly, our TCO champions in last 3 years, rng_58, Petr and tourist started with different tasks (Medium, Easy and Hard) and they all solved all 3 tasks to end up in top 4.
The tasks in this round were old Topcoder style: when you get the idea right they can be solved easily with very short code . So the top contestants solved them quickly: the first 2 contestants to solve all 3 tasks are rng_58, Petr, they all solved them in exactly same amount of time: 43 minutes plus 4 seconds.
In order to get top 40, one needed to solve Easy and Medium quickly, or solve Hard with another task. The examples did not include some tricky test cases intentionally to reward coders who did the reasoning formally and creates opportunities for challenge phase.
 
2017 TCO Algorithm Round 2A – Division I, Level One – FoxAndCake2
The key observation in this task is that in most cases the answer is ‘Possible’: for sufficiently large enough c and s:

• If both c and s are even numbers, we can make a single cake (c, s).
• If both c and s are odd numbers, we can make 2 cakes: (3, 3) and (c-3, s-3).
• If one of them is odd and another is even, say c is even but s is odd, then we can make 2 cakes (3, 6) and (c-3, s-6).

This works for any c,s >= 7. What we need to do is to carefully analysis the remaining cases. Without losing generality, we assume c<=s:

• If c = 1, then that is impossible.
• If c = 2, then it is possible only if s mod 2 = 0, we can make a single cake (2, s).
• If c = 3, then it is possible only if s mod 3 = 0, we can make a single cake (3, s).
• If c = 4, then it is possible only if s mod 2 = 0, we can make a single cake (4, s).
• If c = 5:
  • If s = 5, it is possible, we can make a single cake (5, 5).
  • If s = 6, it is impossible
  • If s > 6, then it is always possible (use the way we mentioned above for both odd case and odd – even case).
• If c = 6: then it is possible only if s mod 2 = 0 or s mod 3 = 0, we can make a single cake (6, s).

Some other ideas of solving it:

• Figure out that using 1 or 2 cakes is enough. What’s more is that one of the cake must be small, say less than 6 cherry and strawberry.
• Use brute force (or dynamic programming) to calculate answer for small c and s, then find patterns.

Code

public class FoxAndCake2 {
    boolean check(int a, int b) {
        if(a > b) {
            int t = a; a = b; b = t;
        }
        if(a == 5 && b == 6) return false;
        if(a > 6) return true;
        if(a == 1) return false;
        if(a == 2) return b % 2 == 0;
        if(a == 3) return b % 3 == 0;
        if(a == 4) return b % 2 == 0;
        if(a == 5) return true;
        return (b % 2 == 0 || b % 3 == 0);
    }
    public String isPossible(int c, int s) {
        if(check(c, s)) return "Possible";
        return "Impossible";
    }
}

2017 TCO Algorithm Round 2A – Division I, Level Two – DistanceZeroAndOne
Let’s start with these 2 key observations, suppose for a given input there exist a solution, let’s call it graph G:

1. For any two vertices a and b, if  , then `edge(a, b) is not in graph G.
2. For any two vertices a and b, if and there is no edge(a, b) in graph G:  let G’ be the graph G + edge(a, b), then G’ is another valid solution.

That means if we repeat step 2, we will get a graph H which is valid solution: H contains all edges (a, b) such that 
So we have a solution:

1. For a given input, we will calculate graph H.
2. Then we verify if it is valid, if so then we return graph H, otherwise output ‘no solution’.

 
This is correct since:

1. If the given input has a solution, then as we proved above, H, the output of our program, is a valid solution.
2. If the given input does not have a solution, then H is not a valid solution, and our program will output ‘no solution’.

public class DistanceZeroAndOne {
    int[] retDist0;
    int[] retDist1;
    void computeDistance(boolean[][] mat) {
        int n = mat.length;
        retDist0 = new int[n];
        retDist1 = new int[n];
        int[][] dist = new int[n][n];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(i == j) {
                    dist[i][j] = 0;
                } else if(mat[i][j]) {
                    dist[i][j] = 1;
                } else {
                    dist[i][j] = 1000000000;
                }
            }
        }
        for(int k = 0; k < n; k++) {
            for(int i = 0; i < n; i++) {
                for(int j = 0; j < n; j++) {
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
        for(int i = 0; i < n; i++) {
            retDist0[i] = dist[0][i];
            retDist1[i] = dist[1][i];
        }
    }
    boolean eq(int[] l1, int[] l2) {
        if(l1.length != l2.length) return false;
        for(int i = 0; i < l1.length; i++) {
            if(l1[i] != l2[i])
                return false;
        }
        return true;
    }
    boolean[][] solve(int[] dist0, int[] dist1) {
        int n = dist0.length;
        boolean[][] ret = new boolean[n][n];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(i == j)
                    continue;
                if(Math.abs(dist0[i] - dist0[j]) <= 1 && Math.abs(dist1[i] - dist1[j]) <= 1)
                    ret[i][j] = true;
            }
        }
        return ret;
    }
    public String[] construct(int[] dist0, int[] dist1) {
        boolean[][] mat = solve(dist0, dist1);
        computeDistance(mat);
        if(eq(dist0, retDist0) && eq(dist1, retDist1)) {
            int n = dist0.length;
            String[] ret = new String[n];
            for(int i = 0; i < n; i++) {
                ret[i] = "";
                for(int j = 0; j < n; j++) {
                    if(mat[i][j])
                        ret[i] += "Y";
                    else
                        ret[i] += "N";
                }
            }
            return ret;
        }
        return new String[]{};
    }
}

2017 TCO Algorithm Round 2A – Division I, Level Three – FourLamps
The rule of ‘4 lamps’ looks random, so the key to this task is to understand it in a good perspective.
Let s[] be the state of lamps, 1 is on and 0 is off. We know that the special condition is:
Among, there is only one 0, or only one 1. Note that it means the number of 1 is odd, which is a big hint, we can rewrite this condition into (here + is xor, or equivalently, under mod 2) :

 
It is still a bit hard to deal with 4 lamps, let’s do this transformation:
 
Let then the condition becomes: 
Note that in order to represent, we need to know .
What will the result look like after one operation in the perspective of d and ? It will be:

1. Choose x such that           
2. Do one of the following

If we ignore the “flip both” part, this problem looks like the following:
Given n boxes and k balls (for each ‘1’ in d, it represent a ball), in each operation we can move a ball into an adjacent empty box. We want to find out how many stats we can get in at most k operations.
This problem is well-known, and the key to solve is this observation:
Letbe the position of balls from left to right in initial state, and be the position of balls from left to right in the final state. We know that the minimal number of operations we need to get it is: 
The it can be solved by dynamic programming easily. The idea is to generatewhile recording .
What left is the special thing about “flip both”. Note that for any state we can get in at least 1 step, we can do this flip odd or even number of times, that means we can get 2 different states of. For the initial state, we can “flip both s0, s1” only if k > 1, it is because after one step we will change  , we need one more operation to restore it.
 

import java.util.*;
public class FourLamps {
    int nGaps;
    int nOnes;
    List  positionOnes;
    long[][][] mem;
    long f(int cur, int haveOnes, int remainDistances) {
        if(haveOnes > nOnes) return 0;
        if(remainDistances < 0) return 0;
        if(cur == nGaps) {
            if(haveOnes == nOnes) return 1;
            return 0;
        }
        if(mem[cur][haveOnes][remainDistances] != -1)
            return mem[cur][haveOnes][remainDistances];
        long ret = 0;
        ret += f(cur + 1, haveOnes, remainDistances);
        if(haveOnes < nOnes)
            ret += f(cur + 1, haveOnes + 1, remainDistances - Math.abs(cur - positionOnes.get(haveOnes)));
        mem[cur][haveOnes][remainDistances] = ret;
        return ret;
    }
    public long count(String s, int k) {
        String diff = "";
        for(int i = 0; i < s.length() - 1; i++) {
            if(s.charAt(i) != s.charAt(i+1))
                diff += '0';
            else
                diff += '1';
        }
        s = diff;
        nGaps = s.length() - 1;
        nOnes = 0;
        positionOnes = new ArrayList<>();
        int nZeros = 0;
        for(int i = 0; i < s.length()-1; i++) {
            if(s.charAt(i) != s.charAt(i+1)) {
                nOnes ++;
                positionOnes.add(i);
            } else {
                nZeros ++;
            }
        }
        if(nOnes == 0 || nZeros == 0) return 1;
        mem = new long[nGaps][nOnes+1][nGaps*nGaps+1];
        for(int i = 0; i < nGaps; i++) {
            for(int j = 0; j < nOnes+1; j++) {
                for(int l = 0; l < nGaps*nGaps+1; l ++)
                    mem[i][j][l] = -1;
            }
        }
        return f(0, 0, Math.min(k, nGaps * nGaps)) * 2 -(k == 1 ? 1 : 0);
    }
}