KawigiEdit update 2.2.1

So, yesterday I released a new version of KawigiEdit that enables you to temporarily disable some test cases for better debugging.

Today I was using KawigiEdit to finish my code for SRM 586's div1 1000 (Editorial will be ready soon). Being able to disable test cases was very useful, but I discovered a bug with it. I fixed it and since I am apparently a strong believer in release soon, update often. I am making a minor revision. Version 2.2.1.

As usual my KawigiEdit mod has been updated too

KawigiEdit update 2.2.0

It appears that I cannot help myself. I told to myself (Since you are updating KawigiEdit anyway, why not add the stuff you have always wanted it to have?). And there we go...

This update is cool mainly because you can now temporarily disable test cases. This can be very useful during a match when there are 7 cases. One test case is wrong. But debugging the test case is difficult because the other 6 cases cause you trouble. I took this idea from watching Petr's screencast for SRM 550. He uses CHelper, which I am sure is a great plugin, but it is only for Java coders.

KawigiEdit unofficial updates thread: http://apps.topcoder.com/forums/?module=Thread&threadID=794920&start=0&mc=8#1759241

Also the KawigiEdit-pfx mod (The plugin I actually use) has been updated too: http://vexorian.blogspot.com/2013/07/my-topcoder-coding-setup.html

SRM 586 division 2 editorial preview

Another day, another editorial preview. Here are the division 2 editorials for SRM 586: https://apps.topcoder.com/wiki/display/tc/SRM+586
SRM 586 was the first match to include Python support in TopCoder. I really wanted to give it a try as it's concise style can be helpful when writing editorials. The small issue is that their wiki system doesn't support python syntax highlighting. It actually doesn't even have c++ highlighting either, I always use the Java one for c++. The Java one is not so great either, it highlights keywords inside comments.
I decided to solve this by using a new javascript library on top of the wiki system topcoder uses. In the past, I already added mathjax support as I usually need to write formulas. I also already used Modernizr so my SVG images can also have a PNG fallback. The slippery slope continues as I decided to add a syntax highlighter library..
Anyway, here is a preview of one of the explanations for fun:

The hard problem - string weight.

The weight of a string is defined as follows: For each letter present in the string, find L and R, the minimum and maximum positions of the letter. The weight is equal to the sum of all R - L for each of the letters.
Given L `(1 <= L <= 1000)`, count the number of strings of minimal weight of that length.

What makes a minimum-weight string?

Before we get into counting these strings, we should understand their properties.
Like the first two examples show. In cases with small L, there are ways to make letters contribute a flat 0 to the weight. This is the smallest possible contribution. By definition: `(R >= L)` therefore: `(R - L >= 0)`. Since we want to minimize the total weight, we should try to make most if not all letters contribute 0.
It is possible to make all letters cost 0. Simply make all letters in the string unique: "acwh". Then for each letter: `(R = L)`. However, we only have 26 available letters. Therefore, we can only make each letter in the string unique when `(L <= 26)`. In that case, we have to use `L` different letters.
When `(L > 26)`, things will change. Let us begin with the smallest of such cases: `(L = 27)`:

• If all letters were equal, then for this letter, `(R = 26)` and `(L = 0)`. The total weight is 26.
• Perhaps it is better to have as many cost-0 letters as possible? As many letters that appear only once. If we use 25 unique letters, there are two remaining positions that must be used by a repeated letter. We are in a interesting situation: 25 letters contribute exactly 0, regardless of their position and we have two positions used by the same letter. We can pick L and R as the two positions used by this letter. The final weight will be `R-L`, so we want them to be as close as possible, let us make them consecutive , this means that the cost is 1. As long as 25 letters appear exactly once and the remaining letter appears twice but in consecutive positions. The minimum string weight is 1.

