Friday, August 30, 2013

Regarding c++ vs. python (in algorithm contests)

Reddit...

Dear people from reddit. Someone linked this blog to you. And it was wrong for it to happen. Because the intended audience of this blog is *not* software developers/ programmers at /r/programming. The intended audience is people who participate in programming contests. Specifically TopCoder. This blog post was made for those people in mind. For example, chances are that you have no idea what an editorial is in this context. The blog is also extremely tongue-in-cheek as I write it using my vexorian persona.

We already know very well about performance. Python runs around 10x slower in comparison to c++ in these contests. Since that's a known fact about the whole thing that's why I didn't even mention it or include "benchmarks".

One thing that you must understand is that the contests are basically designed around C++. This comparison has nothing, absolutely nothing, to do with what language is better than the other for general usage. This is no ammo in some language supremacy flame war. In other words: There is absolutely no need to come to insult me. If you just want to know which language is better for general usage: Just pick the one you are more experienced with and that fits your needs better; If you are undecided, go look for more professional comparisons or something...

--------------------------

So, yesterday I was writing an editorial and things were going ok. I was solving a problem when I decided to include both c++ and python code, like I've been doing plenty of times lately. In this occasion, I wanted the c++ not to rely on libraries or built-in functions, so that someone who just started reading on the syntax understands the code. For the python one, I wanted to make a one-liner, because it was totally possible.

I was aware that this choice would make python 'look good". What I didn't expect was to wake up today to the news that TopCoder's facebook account decided to use those codes as the preview image when talking about my editorial... So now we have this image circulating around that seems to make the point that python allows much shorter code than c++ and it is in part because of me. This was the final trigger that made me write this post, I was planning to write something like this since a while ago.

Python - good?

My relationship with python started on rocky ground. Once upon a time, I was a lame programmer who was obsessed with speed and performance. Python, along with Java and many others was a language that was very slow. So there was no way I would ever use it. Worse, python specifically had syntactically-relevant indentation, which also meant it didn't have brackets or begin/end or something similar. Block depth was implicit. For a good while, this feature made python code make me feel dizzy. It is like the code is floating without something that holds it!. It actually still annoys me, but not as much as before.

