So...

So I participate all the time in TopCoder and can barely mantain a yellow rating. Yet I barely participate in Codeforces and got 2000+ rating. Makes you think...

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.

A white whale defeated

I have wonderful news! (for me mostly), I have defeated a major white whale of mine. A bug that has annoyed me since ages ago, but has become a personal vendetta just recently. Have you ever noticed that problem statements in the topcoder statistics site sometimes have way more line breaks than in the arena?

Try the SRM 602 div1 hard BlackBoxDiv1 , for example. This is how it looks like in the statistics: http://community.topcoder.com/stat?c=problem_statement&pm=12923. Now try it in the arena, it is much better there.

It has become a bigger issue when the Greed plugin added problem statement support. Its ability to automatically generating problem statement HTML was something I never thought I needed, until I started using it. It is so useful for editorials to be able to read statements without having to navigate topcoder's site! It also allows much control in the way the statement looks, making things easier on your eyes. But of course, the same bug that happens in the statistics problem statements happened in Greed's problem statements.

It is a very strange bug that happens only in some problem statements (strangely (Now I know it was not so strange), it always happens with *my* problems). So for long I was clueless as to what causes it or how to fix it. I even tried to write a thread about it asking for help from anyone who could decode this mystery.

Tonight, I was messing with some other bits of the problem statement, when I noticed something funny about how firefox shows source code... It painted some </br> closing tags red. This is something I never bothered to pay attention to before, but tonight it finally hit me: Topcoder statements seem to use XHTML. I know at least that some XML is used in topcoder. Usually if you use the <br> (line break) tag, the problem statement editor would convert it to <br></br> (and thus close the tag). However, when you use HTML , browsers consider a </br> tag as nonsense that probably means <br>... This causes them to add an extra line break :).

So, just rushed to Greed's source code and added a tweak to replace <br></br> patterns with <br/>. Build the plugin , test, and voila!

Before BR fix:

After BR fix:

Cool!

I know what you are wondering: Does this mean that Greed is better at generating problem statements than TopCoder's own site? - The answer is yes.

SRM 602: High note

So there we go, the last SRM of the year. I did sort of good, at least it is a nice improvement over the last few matches.

Div1 250: The one with rating

Your initial rating is `X` , there are `n` matches ahead. If during match `i` you have `x` rating, then you have two choices:

• Increase your rating by `D_i`: `x = x + D_i`.
• Decrease your rating by `D_i`, but if it becomes negative set it to zero : `x = max(0, x -D_i)`.

Constraints are large: `(n <= 50)`, `D_i <= 1000000000`. Whenever your rating changes from bellow 2200 to >= 2200 and vice versa, your rating changes color. Also, you don't like having 2200 or more rating too frequently so, you shouldn't have more than 1199 rating in two consecutive matches. Return the maximum number of rating color changes there can be. X is initially less than 2200.

So besides the large constraints, you never want rating to stay higher than 2199 in two consecutive matches. If `x + D_i >= 2200` , then you should make sure that either the match `i` is the last match or that after match `i+1`, the rating can drop back bellow 2200: `x + D_i - D_(i+1) < 2200`. If that is true, then you can skip to match `i+2`. This ensures that the rating you remember is always < 2200. Limiting the number of states of the function. We can now use dynamic programming:

int getmax(vector<int> D, int X)
{
    const int BROWN = 2200;
    int dp[D.size() + 1][BROWN + 1];
    function<int(int,int)> f = [&](int i, int x) {
        int & res = dp[i][x];
        if (res == -1) {
            if (i == D.size()) {
                //base 
                res = 0;
            } else {
                // { x < 2200 }
                // up:
                if (x + D[i] >= BROWN) {
                    // become brown, must be "ciel" in the next move
                    if (i + 1 < D.size()) {
                        if (x + D[i] - D[i+1] < BROWN) {
                            // can do it
                            res = 2 + f(i + 2, std::max(0, x + D[i] - D[i+1]) );
                        }
                    } else {
                        res = 1 + f(i + 1, BROWN );
                    }
                } else {
                    res = f(i + 1, x + D[i]);
                }
                // down:
                res = std::max( res, f(i + 1, max(0, x - D[i]) ) );
            }
        }
        return res;
    };
    memset(dp, -1, sizeof(dp));
    return f(0, X);
}

I wish I was faster on this problem, it took me a while to get the brain to work. Oh well.

To be fair, I had a couple of distractions. A message appeared saying that "If you see only 5 examples, you should reopen the problem because there are 6 examples!". So I reopened the problem, and something funny: There were 7 examples. I felt like this is either a typo in the message or a mistake when adding the examples that the admins should really know about... Then I noticed that the message I received was about the 550 points problem ... Oh, so nevermind...

... wait. I could swear that I noticed 5 examples in the 250 problem the first time I opened! Indeed, after checking out the problem statement that was generated by Greed, I could notice that there were 5 examples in the first version even though there are 7 examples now. I notified the admins that the number of examples in the div1 250 problem also had discrepancies...

Div1 550: the one with rectangles

There are up to 200000 rectangles of dimensions <= 1000000000. Split the rectangles in 2 groups of equal number of rectangles. Then calculate the maximum intersection between the rectangle areas in each group - Sides must always be paralel to the xy axis - . Return the maximum possible sum between the intersection areas of the two groups.

Oh well, I guess my new year will involve me spending lots of time on this problem. It appears a bit complicated. During the match, I tried many heuristics that were wrong - E.g: Sorting by smallest dimension and making the first group have the smallest rectangles. Also tried sorting in row-major order . Well, things like that. No luck.

My incomplete solution idea is that one of the groups ought to have the smallest width and smallest height rectangles. So maybe there is an optimal-substructure there? No idea.

Challenge phase

There were 3 submissions for 550, two from blue coders. I opened one from a blue coder and could notice something strange. It had an if N < 2 return X[0]*Y[0]. Which doesn't make a lot of sense. If N = 1, there are still two rectangles and you should move them to different groups still. I thought that any case with N = 1 should make it fail, and indeed, I got 50 challenge points :)

Later I was about to go get lunch, but maybe my challenge luck could become a streak. I opened the other blue coder's code, and their code seemed to use one of the heuristics that I tried and was wrong. Definitely the last example case should make it fail... however, I hesitated too long to try challenge it, and someone else got that challenge. This someone else, cup_of_tea already had a challenge and climbed to first place in my room. Not cool!