But how about larger cases? For L = 40. We can try the same logic, make 25 letters appear exactly once and a final letter appear exactly 15 times. The positions of the 25 letters do not matter, so we only care about L and R for the letter that appears 15 times. We should make the difference `(R - L)` as small as possible. Once again, it is most convenient to make the 15 letters appear consecutively. As long as we do this, the result will be: 14. If L is the first position, then the 15 positions of the letter will be: `(L, L+1, L+2, ... , L+13, R = L+14)`.
But we should be critical, although this strategy seems to minimize the total weight, is it the only strategy that manages to do it? In the previous idea, we had 25 letters that appear exactly once and one letter that appears 15 times. However, what about a small change? What about having 24 letters that appear once, 1 letter that appears twice and one letter that appears 14 times? The sum is still 40. Once again, we can ignore the positions of the 24 letters (0 weight). The positions of the other letters are also not important as long as the repetitions are consecutive. If we make sure they are consecutive, the cost of the letter that appears twice will be 1: `(L, R = L+1)`. For the other letter, the cost is 13: `(L, L+1, L+2, ..., L+12, R = L+13)`. The total weight is interestingly, 14: 13 + 1. This is also the weight we assumed to be minimum!
It seems that making sure 25 letters appear exactly once is not necessary to minimize the weight. However, making sure that repetitions are always consecutive still seems important. Let us put some detail.
Assume that the only thing we know about a sequence is that it has 26 different letters and repetitions are always consecutive. Let us calculate the weight of the string. Let us say the first letter appears `K_1` times, then it will fill positions `(0, 1, ... , K_1-2, K_1 - 1)`. It will contribute `(K_1 - 1)` to the weight. The second letter appears `K_2` times: `(K_1, K_1+1, ... , K_1 + K_2 - 2 , K_1 + K_2 - 1)` and therefore contributes `(K_2 - 1)` to the weight. And so and so. The total weight will be: `(K_1 - 1) + (K_2 - 1) + ... + (K_26 - 1)`. The total amount of letters is `L` , therefore: `(K_1 + K_2 + ... + K_26 = L)`. If we tweak things, you can find that the total weight will be: `(L - 26)`. This formula does not depend on the actual number of times each letter appears in the string. And it seems to be the minimum. This also shows that not using all 26 available letters will only yield a higher weight. E.g: if we use only 20 of the available letters the weight will be: `(L - 20)`.
In order to show that this is the minimum, let us prove that not keeping the repetitions consecutive will always yield a larger weight. If we wish to place `K` letters `a` in the string, making them consecutive will make it contribute `(K-1)` to the weight. If they are not consecutive, then there is at least one other letter `b` that will be between the two extremes of the letter in question. This will increase the weight contributed by letter `a`. The weight contributed by letter `b` will either stay equal (if all its instances are consecutive and between the `a` letters) or also worsen. This means that keeping all repetitions consecutive will yield the minimum weight. That this weight is `(L - 26)` and that any other strategy will increase the weight.

How to count the minimum-weight strings

Simple case

If `(L <= 26)`, then each letter in the string must be unique. So what is the cost of making a string of `L` unique letters, where there are 26 available letters in the alphabet? For the first position, we have 26 options. The second position has 25 options (we cannot use the same letter as the first position). Third position has 24 options and so and so. Therefore, the number of strings is:
`26 * 25 * 24 * ... * (26 - L + 1)`

L > 26

In this case, we need to count the number of strings that follow some properties:

• Each letter in the alphabet (26 options) must appear at least once in the string.
• All the repetitions in the string must be consecutive.

How can we count the number of strings?

Dynamic programming

Let us define `f(a, L)` as the number of ways to build a string of length `L` that follows those properties using an alphabet of `a` different letters.
A base case: `(L = 0)`, all the `a` letters must be inserted at least once. If `(a > 0)`, then there is a letter in the alphabet that we cannot use, because there are 0 spaces left, the result is 0. If `(a = 0)`, then there are no more letters to include and no spaces, the total numbers to do it is 1.
In another case, `(L > 0)` and `(a = 1)`, there is only one letter available, we better fill all the `L` positions with it. There is only one way to do this.
When `(L > 0)` and `(a > 1)` , then we have `a` choices for the letter to use in the first positions of the string. The number of those positions can be any `i` : `(1 <= i <= L)`. After using this letter in the first `i` positions, we still need to fill the remaining positions. There are `L-i` remaining positions and we cannot use the letter that we already used. So the partial result is: `a * f(a - 1, L - i)`. We should add together the results for each i, so:
`f(a > 1, L > 0) = sum_(i = 1)^(i <= L)( a * f(a - 1, L - i) )`
There are 27 possible values for `a` and `O(L)` values for `L`. Each time we call the function, we might need `O(L)` steps to perform the sum. If we use dynamic programming or simple memoization to ensure that each argument combination for the function is evaluated at most once, then the algorithmic complexity will be: `O(A * L * L)` where `A` is the size of the alphabet, 26 in this case. This complexity is low enough for the time limit.

static const int MOD = 1000000009;

long dp[27][1001];
long onceConsecutive(int a, int L)
{
    long & res = dp[a][L];
    if (res == -1) {
        if (L == 0) {      // base case
            res = (a == 0);
        } else if (a == 1) {
            res = 1;
        } else {
            // calculate the sum. (We need to use modular arithmetic)
            res = 0;
            for (int i=1; i<=L; i++) {
                res += (a * onceConsecutive(a-1, L-i) ) % MOD;
            }
            res %= MOD;
        }
    } 
    return res;
}

int countMinimums(int L)
{
    memset(dp, -1, sizeof(dp));
    long res = 1;
    if ( L <= 26 ) {
        // The simple case:
        //26 * 25 * 24 * ...
        for (int i=0; i < L; i++) {
            res = (res * (26 - i)) % MOD;
        }
    } else {
        // each letter must appear at least once, all instances
        // of each letter must be consecutive.
        res = onceConsecutive(26, L); //Use the recurrence relation
    }

    return res;
}

Math

An alternative solution. We will separate the decision in two parts: a) The order in which the 26 letters are used and b) The number of positions each letter (In the order picked by a) ) will take in the string.
The order of letters is a permutation. The total number of ways to pick the order is: `26!`. Where `n!` is notation for the factorial of `n`.
Now that the order of the letters is picked, we decide the number of positions each letter will take. The total number of positions is `L` . How many solutions are there to the equation: `(K_1 + K_2 + ... K_25 + K_26 = L)` where each `K_i > 0`.
As you will see later, that question is easier to solve when `K_i >= 0`. We can do the conversion though Let `r_i = K_i - 1`, each `r_i` is the additional number of times the letter is picked.