Eventually, I did some maturing as a programmer. I learned many languages. Learned about good practices. I even made my own languages as an attempt to fix a very bad language (And discovered many things about what works and what doesn't). So I eventually gave python a chance. It helps to have an editor with code-folding or indentation guides. It removes that feeling of things floating without being held :).

My learning process was slow because I never had any project that I had to write in python. But it did become my main calculator application. I also use it for small scripts and to generate test cases for programming contest problems.

There are many good things about python. There are also some things I am not a fan off. What I like about python is that instead of trying to be a better C++ (*cough* Java and C# *cough*), it tries to be a better language. It is also free and not tied to some evil mega-corporation (*cough* Java and C# *cough*). By the time I heard they were going to add python to the list of languages in Topcoder SRMs, I was excited because I would get to use it in editorials, and it seems like a great tool for them.

Python in editorials

And so, began the journey. I started to use python to solve SRM problems and include the code in editorials. I now have some things to say about using python in TopCoder contests.

Small code

Python really shines in problems that need little code. The stuff other languages need to do the simplest of operations, is usually very easily-implementable if not completely built-in. The code from the problem in the image I first talked about is a good example.

class GooseTattarrattatDiv2:
 def getmin(self, S):
    return len(S) - max( S.count(ch) for ch in S )

It is even self-documented. The result is equal to the length of the string, minus the maximum number of times a character appears in S.

It is actually very fun, and a major source of procrastination, to try to come up with the smallest possible python code to solve a problem.

class InsertZ:
 def canTransform(self, init, goal):
    return "Yes" if (goal.replace('z','') == init) else "No"

If the goal is equal to the init after removing all Zs from it, return Yes.

Making readable code

So the division 2 problem of SRM 588 was a typical "bit masks" problem. You had to iterate through all the subsets of songs. More so, songs had two attributes: length and tone. Typically , the code for this looks very messy in c++ or Java. You end up using bitmasks, which means that you will have beautiful things like (1<<i)& in your code, then for each i, you check if it is in the bitmask, if so, call duration[i], etc, etc... You need a formula between the maximum, minimum tones and the sum of durations and other things

The python code, however, looks like this:

import itertools, collections
 
class GUMIAndSongsDiv2:
 def maxSongs(self, duration, tone, T):
    n = len(tone)
    #making this a named tuple is not needed, but it adds readability:
    Song = collections.namedtuple('Song', ['tone', 'duration'] )
    # Make a list of song objects:
    songs = [ Song(tone[i], duration[i]) for i in range(0,n) ]
    res = 0
    for c in xrange(1, n+1):
        # c is a number from 1 to n, increasing order
        for picked in itertools.combinations(songs, c):
            # "picked" is a set of c songs:
            durationSum = sum( s.duration for s in picked )
            minTone     = min( s.tone     for s in picked )
            maxTone     = max( s.tone     for s in picked )
            if durationSum + maxTone - minTone <= T:
                res = c
    return res

itertools.combinations creates an iterator from the iterator that you pass to it, in this case the songs. The new iterator will contain all the combinations of c songs. So if you try c in increasing order, you can easily get all the subsets. In order to easily divide the songs in subsets, we actually made a list of the song objects. To create and define those objects, we only needed a single line to call collections.namedtuple...

There are many ways in which this code is amazing (to me). And it baffles me how readable it is. It is almost a description of the algorithm for the problem, instead of being code. The alternative in c++ or worse, Java , would be much messier. Check it:

int maxSongs(vector <int> duration, vector <int> tone, int T)
{
    int n = tone.size();
    int best = 0;
    // for each subset of songs represented by a bit mask:
    for (int mask=1; mask<(1<<n); mask++) {
        int maxTone = -1, minTone = 200000, durationSum = 0, c = 0;
        // find the minimum/maximum tone, the sum of durations and the
        // number of songs in the subset:
        for (int i=0; i < n; i++) {
            if (mask & (1<<i)) { //is song i in the subset?
                maxTone = max(maxTone, tone[i]);
                minTone = min(minTone, tone[i]);
                durationSum += duration[i];
                c++;
            }
        }
        // If selected songs in optimal order fit the time constraint, this is valid:
        if ( durationSum + maxTone - minTone <= T) {
            best = std::max(best, c);
        }
    }
    return best;
}

Being able to use functions

Most large algorithms will need you to use many functions and call them. You know what this means? In c++ / Java this means that you will have to copy some variables and the arguments as global variables or class members so that the functions can use them. To me, this is very annoying and has been a source of bugs because if you forget to actually make the copy or assign it correctly, you are screwed. c++11 allows lambdas, and I was able to use them to avoid this issue somehow, like in test SRM #2. But c++ lambdas have a very big issue, you cannot (easily) have recursion with them. You need to work around it somehow. The current best answer to the problem I have is to use std::function explicitly when declaring the lambda and it is very messy.

Python has nested functions instead of lambdas, so making them recursive is not hard at all. It is quite normal. Check the codes in the post about SRM 589 and you will see what I mean.

Some more obvious advantages

Sure, there are some obvious things like how overflow is not possible. That whole stuff about tuples is nice to have. Too many times you are dealing with points or coordinates so you are using tuples, so something like (x,y) = ... makes more sense than x = ... ; y = ... The native set() and dict() types. Etc.

Some bad things

After I started to apply this python knowledge to make code at topcoder, I couldn't avoid thinking. What if this is more convenient during a contest? What if I move to python?

Then I try to use this python thing for a larger problem and start to notice a darker side...

My pet peeve against dynamic languages

This is not something new that I just found, or that is specific to programming contests. I have to mention it. Languages that allow you to declare and use variables in the fly. Languages that are not compiled. They have this annoyance, and it is that your typos won't be discovered until the line with the typo is executed. You write these 100 lines of code and run your program. It is not until a few seconds of execution, that the program reaches a line of code in which you type blok instead of block. Sorry, do it again.

Multidimensional "arrays"?

Python doesn't have that array concept, it has tuples and lists. Lists are one-dimensional, but of course, you can make a list of lists and it can be indexed like a bi-dimensional array - a matrix. You can go out of your way and do the same for a list of lists of lists of lists of lists, and you have something with 5 dimensions!

In the Real World™ Programming world, this is likely not a big issue. In the algorithm/programing contests world, specifically the Topcoder world, it can be quite a pain. We have those dynamic programming problems with 4 dimensions and it is like nothing to write home about. You might even have 6 dimensions.

What in c++ looks like :

int dp[w][h][t][n][2][3];    // Just a typical day in topcoder land
memset(dp, -1, sizeof(dp));
dp[x][y][f][p][1][0] = 6;

In python looks like:

dp = [[[[[ [-1]*3 for i in xrange(2) ] for j in xrange(n)] for k in xrange(t)] for a in xrange(h)] for b in xrange(w)]
dp[x][y][f][p][1][0] = 6

Of course, that's ridiculous. Maybe the real problem is that we are approaching it the wrong way. We could use a dictionary?

dp = dict() 
dp[ (x,y,f,p,1,0) ] = 6

But then, since it is a dictionary it will have overhead in accessing the elements... Maybe a list but we will translate the indexes to a single integer? This is what C arrays do anyway.

dp = [-1] * w*h*t*n*2*3 
dp[ (x*h*t*n*2*3 + y*t*n*2*r + f*n*2*3 +  p*2*3 +  1*3 + 0 ] = 6

Yeah, a bit complicated... too, back to square one.

The petty default recursion limit

Speaking of dynamic programming and memoization in functions. I attempted to use python for FlippingBitsDiv2 and it worked... except that it was actually reaching the recursion depth limit way too quickly. In that problem, the recursion depth is as large as 2500, which doesn't really strike me as too high. Specially not for these contests... But that's the default.

Turns out it is perfectly possible to raise the depth limit with a call to a sys. function. So this problem isn't a big deal. Except that you need to be conscious of it when solving something using recursion.

Memory...

I knew of the obvious weakness. Speed. Python's dynamism comes at that price. Actually, I tried to do some tests and it seems like the time factor is 6 times or even 10 times slower. I haven't actually found a division 1 hard problem that can be solved in python yet.

What I didn't expect was the memory usage. This happened to me while solving GameInDarknessDiv2. It needed a depth-first search on a large graph. If you take a look at the c++ code, there are plenty of implementation bottlenecks. My first idea was to use python code for this solution. Because it can make easier to read code if you work for it. The result is beautiful:

def check(field, moves):
    # useful dictionary from move char to position offset:
    move = {'R':(1,0), 'L':(-1,0), 'U':(0,-1), 'D':(0,1) }
    
    # given a position and a move character, return the new position:
    def doMove( (x,y), ch):
        return (x + move[ch][0], y + move[ch][1])

    # find Alice and Bob's initial positions:
    (w,h) = ( len(field[0]), len(field) )
    for y in range(0,h):
        for x in range(0,w):
            if field[y][x] == 'A':
                (ax,ay) = (x,y)
            elif field[y][x] == 'B':
                (bx,by) = (x,y)

    # Save Alice's positions for each of Bob's turns:
    moves = string.join(moves, '')
    alice = [ doMove( (ax,ay), moves[0] ) ] 
    for ch in moves[1:]:
        alice.append( doMove(alice[-1], ch ) )
    # if in the first move, Alice moves towards Bob, it is game over for Bob:
    if (bx,by) == alice[0]:
        return "Alice wins"

    #And the DFS:
    T = len(alice)
    
    visited = [ [ [False]*(T+1) for i in xrange(0,h) ] for j in xrange(0,w) ]
    winner = ["Alice"]
    
    def dfs( (x,y), t):
        if not visited[x][y][t]:
            visited[x][y][t] = True
            if t == T:
                winner[0] = "Bob"
            else :
                for ch in "URDL":
                    (nx, ny) = doMove( (x,y), ch)
                    if (0 <= nx < w) and (0 <= ny < h) and (field[ny][nx] != '#'):
                        if (alice[t] != (nx,ny) ) and ( (t+1 == T) or (alice[t+1] != (nx,ny)) ):
                            dfs( (nx,ny), t+1 )
                            
    #oops, default recursion limit is too conservative for our DFS:
    sys.setrecursionlimit(T+10)
    #call DFS:
    dfs( (bx,by), 0 )
    #and done:
    return winner[0] + " wins"

The amount of code that is not wasted in boring activities is very relevant, at least to me. The use tuples also makes many things make more sense. It is more self-documenting. However, when I actually run system tests on that solution, I found plenty of issues. The need for a 3D "array" was the first. Then the recursion limit. But the one thing that I couldn't fix was the fact that this code was reaching the 64 MB limit.

The memory usage of this approach is `O(w*w*h*h)`, for `w,h <= 50`, such a memory complexity didn't usually seem like a problem to me when using c++ or Java. So I didn't expect this coming at all. 2500*2500 indexes in a boolean array take around 5.96 MB. In python, however, it turns out that lists holding 2500*2500 elements are too heavy (They are still too heavy even if I use the single-list approach that converts 3D indexes to a single dimension). What is going on?

It is not so surprising. Python is dynamic, a single index in a list can describe plenty of things, not just a number or a boolean. The reserved memory is probably at least 4 bytes for each index, that means 23.84 MB instead of just 5. It is more than that. I discovered a secret python function called __sizeof__, it tells me that a list of 2500*2500 False values is worth 47.68 MB (somehow). That is a good chunk of our 64MB. So apparently, not only is the available time around 10 times smaller, it seems like memory is 3 times smaller in practice too.

In codejam

In google codejam, python is the third most popular language and it is very close to Java, in fact, in round 1A it beat Java in popularity for the top 20% contestants. In TopCoder, python isn't working so well (But at least it has beaten Visual Basic and seems to be on its way to beat C# :) ). Python is quite a recent addition, we have had it for 4 official SRMs so far..., there may still not be many coders who know about its availability and the python coders that didn't give TopCoder a try because of the lack of python probably haven't heard of the change yet. It is no surprise usage is low right now. But will it ever reach a popularity level similar to what it has in google code jam?

Codeforces has had python since inception and python's numbers don't seem to match Codejam's (Although a tool like go-hero.net for codeforces language statistics would definitely be great to have, I couldn't find such thing). Codeforces and TC have an audience that is more focused on ACM-ICPC than the Codejam, though, so that skews things up. I have an alternative theory though: Hard time and memory limits like those in TopCoder and Codeforces just don't work well if you want a language agnostic contests. Making the time limits different is not a good solution either, as it would be difficult to pick good limits. What codejam does well is that, with 4 minutes/8 minutes time limits and using your computer's memory instead of google's, the constant factor is quite irrelevant. That allows plenty of more languages to work, including python.

Move to python?

I think python is a great language. But I don't think I will move to using python during contests. At least not for the time being. I am still not as good with python as I am with c++.

Also, although python has a powerful expression power. c++ has also improved a big deal with c++11. The big advantage I would have assigned to python over c++ would be the support for functions as first-class objects and closures. But now c++ has it too. So...

Remember the initial dilemma? In reality the true c++ version, using more of the available features would look like this:

int getmin(string S) 
{
    int n = S.length(), m = 0;
    for (char ch : S) {
        m = max(m, (int)count(S.begin(), S.end(), ch) );
    }
    return n - m;
}

It is still ugly, but not so bad:)

A bonus: Swapping integers

Last week, there was a image circulating around. How to swap two integers without using an additional variable. The "C version": a=a+b; b=a-b;a=a-b;. Then one of those obnoxious meme faces throws a misogynist slur and says that python has: a,b = b,a. Ahahahaha, so python is better, supposedly.

Let me introduce to you, the c++ way: swap(a,b). It has a nice advantage: It is self-commenting. It also follows [once and only once]. But the reason I like is because of what it says about c++. (a,b) = (b,a) is cool, but it is an builtin language feature that was introduced precisely to fix this problem and similar ones. The std::swap is a library function.

template <class T> void swap ( T& a, T& b )
{
  T c(a); a=b; b=c;
}

It is a result of things like templates, and also by reference arguments. Powerful features that also solve plenty of other problems and not just swap. std::swap works with any data types too - Unlike the C approach. :)

