Today's TopCoder Test SRM

So I wanted to take this SRM seriously as it would be good practice. It didn't help that I remembered to have solved two of these problems before. But there we go.

I wanted really hard to try the new c++ features, but there wasn't that much of a chance to do it, I still managed to pull some tricks.

RPSTournament

Problem statement

I didn't remember this problem. I likely didn't see it before. This old problem had a very confusing problem statement (So a competitor defeats people with both larger and smaller seeds within range? But then what decides which of the two competitors wins? I gave up.

WebsiteRank

Problem statement

I remembered solving this problem before, but I of course don't have such a precise memory to remember the solution. I did remember that after SRM 357, there were tons of discussion about how trivial Floyd-Warshall passed (There can be around 800 website names.)

I actually had difficulty with the problem because I initially read the statement wrongly. The statement actually tells you to ignore points from pages that link to a site, if the site directly or indirectly links to them. I initially understood it as making the website ignore only the points "that come from it".

Once you read the problem correctly. You should be able to use Floyd-Warshall to quickly find which sites link directly or indirectly to each website. Once you ignore links between sites that do this - You are basically removing cycles from the graph. The graph becomes a directed acyclic graph. You could top-sort it, but it is not needed to. The total number of points each website receives is equal to the total number of paths that finish in the website (which is easy to calculate, even with a Floyd variation, because the graph is acyclic).

If the 800 website names bother you, just notice that there are only at most 51 relevant website names. (Websites that are the query's website or websites that are linked by other websites), so you can ignore the other websites and just consider them as extra initial points for each website. So in addition to counting the number of paths, you multiply the number of paths between each website i to the query website by the number of initial points of i.

// Using long (instead of long long) without a define!
long countVotes(vector <string> votes, string website)
{
    //maximum number of website names is around 50/3 * 50 ~=  833
    int n = votes.size(), t = 0;
    map<string,int> websiteId;
    vector<vector<string>> data;
    
    // Convert the votes array of strings to a data[][] 2d array of a
    // vector of strings. Note the auto keyword:
    for (auto q = votes.begin(); q!=votes.end(); q++) {
        istringstream st(*q);
        string x;
        // Look at this!:, pushing an empty vector:
        data.push_back( {} );
        auto & v =  *data.rbegin();
        while (st >> x) {
            v.push_back(x);
        }
        if (websiteId.count(v[0]) == 0) {
            websiteId[v[0]] = t++;
        }
    }
    if (websiteId.count(website) == 0) {
        websiteId[website] = t++;
    }
    vector<long> initialVotes(t, 1);

    int adj[t][t];   //Adjacency matrix
    int reach[t][t]; //Direct or indirect adjacency matrix (After Floyd-Warshall)
    long ways[t][t]; //Number of paths between each pair of nodes)
    memset(adj, 0, sizeof(adj));
    memset(reach, 0, sizeof(reach));
    memset(ways, 0, sizeof(ways));
    // First, setup the adjacency matrix: 
    for (int i=0; i<n; i++) {
        for (int j=1; j<data[i].size(); j++) {
            if (websiteId.count( data[i][j] ) == 0) {
                initialVotes[i]++;
            } else {
                int u = websiteId[ data[i][j] ], v = websiteId[ data[i][0] ];
                reach[u][v] = 1;
                adj[u][v] = 1;
            }
        }
    }
    // Find what nodes can be reached indirectly:
    for (int k=0; k<t; k++) {
        for (int i=0; i<t; i++) {        
            for (int j=0; j<t; j++) {        
                reach[i][j] |= (reach[i][k] & reach[k][j]);
            }
        }
    }
    // Now count the number of paths between each pair of nodes:
    for (int i=0; i<t; i++) {        
        for (int j=0; j<t; j++) {
            if (adj[i][j] && ! reach[j][i]) {
                ways[i][j] = 1;
            }
        }
    }

    for (int k=0; k<t; k++) {
        for (int i=0; i<t; i++) {        
            for (int j=0; j<t; j++) {
                ways[i][j] += ways[i][k]*ways[k][j];
            }
        }
    }

    // Done and multiply:
    long c = initialVotes[ websiteId[website] ];
    for (int i=0; i<t; i++) {
        c += initialVotes[i] * ways[i][websiteId[website]];
    }
    return c;
}

It seems I took longer to solve this problem than back in 2007, but this time I got the problem correct. I failed system tests in 2007.

PalindromeMaker

Link to statement

I still used my new strategy of waiting till there are less than 10 minutes before the end of the match before opening the easy problem.

This problem gives you a string of upper case letters. Return a palindrome permutation of those letters. If there are multiple solutions, return the lexicographically first one. If there are no solutions, return "".

Forget about the lexicographical condition. If we were to take any string like AABB and turn it into a palindrome, we would usually need each letter to appear an even number of times, so you can do ABBA or BAAB. There is one exception, when the length of the string is odd, then exactly one of the letters must appear an odd number of times. This letter should be used in the middle position.

Let us now deal with the lexicographically-first decision. Try each of the pairs of repeated letters. It is always better to place the lexicographically-smallest letter of those available in the smallest available position. So, for each letter from A to Z, in that order, pick every two of that letter, and push one to the left end and another to the right end. Remember the letters that appear an odd number of times. Then we can put the left, right (and maybe middle) ends together.

string make(string baseString)
{
    string left, right, odd;
    for (char ch='A'; ch <= 'Z'; ch++) {
        // Count the number of times letter ch appears:
        int c = count(baseString.begin(), baseString.end(), ch );
        // If it is odd, save it as the odd letter:
        if ( c % 2 == 1) {
            // Don't allow more than one odd letter:
            if (odd != "") {
                return "";
            }
            odd = ch;
        }
        // Half goes to the left end, other half to the right end.
        string rep = string( c / 2, ch );
        left += rep; right = rep + right;
    }
    // An odd letter must exist if and only if the string has odd length:
    if ( (baseString.size() % 2 == 1) == (odd != "") ) {
        return left + odd + right;
    } else { 
        return "";
    }
}

The end

It was an ok match, old problems feel very easy in comparison to current contests. Six years! That is depressing...

Read More

TopCoder Test SRM, new c++ features

Have you heard, there will be a Test SRM in just a couple of hours. The intention of the SRM is to test new* compiler versions. (* Relatively speaking). But if you want to practice, a test SRM is a good chance, because the problems will be reused but a surprise, and the time limit will simulate a real contest. It also introduces Python as an usable language. Unfortunately for python coders though, Arena plugins shall take a while to get updated to work with python.

Speaking of the new language versions. The new version for the g++ compiler is 4.4. It is a bit old, but at least it can be found in most Linux repositories (unlike the ultra old version that was in use before). The admins say that even newer versions will be used later.

The upgrade will remove some deprecated features. Most notably, the cool min/max operators like <?, >?, <?= and >?=.

Most importantly, there are new features! Specially because g++ is called with -std=c++0x. In other words, some features planned for c++0x will be available in TopCoder SRMs in the future and in today's match. Of course, not all of them. g++ 4.4 only has some of them implemented. But I found a list: http://gcc.gnu.org/gcc-4.4/cxx0x_status.html

There are a couple of things that C++ coders should know.

auto keyword

While it is in terrible taste to use the word auto instead of var, the new auto keyword will prove to be very useful when dealing with the STL.

void doSomething( vector< pair<string, pair<int,int> > > toocomplex ) 
{
    auto copy = toocomplex; //makes a copy of toocomplex.
    //blah blah blah...
    
    

read more

Initializer lists

This is now possible:

// a quick array:
int A[] = {1,2,3,4,5,6};
cout << A[3]<<endl;

// a vector<int>:
vector<int> B = {5,6,7,89};
cout << B[2] << endl;

// Or how about a set?
set<int> B = {1,2,3,7,8,9};
// Is 3 in the set? (will show 1)
cout << B.count(3) << endl;
// Is 4 in the set? (will show 0)
cout << B.count(3) << endl;

// Yep, you can use any expression, not just constants:
int x = 5, y = 7, z = 8;
set<int> b = {x,y,z};

// Forget about make_pair:
pair<int,int> v = {2,3};

Nuff said.

long

Have I ever complained about having to type long long instead of just long? Yes, yes I did.. Fear not, because long is 64 bits now, without having to type long long.

More

Plenty of changes for templates, look at the gcc 4.4 table linked above for more. Most of these template features would be useful if you are coding data structure libraries. static assertions could be nice to avoid some pit falls. Also, vector<int, pair<int,int>> is valid syntax. That double closing > has caused plenty of problems in the past to people that are just starting getting hold of the STL.

Read More

TurnOnLamps editorial

This is the one other interesting problem in the match. Remember I solved this problem during the match and even wrote a quick explanation already? It is interesting, I knew there was a greedy, but I didn't know if I was going to prove it, so I proposed me to write the editorial about the same dynamic programming approach. Interestingly, while I was writing that explanation, I could see through the problem and notice the idea nad proof for the greedy approach. It is not the first time that the process of writing an explanation for a problem teaches me more about the problem than just trying to solve it. For this reason, there are times I consider it very (VERY) seriously to write explanations for problems at the same time as I am participating in the contest.

I should finally be done with this SRM 583 editorial soon. The other problems are all implementation ones (I fear the explanations will end up boring and tedious). Then I have to write the editorial for round 3B. This job is becoming a busy one.

TurnOnLamps

We have a trees. There are lamps in each of its edges. Some are on, some are off. In a single step, you pick two vertexes and toggle the lamps between the two vertexes. There is a list of important edges that must end with a turned-on lamp (state = 1). Return the minimum number of simple paths you need to pick.

Number of paths and parity

The city is a tree and there are important edges (roads) and unimportant ones. Whenever we pick a pair of vertexes, all the lamps in the simple path between them are toggled. An important edge that starts with a turned-on lamp has to belong to an even number of picked simple paths. If instead, the important edge starts with a turned-off lamp, then it has to be picked an odd number of times. To simplify, we can say that unimportant edges can be picked an even or odd number of times. So we just need to minimize the number of paths we pick following the requirement of the parity of the number of times each edge is picked.

At most once

Since the problem depends on the parity of the number of times we use each edge, let us try to see what happens after we make that decision for each edge. For each edge `(u,v)`, decide the number of times it is picked in a path. Then we try to think of the paths that follow this rule. This is the time where we find out something interesting. Imagine an edge is used two times, by two separate paths:

Since the edge is used twice, its state is not affected at the end. The trick is to notice that those two paths would alter the states in the same way as the following two paths:

And in this case, the edge in question is not visited at all. We can generalize this idea further, it is never necessary to pick the same edge more than once, whenever that happens, we can find an equivalent combination of paths that have the same effect.

Exactly once

We cannot pick an edge more than once, but there are edges that we must pick at least once (Important edges that start with a state equal to 0). Then we have to pick them exactly once. There are other edges that must be picked an even number of times (important edges with initial state equal to 1), since 2 or more picks are not allowed, we must pick these edges zero times - don't pick them at all.

Greedy approach

All important edges with lamp state = 0 must be picked exactly once, we just need to minimize the number of paths that include them. The paths must not include any important edge with lamp state = 1.

There are `O(n^2)` total simple paths in the tree. We can just find each valid one of them. For each path, count the number of important edges with state = 0 that it contains. Then we can just pick the path with the largest amount of important edges it changes and make the change. This approach is optimal because any remaining important edge with lamp state = 0 will have to be changed eventually anyway. Making the changes in the path, can only make other paths unable to be picked in the future, if the other paths share at least one important edge with state = 0 with the largest path. If they do, however, we will always be unable to pick a smaller path that will contain the remnants of the path that is now unable to be picked. Thus the decision can only decrease and never increase the total number of used paths.

Finding the paths

The step to find the simple path between two vertices in the tree is a implementation challenge of its own. Since it is a tree, there is only one simple path and we can use any graph search like a Depth-first search (DFS). We just need to count the number of important edges afterwards.

Read More

SRM 583 Editorial preview: RandomPaintingOnABoard

Edit: So I just noticed a flaw with my strategy. Yep, MathJax renders my math perfectly... except for RSS, if you see giberish in your feed, look closer, it is TeX code, if you want to see the formulas you'll need to read the post in the site, sorry. Will look for work-arounds

Another week, another ultra late editorial ( Just in case, SRM 582 is being written by someone else ).

This was a interesting problem. Very math-focused and I took this chance as a chance to test my idea to start to use mathjax in editorials. I found out about mathjax, thanks to blue.boy's blog and since then I liked the idea, because frankly, my ascii formula art is very poor and I think we need TeX to explain some problems. Specially something like this problem.

I had a week-long difficulty trying to solve this problem. I actually had the main idea two days ago. Thanks to Petr and google translate. But something about the google translated explanation didn't make any sense, how was he pulling a magic trick to try `2^{12}` subsets instead of `2^{21}` ? . I could only notice last night, that there was another constraint for the number of cells...

RandomPaintingOnABoard

There is a board. In each turn a random cell is picked and painted black. Each cell `(i,j)` has probability equal to board[i][j] / (sum of all values in board[][]). The values are between 0 and 9 and each column and each row have at least one non-zero value. Return the expected number of steps before each column and each row have at least one painted cell. Note that the same cell can be picked multiple times.

A note about the constraints

Constraints indicate us that the maximum width and height will be 21. There is another constraint though: The maximum total number of cells is 150. This can help us because it means that the smaller dimension will be at most 12. `13 * 12 > 150`. Since rows and columns behave in the same way in this problem, we can just assume that the width is always the smallest dimension - In case it is not, we can just rotate the board. From now on assume that `1 <= w <= 12` and `w <= h <= 21` are the width and height of the board, respectively.

A sum of probabilities

The expected value of the necessary number of steps is:

\[ \begin{align*} E(\text{number of steps}) = \sum_{i=0}^\infty {i P(\text{i steps are needed}) } \end{align*} \]

We can think of many ways to find the probability that i steps are needed. This time it is convenient to think of the probability that the objective (at least one cell in each row/column is painted) is not fulfilled after `i` steps. Then you can tell, if the objective was not fulfilled after `i-1` steps, but it is fulfilled after `i` steps, then exactly `i` steps were needed. The following is a way to develop a formula to solve the problem after finding this conclusion:

\[ \begin{align*} P\left(\text{i steps are needed}\right) &= P\left(\text{Not done after i-1 steps}\right) - P\left(\text{Not done after i}\right) \\ E\left(\text{number of steps}\right) &= \sum_{i=0}^\infty {\left(i \left( P\left(\text{Not done after i-1 steps}\right) - P\left(\mbox{Not done after i}\right) \right) \right)} \\ E\left(\text{number of steps}\right) &= \sum_{i=0}^\infty {\left(i P\left(\text{Not done after i-1 steps}\right) - i P\left(\text{Not done after i}\right) \right)} \\ E\left(\text{number of steps}\right) &= \sum_{i=0}^\infty {i P\left(\text{Not done after i-1 steps}\right)} - \sum_{i=0}^\infty {i P\left(\text{Not done after i steps}\right)} \\ E\left(\text{number of steps}\right) &= 0 * P\left(\text{Not done after -1 steps}\right) + \sum_{i=1}^\infty {i P\left(\text{Not done after i-1 steps}\right)} \\ &- \sum_{i=1}^\infty {\left(i - 1\right) P\left(\text{Not done after i-1 steps}\right)} \\ E\left(\text{number of steps}\right) &= \sum_{i=1}^\infty {\left(i P\left(\text{Not done after i-1 steps}\right) - \left(i-1\right) P\left(\text{Not done after i-1 steps}\right) \right)} \\ E\left(\text{number of steps}\right) &= \sum_{i=1}^\infty {P\left(\text{Not done after i-1 steps}\right)} \\ E\left(\text{number of steps}\right) &= P\left(\text{Not done after 0 steps}\right) + P\left(\text{Not done after 1 step}\right) + P\left(\text{Not done after 2 steps}\right) + ... \end{align*} \]

With some changes, we have:

\[ \begin{equation*} \tag{1} E\left(\text{number of steps}\right) = \sum_{i=0}^\infty {P\left(\text{Not done after i steps}\right)} \\ \end{equation*} \]

Let us try to find probabilities that the objective is not done after `i` steps.

Inclusion-exclusion

We can see that probability as the probability that, after `i` steps, at least one row or column is not painted.

It is possible to calculate the probability each single row is painted or not after `i` steps. Let `s` be the probability we pick the row (or column) in a single step. The probability we do not ever pick it after `i` steps is ` ( 1 - s )^i `. We can add these probabilities together for each column or row. However ,we would be double-counting any situation in which there are two rows, two columns or a row and a column that are not painted after `i` steps. We can calculate, for each pair of two columns or rows, the probability `t` either of them are picked in a single step. The probabilities ` (1-t)^i ` are now the probability that neither of the two columns/rows/(column and row) will be picked after two steps, so we can subtract them from the original sum. But we would be subtracting some cases more times than necessary - The cases in which there are 3 or more columns or rows that are not painted. In short, we can use the inclusion-exclusion principle:

\[ \begin{align*} P\left(\text{Not done after } i \text{ steps}\right) &= \sum_{ x \in \left( \text{rows } \cup \text{ columns} \right) } { \left(1 - P(x) \right)^i } \\ &- \sum_{ \left\{x_0,x_1\right\} \subseteq \left( \text{rows } \cup \text{ columns} \right) } { \left(1 - P\left\{x_0,x_1\right\} \right)^i } \\ &+ \sum_{ \left\{x_0,x_1,x_2\right\} \subseteq \left( \text{rows } \cup \text{ columns} \right) } { \left(1 - P\left\{x_0,x_1,x_2\right\} \right)^i } \\ &- \sum_{ \left\{x_0,x_1,x_2,x_3\right\} \subseteq \left( \text{rows } \cup \text{ columns} \right) } { \left(1 - P\left\{x_0,x_1,x_2,x_3\right\} \right)^i } \\ &+ ... \\ \\ \tag{2} P\left(\text{Not done after } i \text{ steps}\right) &= \sum_{ s \subseteq \left( \text{rows } \cup \text{ columns} \right) , \left|s\right| \text{ is odd} } \left( 1 - P\left(s\right) \right) ^ i \\ &- \sum_{ s \subseteq \left( \text{rows } \cup \text{ columns} \right) , \left|s\right| \text{ is even} } \left( 1 - P\left(s\right) \right) ^ i \end{align*} \]

For each subset \(s\) of rows and columns, we calculate its probability \( P\left(s\right) \) that any of the rows and columns are picked in a single step. Then we subtract or add \( \left( 1 - P\left(s\right) \right)^i \) to the total, depending on the parity of the number of elements in the set.

Putting it together

Combining equations \( (1) \) and \( (2) \) together:

\[ \begin{align*} E\left(\text{number of steps}\right) &= \sum_{i=0}^\infty { \left( \sum_{\text{odd }s } {\left( 1 - P\left(s\right) \right) ^ i} - \sum_{\text{even }s}{\left( 1 - P\left(s\right) \right) ^ i} \right)} \\ E\left(\text{number of steps}\right) &= \sum_{\text{odd }s } {\left( \sum_{i=0}^\infty \left( 1 - P\left(s\right) \right) ^ i \right) } - \sum_{\text{even }s}{\left( \sum_{i=0}^\infty \left( 1 - P\left(s\right) \right) ^ i \right)} \end{align*} \]

The last trick we used was to distribute the outer summations inside the inner summations. For each set \(s\) of columns and rows, we just need to calculate \( \left( 1 - P\left(s\right) \right) ^ i \). Depending on the number of elements in the set, we add or subtract the resulting value from the total.

Let us find \( \left( 1 - P\left(s\right) \right) \), that is the probability that none of the cells that belong to a column or row in the set are picked. Let \(x\) be the sum of the values outside the set, the probability is then : \( (x / T) \). Where \(T\) is the total sum of all the cells in the board. The sum of all \( \left( x / T \right) ^ i \) is the sum of a geometric progression. Therefore:

\[ \sum_{i=0}^\infty \left( \frac{x}{T} \right)^i = \frac{T}{T - x} \]

For each set of columns and rows with a sum of cells outside it equal to \( x \), if the number of elements of the set is odd then add \( \frac{T}{T - x} \) else subtract \( \frac{T}{T - x} \). That is our result. Note that when \( x = T \), the formula is invalid. This can only happen if the set cannot be picked in any step, which is not true, because any row and column will always have at least one non-zero cell.

Count the sets

Since the value that is added/subtracted to the result depends only on \( x \), the sum of the cells outside the set, we can just count the number of even and odd sets for each value of \( x \). In fact, the result is to just multiply (number of odd sets for \(x\)) - (number of even sets for \(x\)) and \( \frac{x}{T - x} \) together. So we only need to find the total subtraction between the number of odd and even sets for each \( x \).

The sum \( (w + h) \) can be as large as 140, so the number of subsets of rows and columns can be insanely high. Remember though that \(w \leq 12\), so the number of sets of columns is not going to be very high. Assume that the set of columns included in the set \( s \)is already fixed, so we only need to decide which rows to add. If we decide to include the i-th column, then we already know the total sum of the cells outside the set - It is equal to the cells in the i-th row that do not belong to any of the picked columns. We can pre-calculate this sum after picking the set of columns.

Dynamic programming

Let mask be the fixed subset of columns. We precalculate \( b_i \), for each row \( i \), as the sum of the cells not included in any of the picked columns. Find the subtraction (number of odd sets) - (number of even sets) that is possible for every value \(x\) of the sum of cells outside sets of columns and rows that already include mask. Let \( f(i, x) \) be a function that solves this problem for the first \(i\) columns. If the \(i\)-th column is added then \(x\) remains the way it is, and the parity of the number of elements in the set changes. If \(i\)-th column is not added, \(x \) is increased by \(b_i\) and the parity does not change. From this we can make a dynamic programming solution. For each \( f(i, x) \), subtract \(f(i,x)\) from \(f(i+1,x)\) and add \( f(i,x) \) to \( f(i+1,x + b_i ) \). The base case is \( f(0,0) \) which is equal to -1 (If the number of columns in mask is even) or 1 (If the number of elements in mask is odd). After running this dynamic programming approach, we can accumulate the values we have found for each \(x\) given the mask.

For a complexity analysis, we repeat a \( O\left( h \times T \right) \) dynamic programming approach for \( O\left(2 ^ w \right) \) subsets of columns. In total, \( O\left(2^w \times h \times T \right) \). Remember that \( w \leq 12 \) and by constraints \(T \leq 1350\), so this solution can run comfortably under 2 seconds in TopCoder's servers.

Solution

// Assume we already processed the prob String[], we made an
//  int[][] a, with the translated cell values and we rotated
//  it in case w > h, so w is now guaranteed to be at most 12:
public double expectedScoresSmallWidth(int[][] a){
    int h = a.length, w = a[0].length, T = 0;
    
    for (int i=0; i<w; i++) {
        for(int j=0; j<h; j++) {
            T += a[j][i];
        }
    }
    // cnt[x] : Subtraction between the number of odd sets and even sets that
    //           have a sum of x for the outside cells.
    long cnt[] = new long[T+1];
    
    for (int mask=0; mask<(1<<w); mask++) {
        int sign = -1;
        for (int i=0;i<w;i++) {
            if ( (mask&(1<<i)) != 0) {
                sign = -sign;
            }
        }
        // base case: (if mask has an even number of elements -1, else 1)
        long f[][] = new long[h+1][T+1];
        f[0][0] = sign;
        
        // precalculate b[i]: Elements in column i outside of the mask subset:
        int b[] = new int[h];
        for (int i=0; i < h; i++) {
            for(int j=0; j < w; j++) {
                if ((mask&(1<<j)) == 0) {
                    b[i] += a[i][j];
                }
            }
        }
               
        for(int i=0; i<h; i++) for(int x=0; x<=T; x++) {
            f[i+1][x] -= f[i][x];
            if (x + b[i] <= T) {
                f[i+1][x + b[i]] += f[i][x];
            }
        }
        
        for (int x=0; x < T; x++) {
            cnt[x] += f[h][x];
        }
    }
    
    double ans = 0.0;
    for (int x=0; x<T; x++) {
        ans += (double)cnt[x] * T / (T-x);
    }
    return ans;
}

Read More

How to fail in TopCoder Marathon round 3

You are given N circles. Just because the problem setter is evil, the distribution for N is not uniform , the numbers are from 50 to 500, and have a bias towards the bottom. Each circle has a random center inside the [(0,0), (1,1)] rectangle, a random radius (rather small) and a random mass m[i]. They are of course going to overlap initially. Move the circles to any other positions in such a way that they no longer overlap and the total work you spend is as little as possible. The total work is equal to the sum of m[i]*(distance between original and final position) for each i.

So the objective is to waste 2 weeks of your life trying to come up with a good solution to this problem that runs in 10 seconds. If you acquire a good rank (probably at least 44-th) you win a t-shirt. The kind of t-shirt you couldn't win in the algorithm track of the tournament. If you do very good, and that means top 4, you win a free trip. I have no idea what is necessary to ever be in the top 4 of a real Marathon match. I suspect witchcraft is somehow related to it, though.

First week

After a very poor performance in the round 2. I decided to take round 3 very seriously and start working on it since the first day of the match. It was a great plan, and I think I could have gotten a t-shirt if I went through it. However, the week this match started was quite a difficult week. I was busy with an editorial, and then I became busy having to work in problem setting Block3Checkers - That problem that was used in the algorithm round. I actually barely noticed the marathon started the Satuday after the problem was finished. But then I still had to work on the *new* editorial...

I could barely start to work in this problem on last week's Tuesday. Almost all of the first week was not productive.

First version

I dedicate the first version of every marathon to the most trivial approach I can think of. The main purpose of the first version is to test the test environment. I have to tweak plenty of things. I have to adapt the visualizer provided with the problem to my ends. Adapt the testing to the thing that runs 500 tests for me. Make the thing that grades and ranks solutions, etc.

In this first version, I pick an arbitrary circle as the first circle. Then for each of the other circles, I try to put them as close as possible to the first circle, moving in the same angle as the one between the first circle and the new one. Using a binary search for the distance.

In the image, small red points are the original locations of each circle. Darker circles have larger m[i].

Even this solution was non-trivial, large Ns were timing out. It turns out that large cases don't have enough time to try all circles as the best initial circle. So I had to start with the larger circles and break when the time runs out.

More so, there was a bug with this solution, so I had to submit it twice. The outcome was position 169, very low. I knew I needed to point towards top 40 if I wanted a t-shirt.

Third version

So I already knew this problem was going to be complex. Too much geometry and too many factors to consider. One of them was , how exactly to decide where to place each circle? So I thought of something. I created a grid of sqrt(N) x sqrt(N) circle centers that were so separated from each other to ensure that no circle overlaps if put in those centers. Then I ran a bipartite matching between each circle and the new centers. Picking the matching with the best total work.

After the positions are decided, of course there will be tons of empty space between the circles. Do not despair, for I am adding a function that will try the circles in order, and try to move each circle as close as possible towards its center (in that direction). Using binary search.

Bipartite matching is too slow for large cases. So large cases still use the old approach.

Didn't really improve my score that much. Note how the circles in the two images are not in the same scale. The green square is the square from corner (0,0) to (1,1), all centers are picked inside it.

Fourth version

It was the beginning of a new day, and had a silly idea to try to improve the score. The original grid of empty spaces where to place the circles looks like this:

As you can see, that's not the most efficient use of all the space. So how about adding new, smaller spaces between the gaps?

It did improve my results. One of the reasons is that the radii are not uniformly distributed either, so there is a good quantity of small radii as well as very large. This took me to rank 146, still too low.

Fifth version

I needed a good idea, and I needed it quick. However, all I could think of was in lower level optimizations, I made a new min-cost max flow solver that was a bit faster. And indeed it was, it allowed me to use the matching strategy in larger N, but not much else. There was a mild improvement.

Sixth version

Bipartite matching is not the only kind of matching. We could always use a greedy matching. I decided to use greedy matching for larger values of N. Finding the closest position for the large values of m[i] first.

I also noticed that the whole binary search I was using to tighten the circles was slow and not very precise. Then it struck me: I can use equations! So you have a circle at some position (x1,y1) away from the original position (x,y), you want to find the closest position to (x,y) in the same angle that does not overlap with other circles. This means that you want a position that is tangent to some other circle. For each other circle, it is possible to find the positions (in the picked angle, if they exist) that would make the circle tangent to them. Then you need to pick one of these tangets that doesn't overlap with other circles....

This improved things up, but the equation is the important part, it opened some doors...

Seventh version

Another day passed. Kept thinking that the matching idea is probably not the way to go. It is very slow, and at the end, it creates gaps that you then waste tons of time "fixing". A better approach would need to be fast (so I could have some sort of iterative improvement to a solution

What I did like was the equation stuff from the previous solution. Then I somehow thought of something. An approach sort of similar to the very first one, but smarter: First decide an order in which to add the circles. Let us go with heaviest first. For each circle, try to place it as close as possible to its original location without overlaps. To reuse the equation, in each step we pick an angle (from the center), one of 360 ones. Using the angle, it is possible to find the best position for the circle with that angle.

This approach was slow at first. For each of N circles, we needed to repeat the same operation 360 times. The operation itself was slow because it needed to calculate positions using all of the previous circles. For each position it found, it needed to use all the previous circles again to avoid overlap... So slow, that I needed to make it use 180 angles for large values of N, making it less accurate.

This was still the most significant improvement I made. First time in the first page of standings. Top 100. But not good enough. The good thing about this approach is that it has plenty of room for improvement. How to pick the order? Picking the order is very friendly with iterative randomized searches, which makes the question of how to make the process - given an order - faster. How to pick the angle? , for example. How not to do that much work using all of the circles and instead only use the relevant ones? etc.

Eight version

I took a break for three days, because I was very late in writing the editorial for the TCO Algorithm Round 3A. My chronic headache (Which has just entered its 9-th consecutive week! Congratulations!) was also acting up. So I couldn't do much for three days. But I was tweaking the solution and doing X and Y things trying to improve. In the last day, I put things up together for a new submission. Surprising enough, all the small things I did at random times during the three days could really improve my score.

I tried to do Hill climbing for picking the order. In each iteration, pick two random indexes of the order array, swap them and calculate the minimum work when using that order, if the work is an improvement, replace your current order array with the new one, so that in the next iteration, that is your base. There are two problems with Hill Climbing. One is that my approach was too slow (barely executing once in large cases) the other is that Hill Climbing is not very good. It is prone to local minimums and getting stuck. To deal with the speed issue a bit , I changed the number of angles to 180 (small Ns) and 90 (large Ns), so that even large cases would have 4 or 5 iterations to try a modification of the order.

The initial order could also use some fixes. m[i] is a very good marker, but there are other things. For example, you could argue that it is more convenient to add circles that are close to the center (0.5, 0.5) first. So that there are less overlaps. But the weight is still important, so you need a sort of heuristic to combine both ideas. I settled with: sqrt(m[i])*m[i] * (1.5 - (distance to 0.5,0.5) ). Why? You ask. I have no idea, but it seemed to do better in local tests than other things I thought of...

I was able to optimize the cost of the function that adds the circles. Because it tries angles in all directions, then all already-place circles are relevant in that step. But only some few circles are relevant to some angles. In an initial step, I process all of the already-existing circles and find the lower and upper bound for an angle (starting at the original position of the new circle) that would have a ray that intersects with the circle. This is easy done by noticing that there is a straight triangle in there, with the upper and lower angles and that we know two of the distances, so it takes as much as calling asin.

This was good enough to reach top 50, back on June the 18-th... (Everybody keeps improving and your rank keeps getting worse if you don't improve).

Ninth version

A new day. Forgot to mention that the reason I focused so much in this approach is that I could show to myself that the order in which you add the circles alone can greatly improve my score. I tried with N=8 and all permutations. It was clear that if I had a good way to pick the order in which to add the circles, I could beat the first place even. But the problem is how to find this order.

A good idea is to make sure the initial order is as good as possible. The better the initial order, the less iterations you need before finding a GREAT order. In theory at least.

So I changed the order. To the previous formula I multiplied: m[i] / (sum of all m[i]s that overlap with the circle). The idea is that if a circle displaces plenty of heavy circles, it is probably worse as an initial pick that a light circle that does not displace heavy circles. This is all out of my mind and completely made up, but these crazy formulas worked in tests. This is the reason I have 500 tests, and a tester system that runs one in each cores... Before finding a good formula I try tons and tons of bad ones. However, once you reach to the hill climbing phase of a problem, testing becomes very tedious. Change a small bit of code, wait 15 minutes for a result. It is frustrating to wait. Specially near the end of the match...

Tenth version!

So I worked on ways to increase the number of iterations. The best I could find was a logic that made me stop needing to check, for each of the possible positions, if they overlap or not. Back to the tangents approach from 0.6, the two tangents delimit an interval of distances that we are unable to use. So for each relevant circle we have one of these intervals. We can use a line-sweep algorith. Just consider each start of an interval as an open bracket event, and each end of an interval as an end bracket event. After sorting the start/end points, it is easy to find the smallest distance that is not inside any bracket...

So I was finally having plenty of iterations. More than a thousand for small cases, and tens of iterations for the large cases. Remember I said Hill Climbing is not that great because of local minimums? It is the most noticeable when you have plenty of iterations. So I tried to implement a simulated annealing. And I failed. I thought I wasn't failing, because I was getting some good results after adding the annealing. But I was a victim of confirmation bias. A couple of versions later, I noticed that the only reason my annealing was working at all was that it wasn't working at all. Whenever I fixed the formulas to make the annealing work, and keep a less than-optimal solution in memory, results became worse. All that the annealing was doing was add instability to my test results, which made them look better, or worse after small changes, but it wasn't really so. I really need to learn SA....

11-th version

It was yesterday's night. My sleep time was approaching and I had nothing. I reached that moment in Marathons in which you cannot improve anything and can only manage to improvise and do small tweaks. I had just discovered that the SA was a total failure and ended up disabling it completely and decided to stick to Hill Climbing instead.

I needed a good idea. 11:00 PM was approaching, but then I had a good idea!. The angle searching! I can improve the precision of the angle searching. First try angles in increments of 12 (0, 12, 24, ...) then pick the better angle. The trick is that then you go towards the 22 angles next to 12, so in a way you do fulfill precision similar to picking the angles in increments of 1 (In reality this misses a few cases in which the real minimum was well hidden between two multiples of 12 that weren't better than a local minimum). The benefit is that this is faster (needs to check 52 angles in total), but it is more accurate than the previous approaches. So this improves a solution in two ways. Accuracy, and more iterations = better chance to find a good order.

That was in theory. In practice I was not having success making it work. The second phase was giving way wrong results (tons of circles overlapping together). Something was definitely not good with this. Was the theory wrong? Or is there a small bug?

I looked for the bug, but I couldn't find it. I knew that today, I was not going to be able to spend much time in the problem during the morning. It is also not good to do major changes during the last hours because you might end up making a strong mistake that you can't find and fix in time. So that night was probably my last chance to try a significant improvement...

11:00 PM passed, but I still didn't want to give up. Surely one day of not sleeping at 11:00 PM, won't delay my headache recovery much longer than it already is! (And after all, the whole idea to keep a strict sleep schedule seems based on a small study and doesn't seem to have that much success (Or does it? I am noticing some improvement, even though my days with headache have definitely not ended)... Nevertheless, I was still looking for the bug and it was already 12:00 AM...

I kept looking, decided to basically compare the two phases variable by variable until I find a discrepancy. Indeed, some variables weren't working well. I slowly got to the rood of it... It was near 1:00 AM, when I finally saw it, when converting the angle to radians I had int a = angle * PI / 180. I wonder if my readers have noticed the blatant mistake in this.... when I fixed it, and ran tests, it was beautiful. Finally a significant change! It wasn't so significant, per se.. , but enough to climb to 86XXXX score and back to the top 50. It was a symbolic victory, I knew that today, every coder was going to improve and my top 50 was going to be short-lived...

12 and 13-th versions

More tweaks there and there. I tried to think of good ideas. I had little time in the morning, but eventually it occurred me to try a dirty trick. I now use the second iteration to try a new formula for the initial ordering. I was trying this new formula (giving a small advantage to things with small radii) but it was having mixed results- Better results in some cases, worse in others. Why not combine both? I planned this as my last submission, and then went to college. Results were not that bad.

I came back from college earlier than I planned, there were 15 minutes before 12:00 PM, I decided to try another dirty trick! Third iteration tried the simple ordering by m[i]. It seemed to be working fine in local tests, but I didn't have time to finish testing all 500s, so I decided to risk it and submit...

Surprise! Turns out that my 12-th submission was done at 10:15 AM, so I actually had no way to make a new submission before 12:00 PM. That's a bummer. ... wait.. Surprise! The match ends at 13:00 not at 12:00. (what?) so I have a whole hour to try more things. I waited for the local tests for the new dirty trick to end. A small improvement with less variance!. So I decided that I could always do with a new dirty trick. Went to lunch while testing it. Just blatant m[i]/r[i].

I came back around 12:50, the new dirty trick did great in the local tests. When combined, the two tricks would make me improve around 10^4 in points, not bad. So I decided to submit it. ... Surprise! I can't submit because I made a whole submission at 12:35... What? I really didn't remember making that submission. I think I intended it to be an example submission to make sure I don't have any new time outs, but I accidentally made it a full submission. So, only one dirty trick could be used :(.

Preliminary results

Position 57-th, I have to improve 13 positions (not impossible, but unlikely) in the final tests if I want a t-shirt. Ouch.

Did I mention that because I went to sleep at 1:00 AM last night, my headache has gotten very bad today?

But it was a great and fun match. I think I really need to learn Simulated Annealing though.

Read More