`K_1 + K_2 + ... + K_25 + K_26 = L`
`r_1 + 1 + r_2 + 1 ... + r_25 + 1 + r_26 + 1 = L`
`r_1 + r_2 + ... + r_25 + r_26 = L - 26`

Since each `r_i` can be 0, we can use the following trick: We have to place `(L - 26)` stones in 26 boxes. We are able to leave some boxes empty. We can picture this as placing separators between some of the stones. For example:

oooo|ooo|oo||oo|o

Is the same as placing 4 stones in the first box, 3 stones in the second, 2 stones in the third, 0 stones in the fourth, 2 stones in the fifth box and 1 stone in the sixth box.
For 26 boxes, there will be 25 separators. How many ways to combine the separators and stones exist? There are `(25 + L - 26)` positions of which we pick 25 for the separators. The value is: `C(L - 1, 25)`, where `C()` is the binomial coefficient
.
The final result is therefore: `26! * C(L - 1, 25)`.

# define function f() as the factorial:
from math import factorial as f

def C(n, k):
    return f(n) / f(k) / f(n - k)
    
#Calculates weight without the modulo
def Weight(L):
    if L <= 26:
        # 26 * 25 * 24 * ... 
        # the same as saying 26!  / ( (26 - L)! )
        return f(26) / f(26 - L)
    else:
        # 26! * C(L-1, 25)
        return f(26) * C(L - 1, 25)

class StringWeightDiv2:
    def countMinimums(self, L):
        return Weight(L) % 1000000009 # Takes the remainder from the result

New version of KawigiEdit-pf

I was having some fun writing SRM 586's editorial. Since I am now allowed to use python code I was giving it a try. Could make some very short looking stuff. However, I eventually noticed that my code for div2 250 was not actually working in TopCoder's servers - Giving a runtime error about tuples not having the remove attribute. They were working fine locally. My first reaction was to assume that TopCoder's python version was old. So I tried to instal python 2.6 instead of my local 2.7... Still the same error.

Eventually I figured, ffao's python implementation was making KawigiEdit generate "array" function arguments as lists [a,b,c,d] . But TopCoder's server sends them as tuples (a,b,c,d). So I had to make a new release for KawigiEdit-pf.

KawigiEdit-pf forum thread.

Of course, in reality I first updated my KawigiEdit mod. The KawigiEdit-pfx version in that post has been updated too.

SRM 585 Editorial for EnclosingTriangle

The editorial for SRM 585 is complete: http://apps.topcoder.com/wiki/display/tc/SRM+585#EnclosingTriangle

I really wanted a faster release this time, but I couldn't receive the explanation on how to solve this problem until late in the week. I think it is my fault, because I think I could have done it if I didn't wait for it. I should stop limiting myself like that.

I finished the algorithm. I thought it was a cute `O(m)` algorithm, and it seemed like a good idea to explain. I definitely don't understand how to use segment trees (I have no idea how to use them in general, or how they work). And I can't decipher tourist's solution. So this was the best I had... But while writing this I figured that this is a very confusing solution. Although I think it is simple, it is very hard to explain.

SRM 586 : Meh

Another bad day.

Div1 500 : Something with dynasties

Not sure what to do. I reduced it to finding out if there is a solution to a system of inequalities, where the variables are the (real) starting year of each nation's calendar. I had issues even implementing a stub code. I couldn't debug them because my valgrind was suddenly not providing line numbers. The other day, before releasing my test setup I actually tweaked my c++ build file a bit, I may have done something that gives valgrind line number amnesia. I actually spent most of the last 10 minutes (before the 10 minute mark) trying to fix this. Not like I had an actual idea of how to solve this problem.

Div1 250: The one with a function.

You are given an array `Y = { Y_0, Y_1, ... Y_(n-1) }`, the array talks about a real function `f()` with domain `[Y_0, Y(n-1)]`. For each `(i < n - 1)`, the function contains line segment between points `(i,Y_i)` and `(i+1, Y_(i+1))`.

Find an equation `y = "something"` that intersects the largest number of times with this function. And return that number of times. Of course, if a horizontal segment exists in `f()` there exists a `y` that will have infinitely many intersections, in that case return -1.