Thursday, August 29, 2013

SRM 589 Editorial

I have finished writing the editorial for TopCoder SRM 589: http://apps.topcoder.com/wiki/display/tc/SRM+589.

As you most likely noticed. Later I have had many delays in releasing these editorials. I got to say that these delays are really a shameful thing for me. The causes are varied. I plan to make a blog post when I have more time about what was going on and what I learned and what I am trying to do to improve things. At least in the case of this editorial, it seems that my new methods are working. Although the problem set was easier than usual.

I am not sure if the explanations I used for div1/div2 hard are too good. I think I fell in the over -verbose trap a bit. Another thing, the two problems are similar but not similar enough to allow me to just link to div2 hard explanation instead of explaining many things again in div1 explanation.

Something funny happened while I was explaining division 2 - medium. I was intending to explain the dynamic programming approach I created and explaining in the forums. But while I typed that explanation, I noticed that the problem totally had a greedy solution. So I had to do it all over again after finishing the explanation.

Please remember to vote. Positively or negatively, but vote. I want to see more than just 20 votes. 1000s participate in a SRM, why aren't they reading these things?

Tuesday, August 27, 2013

SRM 589: Read the statement! (upd)

So another SRM. This time the scores were very special: 250-450-900. It seemed like a good match to use my strategy. At the end though, I didn't take much advantage of it, because of two blunders...

Div1 450: The one with gears

We have gears of three colors, red, green , blue. Initially, some pairs of gears are meshing: If one of the gears in a meshing pair turns in a direction, the other gear must turn in the other direction. No two gears of the same color ever mesh. We want to be able to turn all the gears in such a way that all the (remaining) gears of the same color turn in the same direction. What is the minimum number of gears to remove?

I think using clock-wise and anti-clockwise for the directions is too verbose, so let us call say that some gears are positive and some gears are negative. Now all the gears of the same color must have the same *sign* and two connected (meshed) gears must have different signs.

There are only three colors and two signs, so how about we do brute force for the signs? There will always be two colors with the same sign, otherwise it doesn't matter which sign. So two colors have equal sign, let us say positive, and another color is negative. Between the two positive colors, there should be no connections...

We can actually ignore the negative gears, all their connections are already valid and removing them won't fix anything. So now we only have gears of two colors that should never be connected. This is the independent set in a bipartite graph. So let us just run max flow...

During the match, I took a bit of time because at first I was considering the negative gears, causing a single wrong case (the other example cases were very weak). It was early in the morning, I was just confused...

Div1 900: The one with bits

You want a binary string of N bits (N is up to 300) to be one in which the prefix of length N-M and the suffix of length N-M are equal. You can flip a single bit at cost 1 and you can also flip the first K*M bits at cost 1 (for any positive K). What is the minimum cost?

I think I have some ideas. Unlike most div1 hards, I think I can solve this in a few hours and without help. It is a dynamic programming problem with complications.

Div1 250: The one with palindromes

Turn a string palindrome (again?). This time your only allowed move is to pick two alphabet letters X and Y , and turn all the X letters into Y. Return the minimum number of letter positions you need to change.

