TCO 2013 round 2A: I wrote the 550 points one

Another year, another year in which I don't get to round 3 of the TopCoder open. But like last year, this brings an opportunity, I can try wearing my problem setter suit this time.

550 points: Block3Checkers

Remember when I talked about problem setting SRM 579 and how we had issues just a day before the match?

Block3Checkers was the problem that was initially intended to be in SRM 579.

First version

You have a NxN board. There are three checkers in the board that belong to Alice, their positions touch the border of the board. 0 to 61 checkers occupy other slots and are neutral (can't be moved). What is the minimum number of squares in the board on which you have to add new checkers so that it is impossible for Alice to move any pair of her checkers to two adjacent cells (She is only allowed to move a checker horizontally or vertically to an empty spot).

I thought of this while walking/running. SRM 579 was nearby and there was no div1 medium. This was my chance to shine. My chance to make 125 bucks. But I didn't have a medium. So my mind started wandering.

The first version of the problem had this intended solution: Let us name Alice's checkers X,Y and Z. We need at most 3 checkers to block the path between X and Y (because we can always surround any of them with only 3 checkers, thanks to them being in the border of the board). We need at most 3 checkers to block the path Z and X or Y. The intersection. Of these two solutions would be THE solution. We just need two brute forces for three cells, and then somehow merge them. Similar to a meet-in-the-middle.

It seemed interested, proposed it. rng_58 liked it, although not because of my approach, but because he thought of another approach, a faster one that I didn't understand at all. But all was right. Kept developing this problem and the others as SRM 579's date approached.

Until the night before SRM 579. In which ivan_metelsky helped us figure out that this clever idea of a solution was wrong. This is a case it gets wrong:

..#A#...
A#.#N...
#.......
...N.N..
.......A
N.......
NN......
.NNN.N..

The Ns are neutral checkers, the As are Alice's checkers and the # are the positions in which to place 5 of Bob's checkers. The clever approach with intersections returns 6.

Pre SRM 579 crisis

So we only had few hours before the match. We didn't have a replacement problem and we knew two things: a) My solution, the intended one, was very wrong. b) rng_58's was probably not wrong but is certainly not easy to find. So we were undecided for a couple of hours whether to use the problem, but allowing brute force (it would become a very simple problem, you bruteforce for up to 5 cells on which to place the checkers, if you don't find a solution, you can return 6 directly). Or find a replacement. As you know, we eventually found a replacement.

TCO revival

This problem still existed, and I knew that, using the solution that rng_58 found, it had potential to either be a div1 hard or be used in the TCO rounds. I made the problem available for the TCO. And it was approved.

It took me a good while to understand the new solution. It requires you to take advantage of the checkers touching the border of the board. They effectively divide the perimeter of the board in three parts. Imagine if there was a 8-connected path of N or B checkers between one segment of the perimeter and another. This would effectively make a cut. Between all checkers inside and all checkers outside the space delimited by the path. So there are four six of connected components of N/B checkers:

1) Does not touch the border.

2) Touches only one of the segments of the border

3) Touches TWO of the segments of the border.

4) Touches all THREE segmens.

In case 1) or 2), this connected component does not block any path between Alice's checkers. If one component like 4) exists, the problem is already solved. Else we need two different components of the kind 3) (Each Connecting a different pair of segments)

So, the problem is, for every possible way to accomplish this, find the minimum number of Bob's checkers to add. What's the minimum number of checkers to make two different pairs of segments connected? What is the minimum number of checkers to make a center checker (N or B) connected to all three segments?.

Constraints discussion

This approach can be implemented fast , in fact it works for 50x50. But it needs work for such an optimization. I initially wanted the constraints to state as 8x8, it would make it not needed to make more test cases. And people would get tricked into making the wrong solution. But it didn't click with the admins. Too much risk to have a situation in which an optimized brute force of up to 5 cells passes.

