Codeforces "Good bye 2013" round

So it was a special round for coders of both divisions, problems ranged from the super easy problem A to the super difficult problems E,F,G... I always mean to participate in CF rounds but time constraints are tough. Since this was a special match I decided to give it a try.

Problem A: New Year Candles

problem statement

I mentioned this was an easy problem. Just simulate the process. For each candle, use it, increment the used candles counter, if used candles ever reaches `b`, join these used candles together to make a new one: set the counter to 0 and increment the number of available candles. The constraints are small so the simulation is fast enough:

int solve(int a, int b)
{
    int r = 0, u = 0;
    while (a > 0) {
        a --;
        r += 1;
        u ++;
        if (u >= b) {
            a ++;
            u -= b;
        }
    }
    return r;
}

Just because a problem is easy, it doesn't mean it is easy to get a good score in comparison to other coders. Indeed, even though I coded this one as fast as possible, by the time I submitted its code there were already 170+ submissions to this problem and some few submissions to problem B :/

Problem B: New Year Present

problem statement

This is the kind of problem that makes me wish Topcoder allowed problems that didn't need a specific answer, but just following some rules. The number of commands can be anything as long as it is less than 1000000. There are at most 300*300 candles, so even the easiest strategy I could think of was guaranteed to do it in less than 1000000 steps. It works as follows:

• We fill the wallets from left to right. Begin with the left-most wallet, if needed, put a coin.
• After putting a coin, robot cannot put a new coin again unless it moves. So we move the robot either right or left (It is best to move it right, since most likely left wallet is already done, but sometimes you cannot move right). If the next wallet is not complete, put a coin before moving back to the original wallet.
• Once all the coins in the left-most wallet are done, move right, and consider this the new left-most wallet to fill.

Logic is basic and it will use at most 3 steps per coin, so it should work under the constraint.

It was actually tricky to implement. It occured me to make a tester so I could simulate the moves and make sure everything is fine. This was a good idea because I found many bugs.

I wonder how an optimal strategy looks like.

const int MAX = 1000000;
void solve(int n, int * a, string & res)
{
    #ifdef DO_CHECK
        int b[n];
        for (int i = 0; i < n; i++) {
            b[i] = a[i];
        }
    #endif
    res.resize(MAX, '-');
    int x = 0;
    int t = 0;
    while (true) {
        if (a[x] == 0) {
            // wallet x is done, move right
            if (x + 1 == n) {
                break; //everything is done, grats.
            }
            res[t++] = 'R';
            x++;
        } else {
            // put a coin
            res[t++] = 'P';
            a[x]--;
            // move to some other wallet and return back
            if (x + 1 == n) {
                assert(x != 0);
                res[t++] = 'L';
                res[t++] = 'R';
            } else {
                // put a coin if needed
                res[t++] = 'R';
                if ( a[x + 1] != 0 ) {
                    a[x + 1]--;
                    res[t++] = 'P';
                }
                assert(x + 1 != 0);
                res[t++] = 'L';
            }
        }
    }
    assert(t < MAX);
    // The checker runs in case the DO_CHECK #define is on
    #ifdef DO_CHECK
        int c[n];
        fill(c, c+n, 0);
        x = 0;
        for (int i = 0; i < t; i++) {
            //cout << res[i] << endl;
            switch(res[i]) {
            case 'L':
                assert( x > 0 );
                x--;
                break;
            case 'R':
                assert (x < n - 1);
                x++;
                break;
            case 'P':
                assert( (i == 0) || (res[i-1] != 'P') );
                c[x]++;
            case '-':
                break;
            default:
                assert(false);
            }
        }
        for (int i = 0; i < n; i++) {
            assert( b[i] == c[i] );
        }
    #endif

}

Problem C: New Year Ratings Change

problem statement

I am not entirely sure about this one, my solution is to sort the clients in non-decreasing order of `a_i`. It follows that the ratings you assign must be in increasing order (we want them to be different). For each `i` (in the order), try the smallest possible rating (must be at least `a_i` and larger than the rating assigned to the previous client).

I did various tests, I was quite cautious today:). Found a couple of bugs, but fixed them. So I thought it was correct. Well, unfortunately, my first submission I uploaded B.cpp (Solution for the previous problem) by mistake. And in the second submission I failed pretests, I didn't notice the maximum `n` was 3*100000, I initially thought it was 1000000. Changing the array size to 300000 passed pretests, let's see if I survive.

const int MAX = 300000;
// I:
int n;
int a[MAX];
// O:
int b[MAX]; //results
//-----------------------------
int id[MAX];

void solve()
{
    // Since the return must be in the same order as original a_i, we cannot
    // just sort the a_i array. Instead, sort the client indexes.
    for (int i = 0; i < n; i++) {
        id[i] = i;
    }
    sort(id, id + n, [&](int x, int y) -> int {
            return a[x] < a[y]; // I <3 lambdas so much.
    });
    int last = -1;
    // now do it in non-decreasing order of a_i :
    for (int i = 0; i < n; i++) {
        if ( last >= a[id[i]] ) {
            b[id[i]] = last + 1;
        } else {
            b[id[i]] = a[id[i]];
        }
        last = b[ id[i] ];
    }
    
}