I only had 10 minutes, so I rushed to code a solution, which was mostly right. I missed the fact that you want to minimize the number of changed positions (it didn't help that this fact was disguised by some talk about seconds). Not the number of changed letters. I only noticed when there were some seconds left before the end of the challenge phase. I fixed the code some time before the end of intermission.

Anyway... The palindrome requirement means that some pairs of positions must be equal. This means that at the end the letters in that pair of position must be equal. This creates a relationship/connection between pairs of letters. At the end, all letters in a group of letters that are connected (directly or indirectly) must be equal. We have to change each of these letters to the same letter. It is best to pick the letter that appears the maximum number of times. Repeat for each connected component.

int getmin(string S) 
{
    int n = S.length();
    vector<bool> visited(26, false);

    // This DFS finds a list of all letters that are *connected* to letter ch:
    // Returns the maximum number of times one of the connected letters appears
    function<int(char)> dfs = [&](char ch)->int {
        if (!visited[ch - 'a']) {
            int res  = count(S.begin(), S.end(), ch);
            visited[ch - 'a'] = true;
            // Two letters are connected if the palindrome rule states that
            // two positions that contain the letters must be equal:
            for (int j=0; j<n; j++) {
                if (S[j] == ch) {
                    res = std::max(res, dfs( S[n-j-1] ) );
                }
            }
            return res;
        }
        return 0;
    };

    // For each group of connected letters, find the letter that appears the
    // maximum number of times, subtract it from the total cost:
    int res = S.length();
    for (char ch = 'a'; ch <= 'z'; ch++) {
        res -= dfs(ch);
    }
    
    return res;
    
    
}

Update Maybe that lambda stuff makes the code appear complicated, here is a python version:

def getmin(S):
    n = len(S)
    visited = set()
    
    # This DFS finds a list of all letters that are *connected* to letter ch:
    # Returns the maximum number of times one of the connected letters appears
    def dfs(ch):
        if ch not in visited:
            visited.add(ch)
            res = S.count(ch)
            # Two letters are connected if the palindrome rule states that
            # positions that contain the letters must be equal:
            for i in range(0,n):
                if S[i] == ch:
                    res = max(res, dfs( S[n - i - 1]) )
            return res
        return 0
    
    # for each connected component, subtract the letter with the maximum number
    # of position: Call dfs for each of the letters in string.lowercase :)
    return n - sum( dfs(ch) for ch in string.lowercase )

Outcome / Comments / etc?

So I am back to yellow, I could have gotten much better rating if I paid attention when reading the 250.

What did you think about the match?

Friday, August 16, 2013

Codeforces #196: slowness

It tends to be difficult for me to find time for Codeforces matches. Today there was finally one in a time/day slot I can try out.

I adapted my TopCoder strategy into Codeforces. I decided not to open problem A until 10 minutes before the contest ends. But I sort of know that problems D and E tend to be too above my level, so I focused on problems C and B.

Problem C: The one with divisor trees

problem statement

A divisor tree is a tree of integer numbers in which all the leaf nodes are prime numbers and every other node is equal to the multiplication of all of its children. Given up to 8 numbers `(a_i <= 10^12)`, return the minimum number of nodes in a divisor tree that contains them all.

My first reaction was to try to think of a dynamic programming idea. Given a sub-set of the numbers, what is the minimum-size tree you can make? But as I was attempting to solve this I eventually noticed a solution that was easier to code and clearly correct.

Other than the numbers `a_i`, you don't need any of the other nodes to be composite. The only exception would be the root, the root of the tree may need to be composite when there is no way to distribute all of the numbers in a single subtree.

This takes us to concluding that each of the numbers `a_i`, will either be a direct child of another `a_j` or of a newly-added root. There are at most `9^8` ways to make this decision, which is not large. You can cut it even more by using backtracking and making sure not to add children to a integer that are not divisors of it, and that the product of all the children divides the parent.

After assigning the parents, we just need to calculate the size of the tree. For this we can use a small dynamic programming. Process the integers in increasing order and find, for each of them, the minimum size of the tree that has it as root. This size depends on the sizes of all the children and the number of remaining prime factors. So we also need something that is able to calculate the prime factors. A memoization does the job well as we only need the number of prime factors for numbers `a_i` and their divisors.

// from library: primesn, number of primes <= 1000000.
//               primes[i] : i-th prime number <= 1000033

// memoizes the number of prime factors for x.
map<long,int> primeFactors;
int countPrimeFactors(long x)
{
    if (primeFactors.find(x) == primeFactors.end()) {
        int res = 0;
        if (x == 1) {
            res = 0;
        } else {
            for (int i=0; i<primesn; i++) {
                if ( primes[i] > x/primes[i]) {
                    break;
                }
                if (x % primes[i] == 0) {
                    //one
                    res = 1 + countPrimeFactors(x / primes[i]);
                    break;
                }
            }
            if (res == 0) {
                res = 1;
            }
        }
        primeFactors[x] = res;
    }
    return primeFactors[x];
}


int n;
const long INF = numeric_limits<long>::max();
long a[8];
int parent[8];
long ta[8];


long best;

void backtrack(int x)
{
    if (x == n) {
        // all right, build the trees
        long tree[n+1]; //tree size
        for (int i=0; i<=n; i++) {
            tree[i] = 0;
            int children = 0; //number of children of a[i]'s root
            for (int j=0; j<i; j++) {
                if ( parent[j] == i ) {
                    children++;
                    tree[i] += tree[j];
                }
            }
            if ( (i != n) && (ta[i] != 1) ) {
                //how many prime factors does ta[i] have?
                int f = countPrimeFactors(ta[i]);
                tree[i] += f;
                children += f;
            }
            if (children > 1) { //we need this because a[i] might be prime.
                tree[i]++;
            }
        }
        best = std::min(best, tree[n]);
    } else {
        // assign a parent to #x, n means the root.
        for (int i=x+1; i < n; i++) {
            if ( ta[i] % a[x] == 0) {
                parent[x] = i;
                ta[i] /= a[x];
                backtrack(x+1);
                ta[i] *= a[x];
            }
        }
        parent[x] = n;
        backtrack(x+1);
    }
}

long solve()
{
    // Call the backtracking
    sort(a, a+n);
    for (int i=0; i<n; i++) {
        ta[i] = a[i];
    }
    best = numeric_limits<long>::max();
    backtrack(0);
    return best;
}

Problem B: The one with the other kind of tree

I opened this problem, seemed difficult but eventually thought of an approach. It took me a while to code it, and when I finished it, there were bugs. 10 minutes before the end of the contest, I switched to A, but it didn't appear that I would be able to solve it in 10 minutes, so I decided to go back to B. Debugged and finishing coding it right as the contest ended. It doesn't really matter though, because it turns out that my idea , while correct, would still time out because of an issue I missed to notice. After I fixed this issue, it works fine.

problem statement

A set of n towns is a tree (n-1 roads and it is connected). m towns are haunted. The origin of the hauntings is a town such that its minimum distance between it and the haunted cities is at most d. Return the number of cities that follow this rule. `(1 <= m <= n <= 100000)`,

Very large constraints, but we got to take advantage of it being a tree.

Since it is a tree, we can pick a root, any vertex works. For each vertex calculate farHaunted, the maximum distance between the vertex and a haunted vertex that is a child or a grand child of it. (In the rooted tree) This is workable in `O(n)` time.

The real challenge is to find the actual maximum distance from a vertex to a haunted one, (possibly outside the subtree). To do this, let me define parentHaunted, the minimum distance between vertex x and a haunted vertex such that the road between x and the haunted vertex visits the parent of x. After this is defined, we can just start on the root and then find parentHaunted for each child and grandchild we find. Using this value we can calculate the real maximum distance between the vertex and a haunted one. parentHaunted depends on the parent's parentHaunted and the data from the siblings, pick the sibling with the worst farHaunted. This is the part that caused my time out bug, it is best to do it in O(degree(x)) time.

int n, m, d;
const int MAX = 100000;
int p[MAX];
bool haunted[MAX];
int a[MAX], b[MAX];

int degree[MAX];
vector<int> g[MAX];

int farHaunted[MAX]; //what is the furthest haunted child of x?

void dfs(int x, int parent)
{
    int & fur = farHaunted[x];
    fur = -1;
    for (int i=0; i<degree[x]; i++) {
        int y = g[x][i];
        if (y != parent) {
            dfs(y, x);
            if (farHaunted[y] != -1) {
                fur = std::max(fur, farHaunted[y] + 1);
            }

        }
    }
    if (haunted[x]) {
        fur = std::max(fur, 0);
    }
}

int reallyFar[MAX];

void dfs2(int x, int parent, int hauntedParent)
{
    //my current position
    reallyFar[x] = std::max(hauntedParent, farHaunted[x]);
   
    pair<int,int> bestChild ={-1,-1};
    pair<int,int> secondBestChild = {-1,-1};
    for (int i=0; i<degree[x]; i++) {
        int y = g[x][i];
        if (y != parent) {
            pair<int,int> p = make_pair(farHaunted[y], y);
            if (p > bestChild) {
                secondBestChild = bestChild;
                bestChild = p;
            } else if (p > secondBestChild) {
                secondBestChild = p;
            }
        }
    }

    
    for (int i=0; i<degree[x]; i++) {
        int y = g[x][i];
        if (y != parent) {
            int furpar = -1;
            if (hauntedParent != -1) {
                furpar = hauntedParent + 1;
            }
            if (haunted[x]) {
                furpar = std::max(furpar, 1);
            }
            int oth = bestChild.first;
            if (y == bestChild.second) {
                oth = secondBestChild.first;
            }
            if (oth != -1) {
                furpar = std::max(furpar, oth + 2);
            }
            dfs2(y, x, furpar);
        }
    }
}

int solve()
{
    fill(haunted, haunted+n, false);
    for (int i=0; i<m; i++) {
        haunted[--p[i]] = true;
    }
    //build the tree
    fill(degree, degree+n, 0);
    for (int i=0; i<n-1; i++) {
        int u = --a[i], v = --b[i];
        
        degree[u]++;
        degree[v]++;
    }
    for (int i=0; i<n; i++) {
        g[i].resize(degree[i]);
        degree[i] = 0;
    }
    for (int i=0; i<n-1; i++) {
        int u = a[i], v = b[i];
        assert(g[u].size() > degree[u] );
        assert(g[v].size() > degree[v] );
        g[u][degree[u]++] = v;
        g[v][degree[v]++] = u;
    }
    // pick an arbitrary root, let us say 0. Find farHaunted
    dfs(0, -1);
    // now do another DFS to fill reallyFar:
    dfs2(0, -1, -1);
    
    for (int i=0; i<n; i++) {
        if (reallyFar[i] <= d) {
            res ++;
        }
    }
    return res;
}

Monday, August 12, 2013

SRM 588: ouch (Update)

As I write this, I have to go, I am scheduling this to be up the time the challenge phase ends.

Div1 medium: The one with keys

There are up to 12 rooms, each with some red and green locks (up to 10 of each kind). You can use red or white keys to open red locks and green or white keys to open green locks. Each key is consumed once you use it. Each room has keys inside. What is the maximum number of keys you can have?

I was at first trying to make a viable dynamic programming solution. Similar to a GCJ problem. But I was not able to optimize it.

I eventually settled for a brute force search. Whenever you decide to open a room, you should only use white keys if you NEED to. This approach was slow, so I optimized it using all the dirtiest tricks in the book. Let us see if it passes.

Update: Turns out it passes system tests, so I will explain it.

Try all permutations of the order in which you open the rooms.

If you decide to enter a room and you have enough red and green keys, then you simply shouldn't use white keys. You should always use as little white keys as possible. Turns out this is also the "key" to solve it using dynamic programming.

With this, your approach needs `O(n!)` time, 12! is high, but not very high. So we can try some optimizations.

Imagine that at a given moment, there is one room that can be opened and after opening it, you end up with at least as many keys of each type as before. Then you should always open this room. So you shouldn't try sequences in which this room isn't opened.

Another special case, there is a room that you can open, but after opening it you end up with less keys of each type. This room is never a good idea. Ignore it.

I think that the two previous optimizations are enough , I was about to submit this, but last second I decided I could do an extra optimization, give priority to moves that give the maximum number of total keys, and cut the search when we tried too many options. I am not sure this is necessary, but I put it just in case.. Update 2: Yeah, it turns out this optimization wasn't needed.

Before the match I found out std::function causes a bug in TopCoder. That was too bad, because since there is no sane way to have anonymous recursion in c++ without using it, I had to use an outside function for the backtracking. This meant I had to copy all 5 argument variables as class members. What a bore.

vector<int> doorR,doorG,roomR,roomG,roomW;
int n, best, options[12];

void rec(int p, int r, int g, int w)
{
    best = std::max(best, r + g + w);

    if (p < n) {
        //each tuple is (i, nr,ng,nb):
        tuple<int,int,int,int> results[n-p]; //possible options
        int t = 0;
        
        for (int i=p; i<n; i++) {
            // for each candidate options[i], find if it is possible,
            // save it in results
            int &x = options[i];
            int nr = r - doorR[x];
            int ng = g - doorG[x];
            int nw = w;
            if (nr < 0) {
                // Not enough red keys, use white keys
                nw += nr;
                nr = 0;
            }
            if (ng < 0) {
                // Not enough green keys, use white keys
                nw += ng;
                ng = 0;
            }
            if (nw >= 0) {
                // if the number of white keys is non-negative we can do it
                // Increase the number of keys
                nr += roomR[x];
                ng += roomG[x];
                nw += roomW[x];
                if ( nr >= r && ng >= g && nw >= w) {
                    // This move is always a good idea, we should do it:
                    swap(options[p], options[i]);
                    rec(p+1, nr,ng,nw);
                    t = 0;
                    swap(options[p], options[i]);
                    break;
                } else if ( nr > r || ng > g || nw > w) {
                    // Make sure the move is a good idea before adding it
                    results[t++] = make_tuple(i,nr,ng,nw);
                }
            }
        }
        // process tuples:
        for (int j=0; j < t; j++) {
            int i, nr,ng,nw;
            tie(i, nr,ng,nw) = results[j];
            swap(options[p], options[i]);
            rec(p + 1, nr, ng, nw);
            swap(options[i], options[p]);
        }
    } 
}

int maxKeys(vector <int> doorR, vector <int> doorG, vector <int> roomR, vector <int> roomG, vector <int> roomW, vector <int> keys)
{
    // copy stuff, this is tedious:
    this->n = doorR.size();
    this->doorR = doorR;
    this->doorG = doorG;
    this->roomR = roomR;
    this->roomG = roomG;
    this->roomW = roomW;
    best = 0;
    for (int i=0; i<n; i++) {
        options[i] = i;
    }
    rec(0, keys[0], keys[1], keys[2]);
    return best;
}

Div1 easy: The one with songs

You have T time available to play as many songs as you can. Each song has a duration and a tone. If the tones of two consecutive songs are `x, y` then you need to rest `abs(x-y)` time units before playing the second song. What is the maximum number of songs?

It took me too long to correctly code this solution. As usual, I waited till there were less than 10 minutes before opening this problem.

The trick is, let us say you decide to play some songs. If the minimum tone is `p` and the maximum tone of the songs you play is `q`, then the minimum time you will need to wait because of the tone is always `q - p`. So, let us pick the minimum and maximum tone of the songs you will play, `O(n^2)` options for this pair. The rest is just to play the best song durations between these tones such that the total duration is less than or equal to `T - q + p`.

int maxSongs(vector <int> duration, vector <int> tone, int T)
{ 
    //sort the tones:
    int n = tone.size();
    for (int i=0; i<n; i++) {
        for (int j=i+1; j<n; j++) {
            if (tone[j] < tone[i]) {
                swap(tone[j], tone[i]);
                swap(duration[j], duration[i]);
            }
        }
    }
    int res = 0;
    // pick the minimum and maximum tone:
    for (int a=0; a < n; a++) {
        for (int b=a; b < n; b++) {
            int t = T - tone[b] + tone[a];
            int c = 0;
            // save the durations in a vector
            int tim = 0;
            vector<int> d;
            for (int i=a; i<=b; i++) {
                d.push_back(duration[i]);
            }
            // sort the durations, so that we pick the smallest c durations:
            sort(d.begin(), d.end());
            for (int x: d) {
                if (x <= t) {
                    t -= x;
                    c ++;
                }
            }
            // remember the best
            res =std::max(res, c);
        }
    }
    return res;
}

Sunday, August 11, 2013

Editorial for SRM 587 is out

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

Yeah, this took too long for my own good.

Please vote. I don't mean vote positively. Vote the way you prefer, but do it. I don't like that there are only 20 or so votes, far more people participate in SRMs.

Saturday, August 10, 2013

Test SRM#2 : In which I abuse lambdas

So, today we had a new test SRM in TopCoder. This time testing the g++ 4.8.1 compiler and a python upgrade too. g++ 4.8.1 has some amazing features over 4.4. So I really wanted to use them in this test. (Disclaimer: I am actually just learning c++11)

Div1 hard

It was a dynamic programming problem. I solved this one before, and though I avoided looking at the past solution, the idea was still evident. This problem is such a standard dynamic programming problem that I don't think we would be able to use it in division 1 as a medium anymore. It was a division 1 hard back in its day...

Was sad because I couldn't find an excuse to put any of the new features.

Div1 Medium: FlightScheduler

The maximum distance a plane can travel given an initial mass of fuel `f` is: `R = K ln( (m + f - t) / m )` where:

  • `K` is a constant for the plane (efficiency)
  • `m` is the plane's mass.
  • `t` is the mass of fuel spent during take off, so the initial amount of fuel has to be at least this.

(Special effort was put to make the problem statement as unclear as possible. I initially didn't know that the take off amount wasn't included in the first formula that appears in the problem statement. This really delayed me).

Anyway, so knowing that, we need to minimize the amount of fuel needed to travel `D` distance units. We are allowed to land at any intermediary point, recharge fuel and take off.

Equal distances

The first thing to know is that if we make `(n-1)` stops, so that the plane takes off `n` times in total, it is always better to cover the same distance in each of the sub-trips. So we should move `D / n` units in each of them.

The independent variable that determines the final fuel cost is then just `n`. We need to find the best value of `n` for this.

Ternary search

So, let us say we make one flight. In this case, the amount of fuel needed for a single round might be too large (Note that the formula for R is logarithmic in the mass of fuel, so increasing the amount of fuel by a large amount will not increase the distance that much).

If we instead do a lot of flights, it is also not very good, because each flight needs at least `t` fuel.

There is a value of `n` that will yield a minimum value for `f(n)`, the total fuel cost. For `(x < n)` and `(y > n)`, we can guess that: `(f(x) > n)` and (f(y) > n). Also, the more we move away from `n`, the worse the result. This is all ternary search-friendly. Let us do it.

f(n)

So let us just find `f(n)`, the minimum fuel cost needed to travel `D` distance units using `n` trips. Let `(d = D / n)` , this is the distance per trip. What is the minimum fuel cost to travel `d` distance units? We need the following to be true::

`K ln( (m + f - t) / m ) >= d`

Let us solve the inequality.

`ln( (m + f - t) / m ) >= d / K`
`(m + f - t) / m >= e ^(d / K)`
`m + f - t >= me ^(d / K)`
`f >= me ^(d / K) - m + t`
`f >= m(e ^(d / K) - 1) + t`

So that is the lower bound for f.

Implementing ternary search

So, I really wanted to use the new c++ features. You know what is funny about ternary search? You need to implement the function f. You know what is lame about solving TC problems using multiple functions? TURNING ARGUMENTS INTO CLASS MEMBERS. It is so tedious to copy variables manually just so a new function can use them in their scope. OOP is truly the worst idea ever. Anyway. It occurred to me... I can use a closure! This way when I create the function f() I will do it inside the scope of the main method, so no need to copy arguments manually.

The result is beautiful:

double minimizeFuel(int distance, int K, int emptyMass, int takeoffFuel)
{
    // so we use closure syntax. The [=] means
    // that any variable like "emptyMass"
    // that is referenced inside the anonymous function (lambda) will be
    // automatically copied, so when we call f() it will use copies just fine.
    
    auto f = [=](long n)->double {
        double d = distance * (1.0 / n); 
        return n * ( takeoffFuel + emptyMass * (exp(d/K) - 1.0) );
    };
    
    long lo = 1, hi = 40000100000L;
    while (lo + 2 < hi) {
        long ha1 = (lo*2 + hi) / 3, ha2 = (lo + hi*2) / 3;
        if ( f(ha1) < f(ha2) ) {
            hi = ha2;
        } else {
            lo = ha1;
        }
    }
    // the minimum is one of f(lo), f(lo+1) or hi = f(lo+2):
    vector<double> res = { f(lo), f(lo+1), f(lo+2) };
    return *min_element(res.begin(), res.end());
}

It turns out that I had to go out in the middle of the match , so I didn't have much time to finish this problem correctly. When I came back, there were few minutes left of coding phase. I tried to debug, I found the bug (The issue with problem statement I mentioned above). But it was still wrong. Eventually, when there were only 5 minutes left, I gave up trying to find the bug and moved on to 250. It turns out that my bug was that I did: d = distance / n. Both distance and n were integers, so it was doing integer division....

Div1 Easy

An implementation problem, I didn't have much time to finish it.

And more

It turns out that lambdas and closures are awesome. There is plenty of more in regards to this new functional c++.

After the match, I figured, that I could actually make myself a TernarySearch library (template) function that does the whole TernarySearch for me and can be used in any situation.

// D: function domain 
// R: function range  , so f: D -> R
// Yep, std::function is useful:
template<class D, class R> R TernarySearch(D lo, D hi, std::function<R(D)> f) {
    while (lo + 2 < hi) {
        D ha1 = (lo*2 + hi) / 3, ha2 = (lo + hi*2) / 3;
        if ( f(ha1) < f(ha2) ) {
            hi = ha2;
        } else {
            lo = ha1;
        }
    }
    vector<R> res = { f(lo), f(lo+1), f(lo+2) };
    return *min_element(res.begin(), res.end());
}

So, if I wanted to use this function to solve today's problem:

double minimizeFuel(int distance, int K, int emptyMass, int takeoffFuel)
{
    return TernarySearch<long, double>(1, 40000100000L, [=](long n){
            double d = distance * (1.0 / n); 
            return n * ( takeoffFuel + emptyMass * (exp(d/K) - 1.0) );
        });
}

Or maybe you prefer the following version:

double minimizeFuel(int D, int K, int m, int t)
{
    std::function<double(long)> f = [=](long n){
        return n*( t + m * (exp(D / (1.0*n*K)) - 1) );
    };
    return TernarySearch(1L, 40000100000L, f);
}

Comments?

What do you think of g++ 4.8.1 so far? Worthwhile upgrade?

SRM 587 editorial previews

It has been a long week. Remember that when I finished SRM 586's editorial I really intended to do 587 quickly?. It seemed like I was going to do it! The match seemed easy too. The problem, however, was that I just couldn't find a good proof for the hard problems. This is a match in which the proof for the hard problems was probably the only complicated thing, so I really wanted to have something very formal. As I was working on it, eventually my chronic headache came back looking for a revenge. It was being a nice guy for the previous weeks, but this week it was affecting me in a way that really slowed me down. But I was going there. I finally finished these editorials. The rest of the match will be easy, I think, div1 medium will require me to spend some time doing Inkscape stuff, though.

ThreeColorability (SRM 587 div1 hard)

(main editorial preview post)

Intro

Link to problem statement. In short, we have a square grid. We want to color the corners of the squares using at most 3 colors, in such a way that points connected by a line segment don't share a color. Is it possible? Of course is possible! so, how about making it harder? You also need to add exactly one diagonal in each of the squares. Some squares already start with diagonals. Find a way to fill the remaining diagonals.

This explanation takes the explanation for the division 2 version as a base. In that explanation we have found a property that is both necessary and sufficient for the setup to be valid. Each row must be equal or completely opposite to the first row. The question is how to use this property to generate the lexicographically-first way to fill the remaining cells?

Is it possible?

Given a grid of some set cells and some unknowns, can the unknown cells be filled in a way that the points are 3-colorable? In a way such that the number of Zs in each 2x2 sub-rectangle is even? In a way such that each row is equal or completely opposite to the first row?

Binary grids that follow those properties follow many other properties. There is a useful one that can be derived from the row property. If each row is equal to the first row or a negative, then we can "negate" the negative rows, the result will look like this (If we once again use 1 for Z and 0 for N):

0110001100101001
0110001100101001
0110001100101001
0110001100101001
0110001100101001
0110001100101001

Then we can negate all the columns that contain 1, and the result is full of zeros. We can conclude that valid setups are those in which you negate a set of rows and a set of columns. Let us assign values to the rows and columns, 0 for rows/columns that are not negated and 1 for the negated ones. Now take a look to the following setup:

????1??????
?0??????0??
????1??????
?0?????????

If cell `(x,y)` has value 0, then there are two possibilities: a) Neither column `x` or row `y` were negated. b) Both column `x` and row `y` were negated. We can just say that the values for row `y` and column `x` must be equal. Likewise, if cell `(x,y)` had a 1, it would mean that the values for the respective row and column must be different. If the cell was '?', then there is no condition that connects the row and column directly.