Then it seemed like up to 12x12 was a fine idea, those bruteforces would be inviable. But rng_58 thought of an exponential approach that relies on dp. You can imagine that all empty cells connected to each of Alice's checkers have a specific color. So all empty cells connected with X are red. All empty cells connected with Y are green and all those connected with Z are blue. The remaining cells, are black. Clearly, two cells of different colors (except black) can't be adjacent, so that they weren't connected. this allows an optimized dp that would pass for n=12. So we needed to increase the constraints, again.

Too bad I learned of that during the morning. I had to give up some hours in the IPSC because of this. I kept my first IPSC hour making new challenges.

Read More

IPSC 2013

Circumstances got in the way this time, and I think I couldn't enjoy IPSC as much as I would have wanted.

I am still battling with my chronic headache. Although it is getting better lately. But I am still trying to keep a strict sleep schedule. This week was when I noticed that this schedule was going to be a problem. IPSC starts at 6:00 in my timezone, and I am supposed to always sleep from 11:00 to 7:00 now. I was willing to make an exception, but with some bad luck I had to sleep at 12:00 AM last night because of other bad combination of circumstances. So today I actually woke up at 6:45. I couldn't begin working with IPSC right away though. You know, breakfast, stuff and ... more circumstances that had to distract me for a while.

The solution booklet is already up, so this blog post is not the best place for explanations.

Problem C: Code inception

Around 8:00 AM-ish, I took a look to the standings. The last place had C1 solved, so I decided to open problem C. In this problem, there are two codes (c++ or python) that are supposed to "eventually, at some point" return a single English word. So the only output you need to send to the server is that English word (two versions of the problem, one for 1 point and another for 2).

The codes used are insane and the ultimate proof that misof is a deranged mad genius. Here is the code:

#include <algorithm>
#include <iostream>
#include <vector>

int B[] = { 1894607624, 1927505134, 1861486949, 2052221263, 1953703270, 1772249212, 1704106159, 1607055075, 1829198849 };
std::vector<int> A(B,B+9);

long long t(long long n) {
    long long z=n;
    for (long long a=2; a<n; ++a) if (t(a)>=a) if (n%a==0) { z/=t(a); z*=t(a)-1; }
    return std::min(z+1,n);
}

int main() {
    sort( A.begin(), A.end() );
    for (int i=0; i<4; ++i) A[i+5] ^= t(A[i+1]-A[0])>>7;
    long long z = std::max( t(A[0])-1, A[0]+1-t(A[0]) );
    for (long long i=0; i<z; ++i) std::rotate( A.begin(), A.begin()+1, A.end() );
    A.insert( A.begin()+1, z );
    for (long long x=8; x<1e7; ++x) {
        int y = A[x/4]>>(18-6*(x%4))&63;
        if (!y) break;
        if (y<60) std::cout << char(31+y); else std::cout << A[y-60];
    }
}

Of course, if you try to run this code it will take too long to give the answer. I guess it takes years. I felt confident , because this is my sort of problem. I really thought I could do it. The trick is to avoid trying to understand the code and just look for optimization points. The first thing I noticed is this:

    for (long long i=0; i<z; ++i) std::rotate( A.begin(), A.begin()+1, A.end() );

This use of std::rotate will just shift the array left. If you repeat this thing z times, it is the same as doing it only z % A.size() times. So we can just change the loop to repeat it ( z % A.size() )

The second thing was that the t function is quite expensive. But this also depended mostly on one line:

    for (long long a=2; a<n; ++a) if (t(a)>=a) if (n%a==0) { z/=t(a); z*=t(a)-1; }

The trick is to notice that the contents of the if do important things only when a divides n. In a moment of sheer stupidity, I thought this meant we only needed to try values of a less than or equal to sqrt(n), that was dumb. You'll see why later.

It is also possible to make it only call t(a) once instead of thrice.