Comments

It is a shame there were issues with the example cases . So far the admins decided to keep the match rated. It was otherwise a good match, even though 550 seemed too tough for me.

SRM 601 div1 hard editorial

I really hate these delays. It is also seeming very dangerous for my well-being now that there are 4 SRMs a month. I just finished SRM 601, and ... SRM 602 is starting in less than 2 hours. So I am basically going to have to keep working...

What's most disappointing is that the problem that caused this delay, was a beautiful one that was not really difficult. Yet I still had a whole damn 46 hours delay on it! What is going on???

You know what? I blame Christmas.

Yes, Christmas. My original plan was to release the first 5 problems ASAP, but could only finish by Noon of the 24-th. Then of course the 24-th and 25-th were going to be a waste of time. My last hope was the 25-th night and the morning of the 26-th. But I underestimated how much stressful and energy draining Christmas is! When I stumbled upon the original explanation and the further explanation from the admins for this problem, I couldn't process it until last night.

It is a very cool problem, which is also impossible to explain and understand. Sorry for the bad, late editorial.

http://apps.topcoder.com/wiki/display/tc/SRM+601#WinterAndShopping

Don't forget to vote (positive or negative, you decide, but please vote). 200 people read this blog monthly and 1000s participate in SRMs, yet there are usually only 25 or so editorial votes?

Just saying...

If you don't like the idea of TopCoder getting a generic logo and renaming the Algorithm and Marathon competition tracks into "Data". You might like to join this discussion

SRM 601 editorial (minus div1 hard)

It is up: http://apps.topcoder.com/wiki/display/tc/SRM+601

This was a very dry editorial to write. All problems were mathy ad hoc or complex yet sort of-obvious dps. It is very hard to explain that stuff.

My plan was to finish it yesterday, but I procrastinated. So the new plan was to finish it today, before the Codeforces match, but I couldn't do it. Now I have to spend the following 48 solving div1 hard. It is going to be an odd Christmas.

SRM 601: Another slow day

At least it wasn't catastrophically bad this time.

Div1 250 - The one with apples and organges

You have `n <= 50` bags. Bag `i` has apples[i] apples and oranges[i] oranges. The process to make a valid gift involves taking exactly X fruit (`X > 0`) from each bag (The number of apples and oranges you take from each bag must be exactly X). The number of apples and oranges determines the kind of gift you make. Count the total number of different kinds of gifts you can make, that is, the total number of distinct pairs `(A,O)` where `A` is the number of apples and `O` is the number of oranges.

The trick is to notice that the value of `X` you pick uniquely determines the sum `(A + O = nX)`, which means that it is impossible to get the same pair using two different values of `X` . The problem is now about counting the number of pairs for each `X`.

Given `X`, then the number of apples you get in total uniquely determines a pair `(O = A - nX)`, so we just need to count the total number of ways to pick `A` given `X`

The next important fact is to notice that the set of valid `A` values ought to be a interval. So if you know `a_0` and `a_1` are valid and `a_0 <= a_1` , then all `a_0 <= i <= a_1` must be valid too. Then you just need to find the minimum and maximum possible number of apples. The maximum can be found by picking the largest possible number of apples from each bag. The minimum number of apples can be found by picking the largest number of oranges from each bag. Once you get the minimum and maximum number of apples, just subtract them to count the total number of ways to pick it.

long getNumber(vector<int> apple, vector<int> orange)
{
    int n = apple.size();
    int m = 2000000;
    for (int i = 0; i < n; i++) {
        m = std::min(m, apple[i] + orange[i]);
    }
    long res = 0;
    
    // For each valid X:
    for (int X = 1; X <= m; X++) {
        // If we take X, then there are nX in total.
        
        // maximum:
        int mx = 0;
        for (int a: apple) {
            mx += std::min(X, a);
        }
        // minimum:
        int mn = 0;
        for (int o: orange) {
            mn += std::max<int>(0, X - o );
        }
        // total:
        if (mx >= mn) {
            res += mx - mn + 1;
        }
    }
    return res;
}

Div1 500: The one with xor

I couldn't think of a solid solution. I did make the conclusion that you can first pick the first bit position at which the xors differ. Then the problem is about counting the number of ways to have xors: yyyyy1????? and yyyyy0?????. It seems this is the starting point of a solution, but no luck yet.

Comments?

So far it seems like an ok match. Time to write the editorial. Got to rush because I don't want to be busy with it during Christmas. ... Or do I?

TopCoder folder organization TAKE TWO

Some time ago I talked about how I made a script to be able to organize TopCoder problem source codes by automatically creating a folder for each contest. But some time after that I had to desist of using this folder organization, because TopCoder contests have different names during the match and when in the practice room ! (During the contest, it is Single Round Match XXX, the practice room is SRM XXX). So if I used Greed to organize my problems like that, I would have to always move my code from a folder to another after every match. And that's annoying.

After that, the hindrances of having all problem source codes in the same folder became more and more noticeable to me. However, I also reckoned that a folder per contest was not so great, either, too many folders. Both approaches return in the main folder having too many children. My dream solution was something of a hybrid. Separating SRMs in groups of 25 SRMs, TCO problems in one folder, TCHS folders in another, TCCC in another. And also a folder for the remaining contests. There are a few of odd contests that don't belong to those categories and we don't really need a whole category or folder for each of them.

Modifying Greed

