Monday, September 30, 2013

SRM 592 Editorial and comments about the match

The editorial is up: http://apps.topcoder.com/wiki/display/tc/SRM+592 and I have some things to say.

The delay

Lately I have been trying really, really hard, to get editorials ready within 48 hours after their match. This time I had to break my successful streak though :(. You see, When the match ended, I wrote my recap , then I caught a tweet from rng_58:

Yep, even though it is in Japanese, it was pretty clear what was going to soon happen to me, as the editorial writer. I have never gotten the chance to learn FFT correctly. Although I tried to figure the theory out, it is a bit confusing. It did take me around a month to actually understand max flow.

Yesterday, I was already past the 48 hours deadline and I really didn't want to, once again, have an editorial take one week of my life, plus I really hate the delays. When an editorial is published too late after a match, most people are no longer interested in the match...

Lately I've been learning that it is sometimes better to admit limitations and delegate. It's not the end of the world if I don't write all the explanations, and knowing my limitations is good. If I really did the thing in which I spend a week working on this editorial, then I would have to delay the next editorial too because of being tired. So I asked Rustyoldman to write this explanation and split the payments. Yay

What is up with division 2 problem sets lately?

I am not sure what's going on, but it seems to me that division 2 problem sets are getting harder. This match's div2 easy requires a proof and the div2 1000 was incredibly complicated, imho. It is an "easy" dynamic programming problem in which you can easily see that it reduces to dynamic programming. But the time and memory optimizations took me a serious while to get to work correctly. This is the second div2 hard in a row that feels out of place and, to me, closer to div1 medium.

The nice evilness in div1 medium

I mentioned in the recap that I tried to come up with a way to split this problem in sub-problems during the match. Well, that was not all the story. The first thing I did when trying to solve this problem during the match was to reduce it to generating a single permutation instead of a pair of permutations (this is the trick to solve the division 2 version quickly). During all the match I was trying to solve this modified version of the problem, and it seemed very complicated to find a polynomial time algorithm.

Then I read ffao's explanation in the forums. It suddenly felt too easy. As long as you don't make the reduction to a single permutation, it is actually easier to come up with a polynomial time algorithm. This is quite a special problem and something to keep in mind. It appears that changing the problem to generating a single permutation instead of two would simplify it, but that't not always true. There is a reason why reducing a problem A to a problem B is said to mean that problem A is as easy or easier than problem B and not vice versa. It is possible that the original problem A is actually easier than the reduction.

The match

I have no complaints about division 1, I actually loved it. The easy problem was fairly easy, but not in anyway uninteresting. Medium was cool, as I mentioned. The hard problem seems to have been enjoyed by the likes of Petr.

I would have done Division 2 much differently though. I think division 1 easy was a good problem for division 2 medium. Like I mentioned before, it is a good thing to share problems between the divisions. And next_permutation problems are not as interesting as the ad hoc div1 easy, plus apparently they give python coders a big disadvantage. Div2 easy may have been slightly harder than usual. But specially I would have given div2 hard smaller constraints. Much smaller , actually.

Friday, September 27, 2013

SRM 592 - sloow

d1 300 - The one with colors

So you have a sequence of balls, each has one of three colors: red, green and blue. You need to place the balls in a row. The order in which to place the balls is given by a string S. When you place a ball, you get points equal to the number of different colors to its right + the number of different colors to its left. Find the maximum possible score.

At first I thought of a dynamic programming solution. It was correct and all, but perhaps I should have waited to think of something better.

Let us name two sides of the row, the left and right side. When we place a new ball, it is best to place it between the two sides. So the score of that step is equal to the number of different colors in the right side + the number of different colors in the left side. The trick is that after adding this ball, we decide whether it belongs the left or the right side. In my dynamic programming solution I simulated both possibilities, but it is not needed. It is always better to add the ball to a side that doesn't already contain its color (This decision will increase the score of following steps by 1, any other decision won't). If both sides contain the color, it doesn't really matter.

int getNumber(string s)
{
    set<char> s1, s2;
    int res = 0;
    for (char ch: s) {
        res += s1.size() + s2.size();
        // if s1 already contains s[i] insert it to s2:
        ( s1.count(ch) ? s2 : s1).insert(ch);
    }
    return res;
}

There are other ways to implement the same logic. For example, in step i, the maximum score you can get is equal to min(2, number of red balls already placed ) + min(2, number of blue balls) + min(2, number of green balls). But the resulting code is actually more complicated.

d1 500: The one with permutations

Given `k` and `n` , count the number of pairs of permutations `(A, B)` of length `n` such that `sum_(i=1)^(i<=n)( max(A_i, B_i) ) >= K`

I spent most of the match trying to come up with a way to divide this problem into workable sub-problems, I sort of knew it would be a dynamic programming solution, but I had no idea how. I was trying and trying to find a way to simplify sub-problems. Oh well.

The rest

Opened div1 hard. I think it will be an approachable one once I get help. Tried to challenge but there was only one suspicious solution to div1 250 in my room and it got challenged before I could think of something.

Saturday, September 21, 2013

Did I just spent all my saturday customizing my Tester?

A word of caution about the Greed plugin. It might enable certain obsessive aspects of your personality.

I was not entirely happy with my previous solution to the Tester problem. So I began customizing even more.

The more I used the previous version of my tester, the more annoyed I was at the select case syntax of c++. It is awful. The need for break really kills me. Also, the whole thing with marking the last test cases with 'm' was messy.

I decided the optimal solution would be to abuse initializer lists and tuples and make the part of the code that saves test cases something like this:

typedef tuple< tuple<int,int,string,string>, int > test;

vector<test> testCases = {
     {  { 2, 2, "ABC", "ADC" }, {2} },
     {  { 2, 2, "ABC", "ABD" }, {0} },
     {  { 3, 4, "ABCDDE", "ACCBDE" }, {1899302} },
     {  { 8, 8, "ZZZZZZZZZZZZZZZ", "ZABCDEFGHIJKLMZ" }, {120390576} },
    // Your custom  goes here:
    // {  { , , , },  {} },
};

This would be the test case section for the StringPath problem. This has many advantages over the previous thing. It is less verbose. Adding a test case is just creating a new line. In case a single line is confusing we can add some formatting. It is also exactly the way input is represented in TC's system tests.

In order to use tuples like this, I would have to heavily modify the template, including the part that does the testing. I would need to extract parts of the tuple through indexes. But Greed doesn't have a field that gives an index to a parameter in the function. So in fact I had to update the source code. The fork that has this feature is at github.

Some time after adding the feature to Greed, I learned some very sad news. My initial idea of doing that with tuples and initializer lists did not work. Tuples don't support initializer lists like that. Initializer lists are also supposed to be used for things that have the same type... Back to square one.

The constructor idea

Although tuples don't allow that usage of initializer lists, they do have constructors, and constructors do support a {} syntax. So the following is possible:

vector<test> testCases = {
     tuple< tuple<int,int,string,string>, int > { tuple<int,int,string,string> { 2, 2, "ABC", "ADC" }, 2 },
     tuple< tuple<int,int,string,string>, int > { tuple<int,int,string,string> { 2, 2, "ABC", "ABD" }, 0 },
     tuple< tuple<int,int,string,string>, int > { tuple<int,int,string,string> { 3, 4, "ABCDDE", "ACCBDE" }, 1899302 },
     tuple< tuple<int,int,string,string>, int > { tuple<int,int,string,string> { 8, 8, "ZZZZZZZZZZZZZZZ", "ZABCDEFGHIJKLMZ" }, 120390576 },
     // Your custom  goes here:
     //tuple< tuple<int,int,string,string>, int > { tuple<int,int,string,string> { , , ,  },  },
};

But that is awful, you might say, well, not so much if we use typedefs:

typedef tuple<int,int,string,string> input;
typedef tuple<int> output;
typedef tuple< input, output > test;

vector<test> testCases = {
     test { input { 2, 2, "ABC", "ADC" }, output{2} },
     test { input { 2, 2, "ABC", "ABD" }, output{0} },
     test { input { 3, 4, "ABCDDE", "ACCBDE" }, output{1899302} },
     test { input { 8, 8, "ZZZZZZZZZZZZZZZ", "ZABCDEFGHIJKLMZ" }, output{120390576} },
    // Your custom  goes here:
    //test {  input { , , , }, output {} },
};

That... actually seems cool, doesn't it? I think it is the closest I can get to the system test syntax in c++. In python though we can use tuples directly.

Unknown output