After I made these fixes. The output was not a word, it was a sentence. CHANGE ?????? to ???????, where the ?????? were large integers that I do not remember specifically. Ok, IPSC is being a trickster again, I thought. The statement does say that the code will output something eventually and at some point, so maybe we are supposed to change the integers. Certainly, the first ????? was in the b[] array, so what if we change it? I made the change, and a new instruction to change something with something else appeared. Then I did it again, and it happened again. Decided to make a program to change stuff for me until it stops saying something like CHANGE X TO Y....

So I modified the program to do that, and then it showed me that it does print plenty of CHANGE X TO Y lines, but eventually it didn't show that anymore. In fact, it showed complete giberish. Like Z@#½#~Z or something like that. Tough luck, something is wrong which my code :(. I tried tons of things to find the mistake. I even tried CHANGE and TO, because maybe you weren't supposed to follow the instructions. This probably stole an hour of my time until I gave up and decided to work on other problems.

When the match ended, I went to the solution booklet. But in the process of skipping to problem C, because I was really curious why I was wrong, suddenly I noticed. No, not all divisors of a number are smaller than or equal to the square root. That is stupid. (I guess my morning brain got confused and used the logic that is used to optimize primality check). But the square root is useful. If we check only number y <= sqrt(x), then divisors are either y or x/y. So we can still use a O(sqrt(n)) loop to optimize this, but making sure to consider n/a as well as just a.

This is the final code that outputs "MATTER"

#include <algorithm>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;
int origB[] = { 1894607624, 1927505134, 1861486949, 2052221263, 1953703270, 1772249212, 1704106159, 1607055075, 1829198849 };


long long t(long long n) {
    long long z=n;
    // First optimization, consider a <= sqrt(n)
    for (long long a=2; a<n && a*a <= n; ++a) {
        if (n%a==0) {
            // But remember that n/a is also a divisor:
            long long aa[2] = {a, n/a};
            for (int i=0; i<2; i++) {
                long long b= aa[i];
                // We only need to call t(b) once:
                long long x = t(b);
                if (x>=b) {
                    z/=x; z*=x-1;
                }
            }
        }
    }
    return std::min(z+1,n);
}

string tostr(int x)
{
    ostringstream st;
    st << x;
    return st.str();
}

int main() {
    long long B[9];
    for (int i=0; i< 9; i++) {
        B[i] = origB[i];
    }
    while(true) {
        std::vector<int> A(B,B+9);
        sort( A.begin(), A.end() );
        for (int i=0; i<4; ++i) A[i+5] ^= t(A[i+1]-A[0])>>7;
        long long z = std::max( t(A[0])-1, A[0]+1-t(A[0]) );
        for (long long i=0; i<z%A.size(); ++i) std::rotate( A.begin(), A.begin()+1, A.end() );
        A.insert( A.begin()+1, z );
        // Instead of printing, save the result to a string
        string s = "";
        for (long long x=8; x<1e7; ++x) {
            int y = A[x/4]>>(18-6*(x%4))&63;
            if (!y) break;
            if (y<60) s += char(31+y); else s += tostr(A[y-60]);
        }
        // Print the string:
        cout << s << endl;
        // Parse it
        istringstream st(s);
        string w1, w2;
        long long i1, i2;
        if (st >> w1 >> i1 >> w2 >> i2) {
            // Follows CHANGE X TO Y format:
            for (int i=0; i<9; i++) {
                if (B[i] == i1) {
                    B[i] = i2;
                }
            }
        } else{
            // Something else, break:
            break;
        }
    }
}

Problem A

So there were only around two hours left, I needed points. Most people seemed to solve A1 and A2. These are easy problems, just greedily take the largest coin denomination until you no longer need coins. I rushed though and submitted a code with an obvious error . It was printing the result wrongly :)

Problem K

I looked at standings, and people near the bottom seemed to solve K1. It turns out it was a classic dp problem. K2 though is not so easy.

Problem statement

The trick is to use dynamic programming to decide the upwards movement AND at the same time decide whether or not you will use the step you are using again when going down.