The first step of making this work is to make the arena plugin do it. After some hacking and some convincing I managed to get the code to do exactly that into the current git version. It will be officially in whatever next release is (second beta? Official Greed 2.0? Who knows?. But you can just compile Greed from its github right now if you want this.

What I did was to create a complex helper Class to render Contest names using very special rules. Basically, you modify Greed.conf and add:

  codeRoot = "${Contest;category(srm=25)}"

This instructs Greed to change the codeRoot folder to a special kind of name. By default, codeRoot is exactly equal to the contest name found out by Greed, but with this modification, it will be equal to "TCO" if the contest name contains "TCO" or "Topcoder open". Or if the contest name is "SRM XXX" or "Single Round Match XXX", the folder name will be "SRM a-b", where a-b is a interval that contains 25 SRMs. E.g. "SRM 400-424". Of course, if you change the srm=25 with srm=100, the number of SRMs per interval changes. Here you can find a detailed explanation of what ;category does.

Moving problems

The old problems were in a single topcoder folder containing them all. Now that greed uses the folder structure I wanted it to use, I still need to move previous problems to the correct folders.

The first issue was getting a problem's contest name automatically. I solved this little problem with the folder organizer script I posted a while back. Now all the problems are inside folders with names equal to topcoder contests. But I still needed to re-organize these folders...

So I made another script:

# Topcoder folder organizer 
#
# err let us say it is released under the zlib/libpng license
# http://www.opensource.org/licenses/zlib-license
# (c) Victor Hugo Soliz Kuncar, 2011 
#
#
import urllib, re, sys, os, time, string, glob

def fixContest(result):
    separate = 25
    if 'TCHS' in result:
        result = 'TCHS'
    elif 'TCCC' in result:
        result = 'TCCC'
    elif re.match( ".*(TCO|(top\s*coder\s*open)).*" , result,  flags=re.IGNORECASE):
        result = 'TCO'
    elif re.match( ".*(SRM|single\s*round\s*match)\s*(\d+).*" , result, flags=re.IGNORECASE):
        num = re.match( ".*(SRM|single\s*round\s*match)\s*(\d+).*" , result, flags=re.IGNORECASE).group(2)
        #print '{%s}' % num4
        num = int(num)
        a = num - num % separate
        b = a + separate - 1
        result = 'SRM %d-%d'%(a,b)
    else :
        result = 'Other'
    return result
        

def inFolder():
    os.chdir("./")
    
    for dirname, dirnames, filenames in os.walk('.'):
    
        # print path to all filenames.
        for filename in filenames:
            if dirname != '.':
                contest = './'+fixContest(dirname[2:])
                if not os.isdir(contest):
                    os.mkdir( contest )
                os.rename( os.path.join(dirname,filename), os.path.join( contest, filename) ) 


inFolder()

What the script does is take each folder in the current work directory ( ./ ) and for each folder, get the contest category (Same as ;category("srm=25") in Greed) (You can change the separate variable in the script from 25 to something else). And move the files inside the folder to the better category.

That's it

Thanks to the modifications of Greed and the two scripts, I have a neatly organized topcoder folder. Note that because of ;category, no matter if a contest is named "Single Round Match XXX" or "SRM XXX", the result is the same.

Setting up Topcoder Greed plugin with your fav. IDE (Code::blocks)

I always talk about the Greed plugin, it is just so customizable. It is hard to measure the power it has. From its simple default setup to what I am going to introduce you to in this post. In this post, we are going to make Greed create a Code::blocks work environment and call code::blocks automatically whenever you open a problem. I hope this example can be adapted also for other IDEs.

This post is about Greed 2.0, which is currently in beta. And not just beta Greed 2.0, but possibly the latest in git, I hope greed can have a jar release soon, but for now you'll need to get it from github and compile it. Basically you just download the contents of the repository and use ./gradlew fatjar to compile it and make a jar for you which will be saved in the build/libs folder

Fiddling with the IDE

In a first step, let's learn all that is needed about the compiler and how to set it up. Open some problem in Greed. My favorite test subject is the problem TBlocks from the TCO13 championship round. After you open it in greed, assuming you are with default config, it will create 3 files in a specific folder in your Greed work folder.

• TCO 2013 Finals/TBlocks.cpp
• TCO 2013 Finals/TBlocks.sample
• TCO 2013 Finals/TBlocks.html

In greed 2.0, the default behavior is to save example data in the .sample file. The .cpp file then has to read from this .sample file, and the .sample file has to be in the command's work folder when you run the compiled program. While the ability to save examples in a separate file is cool, I disagree with this as a default, I think it complicates things too much. It is possible to change this behavior, but for the matter of this tutorial it will be a good thing, because I am teaching you how to make it all work in your IDE.

Let's create a Code::blocks project that runs this stuff for us. Go to File/New project/ when asked for the kind of project, pick console application.

Tell it you want a C++ project. It will then ask you for a project title, folder, etc. For them use the name of the problem and the location in your Greed workspace. In following image, my Greed workspace is /home/vx/topcoder. We want the project file in the same folder as the source code and sample...

It will then ask you for what compiler to run. You should have already set up the correct compiler: (Hint: You'd like GCC 4.8.1 (Mingw in windows) to simulate TopCoder's server the best). If you ask me, you probably don't need a release configuration, as you only want to test code before sending to topcoder, leave it as debug.

Now we have some issues... First, it unilaterally decided that you want the main file to be called main.cpp. We would like it to be the same file as greed generated. Let's change it to TBlocks.cpp. Right click main.cpp and select remove file. Now right click the Project name and select Add files and add the TBlocks.cpp file generated by greed.

Another thing, you'd probably like c++11 support (and I hope you are using gcc 4.8.1) so go to Project/Build options... And tell it to use c++0x.

Actually, there is a plethora of options you'd like to set. To mimic topcoder the best, you'd like "Optimize even more (-O2)" and also I recommend to add "-Wreturn-type -Wcomment -Wunused-variable -Wunused-parameter -Wno-sign-compare" (without quotes) to the other options section.

After this, running the source code by pressing F9 will work just fine. Code::blocks will run the project in the directory we wanted.

Of course, doing this for every single problem is too much trouble, so we'll now use Greed's power to automatize it.

A code::blocks project template

All about greed works using templates. What we'd like Greed to do is to create a project file automatically for each problem. Code::blocks project files are saved with cbp extension and are actually XML files. Let's save all work we put in Code::blocks (Make sure to save the project!) and open TBlocks.cbp:

<?xml version="1.0" encoding="UTF-8" standalone="yes" ?>
<CodeBlocks_project_file>
 <FileVersion major="1" minor="6" />
 <Project>
  <Option title="TBlocks" />
  <Option pch_mode="2" />
  <Option compiler="gcc" />
  <Build>
   <Target title="Debug">
    <Option output="bin/Debug/TBlocks" prefix_auto="1" extension_auto="1" />
    <Option object_output="obj/Debug/" />
    <Option type="1" />
    <Option compiler="gcc" />
    <Compiler>
     <Add option="-O2" />
     <Add option="-std=c++0x" />
     <Add option="-g" />
     <Add option="-Wreturn-type -Wcomment -Wunused-variable -Wunused-parameter -Wno-sign-compare" />
    </Compiler>
   </Target>
  </Build>
  <Compiler>
   <Add option="-Wall" />
   <Add option="-fexceptions" />
  </Compiler>
  <Unit filename="TBlocks.cpp" />
  <Extensions>
   <code_completion />
   <debugger />
  </Extensions>
 </Project>
</CodeBlocks_project_file>

The rest is to create a Greed template to generate files like that. Let's first define the template in greed.conf. If you don't already have this file in your Greed workspace, create it.

greed {
    shared {
        templateDef {
            codeblocks {
                override = false
                outputFile = "${Problem.Name}.cbp"
                templateFile = "codeblocks.cbp.tmpl"
            }
        }
    }
}

That is the basic stuff you need to add a new template to greed. The template will be called codeblocks. By default the file won't be overrided if it already exists. The template file will be codeblocks.cbp, located in your workspace folder. The file it generates will be called just like the problem name and be put in the code root folder (same folder as source and sample). What we'd like for this file is to be exactly like the one above, except to replace TBLocks with whatever problem name we need:

<?xml version="1.0" encoding="UTF-8" standalone="yes" ?>
<CodeBlocks_project_file>
 <FileVersion major="1" minor="6" />
 <Project>
  <Option title="${Problem.Name}" />
  <Option pch_mode="2" />
  <Option compiler="gcc" />
  <Build>
   <Target title="Debug">
    <Option output="bin/Debug/${Problem.Name}" prefix_auto="1" extension_auto="1" />
    <Option object_output="obj/Debug/" />
    <Option type="1" />
    <Option compiler="gcc" />
    <Compiler>
     <Add option="-O2" />
     <Add option="-std=c++0x" />
     <Add option="-g" />
     <Add option="-Wreturn-type -Wcomment -Wunused-variable -Wunused-parameter -Wno-sign-compare" />
    </Compiler>
   </Target>
  </Build>
  <Compiler>
   <Add option="-Wall" />
   <Add option="-fexceptions" />
  </Compiler>
  <Unit filename="${Problem.Name}.cpp" />
  <Extensions>
   <code_completion />
   <debugger />
  </Extensions>
 </Project>
</CodeBlocks_project_file>

We would just like the template to be created whenever we open the problem. Since it is specific to c++ we will modify the c++ templates line.

greed {
    language {
        cpp {
             templates = [ filetest, source, testcase, problem-desc, codeblocks ]
        }
    }
}

The templates line is usually [ filetest, source, testcase, problem-desc ], it is the list of templates to create automatically. By adding codeblocks, we tell greed to create the codeblocks template. In greed reload the configuration, if everything went right, open some other problem, like the 400 points problem in the same TCO finals match.

It should say: Generating template [codeblocks] -> TCO 2013 Finals/PackingSquares.cbp or something like that, depending on the folder.

Now open the newly-created PackingSquares.cbp in Code::blocks, it should have everything set up, including the new source file.

After generation hook

How about that, instead of just creating the project file and needing us to open it manually, Greed also ordered Code::blocks to open it when we open the problem? All is possible.

To the part where we added the codeblocks template, add this:

            codeblocks {
                override = false
                outputFile = "${Problem.Name}.cbp"
                templateFile = "codeblocks.cbp.tmpl"
          afterFileGen {
              execute = codeblocks
              arguments = ["${GeneratedFilePath}"]
          }
            }

Now whenever the project file is regenerated (You may need to tell greed to regenerate code for problems you already opened) code::blocks will be opened...

The arguments part tells codeblocks what file to open. GeneratedFilePath is a special variable that returns the whole path to the file generated by the template.

Ok , we have a problem, if code::blocks was closed before opening the problem/regenerating the code then code::blocks will close immediately after opening. This is because Greed will run the new process without creating a thread. I will ask for an option to fix this in greed, but for now, we have a couple of workarounds, the first is to have code::blocks open while running the arena. The other is to create a script to run code::blocks in another thread for us. In *n*x* operating systems, save the following as threadcodeblocks.sh in greed's workspace folder, remember to set it as executable in permissions:

#!/bin/bash
codeblocks '$1' &

Change the execute = codeblocks line to execute = /path/to/greed/workspace/folder/threadcodeblocks.sh.

And done!

Comments / etc?

I hope it was useful. I think that every decent IDE out there saves project files as XML, there might be variations, but it is usually a text file, I hope.

SRM 600 prelim editorial and recap-rant

So the double contest trouble last weekend ended and it was disastrous to me. But first , let me point you to the first 5/6 of the editorial at : http://apps.topcoder.com/wiki/display/tc/SRM+600

There were t-shirt prizes and I foolishly hoped to maybe get a t-shirt. I forgot how bad SRM 500 was on my luck.

Div1 250

link to statement

I solved this one right-away. You need to pick the bit position that is non-zero in goal and that has the least valid cards. I needed some time to code it and then the strange self-doubt about "maybe something is wrong", also I really wanted to make sure to get that t-shirt. I reviewed the algorithm plenty of times and proved it to myself. So I submitted it. It wasn't a slow submission, but it wasn't particularly fast either, so I rushed to solve div1 600.

It was some time after the system tests that I learned my solution actually got challenged. I was very skeptical, because I was sure the algorithm is right. Well, the algorithm was right, but for some reason I initialized my result variable with 40. I am not sure exactly what happened. It could be I made a typo and typed 40 instead of 50. Or it could be I got the constraints confused and thought to type the maximum number of bits. I don't really remember.

There is a fun story about this challenge that ruined my dreams and rating. I already wrote about it, so here is a link.

Div1 600

Palindrome matrix

I thought that my only hope for t-shirt was solving this problem. And for plenty of time in the match I thought I could do it. My first solution was actually quite close to correct. The only mistake I made was not to figure that you only need sets of palindrome rows/columns with exactly the required number of palindromes. You are not really going to care about the rows/columns so it doesn't really matter. You can actually read the first solution I tried, it is in the site statistics, it was `O(3^m)` because reasons.

When I finished coding it, I had two issues: a) It wasn't giving the right answers to example cases. b) It was taking too long (~4 more seconds than allowed) to solve the large example case. I made the mistake of thinking [Even if I fix this, it would be too slow]. It turns out that besides of bug fixes, the soution was correct. It just needed some pruning and to care only about sets with exactly the required number of palindromes. The new code was a dynamic programming that in reality did exactly the same as the old solution, I just didn't notice... New code was also wrong and somehow still slow. So the coding phase was a missed opportunity.

