May 11, 2019 Single Round Match 756 Editorials

Note: The editorial and the problem NewBanknote were written by misof, all other problems were written and prepared by IH19980412.

CinderellaGirls

The easiest solution is to implement the check described in the problem statement as two nested loops: for each girl A look at each other girl B and check whether B disqualifies A.

Sample implementation in Python:

    def count(self, talent, skill):
        answer = 0
        N = len(talent)
        for a in range(N):
            advances = True
            for b in range(N):
                if talent[b] > talent[a] and skill[b] > skill[a]:
                    advances = False
            if advances:
                answer += 1
        return answer

PAndPuns

Checking for puns by simply implementing their definition may be too small. Luckily, we can make an easy observation that will make our code both faster and simpler. Suppose you have two non-overlapping occurrences of some string S such that |S| > 2. If you take just the first two characters of each of them, you now have two non-overlapping occurrences of some string T such that |T| = 2.

In other words, an equivalent definition of a pun is that a text is a pun iff it contains two non-overlapping identical substrings of length exactly 2. And this is easy to check in O(n^2) using brute force: we just iterate over all possible locations of their beginnings.

    def check(self,text):
        for a in range(len(text)-3):
            for b in range(a+2,len(text)-1):
                if text[a:a+2] == text[b:b+2]:
                    return 'pun'
        return 'not a pun'

NewBanknote

Solution: For each i between 0 and 50,000, try using the new banknote exactly i times. If we already paid too much, break. Otherwise, pay the remaining amount greedily. Pick the best solution over all i.

Below, we prove the correctness of this solution.

Observation: For any amount within the given constraints, the new banknote will never be used more than 50,000 times.

Proof: If the new banknote is the largest of all denominations, 50,000 pieces of the banknote have the value at least 50,000^2, and that is already bigger than the largest amount we can be asked to pay.

If the new banknote with value B is smaller than the largest original banknote (which has the value 50,000), we will never use 50,000 copies of B because it’s strictly better to use B copies of the 50,000-cent banknote.

    int greedy(int suma) {
        int[] denominations = {1, 2, 5, 10, 20, 50, 100, 200, 500,
                               1000, 2000, 5000, 10000, 20000, 50000};
        int used = 0;
        for (int d=14; d>=0; --d) {
            used += suma / denominations[d];
            suma %= denominations[d];
        }
        return used;
    }
    public int[] fewestPieces(int newBanknote, int[] amountsToPay) {
        int Q = amountsToPay.length;
        int[] answer = new int[Q];
        for (int q=0; q<Q; ++q) {
            answer[q] = amountsToPay[q];
            for (int i=0; i<=50000; ++i) {
                long mam = newBanknote;
                mam *= i;
                if (mam > amountsToPay[q]) break;
                int remains = (int)(amountsToPay[q] - mam);
                answer[q] = Math.min( answer[q], i + greedy(remains) );
            }
        }
        return answer;
    }

There are also other ways to get a similar upper bound. For example, you can start by trying to pay the given amount using just the original Euro denominations. This gives you some valid solution that uses X pieces, with X being at most in tens of thousands. Then, it’s obviously not optimal to use the new banknote more than X times, because you are already using too many pieces.

For completeness, we also include a sketch of the proof that for the Euro denominations the optimal number of coins and banknotes to pay any amount can always be determined using the straightforward greedy algorithm: always take the largest one that does not exceed the amount left to pay.

There are general techniques how to show that a greedy algorithm works for a given set of denominations – essentially, it’s enough to check that it matches the optimum (which is easily computed using dynamic programming) on all amounts from 1 to some reasonably low threshold. However, for Euro we can also make a simpler, self-contained proof.

Note that the Euro denominations come in groups of three, always having the values (1,2,5) times some power of 10. If we start with the smallest ones, we can easily verify that any amount between 1 and 9 cents will be paid optimally. Now we can notice the following property: in an optimal solution you will only use these coins to pay at most 9 cents. This is because if you use them to pay 10 or more, you can always swap some of them for a single 10-cent coin, or you can swap some of them for a 10-cent and a 1-cent coin, always getting the same amount paid using fewest pieces. Hence, when paying any amount, we use the 1,2,5-cent coins to pay whatever is the last digit of the amount, and then we can forget about them.

Repeating this argument gives you the proof that the optimal solution is indeed always the one found by the greedy algorithm.

CrazyCrazy

We can solve this problem using the meet-in-the-middle technique. Imagine that we split the string into two halves. First, let’s take the first half of the string and try all 2^(n/2) possibilities for which girl gets which letters. Without loss of generality, we can only consider those in which Shiki gets at least as many letters as Frederica. In some of them, the string Frederica gets will not be a prefix of Shiki’s string. Those options are clearly wrong. Thus, we only look at the options where Frederica’s string is a prefix of Shiki’s string, and for each of them the thing we store is the rest of Shiki’s string — i.e., the part of the song Shiki already heard and Frederica didn’t.