This was a good problem and I felt confident to solve it under 10 minutes. However, I had a bug (didn't notice an issue with code) which delayed me a bit past the end of the coding phase. According to KawigiEdit, I would have scored ~209 points in this problem if I opened it first. Too slow. Then it turns out that my idea was wrong anyway. So I don't think things changed much by my strategy. If I was having a good day, I *may* have found the challenge case , and maybe attempted to challenge. Who knows? I am still preferring to use my new strategy, whilst 250 is tricky, I learned a bit more by trying to solve div1 500 than by solving yet another tricky 250.

Anyway, the solution was to notice that most of the times we only need to try values from `Y[]` as the position of the horizontal line that crosses f(). This is because any intermediary point in a segment will intersect an equal or lesser number of times than the segment's extremes. So just count, for each `Y[i]`, the number of times it intersects with segments in the function

So does `y` intersect with a segment that goes from `Y[i-1]` to `Y[i]`?, if `y` lies in interval `[Y[i-1], Y[i] ]`, the answer is yes. However, the mistake I made was that I was counting some intersections twice. The same point `(x,y)` may be shared by two segments, and you only need to count once. What I did to fix this small issue was to make sure that `y` is not equal to `Y[i-1]` before counting that intersection.

However, there is a catch and it is that there are exceptions to the rule. Imagine `Y = {0, 5, 0, 5}`, in this case, neither 0 or 5 are optimal locations. 2.5 is better (3 intersections). What is up with that?

It turns out that, besides of the segment's extremes, you need to take a point (any point) between any two extremes of a segment. You only need to check once per pair of segment extremes. In fact, you can just check for every segment extreme +- 0.5 and it will suffice. +- 0.5 can be implemented easily by scaling all values by 2 so you just have to try +- 1. I hope to have a formal proof by the time the editorial is released.

int maximumSolutions(vector <int> Y)
{
    // If there is a horizontal segment, return -1:
    for (int i=1; i<Y.size(); i++) {
        if (Y[i] == Y[i-1]) {
            return -1;
        }
    }
    // Scale up all values by 2:
    for (int i=0; i<Y.size(); i++) {
        Y[i] *= 2;
    }
    int mx = 0;
    // for each y such that abs(y - Y[i]) <= 1:
    for (int i=0; i<Y.size(); i++) {
        for (int y = Y[i] - 1; y <= Y[i] + 1; y++) {
            //count the number of intersections:
            int c = (Y[0] == y);
            for (int j=1; j<Y.size(); j++) {
                if (Y[j] > Y[j-1]) {
                    c += ( (Y[j-1] < y) && (y <= Y[j]) );
                } else {
                    c += ( Y[j] <= y && y < Y[j-1] );
                }
            }
            mx = std::max(mx, c);
        }
    }
    return mx;
}

Comments, etc

Ok match, div1 500 had a too complex statement. Div1 250 was good. I am very disappointed by the low amount of python submissions. Hopefully it is because the python coders are still not aware of the news that it can be used.

My TopCoder coding setup (update 4)

Update (Aug 6-th, 2013): New KawigiEdit-pf version. Now 2.3.0. Synced KawigiEdit-pfx with it. Some tweaks.

Update: Updated KawigiEdit-pfx to version 2.1.9.1 (Incorporates changes from normal KawigiEdit. Also it renames the Outside mode window so that it begins with the word "Outside ", updated gnometerm.sh accordingly.

Around a year ago, I had a big , big, enormous problem. I was supposed to be writing blogs for the TopCoder Open, and I had absolutely no idea what to talk about (Speaking of which, whatever happened to this year's TCO blogs?) . So I improvised. I decided to rush a post about arena setups. It is not easy to bring everything to work in the optimal way for you. Back then someone asked if I would release my modified version of KawigiEdit. Although I said I was going to release it, it took me this long to do it.

Why I modified KawigiEdit

KawigiEdit is a great Arena plugin, and everyone just starting in Topcoder should begin with this one. That's the reason I chose it. However, there were some issues with it. Back when I was starting to use TopCoder plugins, the version of KawigiEdit was not very updated and there was an issue with problem method signatures that returned double, TopCoder rules admit an absolute or relative error of up to 1e-9. The old KawigiEdit, however, compared doubles without taking care of this. So whenever you tried to solve one of those problems in KawigiEdit, it was likely that you would have KE tell you the results are wrong, even though they are not - they are really within the accepted range. With Kawigi not around to update the plugin, I had no choice but to add the comparison stuff myself.

Eventually, this issue got fixed by pivanof, but I started slipping downwards the slippery slope of editing KawigiEdit. Overtime things got crazy. It all started when I wanted to add separator lines between the output of example cases. I use print statements to debug issues with my problems and when a test case gets full of output, it is hard to find the test case in the normal KawigiEdit output format.

I added these big lines =========================== to the output. But I had a new problem. The lines were good at separating example cases because they were very visible. Perhaps too visible. They were starting to distract me. I needed these lines to of a color that didn't contrast as much as the background. But adding color to the KawigiEdit output was looking very problematic.

It occurred me that I could use ANS color codes in the kawigi edit output . But then I would have to make the output appear in a terminal window instead of KawigiEdit's output tab... I had mixed feelings, but then I noticed "If I make output appear in terminal, I will also have the benefit of being able to read output and my code at the same time!" unlike the usual KawigiEdit experience... Then I noticed another good benefit. Closing the terminal window would forcefully kill the tester program. Killing programs was something that KawigiEdit was having issues with until a recent update.

The problem was how to move the output to a terminal window...

The gnometerm script

It was not easy to do it. But with the help of a lot of tweaking and a program called wmctrl. I was able to make a program that would run any command inside a terminal window. There were many requirements. The terminal window will be always on top, so that you can type on a larger window without it going missing. After the command finishes execution, the terminal shouldn't close. The active window should still be the coding window. Also, we don't want terminal windows to pile up, it is best if the program closes the previous one. But only this kind of terminal windows... you wouldn't want other terminal windows to go away...

This program is adapted to work with gnome-terminal, the default terminal application in Ubuntu. I am not sure how possible or not it is to make it work in other terminal applications.

#!/bin/bash

# Run command in terminal window
# (c) Victor Hugo Soliz Kuncar under the Zlib/libpng license

# Terminal geometry. Read gnome-terminal manual for more info
# Basically, this is what makes sure the terminal spawns at the left side of the
# screen
GEOMETRY="--geometry=75x50-0-100"
# Terminal profile, I have a profile called KE
PROFILE="--window-with-profile=KE"
# you can leave both options empty...

TITLE='** TopCoder **'
# The window title for the terminal window. It is *not* merely aesthetic.
# It should be something unique that you are sure won't be shared by a window
# you don't want to be closed automatically whenever this command is called

#===============================================================================
if [ "$1" = "_act" ]; then
    wmctrl -r "$TITLE" -b add,above
    # == Activate window command: ==
    
    # The idea is to activate the code window after the terminal window is created
    # so that you can still code on it even after the output terminal appears.
    
    # If the editor is undocked, the code window is called Outside KawigiEdit...:
    wmctrl -a 'Outside KawigiEdit'
    # Else it will be the normal competition arena window:
    if [ $? = 1 ]; then
        wmctrl -a 'TopCoder Competition Arena - Coding Phase'
    fi

    # why twice? Because once seems to fail 1/20 of the times...
    sleep 0.1
    wmctrl -r "$TITLE" -b add,above
    exit 0
fi

if [ "$1" = "_monitor" ]; then
    # == Monitor command: ==
    # In this mode,
    #   - Call the activate command as another process so that there are no
    #     delays before calling the compiler.
    #
    $0 _act &
    #   - Run the command (provided to ./gnometerm as arguments)
    ${@:2}
    # ${@:2} means "all arguments except first one"
    read aok
    # read aox makes the bash program wait until someone presses enter.
    exit 0
fi

# With a tool called wmctrl, close the window with title 'Topcoder Test cases!' so that 
# only one of those windows exists at once:
wmctrl -c "$TITLE"

# Run the terminal: The terminal will run this script in monitor mode...
gnome-terminal $GEOMETRY $PROFILE --title="$TITLE" -x $0 _monitor $@ 2> /dev/null & disown
# 2> /dev/null is just so output doesn't go to KawigiEdit's tab...
# & disown so that killing this script doesn't kill ther terminal.
exit 0;

Modded KawigiEdit

Anyway, by using this gnometerm.sh script and placing it in KawigiEdit's work folder (and setting it as executable). I am able to put things like ./gnometerm.sh python $PROBLEM$.py instead of just python $PROBLEM$.py and the execution will appear in the terminal. There are various issues with vanilla KawigiEdit and this approach.

It is convenient to have both compile messages and output appear in the terminal window. A bit of a problem is that KawigiEdit will automatically switch to the compile and output tabs whenever you run tests.

I had to change that. In fact, I removed the output tab altogether. I would remove Compile, but some of the least used languages still use it. Instead, the compile tab is only switched to automatically when there were "compile errors". Errors in the compile command. For my Java, c++ and Python setup, I use a single command to compile and run (I do not use the compile option in KawigiEdit and instead place an "echo" in the field ). The commands do various things. Specially my c++ command is not content with just compiling the program and running it. It also runs it in valgrind... and recolors the compiler messages :)

Anyway, the important thing is that I have a KawigiEdit mod. It has various "features" / things done different to the KawigiEdit I released before:

• The test case output is very different. Besides of the ======== separators I mentioned, green and red ANSI color codes are used. Also, it has less clutter as it doesn't show your answer to a test case unless it was wrong. It also uses simply +, x and T (all colored) to say if a test case is correct, wrong or failed the time out. Because of the ANSI color codes, you need to use a trick similar to the gnometerm script to run the commands if you want to use this KawigiEdit mod.
• The languages tab in settings is split in tabs, instead of having all settings in a single tab.
• When you click the run tests button, the "Compile" tab will not be automatically selected. Unless the compile command you assigned has an exit code different to 0.
• There is no output tab. If the run command you use has any console output, it will be added to the compile tab.
• Instead of inserting "Powered by ... !" in your code it inserts a message that just says the editor version.
• It doesn't say "you are a stud!" anymore. It says "Seems Ok (... Is It?)". I was never a fan of the stud thing.
• The version is KawigiEdit-pfx 2.1.9. p stands for pavinof, f for ffao and x because it is my mod :).
• Obviously , it supports python, just like KawigiEdit-pf.
• So I would guess it is Linux-specific? Even gnome-specific

So if you are still interested, here is the jar: It has source code too: http://dl.dropboxusercontent.com/u/95690732/KawigiEdit/pfx/2.3.0/KawigiEdit.jar

Run script examples

Like I mentioned, I compile and run in a single command (which is called by gnometerm.sh). Here are some mild examples:

./gnometerm.sh python $PROBLEM$.py. It is easy for python :)