A new issue was that this doesn't allow you to mark a test as not having a known required output. Sometimes you add custom tests just to test for timeout or to learn the solution and you have no idea what the correct solution actually is. Then I thought, well if you are going to use constructor syntax... we might as well just create a struct...

typedef tuple<int,int,string,string> input;
struct output
{
    int value; //the value
    bool u;    //false if the output is known, else we ignore the value.
};
output unknown{ 0, true };
typedef tuple< input, output > test;

vector<test> testCases = {
     test { input { 2, 2, "ABC", "ADC" }, output{2} },
     test { input { 2, 2, "ABC", "ABD" }, output{0} },
     test { input { 3, 4, "ABCDDE", "ACCBDE" }, output{1899302} },
     test { input { 8, 8, "ZZZZZZZZZZZZZZZ", "ZABCDEFGHIJKLMZ" }, output{120390576} },
     
     // A test with an unknown value:
     test { input { 5, 4, "ZZZZZZZZ", "ZAAAABXZ" }, unknown },
     
     // Your custom  goes here:
     //test {  input { , , , }, output {} },
};

Initializing simple classes with the {} syntax tends to be a life saver. output{6} creates an output object that has value 6 and u = false. The unknown variable contains an output object that has u = true. So that the tester (the part that does the grading) can know the output doesn't exist.

Compact layout

Everybody seems to like compact layout for the output of the tester. So I wanted to give it a try. Because of colors, I can actually make the smallest output ever. It looks like this:

Certainly smaller than it was before:

However, I am undecided, so I made this an optional thing. Determined by the value of a boolean constant. I can actually change the constant whenever I want. So maybe I have the compact layout until I really need debugging power in which I enable the full-info layout.

Actually, after a while of using the compact layout, it seems to me that information is more important than the coolness. I remember so many times in which my solution always returns a number that is exactly the intended result plus 1. It is useful to see the intended result and the actual result. It is also useful to see the parameters. Also, the compact layout loses its charm when you start putting tons of debugging messages in your solution.

Clean code

An issue with a full-featured template is that it is generating tons and tons of code. But you are supposed to use the file to code a solution. The code creates visual bloat that is a distraction.

The vector that initializes test cases was at the top, but it still required many things to be declared before it. Things that are distractful. Optimally, the test cases should be as above as possible. Just bellow the solution code. But how?

How do you use the input tuple or the output struct before declaring them? Turns out the only way I found was to use a template...

#include <bits/stdc++.h>
using namespace std;

struct StringPath
{
    int countBoards(int n, int m, string A, string B)
    {
        return 0;
    }
};

// CUT begin
//------------------------------------------------------------------------------
const double CASE_TIME_OUT = 2.0;
const bool   COMPACT_MODE  = false;

template<class test, class input, class output>
vector<test> getTestCases() {

    return {
        test { input { 2, 2, "ABC", "ADC" }, output{2} },
        test { input { 2, 2, "ABC", "ABD" }, output{0} },
        test { input { 3, 4, "ABCDDE", "ACCBDE" }, output{1899302} },
        test { input { 8, 8, "ZZZZZZZZZZZZZZZ", "ZABCDEFGHIJKLMZ" }, output{120390576} },
        // Your custom test goes here:
        //test { input { , , ,  }, output {} },
    };
// output{} = unknown result.
}
bool disabledTest(int x)
{
    return x < 0;
}

// Dragons be below this line:

That is how the file generated for StringPath looks like, just before the part that has a lot of code. Very messy code. Possibly without line breaks so it doesn't take space.

This brought me a new problem. The unknown variable was no longer usable that easily. I eventually settled to making the output struct have explicit constructors: (value) constructs the output with a value . Constructor with no arguments: () creates an unknown output. So if we want a known value we use output{2}, and if we do not know the value, we use output{} with nothing between the braces.

That fix added yet more code to a bunch of code that was already quite bloated.

A meta-tester!

BEEHOLD! Most of the operations the tester performs were the same everywhere (for all problems). Most of the functions were the same everywhere . A good start would be to move all the library and configuration functions like a function called pretty that prints any function argument or return with added "" if there is a string somewhere. Or the thing that compares floating point variables using TopCoder rules. If we put all these library functions into an external file that is shared by all solutions to all problems that are generated by my greed template. This saves a few space.

The real deal is though, to make an abstraction for the tester. Most of what the tester does is the same for all problems: Run each of the n tests. Decorate the output, call solution for each test, show solution results. Only few things vary, the actual types and number of the arguments. The solution class and method. The return type. The problem class name, the time when you opened the problem and the vector of tests.

The vector of tests is already a vector of pairs of tuples and an output struct. What if we made a template main function for the tester that took the test cases vector, the types of the method and everything else and just did the repetitive things?

The first speed bump was that input was represented by a tuple. Processing tuples requires variadic templates and it would have been very messy to, for example, print the arguments, or call the problem class with individual arguments.

This was the moment where I figure out. Maybe OOP is the solution. I really, really, hate OOP. But I was already using an output object. An input object was not that much different. And it would be very useful. The input object stores the parameters of a single test case, but it also has a method to perform the actual test, return the result and measure the execution time. Another useful method is the one to print the argument list.

And the files generated for a single TopCoder problem now look like this:

#include <bits/stdc++.h>
using namespace std;

struct StringPath
{
    int countBoards(int n, int m, string A, string B)
    {
        return 0;
    }
};

// CUT begin
//------------------------------------------------------------------------------
const double CASE_TIME_OUT = 2.0;
const bool   COMPACT_MODE  = false;

template<class test, class input, class output>
vector<test> getTestCases() {

    return {
        test { input { 2, 2, "ABC", "ADC" }, output{2} },
        test { input { 2, 2, "ABC", "ABD" }, output{0} },
        test { input { 3, 4, "ABCDDE", "ACCBDE" }, output{1899302} },
        test { input { 8, 8, "ZZZZZZZZZZZZZZZ", "ZABCDEFGHIJKLMZ" }, output{120390576} },
        // Your custom test goes here:
        //test { input { , , ,  }, output {} },
    };
// output{} = unknown result.
}
bool disabledTest(int x)
{
    return x < 0;
}

//------------------------------------------------------------------------------
// Tester code:
    #include "../tester.cpp"
    struct input
    {
        int n; int m; string A; string B;
        
        int run(double & elapsed) {
            StringPath* instance = new StringPath();
            time_t s = clock();
            int r = instance->countBoards( this->n,this->m,this->A,this->B );
            elapsed = (double)(clock() - s) / CLOCKS_PER_SEC;
            delete instance;
            return r;
        }
    
        void print() { 
            cout << "[" << Tester::pretty(n) << ","<< Tester::pretty(m) << ","<< Tester::pretty(A) << ","<< Tester::pretty(B)  << "]";
        }
    };
    struct output {
        int value; bool u=false;
        
        output(int value) { this->value = value; }
        output() { u = true; }
    };
    
    int main() {
        Tester::runTests(
            getTestCases<pair<input,output>,input, output>(), disabledTest, 
            "StringPath", 900, 1379806426,
            CASE_TIME_OUT, COMPACT_MODE
        );
        return 0;
    }
// CUT end

Note how the part that says Tester code just contains the input / output structs and a main method that calls a runTests function that happens to be a template function. It takes basically everything as arguments, including the test cases, the problem score, the function that determines if a test case is disabled, the configuration constants...

This ../tester.cpp file is the same for all topcoder problems and it works nicely. The tester code in the problem file is very short and nice and takes 33 lines. The actual code in tester.cpp is 168 lines long.

The other benefit is that I can modify the tester.cpp without worrying about Greed't template systax. I can add new features to the tester like multi threading or running in a single thread.

I do wish I could get rid of the input and output structs...

This post is just intended to show once more the power of Greed. Here is the template that generates the files for any TC problem:

const double CASE_TIME_OUT = 2.0;
const bool   COMPACT_MODE  = false;

template<class test, class input, class output>
vector<test> getTestCases() {

    return {
${<foreach Examples e}
        test { input { ${foreach e.Input in , }${if in.Param.Type.Array}{${foreach in.ValueList v ,}${v}${end}}${else}${in.Value}${end}${end} }, output{${if Method.ReturnType.Array}{ ${foreach e.Output.ValueList v ,}${v}${end}}${else}${e.Output}${end}} },
${<end}
        // Your custom test goes here:
        //test { input { ${foreach Method.Params p , }${if p.Type.Array}{}${end}${end} }, output {} },
    };
// output{} = unknown result.
}
bool disabledTest(int x)
{
    return x < 0;
}