Consider a set of variables such that each could be 0 or 1. There are some conditions of the form `(v_i = v_j)`, and others in the form `(v_i != v_j)`. Is there at least one way to assign valid values to the variables? If you assign 0 to a variable, the rules will force you to assign 0 to some variables and 1 to others. You can then process the rules for each of these new variables and you will be forced to assign other values to other variables. Repeat until there is a contradiction or until all variables get an assigned value. If we assigned 1 to the first variable it wouldn't really change the result, all variables would just be negated. In other words, each condition connects two variables and we just need a Depth-first search (DFS) between the variables.

Lexicographically first

Once we can confirm if a setup can be filled correctly. We can use the same function to find the lexicographically-first result. Try the first of the unknown cells in row-major order, if adding a N to this cell position is possible, then the lexicographically-first setup will have a N in this location (Because 'N' is smaller than 'Z'). If it is not possible to put a N, put a Z. Then try the remaining unknown cells in row-major order, always placing the smallest possible value in each of them.

Code

int N;
int graph[110][110];
int color[110];


void dfs(int x, int c){
    if (color[x] != -1) {
        return;
    }
    color[x] = c;
    for (int i = 0; i < N ; i++) {
        if (graph[x][i] != -1) {
            dfs(i, (c ^ graph[x][i]));
        }
    }
}