Next, we do the same with the second part of the string, but now we only check options in which Frederica gets at least as many letters as Shiki, and Shiki’s string is a suffix of Frederica’s string. We can reuse the same code we used for part 1 by reversing the second half of the string before we call it, and reversing all the outputs it returns.

Now, all that remains is to check whether we have a match. For the first part we have all possible parts of song that can be heard by only Shiki in a valid solution, for the second part we have all possible parts that can be heard only by Frederica, hence the song is good if and only if the same string appears in both sets. This is easy to check using any efficient data structure (or even using binary search).

set<string> get_diffs(const string &song) {
    int N = song.size();
    set<string> answer;
    for (int sub=0; sub<(1<<N); ++sub) if (__builtin_popcount(sub)*2 >= N) {
        string first, second;
        for (int n=0; n<N; ++n)
            if (sub & 1<<n) first += song[n]; else second += song[n];
        if (first.substr(0,second.size()) == second)
            answer.insert( first.substr(second.size()) );
    }
    return answer;
}
struct CrazyCrazy {
    string possible(string song) {
        int N = song.size() / 2;
        string first_half = song.substr(0,N), second_half = song.substr(N);
        auto diffs1 = get_diffs(first_half);
        reverse( second_half.begin(), second_half.end() );
        auto diffs2 = get_diffs(second_half);
        for (string diff2 : diffs2) {
            reverse( diff2.begin(), diff2.end() );
            if (diffs1.count(diff2)) return "possible";
        }
        return "impossible";
    }
};

Newgenerations

Clearly, if all four neighbors of a special cell are active, there is no way to color the pipes: we will have two pipes of the same color leaving this special cell due to the pigeonhole principle. Thus, we have a necessary condition: each special cell must have at least one neighbor that is not active.

Luckily for us, this condition is not just necessary but also sufficient for a valid coloring to exist.

Consider a graph in which vertices are the special cells and their active neighbors, and edges are pipes. This is a bipartite graph with degrees at most three. Forget about the topology of the graph and view it just as an abstract bipartite graph. Imagine that we add new vertices and new edges to make both partitions have the same size and to make each vertex have degree exactly 3. By Hall’s theorem we know that this graph has a perfect matching. Color those edges using the same color, discard them, repeat twice more. Thus, the original graph has a valid 3-edge-coloring. In other words, whenever each special cell has a non-active neighbor, we can always 3-color the surroundings of the special cells.

Thus, all that remains is to count the number of ways in which the undecided cells are turned into active and nonactive cells in such a way that the property we just discovered holds. This can be done using the principle of inclusion and exclusion: count all ways, for each special cell subtract the ones where it has all neighbors active, for each pair of special cells add back the ways in which all their neighbors are active, and so on.

public int count(String[] field){
    int N = field.length;
    int M = field[0].length();
    long mod = 1000000007;
    int [] posx = new int [25];
    int [] posy = new int [25];
    boolean [][] select = new boolean [55][55];
    long [] bin = new long [2505];
    bin[0] = 1L;
    for(int i=1;i<2505;i++) bin[i] = bin[i-1]*2L%mod;
    int cnt = 0, num_free = 0;
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            if(field[i].charAt(j) == 'x'){
                posx[cnt] = i;
                posy[cnt] = j;
                cnt++;
            }
            else if(field[i].charAt(j) == '*'){
                num_free++;
            }
        }
    }
    long ans = 0L;
    int [] dx = {0,0,1,-1};
    int [] dy = {1,-1,0,0};
    for(int mask=0;mask<(1<<cnt);mask++){
        long flag = 1L;
        boolean bad = false;
        int free = num_free;
        ArrayList<Integer> changexy = new ArrayList<>();
        for(int i=0;i<cnt;i++){
            if((mask & (1<<i)) > 0){
                flag *= -1L;
                for(int j=0;j<4;j++){
                    int nx = posx[i]+dx[j];
                    int ny = posy[i]+dy[j];
                    if(0<=nx && nx<N && 0<=ny && ny<M
                             && field[nx].charAt(ny) != '.'){
                        if(field[nx].charAt(ny) == '*'){
                            if(select[nx][ny] == false){
                                free--;
                                select[nx][ny] = true;
                                changexy.add(nx*64+ny);
                            }
                        }
                    }
                    else{
                        bad = true;
                        break;
                    }
                }
            }
        }
        if(!bad){
            ans += bin[free] * flag;
            if(ans < 0) ans += mod;
            if(ans >= mod) ans -= mod;
        }
        for(int i=0;i<changexy.size();i++){
            int V = changexy.get(i);
            select[V/64][V%64] = false;
        }
    }
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            assert select[i][j] == false;
        }
    }
    ans = (ans%mod+mod)%mod;
    return (int)(ans);
}