//------------------------------------------------------------------------------
// Tester code:
    #include "../tester.cpp"
    struct input
    {
        ${foreach Method.Params p  }${p.Type} ${p.Name};${end}
        
        ${Method.ReturnType} run(double & elapsed) {
            ${ClassName}* instance = new ${ClassName}();
            time_t s = clock();
            ${Method.ReturnType} r = instance->${Method.Name}( ${foreach Method.Params p ,}this->${p.Name}${end} );
            elapsed = (double)(clock() - s) / CLOCKS_PER_SEC;
            delete instance;
            return r;
        }
    
        void print() { 
            cout << "[" ${<foreach Method.Params p << ","}<< Tester::pretty(${p.Name}) ${<end} << "]";
        }
    };
    struct output {
        ${Method.ReturnType} value; bool u=false;
        
        output(${Method.ReturnType} value) { this->value = value; }
        output() { u = true; }
    };
    
    int main() {
        Tester::runTests(
            getTestCases<pair<input,output>,input, output>(), disabledTest, 
            "${Problem.Name}", ${Problem.Score}, ${CreateTime},
            CASE_TIME_OUT, COMPACT_MODE
        );
        return 0;
    }

Thursday, September 19, 2013

Updating c++/python TopCoder testers

The other day I talked about Greed and posted my c++ and python tester templates. The templates do some magic like putting ANSI color codes to make the results and status easier to read.

I have been using them for a while now which made me realize there was room for improvement. The whole stuff about editing test cases was over complicated. I want the tester to have easy-to add test cases. Test cases without a known result (so that you can test for timeout/runtime error but they don't give WA). Also, ever since the updates I made to KawigiEdit, I was used to being able to disable test cases, so that when running the code, only a few cases run.

Disabling test cases from just an editable file is not as practical as using KawigiEdit's test case editor. I had to come up with workarounds. The workarounds in the initial versions of the tester templates were not working great. Because you needed to specifically list the number of test cases and the test cases to run by default in some vector (And you had to update them manually whenever you added a test case).

I switched to making a function that contains all your test cases and takes a single integer argument (The test case number). If it ever returns 'm', it is a way of marking the end of the list of test cases. So the main method calls this function with 0, 1, 2, 3, ...., x until an x is found that returns m.

For disabled test cases, I make the function return 'd'. It is necessary to find out if test cases were disabled so that the tester doesn't tell you everything is correct when there is a disabled test case (Which could be the one test case that is wrong) . The tester should tell you everything is right only when all test cases in the set are correct or have unknown answer and ran correctly.

Anyway, this is the way it works now, for the SRM 591 div2 easy problem:

char run_testcase(int __no, bool __disabled) {
 int a;
 int b;
 int c;
 double __expected = 0.0;
 bool __unknownAnswer = false;
    
 switch (__no) {
  case 0: {
    a = 0;
    b = 1;
    c = 2;

    __expected = 0.0;
    break;
  }
  case 1: {
    a = 0;
    b = 2;
    c = 1;

    __expected = 1.5;
    break;
  }
  case 2: {
    a = 3;
    b = 2;
    c = 1;

    __expected = 0.0;
    break;
  }
  case 3: {
    a = 4;
    b = 4;
    c = 8;

    __expected = 2.0;
    break;
  }
  /*case 4: { 
    // Your custom testcase goes here:
    a = ;
    b = ;
    c = ;
     
    __unknownAnswer = true; 
    break;
  }*/

  default: return 'm'; //mark the end of tests
 }
 // To disable test cases: 
 if ( __disabled ) {
     return 'd';
 }
 return do_test(a, b, c, __expected, __no, __unknownAnswer);
}

This is the test case code automatically generated by Greed using the template. This problem takes three integer variables, a,b,c. So if you want to add a couple of cases, you edit this part of the file and add:

  case 4: { 
    a = 27;
    b = 383;
    c = 1000;
     
    __unknownAnswer = true; 
    break;
  }
  case 5: { 
    a = 112;
    b = 33;
    c = 67;
     
    __expected  = 56.5; 
    break;
  }

Test case 4 has an unknown answer, this means that no matter what it returns, as long as it didn't time out or seg fault, the tester will not consider the test case wrong. The test case will show a ? to describe the status and if all the other cases with known answer are correct, the whole solution will be considered correct, regardless of the answer. Test case 5 does have a known answer.

Disabling test cases is more complicated. The idea is to make the code return 'd' in case of a disabled case. Doing the following will work well:

  case 4: { 
    a = 27;
    b = 383;
    c = 1000;
     
    __unknownAnswer = true; 
    break;
  }
  case 5: { 
    a = 112;
    b = 33;
    c = 67;
     
    __expected  = 56.5; 
    return 'd'
    break;
  }

However, usually you want to disable all tests but one. At first I thought of doing something clever like making if (__no != 5) return 'd'. (Where __no is the identifier for the test case number). But remember that the function is supposed to return 'm' when a case number is not registered. This would break things if we return 'd' before the return 'm'. That caused some issues, but now I have this:


  default: return 'm'; //mark the end of tests
 }
 // To disable test cases: 
 if ( __disabled ) {
     return 'd'
 }
 return do_test(a, b, c, __expected, __no, __unknownAnswer);

The if statement with __disabled is the one that can be updated to have cooler conditions like (__no != 5) without breaking things (because the return 'm' already exists above).

Link

I am now using github to store these new templates. You can find the latest version of c++ and python templates for Greed with this functionality at: http://github.com/vexorian/topcoder-greed/tree/master/src/main/resources/Resource. The file names are ColorGCC11Test.cpp and ColorTest.py

Wednesday, September 18, 2013

SRM 591 Recap and editorial

So, another SRM, another editorial. http://apps.topcoder.com/wiki/display/tc/SRM+591.

This was another bad day. Well, I was trying to solve the div1 500 for most of the match, but it seemed quite tricky. I opened div1 275 with 10 minutes left. I took a while to code it. Without the 10 minutes constraint I would have submitted this problem. I got tired of the lame strategy. I am going to try something else next match, but opening the problems in the normal order.

When writing the editorial, I learned about div1 900. This SRM had very odd choices for problem scores and slots. I think div1 900 was at least as easy if not easier than div1 medium. Actually, I wonder what would have happened if I opened it during the match. It is my style of problem, bitmask dp when filling a board. Well, I guess I would have probably taken more than 75 minutes to solve it...

The other very odd choice for this SRM was the div2 hard. I actually wasted more time trying to come up with a solution to this problem than I spent understanding the div1 hard solution. That is odd. The thing that made it complicated is that I really didn't expect a solution for a division 2 hard to be so hacky. Tricks to save memory in dp belong to div1 medium. I think even the div1 easy would have felt less out of place for the div2 hard slot.

I think that admins should go back to enforcing there to be at least one shared problem between the divisions. Making div2 medium and div1 easy the same problem was a good way to constraint problem setters to stop them from making the divisions too different and also limited the difficulty of div1 250 which is a serious slippery slope without safeguards. Also, there was nothing that made me feel the division 2 and division 1 versions of this contest were part of the same contest. Part of the experience should be to have red coders and greens talk about the same problems after the end of the match, this cannot happen when the divisions are so different. Also, it is quite easier to write explanations for 5 problems instead of 6 :)

----

Regarding the editorial itself, I suspect the explanation for div1 275 really, really sucks.

Sunday, September 15, 2013

Attempts to organize my topcoder folder

So when I migrated from KawigiEdit to Greed, the biggest issue was that thanks to KawigiEdit, all my topcoder source code files are in a single folder. Greed on the other hand, by default organizes them into sub-folders with the contest name. If I wanted to use Greed's organization powers, I would first need to organize all the files created by KawigiEdit. Move all the source code to their respective contest folders.

As it turns out, my folder contained code for problems from 360 different topcoder contests! So I needed an automatic method. No other choice but to make a python script. I refurbished some of the work I put in the handle tag script to make it search for problem names in the problem archive and then parse the results to get the contest name, then do the move.

As it turns out, it wasn't an incredibly trivial problem to solve:

  • Some problems were used in multiple contests, which one to choose?
  • Some of my problems couldn't be found in statistics (Round canceled, a bug, match was never added to statistic because it was special).
  • The results have a different format for TCHS matches and other contests.

There is even a problem I couldn't solve in anyway: For many tournament rounds, the contest name differs between practice room and problem archive (booo!).

But anyway, here is my script in case anyone needs it. It most likely only works in Unix-like OS, as it uses / for folder paths and commands like mv and mkdir. You are supposed to run it from the folder that contains all the problem codes.