bool check() {
    fill(color, color+N, -1);
    // do a DFS, to fill the values for the variables, start each connected
    // component with 0:
    for (int i = 0; i < N ; i++) {
        if (color[i] == -1) {
            dfs(i, 0);
        }
    }
    for (int i = 0; i < N ; i++) {
        for (int j = 0; j < N ; j++) {
            // Check if there is any inconsistency:
            if (graph[i][j] != -1 && ((color[i] ^ color[j]) != graph[i][j]) ) {
                return false;
            }
        }
    }

    return true;
}

vector <string> lexSmallest(vector <string> cells){
    int X=cells.size(), Y=cells[0].length();
    
    N = X + Y;
    for (int i = 0; i < X ; i++) {
        for (int j = 0; j < Y ; j++) {
            graph[i][j] = -1; //-1 means there is no connection between the variables
        }
    }
    // For each cell != '?':
    for (int i = 0; i < X ; i++) {
        for (int j = 0; j < Y ; j++) {
            if (cells[i][j] != '?') {
                // If the cell is 'Z', the row and column must be different
                // save 1 in the graph. Else 0, they must be equal.
                graph[i][X+j] = graph[X+j][i] = (cells[i][j] == 'Z');
            }
        }
    }
    
    if (!check() ) {
        // the board is already invalid
        return {};
    }
    
    // Lexicographically-first.
    // For each cell in row-major order:
    for (int i = 0; i < X; i++) {
        for (int j = 0; j < Y ; j++) {
            if(cells[i][j] == '?') {
                //Try with N:
                graph[i][X+j] = graph[X+j][i] = 0;
                if (!check()) {
                    // Not possible, put a Z:
                    graph[i][X+j] = graph[X+j][i] = 1;
                }
            }
        }
    }
    // translate the result back to N/Z:
    vector <string> ans(X);
    for (int i = 0; i < X ; i++) {
        for (int j = 0; j < Y ; j++) {
            ans[i] += ((graph[i][X+j] == 0) ? 'N' : 'Z');
        }
    }
    return ans;
}

