Per problem memory and Time limits in Greed

Greed (at least the git version) is now the first plugin to support the per problem memory and time limits that were recently added to topcoder.

I had to cry for help from the arena maintainers to get this to work. I discovered many things I didn't know about the arena API, for example, the Memory limit thing was in it since years ago (huh?). Anyway, I finally got it to work. That was quite a pull request...

Why did I care so much to get this to work? Well, if some TC problems are going to have a custom memory and time limit, you need to know. Currently I am reading problem statements generated by greed instead of those by the arena (it is much better!), so I need them to contain this information. There is also something else though...

My test system is basically just a runcpp.sh script that sets things up correctly and puts the default Memory Limit (256) and runs things. Then it calls the Greed-generated source code file, which has a time limit feature. So my current TopCoder environment makes quite some use of these limits. If a problem gets new limits, they would break without using this information.

Making the environment take advantage of this feature was another issue. For time limit, it was relatively easy, my tester templates already had a time limit constant. I just modified them to use a time factor instead of set limit. My templates are now an official part of greed and you can find more info at: https://github.com/shivawu/topcoder-greed/tree/master/src/main/resources/templates/dualcolor

The memory limit was an adventure of its own. Memory limit was enforced by the runcpp.sh (and similar) scripts I used. But now there was a custom ML per problem. I first needed to store that information somewhere. I am not sure if this was the simplest way possible, but what I did was add yet-another template to greed. The memory-limit template:

    memory-limit {
        overwrite = force
        outputFileName = "limit/${Problem.Name}.txt"
        templateFile = "limittemplate.txt"
    }

(You also need to add memory-limit to the templates line). This would make greed generate a file ProblemName.txt at a limit sub-folder of the contest folder... The template file is just this:

${Problem.MemoryLimitMB}

So this txt file just contains the memory limit in MB.

Next step was to make the runcpp.sh script able to read this txt file (if it exists). The same with the python and Java ones. Posting the Java one for reference as it is the easiest to understand (The other ones need to do far more complicated things like calling ulimits and multiplying the MB limit by 1024...):

#!/bin/bash
#default
LIMIT_MB=256

#extract folder name from $1:
DIR=$(dirname $1)
#extract file name (problem name) from $1:
PROBLEM=$(basename $1)
PROBLEM=${PROBLEM%%.*}
#build the limit file name
LIMIT=$DIR/limit/$PROBLEM.txt
if [ -f $LIMIT ]; then
    #echo "READ MEMORY LIMIT"
    LIMIT_MB=`cat $LIMIT`
#else
    #echo "NO MEMORY LIMIT, USE DEFAULT"
fi
#echo "MB = " $LIMIT_MB

echo "compiling..."
javac $1.java
if [ $? = 0 ];
then
    java -Xmx${LIMIT_MB}m $1
fi

The trick is to modify the java command line, to use -Xmx${LIMIT_MB}m, where LIMIT_MB contains the read memory limit value.

So?...

I just hope that problems with custom memory limits are not too rare to justify all this work.

I am liking greed more and more every day. Nowadays I consider Greed not to be a TopCoder arena plugin, but an arena plugin workshop. The workshop just happens to come with an example simple arena plugin by default :)

The arena plugin survey

Calling all Greed users (and any other plugin users too). It is best to get surveyed in the plugin survey at : http://apps.topcoder.com/forums/?module=Thread&threadID=807988&start=0 I already made a post for Greed, so if you use it, plus that post.

Read More

So...

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

Read More

Codeforces "Good bye 2013" round

So it was a special round for coders of both divisions, problems ranged from the super easy problem A to the super difficult problems E,F,G... I always mean to participate in CF rounds but time constraints are tough. Since this was a special match I decided to give it a try.

Problem A: New Year Candles

problem statement

I mentioned this was an easy problem. Just simulate the process. For each candle, use it, increment the used candles counter, if used candles ever reaches `b`, join these used candles together to make a new one: set the counter to 0 and increment the number of available candles. The constraints are small so the simulation is fast enough:

int solve(int a, int b)
{
    int r = 0, u = 0;
    while (a > 0) {
        a --;
        r += 1;
        u ++;
        if (u >= b) {
            a ++;
            u -= b;
        }
    }
    return r;
}

Just because a problem is easy, it doesn't mean it is easy to get a good score in comparison to other coders. Indeed, even though I coded this one as fast as possible, by the time I submitted its code there were already 170+ submissions to this problem and some few submissions to problem B :/

Problem B: New Year Present

problem statement