The following script works for Java, and adds a memory limit (Pass in class name as argument, if the script is called runjava.sh call it like: ./gnometerm.sh ./runjava.sh $PROBLEM$):

#!/bin/bash
echo "compiling..."
javac $1.java
if [ $? = 0 ];
then
    java -Xmx64m $1
fi

In which I tweak KawigiEdit

I made an unofficial KawigiEdit release. It is all about python support.

Participating in TopCoder without a plugin that would generate a tester (with appropriate problem method signatures) Can get very tedious. Although the admins have finally added python support, it needs plugin support as well if we want it to work*

I want python to be popular in TopCoder, for many reasons. The main one being that it is a free language without attachment to unreliable corporations like Oracle or Microsoft. It is a very open language. It is also dynamic, something that is novel in TC. I know too that python is usually among the third most popular languages in the google code jam. I like the idea of being able to use python in editorials, it should be fun depending on the problem. There are people who claim python is a good beginner language. To be honest I don't think so. I think that the worst thing that could happen to a beginner is to deal with more run-time errors than compiler errors. But because of how the claim that python is good for beginners motivates people to talk to beginners about python, there ARE a lot of programmers that know python much better than C++.

The next Saturday will be the first TopCoder SRM that will officially support python. (SRM 585 was supposed to be it, but there were issues). Ever since the new compilers were announced I was trying very hard to make python work in KawigiEdit. For context, Kawigi was a very notable member and problem setter of the TopCoder community back aeons ago when I first joined. He made KawigiEdit which is probably the best plugin for those who are starting up in the arena. It supports all the TopCoder SRM languages, and it is very configurable. Although I think more advanced coders probably want something that uses an external editor. I knew for a while that Kawigi designed the plugin very well and flexible, so I was trying to implement python support. And failing. It was not until ffao made his own release that I finally discovered what I was missing.