ThreeColorabilityEasy (SRM 587 div2 hard)

(main editorial preview post)

Intro

Link to problem statement. In short, we have a square grid. Each square contains a diagonal connecting two of its corners. We want to color the corners using at most 3 colors, in such a way that points connected by a line segment don't share a color. Is it possible?

This problem had multiple solutions. As usual some solutions need less analysis and others less code.

Simple analysis

This first solution is not difficult to think of or prove, but the code can be very complex.

Think of the setup of lattice points with N and Z patterns. It is actually a set of triangles:

Triangles have three vertexes and they are all connected to each other. Each vertex in the triangle must have a different color. Let us just pick the 3 colors for any of the triangles:

This triangle shares edges with other triangles. These triangles each have two new colors. The decision for the remaining color in each of these triangles is forced. We only have 3 available colors.

Each of these triangles have adjacent triangles of their own, once again we only have one option for the remaining color in each of these triangles:

We can go on... Note that some of the triangles that were adjacent to the previous ones are already completely colored. If this happens, we should verify that they have 3 different colors.

We have found two cases of a contradiction. In the bottom: If we fill one of the triangles, we will guess that the corner must be blue. If we fill the other triangle, it would tell us that the same corner must be red. Note that at the beginning, we just filled a triangle with three distinct colors. It wouldn't matter which order of colors we picked for this first triangle, the contradiction would still happen (but with different colors). Also, the triangle we picked must be colored eventually. So it must have three different colors. No matter what we do, we cannot use three colors to fill this setup.

If, instead, after visiting all of the triangles, we didn't find any inconsistency, then we would already know of one way to color the points. It is both necessary and sufficient that this coloring strategy works in order for it to be possible to use only three colors.

The complicated part about this approach is to implement it. We can pick any triangle to color in the first step. Let us just pick one of the triangles in the top-left cell. After filling one triangle we need to process the remaining triangles in such an order that each triangle shares an edge with at least one triangle that was processed before. Once we fill the two triangles in the top-left cell, we can take the second triangle in the top row, and so and so. If we process the cells in row-major order, we can be sure that at least one triangle in the cell shares an edge with a previously-processed triangle. However, it is not trivial to know which of the two triangles shares the edge, so we still have some potential issues to take care of:

// Each of the following functions returns true if it finds a contradiction.

// Verify/Complete the colors in triangle (a,b,c). Assume that at most one of 
// them is unknown.    
bool completeTriangle(int &a, int &b, int &c)
{
    /*    a
         /|
        / |
       b--c */
    
    // Rotate vertices list until we are sure a, and b are known colors:
    if ( a == -1 || b == -1) {
        return completeTriangle(c,a,b);
    }
    if (c != -1) {
        // All three colors are known, but we must verify that they are
        // distinct:
        return (a == b || b == c || c == a);
        
    } else {
        // c is the unknown, find a number from 0 to 2 that is different
        // from a and b.
        c = 0;
        while ( (c == a || c == b) && (c < 2) ) {
            c++;
        }
        return (a == b);
        //this is not necessary, if a == b, then the contradiction
        // would have been found before.
    }
}

bool fillTwoTriangles(int &a, int &b, int &c, int &d)
{
    /*                       a--b
     Fill the two triangles: |\ |
                             | \|
                             c--d */
    // Special case : all are unknown (The first cell)
    if (a == -1 && b == -1 && c == -1 && d == -1) {
        a = 0;
        b = c = 1;
        d = 2;
        return false;
    }

    // Else either (a,b,d) or (a,c,d) has two assigned colors, 
    // the triangle with two assigned colors first.
    int unknown = ( (a==-1) + (b==-1) + (d==-1) ); 
    if (unknown > 1) {
        // Too many unknowns in (a,b,d), begin with (a,c,d) instead.
        return fillTwoTriangles(a,c,b,d);
    }
    // assume (a,b,d) is a good start:
    return completeTriangle(a,b,d) || completeTriangle(a,c,d);
}


string isColorable(vector <string> cells)
{
    int h = cells.size(), w = cells[0].size();
    // Fill colors from top to bottom, left to right:
    int colors[h+1][w+1];
    memset(colors, -1, sizeof(colors));
    for (int y=0; y<h; y++) {
        for (int x=0; x<w; x++) {
            int &a = colors[y][x]  , &b = colors[y][x+1];
            int &c = colors[y+1][x], &d = colors[y+1][x+1];
            // Thanks to the order in which we fill the colors,
            // either the cell is (0,0) or at least one of the triangles
            // has two assigned colors.
            bool contr = false;
            
            if (cells[y][x] == 'N') {
                /* a--b
                   |\ |
                   | \|
                   c--d */
                contr = fillTwoTriangles(a,b,c,d);
            } else {
                /* a--b
                   | /|
                   |/ |
                   c--d */
                contr = fillTwoTriangles(b,a,d,c);
            }
            if (contr) {
                return "No";
            }
        }
    }
    return "Yes";
}

Simple code

There are actually two approaches worth naming that yield very simple codes.

One problem solving method is to try to find a pattern in boards that are solvable. To this effect, we can try and solve small setups. If you try any setup with only one row or only one column, you will see that they are always solvable. Let us better try setups with 2x2 cells. Of the 16 setups with 2x2 cells, the following 8 are 3-colorable:

There are two interesting ways to find a pattern in these. Perhaps it is clearer if we use 0 for Z an 1 for N:

00 00 01 01
00 11 01 10

10 10 11 11
01 10 00 11

Rule for 2x2 patterns a necessary rule in general

Each of those patterns has exactly an even number of N (and therefore an even number of Z) cells.

We can try to generalize this to larger setups. Perhaps the rule is that each 2x2 sub-rectangle of the setup needs to have an even number of N cells? It is easy to tell that this rules is necessary. We already know that a 2x2 sub-rectangle with an odd number of N cells cannot be colored. If at least one of those sub-rectangles exists, we cannot color it. If we cannot color a sub-rectangle in the setup, then we cannot color the setup itself.

Sufficient?

We need to show that the rule is also sufficient. If it was only necessary, then we wouldn't be able to guarantee that a setup that follows the rule is 3-colorable.

Assuming a setup follows the rule, can we prove that it is 3-colorable?

A new property

Back to the 2x2 setups, consider the 4 possible top rows: {00, 01, 10, 11}. Each has two valid values for the bottom rows. More interestingly, the valid values for the bottom rows are either the same as the top row, or the complete opposite. For example, if the top row is 01, then the two valid bottom rows are 01 and 10.

Now consider a larger row like 0100111101011010. We will pick the values for the row below it:

0100111101011010
----------------

For the first two cells, we have two options 01 (equal) or 10 (opposite). Let us pick equal:

0100111101011010
01--------------

Consider the next 2x2 block. Its top row is 10, so the only two valid options for the row below are 10 and 01, however, the 1 is already chosen. We are forced to pick 10 (also equal). If we continue filling the row, we will always be forced to pick an equal cell:

0100111101011010
0100111101011010

What if in the first step we chose the opposite? The same will happen, this time the whole row has to be the opposite:

0100111101011010
1011000010100101

If a setup follows the 2x2 rule, then it is also true that it follows a new rule: Each row must be equal or the complete opposite of the previous row. This property is nice because it will make the code even simpler. It will also be useful if we intend to solve the division 1 hard version of this problem. It will also help us prove that the 2x2 property is sufficient.

Sufficient

Imagine we have chosen the colors for the top row. We have previously mentioned that it is always possible to use 3-colors to color a single row. If the next row is exactly equal to the top row, can we color it? If the next row is exactly the opposite, can we color it? If the answer for both questions is Yes, then we can use this argument in a proof by induction. Each of these questions will need a proof by induction of its own.

Equal row