Updated script to a windows friendly version thanks to Bjarki Ágúst Guðmundsson.

# Topcoder folder organizer
#
# err let us say it is released under the zlib/libpng license
# http://www.opensource.org/licenses/zlib-license
# (c) Victor Hugo Soliz Kuncar, 2013
#
import urllib, re, sys, os, time, string, glob
 
# Rudimentary proxy support
#  For example:
#  PROXIES = {'http': 'http://7.7.7.7:3128'}
PROXIES = None
 
# Will try all file names with these extensions, and assume they are ClassName.extension :
EXTENSIONS = [".cpp", ".java", ".cs", ".vb", ".py"]
 
BLACK_LIST = [ "template.cpp", "organize.py" ] #put any files that you are pretty sure are not problem source codes
 
 
#Special cases, problems that are not in the web site.
#Not by any chance an exhaustive list:
SPECIAL = {  #NetEase rounds are not in statistics, let's put them all in the same folder:
            'UnrepeatingNumbers     ': 'NetEase',
            'MaximumPalindromeScore' : 'NetEase',
            'RobotKing'              : 'NetEase',
            #This qualification round was canceled and renamed 3A, not in stats:
            'ChessTourney' :'TCO08 Qual 3A',
            'PokerSquare'  :'TCO08 Qual 3A',
            'RandomNetwork':'TCO08 Qual 3A',
            # Same with this one:
            'DNAMatching'    : "TCO'10 Qualifier 1A",
            'Palindromize3'  : "TCO'10 Qualifier 1A",
            'MegadiamondHunt': "TCO'10 Qualifier 1A",
            # SRM 377 is not in the stats, and I have no idea why:
            'AlmostPrimeNumbers'  : 'SRM 377',
            'SquaresInsideLattice': 'SRM 377',
            'GameOnAGraph'        : 'SRM 377',
            'AlienLanguage'       : 'SRM 377',
            # Member SRM 471 is gone from statistics, maybe it was cancelled, maybe
            # it is one of those matches that suffer the fushar curse - a bug that
            # removes matches by fushar from statistics.
            'PrimeContainers'   :'Member SRM 471',
            'EllysPlaylists'    :'Member SRM 471',
            'Thirteen'          :'Member SRM 471',
            'PrimeSequences'    :'Member SRM 471',
            'ThirteenHard'      :'Member SRM 471',
            'ConstructPolyline' :'Member SRM 471',
          }
 
#------------
 
REGEX_CONTEST = re.compile('([a-zA-Z0-9]+)\s*<.A>\s*<.TD>\s*<TD[^>]+>\s*<A\s+HREF="[^=]+[ce]=[a-zA-Z]+ound[a-zA-Z_]+verview&rd=[0-9]+"[^>]+>\s*(.+)\s*</A>')
 
CACHE = dict()
 
QUERY_COUNT = 0
 
def better(c1, c2):
    # when a class has multiple contests, pick the better one.
    # Parallel rounds:
    p1 = 'arallel' in c1
    p2 = 'arallel' in c2
    if p1 and not p2:
        return c2
    elif p2 and not p1:
        return c1
     
    # some problems were used in special contests and also in SRMs, put priority in SRM:  
    s1 = (c1[0:3] == 'SRM')
    s2 = (c2[0:3] == 'SRM')
    if s1 and not s2:
        return c1
    elif s2 and not s1:
        return c2
     
    s1 = ('SRM' in c1)
    s2 = ('SRM' in c2)
    if s1 and not s2:
        return c1
    elif s2 and not s1:
        return c2
   
    return c1 #any one
 
def getProblemContest(handle):
 global CACHE, QUERY_COUNT
 if handle in CACHE:
    return CACHE[handle]
 
 #CACHE memoizes the following function:
 def sub(handle):
    if handle in SPECIAL:
        return SPECIAL[handle]
     
    # Wait 0.5 seconds between queries, and 2 seconds every 10 queries
    # we are not DDoSing TC...
    global QUERY_COUNT
    if QUERY_COUNT == 10 :
        QUERY_COUNT = 0
        time.sleep(2.0)
    else:
        time.sleep(0.5)
    QUERY_COUNT += 1
 
    #download the problem archive search results
    params = urllib.urlencode({'module': 'ProblemArchive', 'class': handle})
    f = urllib.urlopen("http://community.topcoder.com/tc?%s" % params, proxies = PROXIES)
     
    html = f.read()
     
    # extract rating (or at least try)
    m = REGEX_CONTEST.findall(html)
    if type(m) == list:
        m = [x[1] for x in m if x[0] == handle]
         
    # Some problems were used in test SRMs, with a '2' added to their class name:
    if m == None or len(m) < 1:
        if  len(handle) >= 1 and handle[-1] == '2':
            return getProblemContest(handle[:-1])
        return None
    return reduce( better, m)
 
 CACHE[handle] = sub(handle)
 return CACHE[handle]
 
 
def inFolder():
    for f in os.listdir('.'):
        if os.path.isfile(f) and f not in BLACK_LIST:
            c, ext = os.path.splitext(f)
            if ext in EXTENSIONS:
                s = getProblemContest(c)
                if s != None:
                    s = s.replace('/','-')
                    if not os.path.isdir(s):
                        print ('mkdir "./%s"' % s)
                        os.mkdir(s)
 
                    print ('mv %s "./%s/"' % (f, s))
                    os.rename(f, os.path.join(s, f))
                else:
                    print ('%s: contest not found.' % c)
 
inFolder()

Saturday, September 14, 2013

vexorian answers quora questions

So, there are a couple of fun things about quora, one is that it keeps plaguing my search results. The other is that when I tried participating in it, I got banned because it wouldn't allow me to use a nick name. Seriously, I am my nick name. I stopped being my real name a long time ago. Anyway, I've found some questions that I cannot help but to answer. There we go, in no particular order:

Why don't more women participate in programming contests?

Computer science is already male-dominated, but programming contests are even more so (e.g. I counted only a handful of female contests at the 2013 ICPC). Why?

This question is asked on many fields and it is always the wrong way to approach the problem.

  • What you asked: Why don't more women participate in X

  • What you intended to ask: Why is X male-dominated?

  • What you should ask: What is X doing (or failing to do) that drives interested women away?

Once approached from the right perspective, it is a very good question. And I have asked it myself too. My theory: Programming is sadly male-dominated in the first place. The reasons for that are varied and tend to have a lot to do with the bro culture. Programming contests are a super-ultra-niche of programming , and thus it has reduced participation to begin with. If you take a small percentage of programmers, it is more likely the first bunch will be 100% male. And when a group is already male-dominated it becomes very hard to change it. Because there is already an outstanding male majority, there are no guarantees that this world is going to be safe and comfortable for non-males.

How to change it? Well, I don't know. But maybe if the gender problem is solved in programming as a whole, then competitive programming will improve its chances too. Check out the Ada initiative. Although the Ada initiative makes me notice, maybe we need codes of conduct in on site competitions?

Let me clarify: Any answer that involves stories about how men are different to women. How men are supposedly more competitive and thus more likely to enjoy competitive programming is utter BS. The only known difference between male and female brain is that males tend to have bigger brains, and this has not been provenly linked to any difference in behavior, capacity, or skills.

What it is like to meet or know Petr Mitrichev?

So, last year I went to the TopCoder Open. It was a very confusing experience. Also, I really had no idea what to blog during it. I was supposed to blog during it to justify they paying my travel expenses. But that was the point in which I noticed I am terrible at programming competitions, or rather terrible in Programming Finals. The problems that those guys were solving were all very difficult and I had no idea where to approach them.

I did my best to improvise whatever blog post I could. So I took my netbook and went to some of the couches in the TopCoder Open arena (A place similar to paradise, because it had all sorts of free snacks and soda). While I was typing in the TCO wordpress thingy. I noticed the guy next to me was writing in blogspot. Then I noticed he was writing in Petr's blog. A seconds later, I noticed he was Petr. Which was strange, because from pictures I didn't recognize him at all. At that point I really had no idea what to do. So I pretended like it was not happening. I already had enough trouble trying to fake a blog post. The whole thing was so embarrassing that I never tried to introduce myself.

So my answer is: Maybe you already met Petr. Maybe we all did. Maybe he wanders all over the world and shares sits with random people/coders.

Does having a very low TopCoder rating make someone unemployable?