Anyway, this was a cool little evil implementation problem. I wish I solved it during the match.

T-shirts

It annoyed me that division 2 coders were getting t-shirts. It is a way to punish blue and yellow coders for not having low rating. I think that in matches with awards it would be preferable to have a single division (combined div1 and div2).

SRM 600.5

I wish this match didn't happen. So there was a new chance to get a t-shirt. But this time solving very hard problems. The match was advertised to have a normal SRM 1000 points problem. So I went to the match thinking of spending 4 hours on that problem and hopefully solving it. It was actually very obvious that far less than 40 coders were going to solve more than one problem in this match. When I learned the match actually had a challenge phase, I felt robbed. It was obvious that people were going to submit bogus solutions for some reason, allowing other people to get 50 points and probably joining the top 40.

Really, the TopCoder format is terrible for this kind of match. If the act of opening problems didn't penalize you, it would have been much better to open all problems before deciding which to solve. Instead, I had to rely on the point values assigned to the problems, which were terribly wrong. The 1000 points problem I spent 4 hours trying to solve was solved by no one.

It was a interesting problem. Come up with `n` distinct positive integers such that, for each `1 <= i <= n` , the sum of the `i` largest integers is less than or equal to `s_(i-1)`. Where `s_i <= 1000000000`. I spent a whole afternoon trying to find a secret. Trying to decode the safe that hides the solution to this problem. All with no luck.