For n=1. The number of columns is 1. We have colored the single cell in the top row. Can we color the row below it? This is a trivial case, because it is always possible to color a setup that has only one column.

Assume that the rule is true for n=k-1. We have colored the k cells in the top row. Can we color the k cells of the bottom row? Since the rule is true for n=k-1 we can assume that the first k-1 cells of the bottom can be colored correctly. There are 4 cases:

From the hypothesis, we know that the yellow points were colored in such a way that there are no contradictions in any of pink triangles. What we need to confirm if if the remaining white point can be given a color in such a way that there are no inconsistencies in the two white triangles. However, each of these 4 cases represents one of the 2x2 patterns that we already know can be colorable. If the colors for the vertices of the pink triangles are all valid, the remaining color and triangles will be valid too.

The proof for the opposite case is similar to this, it just uses the four 2x2 patterns we didn't use in this proof.

Code

For each row, verify if it is equal or completely opposite to the first row. This property is necessary and sufficient for the setup to be 3-colorable.

class ThreeColorabilityEasy:
 def isColorable(self, cells):
    # row 0
    a = cells[0]
    # the negative of row 0
    b = string.join( ['Z' if ch == 'N' else 'Z' for ch in a], '')
    # All rows must be equal to a or b:
    return "Yes" if all( (row == a) or (row == b) for row in cells) else "No"

-------------------

Isn't that short python code beautiful?

You are now ready to solve the hard version.

Thursday, August 08, 2013

Test SRM #2 : Revenge of the C++11

So, there is another test SRM scheduled for Saturday. This is great news. Whilst TC will be testing new compiler versions for c++ and python, I will be testing a new code environment.

It looks like TopCoder is getting gcc-4.8.1. This is quite serious. Because the c++11 support will be enabled. Take a look to the list of c++11 features available in gcc-4.8.1: http://gcc.gnu.org/gcc-4.8/cxx0x_status.html. Compare it with the puny gcc-4.4 list: http://gcc.gnu.org/gcc-4.4/cxx0x_status.html. Of course, some things like threads will not be supported in SRMs, but otherwise the list of syntax candy will be increased greatly. gcc-4.8.1 is so new, that ubuntu 12.04 repositories don't support it. The list of new features is humongous. If you thought auto and tuples were a big deal. Brace yourselves...

range-based for loops

string canTransform(string init, string goal)
{
    string x = "";
    //Beautiful:
    for (auto ch : goal) {            
        if ( ch != 'z') {
            x += ch;
        }
    }
    return (x == init) ? "Yes" : "No";
}

You could use char ch too if that's your taste.

Lambda expressions

Remember sorting in c++? When the ordering is not a trivial one, you often had to declare a whole struct with strange syntax inside and then use the struct in the call to sort. This is an alternative to all that:

// How to sort elements in a vector by their absolute value:
vector<int> v = {5, 0,-1,-5, -3,3,2, -5};
sort(v.begin(), v.end(), [](int a, int b) {
    return abs(a) < abs(b);
});
// shows: 0 -1 2 -3 3 5 -5 -5
for (auto &y : v ) {
    cout << y << ", ";
}
cout <<endl;

Lambdas are anonymous functions that you can create inside code blocks. In the example we use the [](int a, int b) { return boolean } syntax to create a function pointer that is then used and called by sort. The world of lambdas is a huge one. And their usefulness is understated the first time you hear about them. Here is a page that explains them throughly.

Closures

One of the good things about lambda syntax is that it enables closures. Aaaand things just got crazy...

For example, what if you want to sort some numbers `x` by the values `y[x]` in some array?

vector<int> y = {10, 7, 8, 3, 5, 1 ,1};    

vector<int> x = {0, 1, 2, 3, 4, 5 ,6};
// sort x[i]s by y[x[i]]:
sort(x.begin(), x.end(), [=](int a, int b) {
    return (y[a] < y[b]);
});
// note the [=] syntax, we are making copies of vector<int> y.

// display 5, 6, 3, 4, 1, 2, 0,
for (int z : x ) {
    cout << z << ", ";
}
cout <<endl;
// we can use int z : x
// If we did int &z: x, they would be references
//   (modifiable and maybe faster)

So...

It's hard to overstate my satisfaction.

If only the python version was python 3, everything would be 110% perfect

Tuesday, August 06, 2013

KawigiEdit 2.3.0

Yep, it seems like I am sliding the maintainer slippery slope.

The major changes in this version of KawigiEdit were caused because I wanted to try the idea of using an external editor to code TopCoder stuff. KawigiEdit is good as an editor - definitely much better than the vanilla editor. But jEdit has a lot of features. Let us face it, the "Code Editor" problem is a problem that has already been solved and a minor project like KawigiEdit can't compete with other editors in that area.

So , move to FileEdit / moj, etc ? Not really. The thing is that although KawigiEdit can't beat external editors, the TopCoder integration is something that KawigiEdit does wonderfully. As an editorial writer / problem setter that really, really likes c++, I need a plugin that works with Java, c++ and python. Language support is definitely a deal-breaker. Having to install and use multiple plugins - one for each language would be quite terrible.

Kawigi is great at generating tester code. The resulting file compiles and run. The tester code is removed before you send it to TC. And that includes all 5 languages. Not only that, but you can easily edit/add the test cases it uses. And temporarily disable some without deleting them.

Another super ultra convenience is that it saves independent files for anything you code in topcoder. I have a giantic directory full of old solutions I can use for reference. I actually have this directory synced with a private dropbox folder, just in case my computer explodes during a SRM, I can take my laptop and keep on working...

So, the point is that nothing really beats KawigiEdit as a plugin for vexorian's use. So I tried to give it a try as a bridge between topcoder and jEdit . It worked ok (And I even managed to add a jEdit macro that calls my separate terminal window tester just like KawigiEdit did). But I found some issues. There is specially too much cluelessness as to what is the editor doing. Is it using your code or its own? Why isn't it loading your code? Etc. Overall I had to make many additions, including a log window. The log window is also very useful when I am editing KawigiEdit, I can use it to show debugging messages :). I fixed some other things related to syncing with an external editor.

So, there it is. If you want to try it out, go to its topcoder forums thread.

As usual, my personal mod for KawigiEdit has been updated too. Refer to the old blog post to find it. Actually, it has been changed. Now it dose not have the compile tab. Only the output tab. Any exit code error in running compile/run commands will be reported there.

Friday, August 02, 2013

SRM 586 Editorial finally there

http://apps.topcoder.com/wiki/display/tc/SRM+586. If you already read it before and are not interested in div1 medium, please go to the link anyway, because it now has the vote thing... I mean really, supposedly TopCoder has 500000 members, and a couple thousands are active in SRMs, but editorials only get around 20 votes if lucky? That doesn't make any sense.

I finally finished the editorial for the medium problem. Not without getting directions from hex539. I actually was quite close during the match. Remember my recap? Now that I fixed my setup, and valgrind shows line numbers, I was able to quickly find the mistake I had during the match. It turns out that battles could be space-separated lists and not just each index = a single battle. I didn't notice because the first example was nicely formatted. Then when valgrind wasn't giving me line numbers I think I panicked. It seems that I am a completely incapable c++ programmer without valgrind...

Anyway, although I had the top-level idea - You can find bounds from each battle, then you need a transitive closure to improve the bounds. I had no idea how to do the transitive closure. So I doubt I would have solved the problem during a match even in optimal test environment.

So, now I have to write the editorial for SRM 587. I started SRM 586 late because of finishing SRM 585, this is starting to be an issue. I wanted to finish 586 really fast , but it took me too long to get the hard. I hope to finish SRM 587 quickly, because I can't spend all my time doing editorials. I'd like to have a breath before SRM 588, really.

Thursday, August 01, 2013

SRM 586 div1 easy and hard editorials

They are ready.

I solved div1 hard yesterday. Although it is probably not the easiest solution to explain. It took me very long to wrap everything it involves. This was long to write. I hope it is not a long boring read.

Div1 500 is a completely different story. I am still not sure how to solve it. I hope it doesn't take long.