The crux of the matter is that ffao's changes needed a bit of minor tweaks and I made them. Updated KawigiEdit.jar. There is more information in the forum thread.

I did my best to test that the python support is working in various problems. (Things like double return values, arrays of double, string comparisons). And it seems to work fine. But I don't take responsibility for any issues you might find during a match. Sorry:).

It is amazing how little (relatively speaking) work we needed to make KawigiEdit able to use python. Kawigi is a great software designer even in such a minor project as KawigiEdit. It is no surprise that you would later hear of him working for a couple of tech giants...

Am I going to maintain KawigiEdit now? The answer is no officially. I have not asked permission to pivanof yet to make new releases and those things. I also think that for the most part (except for the python support) KawigiEdit is not lacking in features and is working Ok. So there is no rush to pick a new mantainer. There is also the small issue that I actually use a KawigiEdit mod (which I will be releasing in a later blog post), so I don't really use the upstream version of the plugin. I think it is better to leave the possibility of someone else with more time and interest in improving the plugin to become the mantainer.

* In reality, it seems that the performance difference between python (at least the version in TC's servers) and Java is too grand and it may be impossible to make a passing submission in certain problems.

"Topcoder Arena doesn't work in openJDK 7"

Trying to run the TopCoder arena in Ubuntu? It seems there are issues when not using that piece of evil nastyness called Oracle's Java. Do not fear! We do not need that trash to run the TopCoder arena. OpenJDK 7 is good enough to run the arena.

What doesn't work is the packaged version of the iced tea plugin in Ubuntu. For somre reason, it expects only OpenJDK 6 to exist. So even you have openJDK 7 installed, IcedTea will run openJDK 6 (Even if it is not installed!).

The trick is simply to modify the javaws script. Yep, it turns out it is just a script.

You need:

• OpenJDK 7
• IcedTea plugin
• Unless you really, really need it, you should really get rid of Java 6, it is not only old, it is insecure and will interfere with your attempts to make sure to use Java 7.

sudo nano /usr/bin/javaws

The beginning of that file says this:

#!/bin/bash

JAVA=/usr/lib/jvm/java-6-openjdk-amd64/jre/bin/java
LAUNCHER_BOOTCLASSPATH="-Xbootclasspath/a:/usr/share/icedtea-web/netx.jar"
LAUNCHER_FLAGS=-Xms8m
CLASSNAME=net.sourceforge.jnlp.runtime.Boot
BINARY_LOCATION=/usr/bin/javaws

Just change it to :

#!/bin/bash

JAVA=/usr/lib/jvm/java-7-openjdk-amd64/jre/bin/java
LAUNCHER_BOOTCLASSPATH="-Xbootclasspath/a:/usr/share/icedtea-web/netx.jar"
LAUNCHER_FLAGS=-Xms8m
CLASSNAME=net.sourceforge.jnlp.runtime.Boot
BINARY_LOCATION=/usr/bin/javaws

The good news is that this works. The bad news is that you need to edit the javaws script every single time icedtea plugin is updated by the update-manager.

SRM 585 Recap and Editorial preview

I know that I haven't been making updates to this blog lately. But I bring news. The good news is I have finished the editorial for the easy problems in this editorial. The bad news is that I am still clueless about the geometrilicious div1 hard. So it might take a while.

The link to the complete preliminary editorial is at : http://apps.topcoder.com/wiki/display/tc/SRM+585 meanwhile, I will write about my experience in this match and also show the div1 500 explanation:

The match

I had some bad luck in this match , I think I could have done much better in different circumstances.

I opened div1 medium. A LISNumber of a sequence is the minimum number of increasing sequences that need to be concatenated to make the sequence. You have `"cardsnum"[i]` cards with number `i` written on them, what is the number of ways to make sequences out of these cards such that they have a LISNumber equal to `K` ? `(K <= 1296)` and the number of card types and the number of cards of each card are at most 36.

I felt I should be able to solve the problem, it looked like a dynamic programming one that needs you to be clever to make it run in time. So I gave it a try. I was able to come up with the reduction to represent the state as just the number of card types left to place and the number of new sequences you need to start in addition to the ones already placed. Taking care of the duplicates was very hard. I was first trying to do it using two dynamic programming problems, one nested inside the other. When I noticed that the nested problem required too much memory, I was able to come up with an alternative that didn't take as much memory : 3 dynamic programming problems in total, 2 nested inside the other!

While coding that mess, I noticed that the timer was approaching the 10 minute mark. I am supposed to open the division 1 easy problem at that time. But I was so close to debug my approach and I was so sure it was going to work that I decided to stay with 500. A couple of minutes later, I finished the code and it was giving correct results... Except for a case, that had segmentation fault! . For some reason (I think it might be case 2) which has {36, ... 36,...,36}, 36 as input), I thought that K was going to be at most 36, but it is in fact at most 36^2. The approach with nested dynamic programmings would work with `K <= 36` , but 1296 was too much. By the time I figured, it was too late to try to come up with a faster solution, my last chance was the easy problem.