I was having issues implementing this. The solution is correct, but it can be confused to implement. So I decided to rework the approach.

Consider two binary strings of n elements: Like 11010110001100011 and 110100101100101. The first string determines the steps you will use when going up, and the second the steps you will use when going down. The second must be a subset of the first. Also, the last step should be 1 in both strings. In the first string, there can not be two consecutive zeros. In the second string, there can not be four consecutive zeros. The problem is to count the number of ways to fill these two strings. You can just go from bit 0 to n-1 and decide the bit for both of them at each position. In order to correctly fill the first one, you need to remember the last bit. In order to correctly fill the second one, you need to remember the last three bits. We can use dynamic programming:

const int MOD = 1000000009;
const int X = 3;
struct solver
{
    long dp[100001][1<<X][2];
    int n;
    long rec(int p, int mask, int last)
    {
        long & res = dp[p][mask][last];
        if (res == -1) {
            res = 0;
            if (p == n) {
                res = last && (mask&1);
            } else {
                res = 0;
                //after moving to p+1, we need to shift the bits of the downwards
                //string by 1, and include the new result:
                
                int shuf = (mask << 1) & ( (1<<X) - 1);
                if (last && (mask != 0) ) {
                    //can put 0 in the upwards string:
                    // 0 is forced in the downwards one:
                    res = rec(p+1, shuf, 0);
                }
                //put 1 in the upwards string:
                if (mask != 0) {
                    // Put 0 in the downwards one:
                    // Only possible if at least one of the last 3 bits is 1:
                    res += rec(p+1, shuf, 1);
                }
                // Put 1 in the downwards one:
                res += rec(p+1, shuf|1, 1);
                res %= MOD;
            }
        }
        return res;
    }
    long solve()
    {
        memset(dp, -1, sizeof(dp));
        return ( rec(0,1,1) ) % MOD;
    }

L1

Then it seemed that many people had L1 solved. So I opened it. And it was about playing a labyrinth javascript game. All fun stuff. I manually solved the easy cases. The large cases were massive though.

B1

15 minutes left, and I decided to open problem B. I only had time to solve the easy one. Which was really just simulation which could be optimized with precalculation.

Conclusion

Even though I could only see few problems and didn't have as much time as usual, this was still a fun round. IPSC is still one of the best yearly competitions.

Read More

Codeforces Round 187

I don't participate in codeforces rounds as much as I'd like. But it is hard enough to free my schedule to participate in TopCoder rounds (and I need to participate because it is my job to write editorials), then writing the editorials consumes quite a lot part of each week. Today I finally found a period of time in which I am both willing to try a codeforces round and I feel like I have time. So this happened.

Problem C - Sereja and Subsequences

Link to problem

I remember getting bored with the first two problems of division 1 codeforces, so this time I decided to start with the C.

In this problem, you like to find the sum of the products of each unique non-decreasing subsequence of a sequence. For example, if the unique non-decreasing subsequences were {1},{2} and {1,2}, the result is (1) + (2) + (1*2) .

An easy version

Let us forget that the maximum number of integers in the sequence is 10^5 and solve a slower version. This is a simple dynamic programming solution.

Let f(i) the sum of all the products of subsequences that start with seq[i]. It is easy to calculate it for i=N-1 (Base case). For other cases:

• f(i) is at least seq[i], because there is a subsequence that contains only seq[i].
• Else we need to find indexes j for subsequences starting with seq[j], so that we append seq[i] in front of the subsequences. We multiply seq[i] to the count of f(j) to find the sum of those products. however, in order not to repeat subsequences, we need j to be the smallest index that has value equal to seq[j].

The final result is to add up all res[i], whenever i is the smallest index to have value equal to seq[i].

const long MOD = 1000000007;
int N;
long seq[100000];
long res[1000001];

int solve()
{
    memset(res, 0, sizeof(res));
    for (int i=N-1; i >= 0; i--) {
        long nw = seq[i];
        
        for (int j=seq[i]; j <= 1000000; j++) {
            if (seq[j] >= seq[i]) {
                bool seen = false;
                for (int k=i+1; k<j; k++) {
                    seen |= (seq[j] == seq[k]);
                }
                if (! seen) {
                    res[i] = (res[i] + seq[i] * res[j] ) % MOD;
                }
            }
        }
    }
    long total = 0;
    for (int i=0; i<N; i++) {
        bool seen = false;
        for (int j=0; j<i; j++) {
            seen |= (seq[j] == seq[i]);
        }
        if (! seen) {
            total = (total + res[i]) % MOD;
        }
    }
    return total;
}

A less easy version

Instead of making sure the index j is the smallest index with value equal to seq[j], we can save up the work by replacing the function of the res[i] array, this time it returns the currently-known sum of products of subsequences that start with i (not seq[i]).

Then the dp looks like this:

const long MOD = 1000000007;
int N;
long seq[100000];
long res[1000001];

int solve()
{
    memset(res, 0, sizeof(res));
    for (int i=N-1; i >= 0; i--) {
        long nw = seq[i];
        
        for (int j=seq[i]; j <= 1000000; j++) {
            nw = (nw + seq[i]* res[j] ) % MOD;
        }
        res[i] = nw;
    }
    long total = 0;
    for (int i=1; i<1000000; i++) {
        total = (total + res[i]) % MOD;
    }
    return total;
}

Final one

In each step i, we just need to find the sum of all res[j] such that j >= seq[i]. Then replace res[i] with a new value. At the end, we need the sum of all res[j] such that j is >= 0. We can implement this solution using a tree. A special data structure that can quickly return the sum of all inserted values greater than or equal to an index. It should also be possible to quickly insert and remove. We can just use a binary indexed tree for this.

const long MOD = 1000000007;
int N;
long seq[100000];
long oldvalue[1<<20];

// Stuff for the tree:
// An index i is parent of 2*i+1, 2*i+2, and is related to an interval [a,b)
long tree[1<<21];

const int MIN = 0;
const int MAX = 1<<20;
void insert(int x, long value, int node=0, int a=MIN, int b=MAX)
{
    tree[node] = (tree[node] + value) % MOD;
    if (a < b-1) {
        int left  = 2*node + 1;
        int right = 2*node + 2;
        int m = (a + b) / 2;
        if (x < m) {
            insert(x,value, left, a, m); 
        } else {
            insert(x,value, right, m, b);
        }
    }
}

long sum(int x, int node=0, int a=MIN, int b=MAX)
{
    if (a >= x) {
        return tree[node];
    }
    if (b <= x) {
        return 0;
    }
    int m = (a + b) / 2;
    int left  = 2*node + 1;
    int right = 2*node + 2;
    long p = sum(x, left,a,m);
    long q = sum(x, right,m,b);
    return (p + q) % MOD;
}

int solve()
{
    memset(tree, 0, sizeof(tree) );
    memset(oldvalue, 0, sizeof(oldvalue));
    for (int i=N-1; i >= 0; i--) {
        // New value:
        long nw = (seq[i] * (1 + sum(seq[i])) ) % MOD;
        // This should remove the old value:
        insert(seq[i], MOD - oldvalue[seq[i]] );
        oldvalue[seq[i]] = nw;
        // Insert the new value:
        insert(seq[i], nw);
    }
    return sum(0);
}

Other problems

I opened B, decided to go to lunch while I think about it.

Apparently lunch took much longer than planned. When I came back to my computer I started to write and continued to think of a solution. I think it is correct, but when I was in the middle of debugging it, I noticed that there were only 15 minutes left for the match. Eventually finished coding it with two minutes left. I hope it is all right.

Update: Just as I finished writing this post, I found out my B was wrong. Well, I didn't have high expectations for that rushed solution.

Update 2: "Hot news" http://codeforces.com/bestRatingChanges/249522. All hail vexorian the orange.

Read More