Problem D: New Year Letter

problem statement

And so this is when the problems become challenging. The trick is to notice that `k` is sort of small, at most 50... The strings themselves can be quite complicated. For example, is `s_1` is "A" and `s_2` is "C", then `s_3` can have one "AC".

To calculate the final number of AC strings in the final string, we need to know 6 things (Yep, 6):

• The number `p` of AC in the first string `s_1`
• The starting character `a` of `s_1`
• The final character `b` of `s_1`
• The number `q` of AC in the second string `s_2`
• The starting character `c` of `s_2`
• The final character `d` of `s_2`

With this in mind, we can find the number of AC in the final string `s_k` in `O(k)` time. You can do it recursively. There are things you can find about `s_3`:

• It will start with `a`.
• It will end with `d`.
• It will have at least `p+q` ACs, it might have an extra one if `b = "A"' and `c = "C"`.

`s_2` and `s_3` can become `s_1` and `s_2` in a version of the problem that has `k-1` steps.

There are only 3 characters that are relevant to simulate for starting and ending characters: A , C and something else. We can use X for that something else. This means that the number of tuples `(p,a,b,q,c,d)` is `O(nm)`. We can just brute force them until we find a case that returns `x` ACs.

However, not all tuples `(p,a,b)` and `(q,c,d)` are valid. We still need to actually build those strings. This was the most complicated sub-problem in my case. Though probably you can use dynamic programming to make it easier. What I did was a lot of case studying. Thankfully I also tested this throughly. I *think* it is correct

const string WRONG = "Happy new year!";

// given the parameters:
// p: number of ACs in s1
// q: number of ACs in s2
// a: starting character of s1
// b: final character of s1
// c: starting character of s2
// d: final character of s2
// : Count the number of ACs in sk:
int simulate(int k, char a, char b, char c, char d, int p, int q)
{
    if (k == 2) {
        return q;
    }
    int r = 0;
    if (b == 'A' && c == 'C') {
        r = 1;
    }
    long np = p + (long)q + (long)r;
    np = std::min<long>(np, 1000000001LL);
    return simulate(k - 1,  c,d, a,d, q, (int)np);
}

// Build a string
// - Contains n characters
// - Contains exactly p "AC" substrings.
// - Starts with a
// - Ends with b
string build(int n, int p, char a, char b)
{
    if (n == 1) {
        if (a != b) {
            return WRONG;
        }
        if (p > 0) {
            return WRONG;
        }
        return string(1, a);
    } else if (n == 2) {
        string r = string(1,a) + string(1,b);
        int q = 0;
        if (r == "AC") {
            q = 1;
        }
        if (q != p) {
            return WRONG;
        } else {
            return r;
        }
    } else {
        string res(n, '?');
        res[0] = a;
        res[n - 1] = b;
        int j = 0;
        int q = 0;
        for (int i = 0; i < p; i++) {
            //cout << "[" << res << "]"<<endl;
            while ( (j + 1 < n) 
                    && ( ((res[j] != 'A') && (res[j] != '?')) || (res[j+1] != 'C') && (res[j+1] != '?') ) 
                ) {
                j++;
            }
            if (j + 1 >= n) {
                break;
            }
            res[j] = 'A';
            res[j+1] = 'C';
            j += 2;
            q++;
        }
        for (int i = 0; i < n; i++) {
            if (res[i] == '?') {
                res[i] = 'X';
            }
        }
        if (q != p) {
            return WRONG;
        }
        return res;
    }
}

// Find the two strings with a huge brute force
tuple<string, string> solve(int k, int x, int n, int m)
{
    string A, B;
    A = WRONG;
    // for example if k=3, x=1, n=1, m=1, then we can even do s1 = A, s2 = C.
    string CHARS = "ACX";
    for (char a: CHARS) { // x 3
        for (char b: CHARS) { // x 9
            for (char c: CHARS) { // x 27
                for (char d: CHARS) { // x 81
                    for (int p = 0; 2*p <= n; p++) { //x81 x 25
                        for (int q = 0; 2*q <= m; q++) { //x81 x 25 x 25
                            if (simulate(k, a,b, c,d, p, q) == x) { //x81 x 25 x 25 x 50
                                //a good one?
                                string tem1 = build(n, p, a,b); //x81 x 25 x 25 x 50
                                string tem2 = build(m, q, c,d);
                                if (tem1 != WRONG && tem2 != WRONG) {
                                    A = tem1;
                                    B = tem2;
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    
    return make_tuple(A,B);
}

The rest

There were less than 30 minutes left when I finished problem D. The other problems were solved by few people and though problem F seemed like something I could eventually solve, I didn't think I could do it in 30 minutes. So I prefered to write this blog post. Enjoy!

It was a fun match. Although my rating shall suffer.