So the t-shirts given to people that just got lucky (Many rooms didn't even have any submission at all, whilst some rooms were full of bogus solutions). It was a bit of a waste of t-shirts. I wish they would have included at least a div1 medium or easy problem so that there was a better tie-breaker than the challenge phase. IMHO, maybe not include a challenge phase at all.

Comments?

Problems seemed good. I am just in a very bad performance streak. My decisions during contests are seeming to be very bad lately. Also, I seem to have completely lost the ability to correctly estimate whether a solution will run in time or not.

The way the SRM 600 celebration was made was very disappointing, giving prizes to div2 in SRM 600 or to people being very lucky in SRM 600.5. I would have preferred to have a single division in SRM 600 so that if div2 coders win a t-shirt it is by performing very well , or by being lucky. SRM 600.5 really didn't need a challenge phase...

New version of my Greed tester and template

Shortly after I discovered the Greed topcoder plugin, I spent some time customizing its templates and later did some really cool stuff by making a generic tester. It has been working great so far.

During the weekend a discussion erupted at the Greed github about making Greed support running test cases in different thread/process the main reason people like this feature is because if you make code that depends on global variables' values and requires them to be initialized with 00 bytes, then running all test cases as part of the same process causes errors. I never really cared much about this, because I wouldn't ever use globals like that :/. But during the weekend I figured I had good reason to use this sort of feature:

• Sometimes I need to test some other people's code locally and they have the sort of bad taste about global usage that I described. E.g, during the weekend I had to reverse engineer the solution rng_58 wrote for the SRM 599 Hard problem.
• Most importantly, there is a much better reason to run in multiple processes: Runtime errors. C++ poor exception handling makes it so in my old version of tester, a single failed assert, a segfault or an exception would stop the execution of the whole thing. If the exception happened in just test case 1, it would still halt the execution of all test cases.

So that is when I started to experiment. The first thing I did was make Greed 2.0's default test template get this feature. I did some hacky stuff: Basically, the c++ program calls itself over and over again for each argument. But it works.

For my so-called "dualcolor" templates though, the requirements were higher because there is a lot more things to care about when printing results. The report at the end needs to know exactly what happened during the execution of test cases. Another issue is that I wouldn't be able to have access to the command line arguments in the tester file, unless I modified the tester call syntax (which would break old source files generated by old version of the template). So I had to do something else.

The eventual decision was to use fork and wait. fork() works great because it makes a copy of the current process. Wait is needed to wait for the process to end. The one problem about this is that it effectively makes the feature unable to work under windows (unless you use cygwin, I think). I make these templates for myself mostly and I don'tt have time to port to winapi. If you use windows and wanted this feature in my template I guess it sucks it when someone's software doesn't work fully on your OS of choice, eh?. Of course, maybe windows users still want the other cool features like the output colors and the easy-to-modify test cases, so when running in windows the whole thing is disabled. Metaprogramming to the rescue.

#if defined(WIN32) || defined(_WIN32) || defined(__WIN32) && !defined(__CYGWIN__)
    #define DISABLE_THREADS
#endif
#ifndef DISABLE_THREADS
    #define DO_THREADS
#endif
#ifdef DO_THREADS
   #include <unistd.h>
   #include <sys/wait.h>
   #include <sys/types.h>
#endif

The other negative side is that communicating with child process was sort of too complicated for me to implement without using an external file. So the tester now needs an external file to work. Currently it is located in /tmp/

Maybe some *n*x users have trouble getting this to work. Or maybe it is failing for some reason or making testing a specific problem difficult. Hence why if the DISABLE_THREADS thing is defined before including the tester.cpp file, the feature can be disabled.

The result is great. It can catch the usual issues (aborted due to some std:: exception, division by zero, segfault). To be consistent with the python version, letter E is used to signify test cases with runtime errors. Here is a sample:

Keeping one line per test case in the report

Another feature that can be caught in the screenshot above is that the final results report in the bottom is now guaranteed to be one-line long. If the reported results is longer than that, it will be stripped. Of course, the line length can be configured in tester.cpp.

Return of the super compact mode

By popular (one person) demand. The mode that printed just and only the "final" report and nothing else is back. I don't like it because it doesn't work very well when you use printing for debugging. But I guess there are people who don't do that.

To choose output mode, find this line in template:

        return Tester::runTests<${ClassName}>(
            getTestCases<input, Tester::output<${Method.ReturnType}>>(), disabledTest, 
            ${Problem.Score}, ${CreateTime}, CASE_TIME_OUT, Tester::FULL_REPORT
        );

Change Tester::FULL_REPORT to one of these:

• Tester::FULL_REPORT : Full , verbose output and report at the end.
• Tester::NO_REPORT : Full , verbose output but the bottom report is a single line with less info.
• Tester::ONLY_REPORT : Only the report and nothing more.

Get them

• Test code template for greed, needs Greed 2.0 unless you tweak something small. testtemplate.cpp
• Generic Tester (Place at .. folder relative to where source codes are generated): tester.cpp

The official Greed version 2.0 is probably going to include these templates and just need a small configuration line to use them. Greed git already includes the older version.

Two hundred fifty six

TopCoder just updated default memory limit for new problems from 64MB to 256MB. More so, some problems might have different time/memory limit than default.

Very mixed feelings about this.

Time to update test script to use 256 MB, I guess.

SRM 599 Recap and editorial : Cursed

I just barely finished SRM 599's editorial. After failing this match both as contestant and editorial writer. My conclusion is that this match has been cursed.

Div1 250

(Read editorial for actual explanation)

I was so happy with this problem when I first read it and... horribly misinterpreted it. For some stupid reason, I thought that when doing the second kind of step, you would always raise the number to square. I am not sure why this assumption happened, or how I managed to misread the problem. But it happened. The reason I liked this, is that with this assumption, the problem reduces to a div1 250 we already solved very recently. So I thought that sort of thing was cool.

I coded my solution, it passed example tests (should so confused solutions pass example tests? Maybe examples were weak?), moved on to div1 500.

Challenge phase and destruction

For a second I thought of not participating in the challenge phase. I was sort of busy that day. But last minute I decided [[It is likely people are making all sorts of bugs in 250 and bad assumptions in 500]]. I was right. Unfortunately, the first solution I opened was correct, but I didn't know it was correct (remember I misunderstood the problem entirely). So I challenge it. The challenge failed and the [Correct answer] provided by the system didn't make any sense to me. That's when I figured that a) My 250 was utterly wrong. b) I had a bad challenge, so this means -25 overall points. Worst position possible, worst rating loss possible. My only hope was to find codes that were wrong and challenge them and recover frm the -25. And to do it fast, because if someone challenged by 250, I would not be able to make any challenges any more. I tried a solution, my challenge was also wrong. Gave up...

Div1 500

What a hellish problem from hell!

During the match, I was able to do just about most of the theory. You can only use integer sides. It is impossible for odd cases. Even cases can be solved with 4 sides. You need bruteforce to find out if a triangle is possible. Unfortunately the time I had allocated during the match was not nearly enough for me to code a solution using this idea and optimize it. OMG, optimizing this brute force was so difficult.

I think this problem would have been a good div1 medium, if it only had the theory part. Such complex implementation on top of the theory makes it too extreme for this slot, imho. The constraints were certainly too tight. I think L <= 1000 or 2000 would have been just fine.

I had so many issues solving and explaining this problem. I had to spend ages coming up not only for optimizations, but for optimizations that I can prove are correct. Eventually it was clear I was not going to finish in less than 48 hours if I wanted to solve this problem. So I moved to the hard... Bad idea.

Div1 950

I didn't open this problem during the match. At first the description sounded very easy. rng_58 called it "an implementation problem". Well yes, but not that much. I didn't really understand how the recurrence worked, and I had to do plenty of reverse engineering of rng_58's code. ... If only Petr made his blog linking to author explaining it in codeforces before, maybe it would have been better. ... (BTW, why?, why can't we have TC problem set writers explaining that way in TC's forums? I mean, how did TopCoder manage to kill its community so much? The forums used to be so active and interesting before)

Finishing the editorial

When I noticed, I was already late for both deadlines. And I was finally understanding how to do the hard. Then I had to fix again what I had for div1 medium. Then do the other problems, which were not non-trivial to explain at all. There was a time period in which I thought I would never finish this editorial.

If you think editorial delays are bad for you, editorial reader, think about how awful they are for the editorial writer. Instead of spending a couple of days in a SRM, I ended up spending almost a week on it. There's plentyof things I couldn't do because of it.

Comments and please vote

Any comments. Also please post feedback to the editorial page, specially, vote. I really dislike that there are so few votes (negative or positive) in editorials when SRMs have hundreds of participants. (Did I already mention something about TopCoder's community being dead?)

The problem set was cool, although 500 was probably too interesting for div1 medium. Maybe swapping div1 500 and div1 hard and making div1 hard have smaller constraints would have been better? I really dislike to have failed this match, I really could have done more.

Topcoder SRM 598 Editorial part 1

http://apps.topcoder.com/wiki/display/tc/SRM+598

What an odd match. People keep saying the div1 medium was too easy. I just can't see it. From what I am looking at it is going to be very hard to explain. Whole match was incompatible with my editorial method. Problems are too hard to explain when they tend to be "obvious".

Now that I understand div1 hard better, I think that the "dirty tricks" solution I used during the match can be shown to have a very low probability to fail. From the analysis it sorts of follows that the number of beacons tends to be high. Except in cases were it should be easy to find the solution through the brute force anyway.

SRM 598: Dirty tricks

Another week, another Topcoder SRM.

Div1 250: The one with bins.

We have up to 50 items of different weights `100 <= "item"[i] <= 300`, we have to put these items in bins that have a maximum capacity of 300. Which means that the total weight of the items in a bin cannot exceed 300. Return the minimum number of bins we can use to store all items.

It is unusual for an input to have a lower bound. The items' weight is at least 100. This means that a bin can hold at most 3 items. More so, if a bin ever holds 3 items, all 3 items must have weight 100. So we can just treat weight 100 items separately.

There is a case: `{100, 100, 100, 100, 100, 100, 200, 200, 200}` that shows that the optimal strategy is not always to put the 100-weight items in as many bins with 3 items as possible. However, the number of bins holding 3 items is finite and at most 50/3, we can just try all possible numbers of 3-item bins that we will use. 0, 1, 2, ... `h/100` (where `h` is the number of items of weight 100). Once you do this, all of the remaining bins will contain at most 2 items. We should maximize the number of pairs of items with total capacity <= 300.

int optimal2(vector<int> item)
{
    // solve if a bin can only hold at most 2 items.
    int cost = item.size();
    sort(item.begin(), item.end());

    // Each bin can now have at most 2 items
    int i = 0, j  = item.size() - 1;

    // Maximize the number of pairs of items that can enter a single bin: 
    while (i < j) {
        // simply match the smallest item with the largest item possible:
        while ( (j > i) && (item[j] + item[i] > 300) ) {
            j--;
        }
        if ( (j > i) && (item[i] + item[j] <= 300) ) {
            cost--;
            i++;
            j--;
        } else {
            break;
        }
    }
    return cost;

}

int minBins(vector<int> item)
{
    vector<int> not100;
    int count100 = 0;
    for (int x: item) {
        if (x != 100) {
            not100.push_back(x);
        } else {
            count100++;
        }
    }
    // It is possible for a bin to hold 3 items, but they must all be 100.
    int res = item.size();
    for (int a = 0; a <= count100 / 3; a++) { // number of bins that hold 3 items
        // the rest of the bins can hold at most 2 items:
        vector<int> tem = not100;
        for (int i = 0; i < count100 - a * 3; i++) {
            tem.push_back(100);
        }
        int cost = a + optimal2(tem);
        res = std::min(res, cost);
    }
    
    return res;
}

I made plenty of mistakes while coming up to this solution. Coded a wrong solution that failed test cases (the test case I mentioned above). Coded another wrong solution that passed all test cases, but I was very suspicious about it and could notice its mistake. I had the feeling this problem was going to have many wrong solutions and I was right. Unfortunately, during the challenge phase I remembered I am unable to read other people's codes. Many of the codes seemed overly complicated and possibly wrong, but I had no idea how to find a good case for them.

Div1 550

It seemed complicated, I eventually decided to test my luck and skip the div1 550 to open the hard problem.

Div1 950: The one with cities

You have a country/set of n (at most 50) cities. The cities have connections and these connections makes the graph of cities a tree (how suspiciously convenient). The plan is to put beacons in some of the cities so that, when evaluating the list of distances from a city to each of the beacons, the distances make a sequence that is a unique identifier for the city.

A basic `O(2^n)` solution would be to just try each subset of cities and place beacons on it and pick the smallest subset that allows the unique identification to work. It occurred to me that with backtracking and some cleverness, maybe we can optimize this solution to run fast enough and give a correct answer at least most of the time. I expected it to be quite hard to make system tests for this problem.

So I made some backtracking algorithm. All cities begin with beacons on them and we decide from city 0 to n-1 whether or not we remove the beacon from it. It is only possible to remove a beacon if all the remaining beacons allow the identification. Note that when all cities have beacons, the identification works just fine, because each city is the only city with a distance of 0 to its beacon. When doing the backtracking, make sure not to remove a beacon if it no longer allows identification of cities.

The backtracking wouldn't run in time. But my dirty trick idea was to make the backtracking search stop after a high number of steps. So that we use 2 seconds of time to do the search and return the best result we found in those limited 2 seconds.

It wasn't good enough, what if the optimal set of beacons to remove happens to be a set of the last indexed items? My new idea was to make this an unlikely event, my algorithm would randomly modify the positions of the input cities, lowering the chances of a crafted test case of occurring. Now, this approach would be wrong if there was a case that required a perfectly unique set of beacons to be removed, so the probability would be low. I had another trick idea: Spend half of the time in a greedy idea, giving priority to nodes with little edges so we can remove them.

Implementing the dirty tricks was not easy and took me quite a while. So much that in fact the only code I could submit was incomplete. It only did the randomized idea and it still only allocated half of the execution time for it. The randomized idea seemed to be returning a wrong result for a large case I had, so I sort of suspected it would either fail in the challenge phase or in the system tests.

Unfortunately, that didn't happen, and my very dirty brute force algorithm passed system tests. Good for my rating.

Comments?

SRM 597 Editorial

It is up: http://apps.topcoder.com/wiki/display/tc/SRM+597. Don't forget to vote and comment. Feedback is important.

I really failed this time, first time I fail the deadline since the 96 hours deadline for div1 hard's editorial was added . The problem was that div1 900's is not difficult, but I completely underestimated the time it took me to code it correctly (had a very dumb bug last night and I couldn't debug it and kept falling asleep). Then explaining it was impressively hard.

Match comments

This was a good match. I was angry the last day because of missing it. I still think the 600 points problem wasn't suitable for medium. I ow think that 900 was better for that slot. Hmnn. The rest of the match had cool problems.

SRM 597: argh

The other day I accepted to write editorials to the TCO. Unfortunately they never warned me that some of the problems I would read could end up getting used outside of the TCO. I only learned that after the problems were sent to me. Had I know that I could miss SRMs just for helping with these editorials, it would have been a deal breaker. I hate missing SRMs. I really hate missing SRMs.

I had hopes that maybe if one of the problems I read gets used like this in a SRM, I could at least have a chance to write the other problems in the SRM. Nope. Then I tried to maybe get added as a tester to read the other problems so I could at least have progress in the editorial. Nope. So missing this SRM was useless. Week ruined.

Div1 600: ConvexPolygonGame

This is the problem that ruined my week. Two players take turns. It all starts with a convex polygon. In each turn, the player draws a polygon such that:

• The previous polygon contains all the vertices of the new polygon.
• The vertices of the new polygon are lattice points
• No three vertices are colinear.

The player loses when it is impossible to draw such a polygon.

The trick is to notice that as long as a player can make a move, the player can always pick a minimal triangle that will win the game. We know that the game will end with a single triangle. Imagine this triangle came after a sequence of moves. This triangle will then be inside each of the polygons used in the game, including the first one. Then first player can just directly use this triangle and win.

So we just need to check: Is there at least one triangle with non-zero that can be drawn in the first turn? If so, first player draws a terminal one and wins, else the first player loses.

So far it is a cool little problem. The original version planned for TCO had `(-500 <= x,y <= 500)` constraint for the vertices of the first polygon. Which had a couple of cute solutions, for example, you could iterate through all the points inside the polygon and if you ever find a point that is not colinear to the previous two points, the job is done. Unfortunately, when migrating it to SRM format, they changed the problem by making the constraints much larger. So the clever conclusion that you only need to check if one drawable polygon exists becomes just problem obfuscation, because the real issue is to work up the implementation problem of checking for that condition. Apparently the idea is to use only the points that are close to the vertices, within 200000 distance or something like that.

I think this problem was a decent TCO finals easy with the small constraints. With the large constraints though, it becomes a SRM div1 medium with excessive implementation that doesn't make it more interesting.

Bragging about incoming Greed features part 2

Last time I mentioned that Greed Topcoder arena plugin is getting a 2.0 version that has plenty of nice features. Between that last post and today, many things happened. The first is that Greed 2.0 is now officially in beta state. So you can now get the jar in the releases page. If you used Greed 1.5, the configuration has really changed, it might actually be more productive to start configuration all over from the beginning and try to reuse your templates if they were too complicated. (There is only one breaking change in the template format, the ;zeroVal was changed with ;zerovalue, but the configuration file has really changed).

Also important: I committed a couple of cool things that will also be part of the new version. These changes are not in the beta jar, so you might have to compile the git branch yourself if you want to try them now. If you can wait, that's better.

Modulo detection

Counting problems in algo contests tend to ask you for the result modulo 1000000007, or modulo 1000000009 or some other large prime. This is because everyone hates bignums. Anyway, it does add a bit of an annoyance when solving these problems, you have to paste the number in your code, preferably as a constant. In TopCoder, they have the bad habit of using the absurd format that uses commas as separators , so the constant appears in the statement as 1,000,000,007. So you actually have to remove the commas. This is if you actually think of using copy paste, maybe you don't and just type the number manually, possibly typing the wrong number (like using 1000000009 instead of 1000000007 or missing a zero).

We deserve better. Now that greed has access to the problem statement, it occurred to me that it could totally try to detect this modulo. It looks for the phrase ":modulo (some number)" and then saves the number in a convenient spot. If there are multiple of them, it saves the last one that is mentioned, because that tends to be one of the last phrases in the statement. It probably won't work all the time, but most of the time it shall be of some help.

My template looks like this:

${<if Problem.Description.Modulo}
    static const int MOD = ${Problem.Description.Modulo}; 
${<end}

The result is:

    static const int MOD = 1000000007;

Or whatever number is parsed. This constant is only added if the Modulo was detected. You know, automatically.

The colorful templates with generic tester

I added tweaked versions of my current templates so that it is easy to use them in greed out of the box after just tweaking two configuration lines.

More info

Topcoder Open 2013 editorial: TheGameDAG

The other month, I utterly failed and couldn't advance to round 2 of the TopCoder open. I didn't even get a t-shirt. Something after that I was contacted by an ominous figure, goes by the name of Rustyoldman. Apparently this year the TCO bloggers (read: Rustyoldman and .... misof) were going to write the editorials for the TCO onsite problems. The catch would be that this time editorial writer would have access to the problems long before the matches, so that editorials could be published fast.

I was undecided. On one side, that means money. On the other side, if my explanations get published at the same time as Rustyoldman's or, worse, misof's, then it would become very clear that my editorials are awful in comparison. I have a very fragile ego and I do not need any of this. Also, TCO onsite problems are ...hard. This was going to be a time sink.

But I eventually agreed. I only had time to write a small amount of editorials (possibly just the following one, I can't disclose more info). So here we go:

TheGameDAG

Problem statement available at: http://apps.topcoder.com/forums/?module=Thread&threadID=803574&start=0

Editorial available at: http://apps.topcoder.com/wiki/display/tc/TheGameDAG

This one problem was very hard. I needed a couple of weeks (of course, also busy with homework and the other editorials) to think of it. Ultimately I had to ask for help. Gotta thank bmerry for the help in getting me to understand this problem.

Some great incoming topcoder-greed features

So Greed is a topcoder Arena plugin that is very customizable (And I mean, very customizable).

When I started using these plugins I took advantage of its github to provide patches and suggestions. This helped shivawu implement some wonderful features that will make Greed 2.0 a plugin with unprecedented power (I think).

Custom templates

In the current stable version, there are 3 templates: source, tester and unit tests (optional for Java and C#). The 2-3 templates are used by Greed to generate the source and unit test files. The templates use a language of their own that is very powerful. So powerful that implementing python support almost didn't need much modification to the plugin itself, just the creation of templates for python and an update to make the plugin use them.

Why stop there, though? The new idea is that you can, define custom templates. Any template for any kind of file in addition to the source and test ones. The plugin will use its configuration to read a template and put the generated contents in some location that depends on contest name and problem name. Why is this important? Well, it adds plenty of options that weren't there before. After some tweaking I was able to customize greed to generate ACM-style input and output files and a source code file that takes input and generates output ACM style.

This is the input file generated for FoxAndGo3:

6

3
o.o
.o.
o.o

3
...
.o.
...

5
xxxxx
xxoxx
xo.ox
xxoxx
xxxxx

5
.xox.
.o.ox
x.o.o
ox.ox
.ox..

5
o.o.o
.ox..
oxxxo
..x..
o.o.o

3
...
...
...

But I really didn't want these input/output files, I like my meta testers just fine. However, this feature is also helpful for other things. How about automatically creating a project XML file for your favorite IDE's ? Or a build file for whatever build system you have? Separating tester and source code. Whatever you need you can now do it.

Problem statement HTML

The first good use for the custom templates is that, just by adding some info from the problem statement to the template engine. The plugin can now generate problem statement HTML files from a template. Because it is a template, there is plenty of flexibility in regards to the format of the problem statement. The default looks like this:

There are plenty of uses for saving the problem statements in files. If the internet goes down during the contest, you can pretty much still work in the problem - You can read the problem and the source code is in an external file.

After generation hooks

My favorite new feature is, however, the "After Gen Hook" as it makes everything work great now. You can tweak configuration so, whenever Greed finishes generating a file from a specific template, it runs a custom command. Whatever command you need.

In my case, I tweaked Greed to make it automatically open source code files in jEdit, and opens the problem statement in Firefox. Manually opening the generated source code files in jEdit was an annoying bottleneck.

How to get the features

They are currently in a test branch and are still in development. But if you want to give them a try, just get the contents of the tmpl-seq branch from their github. The command to build a jar file from the new sourcecode is ./gradlew fatjar.

The new configuration options are not documented, so you will need to take a look to at the default.conf file in the source/main/resources folder and do some reverse engineering.