This is the kind of problem that makes me wish Topcoder allowed problems that didn't need a specific answer, but just following some rules. The number of commands can be anything as long as it is less than 1000000. There are at most 300*300 candles, so even the easiest strategy I could think of was guaranteed to do it in less than 1000000 steps. It works as follows:

• We fill the wallets from left to right. Begin with the left-most wallet, if needed, put a coin.
• After putting a coin, robot cannot put a new coin again unless it moves. So we move the robot either right or left (It is best to move it right, since most likely left wallet is already done, but sometimes you cannot move right). If the next wallet is not complete, put a coin before moving back to the original wallet.
• Once all the coins in the left-most wallet are done, move right, and consider this the new left-most wallet to fill.

Logic is basic and it will use at most 3 steps per coin, so it should work under the constraint.

It was actually tricky to implement. It occured me to make a tester so I could simulate the moves and make sure everything is fine. This was a good idea because I found many bugs.

I wonder how an optimal strategy looks like.

const int MAX = 1000000;
void solve(int n, int * a, string & res)
{
    #ifdef DO_CHECK
        int b[n];
        for (int i = 0; i < n; i++) {
            b[i] = a[i];
        }
    #endif
    res.resize(MAX, '-');
    int x = 0;
    int t = 0;
    while (true) {
        if (a[x] == 0) {
            // wallet x is done, move right
            if (x + 1 == n) {
                break; //everything is done, grats.
            }
            res[t++] = 'R';
            x++;
        } else {
            // put a coin
            res[t++] = 'P';
            a[x]--;
            // move to some other wallet and return back
            if (x + 1 == n) {
                assert(x != 0);
                res[t++] = 'L';
                res[t++] = 'R';
            } else {
                // put a coin if needed
                res[t++] = 'R';
                if ( a[x + 1] != 0 ) {
                    a[x + 1]--;
                    res[t++] = 'P';
                }
                assert(x + 1 != 0);
                res[t++] = 'L';
            }
        }
    }
    assert(t < MAX);
    // The checker runs in case the DO_CHECK #define is on
    #ifdef DO_CHECK
        int c[n];
        fill(c, c+n, 0);
        x = 0;
        for (int i = 0; i < t; i++) {
            //cout << res[i] << endl;
            switch(res[i]) {
            case 'L':
                assert( x > 0 );
                x--;
                break;
            case 'R':
                assert (x < n - 1);
                x++;
                break;
            case 'P':
                assert( (i == 0) || (res[i-1] != 'P') );
                c[x]++;
            case '-':
                break;
            default:
                assert(false);
            }
        }
        for (int i = 0; i < n; i++) {
            assert( b[i] == c[i] );
        }
    #endif

}

Problem C: New Year Ratings Change

problem statement

I am not entirely sure about this one, my solution is to sort the clients in non-decreasing order of `a_i`. It follows that the ratings you assign must be in increasing order (we want them to be different). For each `i` (in the order), try the smallest possible rating (must be at least `a_i` and larger than the rating assigned to the previous client).

I did various tests, I was quite cautious today:). Found a couple of bugs, but fixed them. So I thought it was correct. Well, unfortunately, my first submission I uploaded B.cpp (Solution for the previous problem) by mistake. And in the second submission I failed pretests, I didn't notice the maximum `n` was 3*100000, I initially thought it was 1000000. Changing the array size to 300000 passed pretests, let's see if I survive.

const int MAX = 300000;
// I:
int n;
int a[MAX];
// O:
int b[MAX]; //results
//-----------------------------
int id[MAX];

void solve()
{
    // Since the return must be in the same order as original a_i, we cannot
    // just sort the a_i array. Instead, sort the client indexes.
    for (int i = 0; i < n; i++) {
        id[i] = i;
    }
    sort(id, id + n, [&](int x, int y) -> int {
            return a[x] < a[y]; // I <3 lambdas so much.
    });
    int last = -1;
    // now do it in non-decreasing order of a_i :
    for (int i = 0; i < n; i++) {
        if ( last >= a[id[i]] ) {
            b[id[i]] = last + 1;
        } else {
            b[id[i]] = a[id[i]];
        }
        last = b[ id[i] ];
    }
    
}

Problem D: New Year Letter

problem statement

And so this is when the problems become challenging. The trick is to notice that `k` is sort of small, at most 50... The strings themselves can be quite complicated. For example, is `s_1` is "A" and `s_2` is "C", then `s_3` can have one "AC".

To calculate the final number of AC strings in the final string, we need to know 6 things (Yep, 6):

• The number `p` of AC in the first string `s_1`
• The starting character `a` of `s_1`
• The final character `b` of `s_1`
• The number `q` of AC in the second string `s_2`
• The starting character `c` of `s_2`
• The final character `d` of `s_2`