Nah. I think that if you are someone active in TopCoder then you are already in the top 10% in traditional algorithm skills. (Note that it is a one way conditional, many people in the 10% , specially women, don't participate in TopCoder.

But of course, you can have a high rating and be unemployable. You can have a mediocre rating, like mine and be unemployable. You can also have green topcoder rating, like Mark Zuckerberg and be an evil CEO.

How do programming contest problem setters make test cases ?

In various ways. I just make a python script that takes various parameters (constraints for the input) and then generates a random one. Some problems need some sophisticated generation algorithms that are by itself an interesting algorithm problem (or more interesting?). Then I run the program and generate 5s, 10s or 20s of tests following a spec. Change the spec to cover another area of tests, generate other 10s of tests.

It is also needed to make some manual cases. That probably needs you to know what (wrong) solutions to expect from coders. Each problem is a different story.

What are the good ways to switch between C++ and Java in programming contests?

Don't. You will hardly have many opportunities to use c++ in your life. Java on the other hand, will most likely be forced on you eventually.

Do red coders and targets read the full question in a SRM?

No, they read the first two lines and then guess the rest of the statement*.

* Seriously, high level coders are not superhuman, they need to read the statement just like anybody else.

Which format of online programming contest i should participate more if eventually i want to get placed at companies like GOOGLE and FB?(long or short)

Why would people limit their career future to two companies? But if that was my life objective, I would actually dedicate myself to make commits, tons of commits to open source projects. Get involved in Summer of Code and stuff. Programming contests are a messy gate for these things in my opinion.

Why do most people on TopCoder use C++ as their default language?

Same question can be extrapolated to just about all contests for traditional algorithms.

People will bring excuses like familiarity, or how few sites support other languages. Etc.

But what if c++ is just the best language for this? It is fast, the STL seems to have been designed specifically for algorithm contests, things that are usually a c++ weakness (like threading support) are usually not allowed in programming contests anyway, etc.

Is PHP a good language to solve problems of spoj,codechef and topcoder?

PHP is never a good language.

Is it disadvantageous to use python on TopCoder over other languages?

Hmnn, I answered this in a long blog post. Short answer: Against c++, it is a mixed bag, the expressive power is great, but the performance cost really bytes. Against other languages, it is better :)

How do I go from blue to yellow on Top coder?

Solve the division 1 easy problem in 95% of the matches you participate in. Do not challenge any solution. Even if it is totally wrong.

It takes me hours to completely understand solutions to 1000-pt problems on TopCoder. Should I get discouraged?

You are obviously talking about div1 hard problems. If so, don't worry. Here is a little problem setter secret: The only reason we add div1 hard problems is so that the very, very, very high level coders don't get bored. For 99% of the coders, they don't cause any difference in the competition. I wouldn't even bother opening them if I didn't get paid to write editorials.

By doing practice can one be a red/yellow coder inspite of not being that intelligent?

Over the years I have learned a key insight: Nobody is that intelligent. Intrinsic skills are really worthless. Hard work is more important. People like Petr started solving Math puzzles at age 11 and have not stopped since. It has nothing to do with intrinsic intelligence.

The whole tale of there being programming geniuses does not seem to agree with reality. And it is also a dangerous tale. The idea of intrinsic intelligence is not founded in science and tends to support awful ideas like eugenics. My tip is don't fall for this. It is a useless belief. If you are good at something, it limits the effort you put into it , because you believe you are just good. If you are bad at something, it makes you give up. This belief is useless and only stops people from improving.

---

Have more questions?

Customizing the Topcoder greed plugin

Yesterday I wrote a quick howto about setting up the topcoder greed plugin. But that post doesn't really do much to show why I switched to it. What Greed does well is, it is very customizable. So customizable that you change the tester code. You can change not only the output format but also even add new test behaviors.

Configuration file

Greed's configuration is all file-dependent. It is not for everyone, I think some people prefer GUIs, but files are very convenient once you get used to them.

You can start a Greed configuration file by just adding a text file called greed.conf to the workspace folder. Whenever you modify this file while Greed is open, you should click the [Reload Configuration] button in the plugin window.

The first basic thing you would like to decide is where and how to place the code files. By default it saves them in a subfolder called "Contest Name", and the filenames are the same as the problem name. While I appreciate the concept of saving code in sub-folders named after the contest, I think I prefer having all my code in the same workspace folder. For starters, all my build scripts are there and it would be difficult to change my system to consider sub-folders :). Anyway, let us do it.

Greed's wiki has a page explaining all of this. So what I do is add this to my (currently empty) greed.conf:

greed {
  templates {
    pathPattern = ""
  }
}
Or this works too:
greed.templates.pathPattern = ""

Basically, my making the pathPattern an empty string, I make it save code files in the workspace root. This works ok in Linux, perhaps other OS need ".". Normally this setting is "${Contest.Name}". Greed has a cool configuration and templates system that has replacement variables like that one. This means the folder name will be replaced with the contest name.

Template

The code template is an important part of your topcoder life. What library modules do you want to include? Any macros (boo!)? What is the code style you prefer for your class? Default comments, etc. In the last post we saw that the code it generates for c++ looks liek this:

#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <typeinfo>
 
using namespace std;
 
class FoxAndChess {
    public:
    string ableToMove(string begin, string target) {
        return "";
    }
};

I have other tastes. I prefer to include only <bits/stdc++.h>, it is a magical header that includes the whole standard library. This is very convenient because of precompiled headers. If you know how to configure a g++ setup, you can use precompiled headers and bits/stdc++ to make compilation time smaller. I also prefer to use struct instead of class in c++, that way I don't have to type public: . The braces format is also all wrong :).

So, we need to change the template. According to the configuration wiki page, the default template file for c++ is said to be res:/Template.cpp, ok... the res:/ folder is inside the package, the jar and that is where we can find Template.cpp:

#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <typeinfo>

using namespace std;

class ${ClassName} {
    public:
    ${Method.ReturnType} ${Method.Name}(${Method.Params}) {
        return ${Method.ReturnType;ZeroValue};
    }
};

${CutBegin}
${<TestCode}
${CutEnd}

So that's what a Greed template looks like. It is easy to see how to make the modifications I was planning:

#include <bits/stdc++.h>
using namespace std;

struct ${ClassName}
{
    ${Method.ReturnType} ${Method.Name}(${Method.Params})
    {
        return ${Method.ReturnType;ZeroValue};
    }
};

${CutBegin}
${<TestCode}
${CutEnd}

Now we just need to make Greed use this template. I will save it as template.cpp in the workspace folder. The configuration field for the c++ code template is : greed.templates.cpp.tmplFile, so I will just add:

greed.templates.cpp.tmplFile = "template.cpp"

Go to a practice room and open a problem. Maybe the source file already exists and greed by default doesn't override files that already exist, so click [Regenerate Code]. You probably need to [Reload configuration] first. Now open the new file and verify the template changes.

Advanced template tweaks

So from now it is all very mundane. All plugins that generate code for TopCoder probably have some sort of template for your own code and can be configured in similar ways.

The cool thing about Greed is that it has a very flexible templates system. Namely it uses a library called jmte. You can not only add text bits that are replaceable by special values, like how ${ClassName} is replaced with the TopCoder-defined class name. You can also use conditional statements and ${foreach ...} in the templates. The template language is actually a whole language you need to learn, but it can be very useful, if you are like me and need all the flexibility you can use.

This tends to be more useful for the Tester template, but still, let us try to take some advantage of the power we have here. You know what's annoying? To copy the arguments the function receives so that they become class members. What if we wanted a template that did that automatically?, so the code for the problem would look like this:

#include <bits/stdc++.h>
using namespace std;
 
struct FoxAndChess
{
    string begin;
    string target;
    
    string ableToMove(string begin, string target) {
        this->begin = begin;
        this->target = target;
        return "";
    }
};

Believe it or not, it is possible to make a Greed template that automatically does this for us. The first thing we need is to add the member variables to the struct. For each argument in the method, create a member variable with the same type and name.

#include <bits/stdc++.h>
using namespace std;

struct ${ClassName}
{
${<foreach Method.Params p}
    ${p.Type} ${p.Name}; 
${<end}
    ${Method.ReturnType} ${Method.Name}(${Method.Params})
    {
${<foreach Method.Params p}
        this->${p.Name} = ${p.Name}; 
${<end}
        return ${Method.ReturnType;ZeroValue};
    }
};

${CutBegin}
${<TestCode}
${CutEnd}

The important part to understand is this one:

${<foreach Method.Params p}
    ${p.Type} ${p.Name}; 
${<end}

