SRM 625: I semi-wrote it

Two days ago I was busy trying to come up with a way to finish SRM 624's editorial. I get how to solve div1 hard in the top level, I have no idea how to explain the initial step: Split in centers subtrees. I am fairly sure it is probably a known algorithm, can't find info. Was stuck there when I was contacted by the admins about SRM 625. They needed problems urgently and I apparently had some problems that were created long ago and could work.

I wrote all problems except div1 hard (the important one). They really weren't intended to be part of the same match. And I think that they go more towards the standard side of things. Please note that I've gone through a huge writer's block and I can't seem to come up with interesting problems anymore. But oh well. I just hope there are no big issues of the sort that cause match cancellations.

Div2 250: The one with challenge phase

Unlike the other problems, I thought of this one specifically for this match. Ever since multiple-answer problems were added to topcoder, I wanted to make something that takes advantage of it.

The problem is easy, given `y` find `(a,b,c)` such that `ab + c = y`, `(a,b,c)` must be integers between -1000 and 1000 different to 1 and 0. `y` is between 0 and 500. Otherwise any `(a,b,c)` is correct.

There is a bruteforce search here. But we can also get clever. Note that no matter which two values `(a,b)` you pick, there will always be a `c = y - ab`. So we can do `(a,b) = (1,1)` and then `c = y - 1`. This would be wrong because values cannot be 0 or 1. But we can try to pick values `(a,b)` that don't have this problem. For example `(a,b) = (2,2)`, now `c = y - 4`. This is almost fine, but `y = 4` or `y = 5` would yield a wrong value of `c`. We could handle those cases separately OR we could try something different. We would like `y - ab` to be distinct to 0 or 1. How about : `y - ab > 1` then `ab < y -1`. We can guarantee this to be true with `(a,b) = (2,-2)`. Then we have `c = y + 4`. So the result can always be `(2,-2, y + 4)`.

Div2 500: The one with sequences

This problem is very old. I think I thought of it for some TCO qualification round of a past TCO. I didn't even remember much about the problem. It was already developed but it was never used. So we mostly just enabled the problem for use.

If I remember correctly, this problem can be very tricky.

Div2 1000: Minimum Liars Again

A circle of friends. For each i, we have answers[i]:

• If answers[i] is ?, we didn't ask friend i anything.
• Else we asked the i-th friend if friend (i + 1) mod n is a liar. If friend i is a honest person, they would always tell the truth , else they would always lie. answers[i] is H if friend i said friend (i + 1) mod n is a honest person, else L.

Return the minimum number of liars in a consistent case. If no case can be consistent, return . 1.

This is another very old problem. It was also already developed, but for `n <= 20`. We decided `n <= 50` is better for this problem slot.

The idea is simple: If there are no ? in the input, the whole thing is cyclic. You can try making the first person a liar or not. If first person is a liar, and you know their answer, then you know if second person is a liar, then third person and so and so. Eventually, you will know if person `n - 1` is a liar or not, and this is important the conclusion we make about person 0 must be consistent with the hypothesis we made. Return the minimum number of liars in the consistent cases.

If there is at least one ? , the case is not really cyclic. You can just split the friends in groups of consecutive non-? friends. These cases are linear and you can use the same logic (try if first person is a liar or not). But this time, no consistency is needed.

Like this:

import itertools
class ConundrumReloaded:
 def minimumLiars(self, answers):
        
    def simulateLine(f, s):
        p = f
        liars = 0
        for i in range(1, len(s) + 1):
            h = (answers[i - 1] == 'H') ^ (not p)
            liars += not h
            p = h
        #print (f,s), (liars,p)
        return (liars, p)
        
    n = len(answers)
    q = -1
    for i in range(n):
        if answers[i] == '?':
            q = i
    INF = 10**9
    res = INF
    if q == -1:
        for f in (0,1):
            (liars, p) = simulateLine(f, answers)
            if p == f:
                res = min(res, liars)
    else:
        res = 0
        curr = ''
        for i in range(n + 1):
            j = (i + q) % n
            if answers[j] == '?':
                if curr != '':
                    res += min( (not f) + simulateLine(f, curr)[0] for f in (0,1) )
                    curr = ''
            else:
                curr = curr + answers[j]
        
    return -1 if res >= INF else res

Div1 250: When you are desperate combine palindromes and probabilities

Given a string. We pick one of its anagrams with uniform probability. Return the probability the picked anagram is palindrome.

This problem is also very old. I think I tried to use it in many matches, but (thankfully) we always found something more interesting and less standard. Until now.

Simply return: (Number of palindrome anagrams) / (Number of anagrams).

The number of anagrams is calculated by dividing `n!` by `r!` for each letter in word that is repeated `r` times.

So we just need to calculate the number of palindrome anagrams. First of all, if `n` is even, then all characters must appear an even number of times. If `n` is odd then only one character should appear an odd number of times. If `n` is odd, we already know what character is in the center and we can just remove it and treat it as if everything was even.

We have many letters that appear an even number of times. We know that we should put each of these letters in both sides of the palindrome. The order depends only on the first side. So actually, we should count the number of ways to order the `n/2` letters that remain after dividing each letter quantity by 2. This is the same as dividing `(n/2)!` by `(r/2)!` for each letter that is repeated `r` times.

As I type this, it appears that many people including div1 hard's writer have issues with precision in their solutions.

Div1 500: The one with blocks

The original version of this problem was meant for the last TCO rounds, I think last year. But was too complicated. In the original version , there were multiple goals and exactly two start cells. I don't even remember how was it solved.

In the current version, there are multiple start cells but only one goal. The game is symmetric so we can just begin at the goal and if it reaches a start cell, there is a solution if you begin at that start cell.

So we should just find the minimum number of holes to cut the path between the goal cell and any start cell.

Now analyze the allowed moves, you will see that the set of reachable cells is like this:

*SZ*SZ*
A  A  A
V  V  V
*SZ*SZ*
A  A  A
V  V  V
*SZ*SZ*

Where SZ are horizontal 2x1 pairs of cells that can be touched by a 2x1 face, the * are the cells that can be touched by 1x1 faces (including the goal) and AV the vertical 2x1 pairs of cells.

We can just ignore any start cell that is not *, no matter what we do, we can't reach them.

So now we just have a minimum cut problem. The trick is to take the 2x1 pairs of cells as edges then the cost to remove an edge equals the number of normal cells in the edge. You can also remove * cells, this means using an intermediary edge connecting entry and exit point for each * cell. Okay. The minimum cut requires you to get clever and implementation will be a headache but the concept is easy!