With this in mind, we can find the number of AC in the final string `s_k` in `O(k)` time. You can do it recursively. There are things you can find about `s_3`:

• It will start with `a`.
• It will end with `d`.
• It will have at least `p+q` ACs, it might have an extra one if `b = "A"' and `c = "C"`.

`s_2` and `s_3` can become `s_1` and `s_2` in a version of the problem that has `k-1` steps.

There are only 3 characters that are relevant to simulate for starting and ending characters: A , C and something else. We can use X for that something else. This means that the number of tuples `(p,a,b,q,c,d)` is `O(nm)`. We can just brute force them until we find a case that returns `x` ACs.

However, not all tuples `(p,a,b)` and `(q,c,d)` are valid. We still need to actually build those strings. This was the most complicated sub-problem in my case. Though probably you can use dynamic programming to make it easier. What I did was a lot of case studying. Thankfully I also tested this throughly. I *think* it is correct

const string WRONG = "Happy new year!";

// given the parameters:
// p: number of ACs in s1
// q: number of ACs in s2
// a: starting character of s1
// b: final character of s1
// c: starting character of s2
// d: final character of s2
// : Count the number of ACs in sk:
int simulate(int k, char a, char b, char c, char d, int p, int q)
{
    if (k == 2) {
        return q;
    }
    int r = 0;
    if (b == 'A' && c == 'C') {
        r = 1;
    }
    long np = p + (long)q + (long)r;
    np = std::min<long>(np, 1000000001LL);
    return simulate(k - 1,  c,d, a,d, q, (int)np);
}

// Build a string
// - Contains n characters
// - Contains exactly p "AC" substrings.
// - Starts with a
// - Ends with b
string build(int n, int p, char a, char b)
{
    if (n == 1) {
        if (a != b) {
            return WRONG;
        }
        if (p > 0) {
            return WRONG;
        }
        return string(1, a);
    } else if (n == 2) {
        string r = string(1,a) + string(1,b);
        int q = 0;
        if (r == "AC") {
            q = 1;
        }
        if (q != p) {
            return WRONG;
        } else {
            return r;
        }
    } else {
        string res(n, '?');
        res[0] = a;
        res[n - 1] = b;
        int j = 0;
        int q = 0;
        for (int i = 0; i < p; i++) {
            //cout << "[" << res << "]"<<endl;
            while ( (j + 1 < n) 
                    && ( ((res[j] != 'A') && (res[j] != '?')) || (res[j+1] != 'C') && (res[j+1] != '?') ) 
                ) {
                j++;
            }
            if (j + 1 >= n) {
                break;
            }
            res[j] = 'A';
            res[j+1] = 'C';
            j += 2;
            q++;
        }
        for (int i = 0; i < n; i++) {
            if (res[i] == '?') {
                res[i] = 'X';
            }
        }
        if (q != p) {
            return WRONG;
        }
        return res;
    }
}

// Find the two strings with a huge brute force
tuple<string, string> solve(int k, int x, int n, int m)
{
    string A, B;
    A = WRONG;
    // for example if k=3, x=1, n=1, m=1, then we can even do s1 = A, s2 = C.
    string CHARS = "ACX";
    for (char a: CHARS) { // x 3
        for (char b: CHARS) { // x 9
            for (char c: CHARS) { // x 27
                for (char d: CHARS) { // x 81
                    for (int p = 0; 2*p <= n; p++) { //x81 x 25
                        for (int q = 0; 2*q <= m; q++) { //x81 x 25 x 25
                            if (simulate(k, a,b, c,d, p, q) == x) { //x81 x 25 x 25 x 50
                                //a good one?
                                string tem1 = build(n, p, a,b); //x81 x 25 x 25 x 50
                                string tem2 = build(m, q, c,d);
                                if (tem1 != WRONG && tem2 != WRONG) {
                                    A = tem1;
                                    B = tem2;
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    
    return make_tuple(A,B);
}

The rest

There were less than 30 minutes left when I finished problem D. The other problems were solved by few people and though problem F seemed like something I could eventually solve, I didn't think I could do it in 30 minutes. So I prefered to write this blog post. Enjoy!

It was a fun match. Although my rating shall suffer.

Read More

A white whale defeated

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

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

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

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

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

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

Before BR fix:

After BR fix:

Cool!

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

Read More

SRM 602: High note

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

Div1 250: The one with rating

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

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

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

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

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

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

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

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

Div1 550: the one with rectangles

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

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

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

Challenge phase

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

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

Comments

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

Read More

SRM 601 div1 hard editorial

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

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

You know what? I blame Christmas.

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

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

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

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

Read More

Just saying...

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

Read More