The easy problem was easy, but I only had 4 minutes to solve it. It actually seemed like I was able to solve it. I guessed a solution formula (that turned out to be wrong) and I coded it. I finished it, but when the time I noticed it was wrong, it was too late). Scored a flat 0.00 in this match.

The editorial preview

First, It is good to see interpret the LISNumber as 1 + (Number of times an element in the sequence is less than or equal to the previous element).

Ignore the repetitions

It is useful to first ignore that there are going to be multiple cards with the same number and just solve the variation of the problem in which each card is unique, no repetitions. We want to count the number of sequences of n distinct elements such that the number of times an element is strictly less than the previous one is K - 1. We will call these positions the start of an additional sequence.

It is convenient to have an order when deciding the positions of the cards. Let us try decreasing order. For example, a card [3] when n is 7, so cards [4],[5] and [6] were already placed. If, for example, the current sequence of cards was {4,6,5}. There is already one position in which a new sequence starts: From 6 to 5. We have some choices:

• Since all the cards are already larger, then placing card [3] at the beginning of the sequence: {3,4,6,5} will not change the number of sequences.
• Placing [3] after 4 or 5, will increase the number of increasing sequences: {4, *3, 6,5}.
• Placing [3] after 6, will not increase the number of increasing sequences: {4,6, 3,5}. This is a interesting case, because `(6 >= 5)`, there is already a separation, this is already the beginning of a new increasing sequence. All the elements are greater than [3], so we are guaranteed that placing [3] at the beginning of a sequence will not increase the number of sequences.

For the most part, when all the placed cards are already greater than the card you are placing, then positions you pick for the card will increase the number of sequences unless the position is already the beginning of an increasing sequence. Let us try to define a state for the current problem. Let us say that we need to count the number of ways to add the t remaining cards (0, 1, 2, ... , t-1) after (n-t) cards (t, t+1, ... n-1) were already placed , such that we create k additional decreasing positions. In other words, (K - 1 - k) positions are already decreasing (A position of a number that is strictly smaller than the previous number) . The function f(k, t) will return the total number of ways to do the objective.

• As a base case, when t=0, there are no cards left to place, If k is 0 then we don't need to create any additional decreasing position, so the result is 1. If k is not 0, then we cannot create the needed decreasing positions, there are zero ways to do it.
• Otherwise, we have (n - t) cards, of them (K - 1 - k) are already decreasing positions.
  • There are `(K - k - 1 + 1 = K - k)` positions that won't change the number of sequences (The beginning of the main sequence and the beginning of the additional ones). After picking one of these positions and placing card (t-1) there will be (t-1) cards left and k will not change. There are `(K - k) * f(k, t - 1)` different ways to complete the objective making this choice.
  • There are `(n - t + 1 - K - k)` remaining positions in which placing card (t - 1) will increase the number of sequences: `(n - t + 1 - K - k) * f(k - 1, t - 1)`.
  • The addition of those two results is the total number of ways, the result for `f(k , t)`.
• Finally, the overall result for the main problem is `f(n, K-1)`. There are n cards and we need (K-1) starting positions for new sequences.