That is how the foreach template command works like. Method.Params contains the list of method parameters, p is the variable that will represent a single parameter. p.Type is the type, p.Name the name. We declare each variable and finish with a ;. Note that some commands begin with ${< and some with just ${. The ${< is an custom extension to jmte included in Greed that just says (Please ignore the line breaks surrounding this command). It is useful because without it, all the contents of the ${foreach } macro , including the line breaks, would be repeated for each parameter.

There is a conditional statement, it doesn't have things like a = operator for strings or binary operators, it is mainly used to call predefined boolean variables. It does have a ! operator and optional ${else}.

Customizing the Tester

The template language is great because it is also used in the Tester code and not just the template code. You can customize the tester template in the same way as the source template.

In a previous post, I mentioned all the trouble I went through to customize the tester in KawigiEdit to have cool things like colors. In greed, I wanted just about the same thing. I also don't really like not being able to read the input of a test case in the output text. I learned that it is very useful to be able to notice what the differences are between passing example cases and the ones you are not having correct. There are many other things that KawigiEdit does and the default tester in Greed didn't, like telling you if a test case is timing out. Allowing you to disable test cases, or allowing test cases that do not have a known return value. Also changed the format of the test case code so that it is easier to edit and so that it is the first part of the code, away from the messy tester code. The result looks like this:

I also modified the python tester template to have the same features. I am quite sure that TopCoder has other languages and that Greed supports them too, but I currently cannot remember their names.

My c++ tester template:

${-- /*
    Vexorian's c++ tester template for greed. Version 0.1
    - Colors using ANSI C codes.
    - Allow custom test cases with unknown result.
    - Allow "disabling" custom test cases by modifying the list of tests to run.
    - Timeout for individual cases, modify CASE_TIME_OUT below to customize
    (c) Victor Hugo Soliz Kuncar, ZLIB/LibPNG license 
*/ }  
using namespace std;${-- /*Maybe template/your final code doesn't include using namespace std*/ --}
char do_test(${foreach Method.Params p}${p.Type},${end}${Method.ReturnType},int,bool);
//------------------------------------------------------------------------------
${<if RecordRuntime}
const double CASE_TIME_OUT = 2.0;
${<end}

char run_testcase(int __no) {
${<foreach Method.Params p}
 ${if p.Type.Array}vector<${p.Type.Primitive}>${else}${p.Type.Primitive}${end} ${p.Name};
${<end}
 ${if Method.ReturnType.Array}vector<${Method.ReturnType.Primitive}>${else}${Method.ReturnType.Primitive}${end} __expected = ${Method.ReturnType;ZeroValue};
 bool __unknownAnswer = false;
    
 switch (__no) {
${<foreach Examples e}
  case ${e.Num}: {
${<foreach e.Input in}
${<if !in.Param.Type.Array}
    ${in.Param.Name} = ${in};
${<else}
    ${in.Param.Name} = { ${foreach in.ValueList v ,}${v}${end} };
${<end}
${<end}

${<if !e.Output.Param.Type.Array}
    __expected = ${e.Output};
${<else}
    __expected = {${foreach e.Output.ValueList v ,} ${v}${end} };
${<end}
    break;
  }
${<end}
  /*case ${NumOfExamples}: { 
    // Your custom testcase goes here (don't forget to add to num/runTests below)
${<foreach Method.Params p}
    ${p.Name} = ;
${<end}
     
    __unknownAnswer = true; 
    break;
  }*/

  default: return 'm';
 }
 return do_test(${foreach Method.Params p , }${p.Name}${end}, __expected, __no, __unknownAnswer);
}

// Tests total:
int      numTests  = ${NumOfExamples};
// Tests to run when there are no arguments:
set<int> runTests = { ${foreach Examples e , }${e.Num}${end} };

//------------------------------------------------------------------------------
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <ctime>
${-- /*Maybe template/final code doesn't #include those files*/ --}
template <typename T> string pretty_print(T t) { stringstream s; typeid(T) == typeid(string) ? s << "\\"" << t << "\\"" : s << t; return s.str(); }
${<if HasArray}
// Vector print
template <typename T> ostream &operator << (ostream &out, vector<T> arr) {
    out << "{";
    for (int i = 0; i < arr.size(); ++i) out << (i == 0 ? "" : ",") << pretty_print(arr[i]);
    out << "}";
    return out;
}
${<end}

${<if Method.ReturnType.RealNumber}
#include<cmath>
bool double_equal (const double &expected, const double &received) { return abs(expected - received) < 1e-9 || abs(received) > abs(expected) * (1.0 - 1e-9) && abs(received) < abs(expected) * (1.0 + 1e-9); }

${<if Method.ReturnType.Array}
bool double_vector_equal (const vector<double> &expected, const vector<double> &received) {
    if (expected.size() != received.size()) return false;
    int n = expected.size();
    for (int i = 0; i < n; ++i)
        if (!double_equal(expected[i], received[i])) return false;
    return true;
}
${<end}
${<end}

string colorString(string s, int q)
{
    if (q == 0) {
        //neutral
        return s;
    } else if (q < -1) {
        //bad (score)
        return "\\033[1;41m"+s+"\\033[0m";
    } else if (q < 0) {
        //bad (single result)
        return "\\033[1;31m"+s+"\\033[0m";
    } else {
        //good
        return "\\033[1;32m"+s+"\\033[0m";
    }
}

string colorTestResult(char r)
{
    string s = string(1, r);
    switch(r) {
        case '+' :
            return colorString(s, 1);
        case '?':
            return colorString(s, 0);
        default :
            return colorString(s, -1);
    }
    return "";
}

char do_test(${Method.Params}, ${Method.ReturnType} __expected, int __caseNo, bool __unknownAnswer) {
 cout << "\\033[1;36mTest " << __caseNo << "\\033[0m: [" ${<foreach Method.Params p << ","}<< ${if p.Type.Array}${p.Name}${else}pretty_print(${p.Name})${end} ${<end} << "]" << endl;


${<if RecordRuntime}
    time_t __startClock = clock();
${<end}
    ${ClassName} *__instance = new ${ClassName}();
    ${Method.ReturnType} __result = __instance->${Method.Name}(${foreach Method.Params par , }${par.Name}${end});
${<if RecordRuntime}
    double __elapsed = (double)(clock() - __startClock) / CLOCKS_PER_SEC;
    cout << "Time: "<<__elapsed<<" seconds." << endl;
${<end}
    delete __instance;

    bool __correct = __unknownAnswer || ${<if Method.ReturnType.RealNumber}
${<if Method.ReturnType.Array}${--
    --}double_vector_equal(__expected, __result);
${<else}${--
    --}double_equal(__expected, __result);
${<end}
${<else}${--
    --}(__result == __expected);
${<end}

    if (! __correct) {
        cout << "Desired answer:" << endl;
        cout << "\\t" << ${if Method.ReturnType.Array} __expected ${else} pretty_print(__expected) ${end} << endl;
    }
    cout << "Your answer:" << endl;
 cout << "\\t" << ${if Method.ReturnType.Array} __result ${else} pretty_print(__result) ${end} << endl; 

    char __res = '-';
    if (! __correct) {
        __res = 'X';
${<if RecordRuntime}
    } else if (__elapsed > CASE_TIME_OUT ) {
        __res = 'T';
${<end}
    } else if (__unknownAnswer) {
        __res = '?';
    } else {
        __res = '+';
    }
    cout << " "<<colorTestResult(__res)<<endl;
    
    cout << "\\033[0;2m===============================================================\\033[0m" << endl;
    return __res;
}

int main(int argc, char *argv[]) {
    string result;
    if (argc > 1) {
        runTests.clear();
        for (int i = 1; i < argc; ++i) {
            runTests.insert(atoi(argv[i])); 
        }
    }
    int j = 0;
    for (int i: runTests) {
        while (j < i) {
            result += 'd';
            j++;
        }
        result += run_testcase(i);
        j = i + 1;
    }
    result += string( std::max(0, numTests - j), 'd' );
    cout << "${Problem.Name}: ";
    bool good = true;
    for (char ch: result) {
        good &= ( ch == '?' || ch == '+' );
        cout << colorTestResult(ch);
    }

${<if RecordScore}
    int T = time(NULL) - ${CreateTime};
    double PT = T / 60.0, TT = 75.0, SS = ${Problem.Score} * (0.3 + (0.7 * TT * TT) / (10.0 * PT * PT + TT * TT));
    string SSS = std::to_string((int)SS) + "." + std::to_string((int)(SS*100) % 100);
    cout << " (" << colorString(SSS, good? 1 : -2) <<")." << endl;
${<else}
    cout << endl;
${<end}
    return 0;
}

My python tester template:

${--
#    Vexorian's python tester template for greed. Version 0.1
#    - Colors using ANSI C codes.
#    - Allow custom test cases with unknown result.
#    - Allow "disabling" custom test cases by modifying the list of tests to run.
#    - Timeout for individual cases, modify CASE_TIME_OUT below to customize
#    (c) Victor Hugo Soliz Kuncar, ZLIB/LibPNG license 
}  
#-------------------------------------------------------------------------------
${<if RecordRuntime}
CASE_TIME_OUT = 2.00
${<end}

def run_testcase(__no):
${<foreach Examples e}
 if __no == ${e.Num}:
${<foreach e.Input in}
${<if !in.Param.Type.Array}
     ${in.Param.Name} = ${in}
${<else}
     ${in.Param.Name} = (${foreach in.ValueList v} ${v},${end})
${<end}
${<end}

${<if !e.Output.Param.Type.Array}
     __expected = ${e.Output}
${<else}
     __expected = (${foreach e.Output.ValueList v} ${v},${end})
${<end}

${<end}
 # Your custom testcase goes here (don't forget to update num/runTests below)
 #if __no == ${NumOfExamples}:
${<foreach Method.Params p}
 #    ${p.Name} = 
${<end}
 #
 #    __expected = None
 #
 #...
 
 # run the code
 return do_test(${foreach Method.Params p , }${p.Name}${end}, __expected, __no)

#Tests total:
numTests = ${NumOfExamples}
#Tests to run when there are no arguments:
runTests = [ ${foreach Examples e , }${e.Num}${end} ];

#-------------------------------------------------------------------------------

import sys
import time
import string

def colorCode(q):
    return [ "\\033[1;41m%s\\033[0m", "\\033[1;31m%s\\033[0m", "%s", "\\033[1;32m%s\\033[0m" ][q+2]  

def colorTestResult(r):
    q = {'+': 1, '?':0 }
    return colorCode( q[r] if r in q else -1 ) % r

def prettyStr(x):
    if type(x) == str:
        return '"%s"' % x
    elif type(x) == tuple:
        return '(%s)' % string.join( (prettyStr(y) for y in x), ',' )
    else:
        return str(x)

def tc_equal(expected, received):
    try:
        _t = type(expected)
        received = _t(received)
        if _t == list or _t == tuple:
            if len(expected) != len(received): return False
            return all(tc_equal(e, r) for (e, r) in zip(expected, received))
        elif _t == float:
            eps = 1e-9
            if abs(expected - received) < eps: return True
            if abs(received) > abs(expected) * (1.0 - eps) and abs(received) < abs(expected) * (1.0 + eps): return True
        else:
            return expected == received
    except:
        return False

def do_test(${Method.Params}, __expected, __caseNo):
    sys.stdout.write("\\033[1;36mTest " + str(__caseNo) + "\\033[0m: ["+${foreach Method.Params p +","+}prettyStr(${p.Name})${end}+"]\\n")


${<if RecordRuntime}
    startTime = time.time()
${<end}
    instance = ${ClassName}()
    exception = None
    try:
        __result = instance.${Method.Name}(${foreach Method.Params par , }${par.Name}${end});
    except:
        import traceback
        exception = traceback.format_exc()
${<if RecordRuntime}
    elapsed = time.time() - startTime   # in sec
${<end}

    if exception is not None:
        sys.stdout.write("RUNTIME ERROR: \\n")
        sys.stdout.write(exception + "\\n")
        correct = False
    else:
        correct = __expected is None or tc_equal(__expected, __result)
        if not correct:
            sys.stdout.write("Desired answer:\\n")
            sys.stdout.write("\\t%s\\n" % prettyStr(__expected) )
        sys.stdout.write("Your answer:\\n")
        sys.stdout.write("\\t%s\\n" % prettyStr(__result) )
    
    res = '?'
    if not correct:
        res = 'X'
${<if RecordRuntime}
    elif elapsed > CASE_TIME_OUT:
        res = 'T'
${<end}
    elif __expected is not None:
        res = '+'
    sys.stdout.write(" %s\\n" % colorTestResult(res) )
    sys.stdout.write("\\033[0;2m%s\\033[0m\\n" % ('='*63))
    return res


def run_tests():
    global numTests, runTests
    result = ""
    if len(sys.argv) > 1:
        runTests = [ int(arg) for arg in sys.argv[1:] ]
    j = 0
    for i in set(runTests):
        while (j < i):
            result += 'd'
            j += 1
        result += run_testcase(i)
        j = i + 1
    result += 'd' * max(0, numTests - j)
    line = "${Problem.Name}: %s" % string.join( (colorTestResult(ch) for ch in result), '')
${<if RecordScore}
    T = time.time() - ${CreateTime}
    PT, TT = (T / 60.0, 75.0)
    points = ${Problem.Score} * (0.3 + (0.7 * TT * TT) / (10.0 * PT * PT + TT * TT))
    points = "%.2f" % points
    q = 1
    if any( ch != '+' and ch != '?' for ch in result ):
        q = -2
    points = colorCode(q) %  points

    line = "%s (%s)" % (line, points)
${<end}
    sys.stdout.write("%s\\n" % line)

if __name__ == '__main__':
    run_tests()

So

As you can see, it only took me a couple of hours distributed in a couple of days, to make the tester template I wanted, with all the features I liked and needed. For KawigiEdit, I needed to edit the source code, and I still didn't have such great results. This is the reason I switched to greed.

I did have a couple of issues in other places. For example, I like to use long instead of long long for 64 bits integers. I was unable to do that using only templates. I had to patch the source code to add a configuration point. Greed is open source and in github, so it wasn't complicated. Hopefully these updates will be incorporated in the official build :).

I wonder, for example, what is the limit now. Maybe I am going to make a tester that uses individual threads for each test cases, so that multicore computers run test cases faster. My Google code jam template already does this, although Google code jam has a more urgent need for that as you need to run code locally for the complete test cases and not just examples. However, I once lost qualification to a TCO tournament round because of 0.2 seconds of difference in submission speed against another coder. Do not underestimate the importance of the time it takes you to test things.

Friday, September 13, 2013

Getting started with TopCoder Greed plugin

It may appear that there are already too many TopCoder arena plugins. The truth, however, is that there are as many preferences for work environments as there are coders. So new plugins will pop up all the time.

The Greed plugin was started last year, although few people seem to have heard of it. I only learned of it two days ago and by now already decided to switch to it. And this is coming from a guy who spent various hours and days working on tweaking KawigiEdit.

Why use the greed plugin?

If you intend to use an external editor, I think Greed is a good choice. Unlike some plugins out there, it doesn't require you to use 3 or 4 plugins at the same time to work at all. It is amazingly simple to set up.

It supports c++, python, Java and even that C# thing. Of course, it generates your code from a template, and also adds tester code to test all the examples automatically.

It is easy to get started with Greed. But it is also very customizable. That is the actual reason I switched to it. I have more control over the tester code than I ever had in KawigiEdit. Of course, what helped me made the switch was that I recently decided to start using KawigiEdit not for its internal editor but to allow an external editor - In my case, jEdit.

If you like coding from the Arena or if you use Visual Basic, then Greed will not help you. I'd suggest to stick to KawigiEdit.

Greed Setup

  • Download Greed's jar file. Latest version 1.5 is at: http://github.com/shivawu/topcoder-greed/tree/master/dist. However, I am not sure if future versions will be added there.
  • Start your topcoder arena.
  • Options\Editor
  • Click [Add]
  • Set the [Default] checkbox of the new entry for the Greed plugin to true. If you don't do this, you would have to manually select Greed after opening a problem.
  • Select Greed and click configure.
  • Type the path for a workspace. What is a workspace? You ask. It is just a folder that will store all the TopCoder code Greed generates for you. By default, it will save the files in sub-folders named after the SRMs. The workspace will also hold configuration and your custom templates. The good thing about this, is that setting up greed in another computer is the same as just copying the workspace and telling greed to use it.

Using Greed

Go to SRM 590 Div 1 practice room and open the 250 points problem.

 - Source code will be generated, "./SRM 590/FoxAndChess.cpp", in your workspace
 - I'm generating source code for you~
 - Using test template "res:/GCCTest.cpp"
 - Using source template "res:/Template.cpp"
 - Overriding "./SRM 590/FoxAndChess.cpp", old files will be renamed
 - All set, good luck!
 -

So, let's open FoxAndChess.cpp.

#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <typeinfo>

using namespace std;

class FoxAndChess {
    public:
    string ableToMove(string begin, string target) {
        return "";
    }
};

// CUT begin
template <typename T> string pretty_print(T t) { stringstream s; typeid(T) == typeid(string) ? s << "\"" << t << "\"" : s << t; return s.str(); }

bool do_test(string begin, string target, string __expected, int caseNo) {
    cout << "  Testcase #" << caseNo << " ... ";

    time_t startClock = clock();
    FoxAndChess *instance = new FoxAndChess();
    string __result = instance->ableToMove(begin, target);
    double elapsed = (double)(clock() - startClock) / CLOCKS_PER_SEC;
    delete instance;

    if (__result == __expected) {
        cout << "PASSED!" << " (" << elapsed << " seconds)" << endl;
        return true;
    }
    else {
        cout << "FAILED!" << " (" << elapsed << " seconds)" << endl;
        cout << "           Expected: " << pretty_print(__expected) << endl;
        cout << "           Received: " << pretty_print(__result) << endl;
        return false;
    }
}

bool run_testcase(int __no) {
    switch (__no) {
        case 0: {
            string begin = "R...";
            string target = "..R.";
            string __expected = "Possible";
            return do_test(begin, target, __expected, __no);
        }
        case 1: {
            string begin = "..R.";
            string target = "R...";
            string __expected = "Impossible";
            return do_test(begin, target, __expected, __no);
        }
        case 2: {
            string begin = ".L.R.R.";
            string target = "L...R.R";
            string __expected = "Possible";
            return do_test(begin, target, __expected, __no);
        }
        case 3: {
            string begin = ".L.R.";
            string target = ".R.L.";
            string __expected = "Impossible";
            return do_test(begin, target, __expected, __no);
        }
        case 4: {
            string begin = "LRLLRLRLLRLLRLRLRL";
            string target = "LRLLRLRLLRLLRLRLRL";
            string __expected = "Possible";
            return do_test(begin, target, __expected, __no);
        }
        case 5: {
            string begin = "L";
            string target = ".";
            string __expected = "Impossible";
            return do_test(begin, target, __expected, __no);
        }

        // Your custom testcase goes here
        case 6:
            break;
        default: break;
    }
    return 0;
}

int main(int argc, char *argv[]) {
    cout.setf(ios::fixed,ios::floatfield);
    cout.precision(2);
    cout << "FoxAndChess (250 Points)" << endl << endl;

    int nPassed = 0, nAll = 0;
    if (argc == 1)
        for (int i = 0; i < 6; ++i) nAll++, nPassed += run_testcase(i);
    else
        for (int i = 1; i < argc; ++i) nAll++, nPassed += run_testcase(atoi(argv[i]));
    cout << endl << "Passed : " << nPassed << "/" << nAll << " cases" << endl;

    int T = time(NULL) - 1379094076;
    double PT = T / 60.0, TT = 75.0;
    cout << "Time   : " << T / 60 << " minutes " << T % 60 << " secs" << endl;
    cout << "Score  : " << 250 * (0.3 + (0.7 * TT * TT) / (10.0 * PT * PT + TT * TT)) << " points" << endl;
    return 0;
}
// CUT end

As you can see, Greed generated just about everything you need to begin coding in some editor. Open the file in some editor , you probably need something to compile it and run it. I use some shell scripts. The output looks like this by default:

FoxAndChess (250 Points)

  Testcase #0 ... FAILED! (0.00 seconds)
           Expected: "Possible"
           Received: ""
  Testcase #1 ... FAILED! (0.00 seconds)
           Expected: "Impossible"
           Received: ""
  Testcase #2 ... FAILED! (0.00 seconds)
           Expected: "Possible"
           Received: ""
  Testcase #3 ... FAILED! (0.00 seconds)
           Expected: "Impossible"
           Received: ""
  Testcase #4 ... FAILED! (0.00 seconds)
           Expected: "Possible"
           Received: ""
  Testcase #5 ... FAILED! (0.00 seconds)
           Expected: "Impossible"
           Received: ""

Passed : 0/6 cases
Time   : 11 minutes 25 secs
Score  : 217.08 points

(Of course, when you pass a test case it will tell you it is correct, and the time it took to run). It is nice that it also tells you the time since you opened the problem and estimates the score you'll get in TopCoder (Assuming it is not a resubmit, and that the file was generated at the same time as you opened the problem).

When you click [Compile] or [Save] in the Topcoder arena, everything between // CUT begin and // CUT end will be automatically removed from the submission, everything else will be sent to topcoder.

What is cool about this is that you can customize it and do some cool things using the configuration and templates option. I'll give more details and share my tester templates in a later blog post, but you can read Greed's wiki for more information.

Thursday, September 12, 2013

KawgiEdit-pfa with c++ code cleaner and Greed

I released a new update to my unofficial version of KawigiEdit. Among other minor things, I added ahmed_aly's unused code cleaner. He made a custom version of KawigiEdit a long ago that would clean some unused code in c++. When browsing codes in the TopCoder arena, I noticed that there are many coders using his version of KawigiEdit, but since he coded it a while ago, it is missing some of the new features KE has. I merged the two forks together so that coders interested in both the code cleaner and the new features are able to use them. Anyway, the code cleaner is disabled by default (I, for example wouldn't use it, I *love* to make codes full of comments visible to anyone). But it can be enabled in the c++ options.

Get it at the Forum thread

Fun anecdote: This might be the last version of KawigiEdit I release. Yesterday, after making these updates, I thought to myself ("Why are you bothering with this? No one uses it") so I decided to go to the SRM 590 division summary and read codes. Everyone is using some FileEdit variation. Many people are using an old KawigiEdit version (Including some VERY OLD ones). A couple are using the KawigiEdit version with ahmed_aly's code cleaner. Another couple are using fushar's plugin. I did find one submission that uses KawigiEdit-pf though :) Great. (Although since KawigiEdit-pf allows you to remove the Powered by line, maybe some people are using it and just remove it).

Well, I am mostly making these KawigiEdit updates for myself. So it doesn't matter if it doesn't have many users. However, I was noticing that KawigiEdit was giving me some issues in becoming what I wanted it to become. Or rather, I want it to become something that it is not good at. The option to completely disabling loading of code saved in TopCoder is one example.

When reading the codes, I noticed around 5 or so submissions that used "Greed 1.5", that was curious because, unlike the other plugins, I never heard of this one and it wasn't announced in the forums. I was curious and googled. And it is very promising. Actually, Greed turns out to be close to my ideal plugin. Because you can customize even the tester code. I have been having some nice results with it although currently have an issue with long long. I might have more to say more about this plugin and post some tutorials once I decide if it can really do all that I need.

Monday, September 09, 2013

SRM 590 recap and editorial

Another week another Topcoder match. Not a great day. I had a bad flu and still do.

Div1 500: The one with Xor

Given a list of cards with numbers on it count the number of subsets that give a total binary xor value less than or equal to limit.

I actually got close to solve this problem though I started with dumb ideas about dynamic programming. I actually even started to code a bad dp solution. I noticed in the middle of the code process that it didn't make any sense. Too much dependency between decisions and no way to order them.

I figured that it was possible to reduce it to the exact case instead of <= case, and I noticed "We can create a condition for each bit, then we just need to count the number of ways to follow those conditions". For some reason though, it never occurred to me that this meant "System of modular linear equations". I am disappointed because I learned to count solutions to those systems just recently, when writing round 2A's editorial .

Div1 250: The one with pawns

You have a row of cells . Some pawns on the cells can only move right, some can only move left. Is it possible to reach a given configuration?

With only 10 minutes left before the end of the coding phase. I felt like the solution was going to be tricky to code. For some lame reason I thought of trying a bipartite matching. While that was technically correct, it turns out that a bipartite matching didn't make the problem any less tricky. I took long to code a solution, and the first version was going to fail system tests anyway.

When challenge phase started, I thought that this problem was challenge material. I did find a wrong code in my room, got 50 points thanks to this. I think that these 50 points prevented me from losing my yellow rating.

Editorial

It is up: SRM 590.

There were a couple of problems that gave me ... err ... problems when explaining them. Div2 easy and div2 medium are the sort of problems I don't like seeing in a SRM I am writing the editorial for. Too obvious of a solution and I felt like there was nothing to explain really.

For div1 easy and div2 hard, I was going to show a much more complicated solution. It was not until today at 5:00 AM when I noticed that I was not sleeping at all that I noticed that there could be an easier idea.

Not sure I like my explanation for div1 hard. Not sure if I explain how to get the solution or just the solution itself.