This recurrence relation can be calculated efficiently by using memoization or iterative dynamic programming. The complexity is `O(n * K)`.

Repetitions

The real version of the problem has up to 36 repetitions of each card type. There are n card types and cardsnum[i] cards of type i.

What will complicate the problem is that, if you place two consecutive equal cards like 3,3, you create a new sequence. Since they are equal we need to be careful about counting different each setup only once.

Otherwise, the problem is similar in that you can still tell about the available positions that increase or not the number of sequences by just t and k (Where t is the number of card types whose positions were not assigned yet). Formally, let us solve `f(k, t)`, the total number of ways to place the cards of types `(0,1,...t-1)` if cards of types `(t,t+1,...,n-1)` are already placed and `(K-1-k)` of the already-placed cards are the beginning of a new increasing sequence.

• The base case is identical. when t=0, there are no cards left to place, k must be 0.
• There are `(K-k)` positions such that we can place a card of type (t-1) without changing the number of sequences. For convenience, we will call this number slotsUp.
• There are `S + 1 - (K - k)` positions in which we can place a type (t-1) card and create a new starting position for a sequence. We will call this number slotsDown.

Of the `(s = "cardsnum"[t-1])` cards of type t-1, some will be placed next to the slotsUp positions that don't change the number of sequences. Others will be placed next to the slotsDown positions that do. The remaining cards must be placed next to cards of the same type. Let us name these numbers up, down and (s - up - down), respectively. There are `O(s^2)` triples `("up","down", s-"up"-"down")`. There are `O(n * K)` different argument combinations for function `f()`. With `(n, s <= 36)` and `(K <= 1296)`, these constraints are actually small enough to allow us to simply try all possible values of `("up","down", s-"up"-"down")`. Let us do it. For fixed values of down and up:

• There are `C( "slotsUp", "up")` ways to pick the up positions. Where C is the binomial coefficient
• There are `C( "slotsDown", "down")` ways to pick the down positions.
• Let `"eq" = s - "up" - "down"`, we would like to distribute eq extra cards and place them next to other cards of type (t-1). There are initially (up + down) cards placed. The sub-problem involves assigning a certain number of additional cards to go in each of the (up + down) cards. We split the eq set in (up + down) partitions, how many ways are there to do it? I will leave it as an exercise because it is a common riddle, but the value is `C("up" + "down" + "eq" - 1, "eq")`.
• down and eq positions will become the start of a new increasing sequence. k will be reduced accordingly. t will also be reduced because we processed all the cards of type t-1.
• In short, for fixed `("up","down", "eq")`, the number of ways is:
  `C( "slotsUp", "up") * C( "slotsDown", "down") * C("up" + "down" + "eq" - 1, "eq")` `* f(k - "down" - "eq", t-1) `
  

Wit the help of Pascal's triangle we can pre-calculate all the needed binomials in `O(n^2*s^2)` time ( slotsDown can be as large as the number of cards above t-1). There are `O(n*K)` ways to call the function, in which we do `O(s^2)` iterations. For a total complexity of `O(n*K*s^2)`. For the given constraints it will be fast enough.

Code

{html}{code}
static const int MOD = 1000000007;
long C[1298][1298];

int count(vector <int> cardsnum, int K)
{

    //We would like there to be (K-1) elements i such that:
    // v[i] <= v[i-1].
    int n = cardsnum.size();

    //total number of cards (at most 36^2) :
    int S = accumulate(cardsnum.begin(), cardsnum.end() , 0);
    
    // Precalculate binomials using Pascal's triangle:
    memset(C, 0, sizeof(C));
    for (int i=0; i<=S+1; i++) {
        C[i][0] = 1;
        for (int j=1; j<=i; j++) {
            C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
        }
    }

    long dp[K][n+1]; //The size is at most ~ 36^3 
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;        
    for (int t=1; t<=n; t++) { // O(n)
        //S = total number of cards greater than t-1:
        S -= cardsnum[t-1];
        
        for (int k=0; k<=K-1; k++) { //O(n*K)
            int s = cardsnum[t-1];
            int slotsUp = (K - k);
            int slotsDown = S + 1 - (K  - k);
            
            dp[k][t] = 0;

            // Fix (up, down, eq):
            for (int up = 0; (up <= s) && (up <= slotsUp); up++) {  //O(n*K*s) 
                for (int down=0; (down + up <= s) && (down <= slotsDown); down++) {
                    //O(n*K*s*s) : 36^5
                    
                    int eq = s - up - down;
                    
                    // ways to pick up , down:
                    long a = C[slotsUp][up];
                    long b = C[slotsDown][down];
                    long res = (a * b) % MOD;
                    
                    // The lower cards, continue the recurrence:
                    if (nk >= 0) {
                        res = (res * dp[k - down - eq][t-1]) % MOD;
                    } else {
                        res = 0;
                    }

                    if (eq > 0) {
                        //repeated cards
                        res = (res * C[eq + up + down - 1][eq] ) % MOD;
                    }
                    dp[k][t] += res;
                }
            }
            dp[k][t] %= MOD;
        }
    }
    
    return dp[K-1][n];
}