In case you are wondering why that editorial was taking so long

Since some TopCoder matches ago, I was given the responsibility of being the editorial writer for all Topcoder matches. Too bad that my last two experiences did not go very well in regards to the time these editorials are taking.

In SRM 565, the main cause of issues was the division 1 Hard. I think it was one of the hardest problems of 2012, if not the most confusing one. SRM 565 finished it on a Thursday, and I intended to get the editorial ready the next Friday. Because, mind you, the time of the year was a very complicated one and I had to do a ton of shopping in Saturday and stuff...

The plan failed. I could not really do much about understanding the hard problem until the Sunday. The Sunday was a day in which I was forced beyond my will to spend a good chunk away of a computer with extended family. Meh. But the good thing is that the empty time was a good chance to get to think about the problem. Points, trees, paths, distances. I got something that *looked* like an idea. I could only begin to test it until that Sunday night though. If you head to the editorial the part that I got correct that day was the section [Variation with a fixed center].

When I implemented, I noticed some issues with the other variation, I tried hard to fix them. I actually got it correct. But I was failing one of the big, random test cases. I spent the next two days working on it. Those two days happened to be Christmas eve and Christmas :).

It turns out that I underestimated the "2 roots" version greatly. The recursive part from the editorial was not in the first draft of the solution. I finally found the challenge case that would defeat my first wrong solution during Christmas, it was ok.

SRM 566 now turns out to have a similar fate. But at least I have finally solved the div1 hard.

Div1 hard: The one with penguins and polygons

There are numPosts (at most 222) posts scattered around the border of a circle at equidistant angles. There are also penguins (at most 50) of possibly different colors at some fixed positions. The objective is to create closed polygons (using the posts as vertices) in such a way that a) All polygons contain at least one penguin. b) No two segments cross. c) All penguins of each color are inside one of the polygon (A polygon may contain various colors). The objective is to return the total number of ways to create these polygons modulo 100007. Two ways to create polygons are different if a segment is present in one and not in the other.

The solution is not that hard conceptually. It is typical dynamic programming. But it is hard to think of it, understand it and also cover all possible corner cases. When you solve a counting problem using dynamic programming and there is a circle involved, you need to be careful not to count the same thing twice...

I will not explain it fully right now because that bellongs to the editorial. But the solution requires two main ideas:

• There are O(numPosts^2) possible segments. If a segment separates two penguins of the same color (one penguin is at one side to the segment and the other at the other side) then this segment is certainly invalid. In fact, it does not matter what you do with the polygons, as long as you only use segments that are not invalid, the polygons will always contain all the penguins of one color. Once you identify the invalid segments, the problem becomes about counting the ways to create polygons such that each polygon uses only valid segments and contains at least one penguin.
• To solve the new problem, think about how to create a function f(l,r) that counts the total number of ways to have polygons using only the posts with indexes between l and r, inclusive. An easy way to avoid issues is to, pick the index of the smallest vertex that will be used and the index of the vertex it will be connected to. This already creates a sub problem of the form (nr + 1, r) (more details in the editorial). But then you have to solve g(l,r): The total number of ways to create a polygon that starts with l and finishes with r. While you create this polygon, you create new subproblems f(l,r).

I was barely able to come up with this solution yesterday, and I had to spend a lot of time debugging. Until I ran out of ideas about how to fix the solution. I figured many corner cases in the process, but I reached a moment in which the only example case I was failing was a big one that I could not debug.

I spent all this time, since last afternoon to now, trying to come up with the reason. One last logic flaw in my polygon counting. One last small bug, maybe? The more time I spent, the more convinced I was that the logic was correct. So it must be a small issue. I could not help but notice that I was only failing large cases, and could not find a small case that was wrong.

- Maybe it is overflow?

-"NAH" I foolishly replied myself. When I first read the statement, I noticed that the modulo value is 100007 instead of 1000000007. Such a small value gave me the idea that the admins decided to use a small value because that would allow you to use only integer operations (for product) and since the processors in TopCoder are 32 bits, this would speed up things. Maybe they intend the solution to be a bit tight.

I spent more hours looking for issues. Until just now, I finally notice: 100006 * 100006 can still overflow!. All this time I skipped the overflow possibility because of a lame assumption. Right now I have no idea why they picked a smaller value than usual for the modulo. If it was 10007, then indeed we could have avoided 64 bits operations. But the 100007 is quite a mystery.

It is a bit discouraging that after all this time I still manage to get problems wrong because of overflow. Such is life, I guess.

Div1 hards cause too many editorial delays

Looking back, most of the time I spend making an editorial is spent trying to solve the div1 hard. Mind you, I am only a yellow, soon to be blue, coder and some of these problems are not even solved by guys like Petr. If the best coders cannot solve a problem, then it is likely I will need quite some time to do it.

We are working in new ways to deliver editorials that might allow the editorial for the easier problems to appear in less than a day (at best) so that at least those problems get delivered faster. Let us see how well this goes in the next SRM.

Read More

TopCoder SRM 566: The road to blue

If you recall, I am going with a "suicidal" strategy, to never open the division 1 easy before there are less than 10 minutes left for the end of coding phase. The results so far are not very surprising. I have the feeling that 250s are lately becoming longer. This is my second 0.00 in a row.

Div1 1000: The one with penguins, a circle and colors

Skipped this one quickly after reading the statement. Seems to be the typical div1 hard that I won't solve until after a couple of hours and with admin help. This one will stop me from finishing the editorial quickly...

Div1 500: The one with a mountain and cities

You have numCities total cities all in the border of a circle. You start at city 0. You make numSteps steps in total. In step 1, you move 1 city clockwise or counterclockwise. In step 2, two cities clockwise or counterclockwise. ... In step k , k cities clockwise or counterclockwise... Count the number of different sequences of numSteps steps such that you end back in city 0 modulo 1000000007.

At first I thought I was gonna to solve this problem. It seemed like a standard matrix multiplication one. Then I noticed that there can be at most 350 cities. That changes things... Let us explain the matrix approach though.

When the step number k is too big, the clockwise or counterclockwise distance between your current city and the new one is (k % numCities). This means that every numCities steps, we basically repeat the same thing. Over and over again.

Let us describe a transition matrix for step 1: For each i, there is one way to move from vertex i to vertex (i+1)%numCities and one way to move from vertex i to vertex (i-1+numCities)%numCities. This works for step k: One way to move from vertex i to (i+k)%numCities and one way to move from i to (i-k+numCities)%numCities. Note that if the two vertices are the same, there is only one way in total (Two paths are different not because of the direction you move but because of the city you move to).

If we multiply together the first numCities matrices. You will get a matrix that represents numCities moves. You can raise this one to the x-th power. Let x be numSteps / numCities. Then you can multiply the result to the product of the first numSteps % numCities matrices. Then this will be the total transition matrix.

The problem is that there are numCities matrix multiplications we have to use. This yields a O(n^4) algorithm and it is too slow for n=350. In fact, n seems to be crafted with this in mind.

The solution is that if you take a look to the matrices, you will see that each element inside the matrix is at most 1, and each row contains at most 2 ones. If you tweak the matrix formula a bit, you can actually do each multiplication in O(n^2) instead of O(n^3). This is very nice and clever...

When I finished coding that optimization I began to have issues. Apparently, my classic matrix exponentiation library might have some seg fault bug that happens when the matrixes are larger than usual. Then I had the other issue that it was timing out, apparently the number of steps is so large that even O( log(numSteps) * numCities ^ 3) is too much.

I thought of the solution for the time out issue when it was too late to code it. It turns out that the product of the numCities matrixes tends to generate very dull matrixes. Containing the same numbers repeated over and over again in the matrix and following some pattern. There is also symmetry in the matrix, so the same row is repeated over and over again, just slided a bit in each new row... I think that you can turn the matrix idea into a vector idea and turn the whole thing O(n^2).

Div1 250: The one with points and crossing

With less than 10 minutes left I open this problem and it turns out to be a bit tough to read. (long).

Ok, so you have at most 50 points. And some segment definitions that connect pairs of the points. You do not know the actual positions of the points. You can remove 0 or more segments. Count the total number of subsets of segments such that it is GUARANTEED that no two segments will ever cross, regardless of the position of the points.

After thinking for a while and looking at the statement images you can make some conclusions:

• Empty set (no segments at all) is always possible and valid.
• Whenever there is more than one connected component of segments, it is possible they would cross (take two separated segments and make them cross).
• When there is only one segment. It is valid.
• Star patterns are valid. A point that acts as a center and is connected to other points by a segment each.

We can count the pattenrs (single segment, star) that can be made using only the input segments. It is easy to count the segments. The stars are a bit harder: Pick a center point, then count the number of points that are initially connected with that center, each combination (use the binomial) of 2 or more points connected to it can make a star pattern.

I coded that stuff and had a bit of debug issues (again). Some seg faults and stuff that I could only fix after the end of the coding phase. That is when I noticed that the logic was failing the last test case...

It turns out that I forgot of yet another valid pattern: A single polygon of exactly three connected points (A triangle, a cycle of 3, etc). It is impossible to cross this pattern too. So you also pick the number of triples in whcih each pair is connected. This fixes the issue, you pass system tests and all is good

long long countDesigns(int numCheckpoints, vector <int> checkpoint1, vector <int> checkpoint2) 
{ 
    int n = numCheckpoints; 
 
    // make an adjacency matrix. The original input format is a bit hazardous: 
    bool con[n][n] ; 
    memset(con, 0, sizeof(con)); 
    for (int i=0; i<checkpoint1.size(); i++) {  
        con[ checkpoint1[i] -1][ checkpoint2[i] -1] = true; 
        con[ checkpoint2[i] -1][ checkpoint1[i] -1] = true; 
    } 
    // Pascal triangle to generate the binomials we will need: 
    long long C[50][50]; 
    memset(C, 0, sizeof(C)); 
    for (int i=0; i<50; i++) { 
        C[i][0] = 1; 
        for (int j=1; j<=i; j++) { 
            C[i][j] = C[i-1][j] + C[i-1][j-1]; 
        } 
    } 
 
    long long res = 1 + checkpoint1.size(); // the empty set + the number of segments 
                                            // all are valid 
                                             
    // Count stars with center i: 
    for (int i=0; i<n; i++) { 
        int x = 0; 
        for (int j= 0; j < n ; j++) { 
            if (con[i][j]) { 
                x++; 
            } 
        } 
        for (int y = 2; y <= x; y++) { 
            res += C[x][y]; 
        } 
    } 
    // Count triangles: 
    for (int i=0; i<n; i++) { 
        for (int j=i+1; j<n; j++) { 
            for (int k=j+1; k<n; k++) { 
                if (con[i][j] && con[j][k] && con[i][k]) { 
                    res++; 
                } 
            } 
        } 
    } 
    return res; 
     
} 

Conclusion

The problems were good and interesting. My rating will suffer. Any comments?

Read More

SRM 565: Huge little differences

Ouch, now with 16XX. My new strategy of not opening div1 easy until 10 minutes before the end of the match is really killing my rating.

Div1 250: The one with trees

This one seems very tough. I am very worried because I will have to write the editorial and explain this problem. Seems I will be working hard these two days :(

Div1 500: The one with the division game

Two players play a game with a list initially consisting of all numbers in a interval [A, B]. A turn consists of picking one of the numbers in the list, find a divisor != 1, and divide the number by that divisor. The player who does not have a valid move loses the game.

You are given L and R, count the number of intervals [A,B] such that L <= A < B < R in which the first player wins (both players play optimally.

All right, I just recently solved a problem that used nimbers (Grundy numbers); and it was actually the first time I learned about them and had to write the editorial. So they were in my mind today. The game is a two player, symmetric, turn based game, so a state of the game should have a nimber.

First let us find the nimber of a single game consisting of a number x. I had no ideas so I just did this for the first 40 numbers looking for a pattern: I define a function nimber(x) that calculates the number. Each divisor of x will give us a number y with a nimber of its own. The minimum number that is not in the set of nimber(y)s is the result (minimum excluded ordinal).

In fact, after doing all of that and printing the results from 1 to 40, it was clear that nimber(x) = number of prime factors of x (0 for x=1, 1 for prime x). Now it is clear why this happens. Imagine a number as a set of stones, each labeled with one of the prime factors. So 12 is equal to two stones labeled 2 and one stone labeled 3. Dividing by a divisor of the number is the same as taking some of the stones. For example 12/4 = 3, it is the same as if we took the two stones labeled 2. At the end, what matters all the time is the number of stones, not their labels. This becomes exactly a nim game in which the number of stones in the stack is equal to the number of prime factors.

Let us say that we have found the number of prime factors, the nimbers for all n numbers between L and R, inclusive. The problem becomes: Given n numbers, where n is up to 1000001. Count the number of intervals of consecutive numbers in that list such that the xor of the numbers in the interval is not 0. (Each number is a nim game, the combination of a set of nim games, has a nimber equal to the xor of all those games).

This new sub-problem can be solved with dynamic programming. Let us define a function f(x,i) that returns the number of intervals that start with number i and with a total xor equal to x. (The final result will then be the sum of all f(x,i) such that x is not 0). After placing number i in the interval, you have two choices: Finish the interval with this number, in which case x = number[i]. And not finish the interval, in which case it has to continue (and include number[i+1]) and there are f( x ^ number[i], i+1) intervals that work like that.

The slight inconvenient with that dynamic programming approach is that an array [32][1000001] (The maximum xor will be 31, because the maximum number of prime factors by the constraints is 29). Will not fit in the memory. But fear not, we can approach this complication by using an array [32][2], because each i, only needs to remember the results for i+1.

THE REAL problem (at least to me) was to actually calculate all the nimbers from L to R. This means calculating the number of prime factors for up to 1000001 numbers. In the worst case, each of those numbers is greater than 999999999. Straight forward approaches are too slow. And I could not think of anything during the match.

In my frustration, I decided to just submit a solution with the dynamic programming and all the logic already made, but using a slow approach for the nimber calculation. I knew it would fail. But at least it shows I solved the rest ^^.

At the end of the match, I read Petr's code and the trick to calculate the numbers became clear. It is similar to a Sieve of Erathostenes, but only caring about the numbers from L to R. Given a prime p (up to sqrt(R)), we can just iterate through all numbers between L and R that are multiples of it. And increase the counts of prime factors. This saves a lot of time.

typedef long long int64; 
#define long int64 
 
int current[1000001]; 
int nimber [1000001]; 
 
long dp[32][2]; 
 
struct TheDivisionGame 
{ 
 
    long countWinningIntervals(int L, int R) 
    { 
        int n = R - L + 1; 
        // Cleverly calculate nimber[i] for each 
        // number between L and R (The number of prime factors) 
        for (int i=L ; i<=R; i++) { 
            nimber[i - L] = 0; 
            current[i - L] = i; 
        } 
        for (int p=2; p <= R/p; p++) { 
            int s = L; 
            if (L % p != 0) { 
                s += p - (L % p); 
            } 
            //cout << L << ", "<<s<<", "<<p<<endl; 
            while (s <= R) { 
                while( current[s - L] % p == 0) { 
                    current[s - L] /= p; 
                    nimber[s - L] ++; 
                } 
                s += p; 
            } 
        } 
        // some numbers might still have current[i] > 1, they are primes. 
        for (int i=L ; i<=R; i++) { 
            if (current[i - L] != 1) { 
                nimber[i - L]++; 
            } 
        }  
         
        // Now the dynamic programming part: 
        long s = 0; 
        // dp[x][i] : Number of intervals that start with nimber[i] 
        //            such that the total xor of the interval is x. 
        for (int i=n-1; i>=0; i--) { 
            for (int x=0; x<32; x++) { 
                dp[x][i&1] = 0; 
                // Use nimber[i] and nimber[i+1] 
                // then we need to know the number of intervals 
                // starting with nimber[i+1] that give x ^ nimber[i] 
                if (i+1 < n) { 
                    dp[x][i&1] += dp[x ^ nimber[i]][ (i&1)^1]; 
                } 
                // Use only nimber[i] then x must be == nimber[i] 
                if (x == nimber[i]) { 
                    dp[x][i&1]++; 
                } 
                // Count the intervals with x!=0 
                if (x!=0) { 
                    s+= dp[x][ i& 1]; 
                } 
 
            } 
        } 
        return s; 
    } 
}; 
#undef long 

Div1 250: The one with monsters

I exceeded my time with div1 500 and actually had 8 minutes to solve this problem. I think I should have been able to solve it though. At first it seems like an innocent dynamic programming problem. Then you notice that the scary ness of monsters can be very high.

The trick is to notice that prices are 1 or 2. You can change the problem to calculating f(i, p) : The maximum scaryness you can buy using the first i monsters and spending at most p. This allows a recursive solution. Let us say you want to solve f(i,p), then you have to decide whether or not to bribe monster (i-1), then your available money becomes p - something, but the scaryness is scaryness[i-1] + f(i-1, p - something). If you decide not to bribe the monster, then the maximum scaryness f(i-1,p) you can find must be greater than scaryness[i-1].

See? It is easy!. But it took me far more than 8 minutes to think of this reversal. Ouch. The result is that I am back to 16XX rating. That is a record low, I think. Probably the lowest rating I reeached in years :(.

But this was deserved. I think I should have known how to do the fast prime factorization already. That would have given me a score in div1 500 and more time for div1 easy. Which I should have been able to solve in less than 8 minutes anyway.

Comments?

Any comments?

Read More

I wrote SRM 564 (Except div1 hard)

The other day I was writing the editorial for SRM 562. I have noticed some trends in the topcoder problem setter list that made suspect that there is a scarcity of problems being submitted. I really didn't have a problem set prepared, but I gave it a shot and asked the admins if they need problems. They did!

But then I had to think of a problem set. My first reaction is try to finally use some of the problems I never get to use. You may suspect why. All the previous times I got a SRM assigned, I was close to use those problems, but something better appeared...

Until now! Unfortunately I just could not think of or find a problem that was good enough for division 1 medium or hard difficulties...

The Knights ones

This Knight circuits problem is very old. If my memory works, it is probably some of the first problems I came up with. Contemporary to my second problem set, probably.

When I thought of it, it seemed so edgy and good. But I could not use it until now. Nowadays, the whole "knight circuit = connected component" thing sounds so obvious.

There were two variations, the "harder" one was the one used in division 1. The easier one was, actually given a board with some blocked cells. So it was just solvable with a simple BFS. It was supposed to be used in division 2 as a medium.

I also proposed many other lame problems which were not in use yet.

The change in plans

The division 2 version of the knights problem was going to be used. But then ivan_metelsky, memetic tester opined that it was very boring, even for that slot. Proposed that instead, we could use a variation of the division 1 version, but with variable allowed moves for the knight. This also fixed the issue that the division 2 hard that I proposed was very standard. The new issue would be to find a new division 2 medium. Ivan proposed we go back to the original version of the palindromes (division 2 easy) problem that was harder. So then all I needed to do was find a new division 2 easy.

So, I suddenly had an idea for division 2 easy. Balls of three colors, getting alternated, find the color of the k-th ball. A simple simulation thing that at least was more interesting than the recent div 2 easies... I proposed it and it was accepted.

The most amazing thing happened after that. I went out to buy groceries, when in the way I suddenly started to think of how that alternating colors thing was so like some of my favorite problems that I wrote. Some ad hoc thing to do using a program as a starting point... Then I remembered a mantra: If you want to turn a simulation problem into a harder problem, turn it into a counting problem. I started to wonder how to solve a variation about counting the number of ways to have a certain ball color in a certain position. This variation was hard. So hard that it started to look good for division 1 medium. And it was!

Finally, I noticed that turning the division 2 easy about palindromes into a division 2 medium was going to take time to develop. Also the alternating balls problem was interesting to solve in O(k) time. So I asked to make that problem the division 2 medium instead of the previous plan.

What is going to happen?

I am writing this before the match. I think that the main complaint about the division 1 match will be that it is too mathematical. I do not know yet about the division 1 hard problem , but I hope it is hard and programmatic to compensate.

People will probably think division 1 easy was too easy. But division 1 medium will probably have a healthy success rate (not too low or too high). When I solved it, I took 4 hours, which is usual for me and division 1 medium. Since I thought division 1 easy was too easy, I left very weak example cases. I wonder how many people are going to fail the 3x3 case. I hate fake difficulty as much (if not more) as anyone else, but for this problem I think it was needed.

Division 2 will be very challenging. I actually needed help to solve the division 2 hard. Whereas division 2 hards are usually very simple and quick for me to solve.

Read More

SRM 563: The trend has been stopped, for now

So, to recap, I made the decision that from now on I will never solve a TopCoder division 1 easy problem in more than 10 minutes. This new strategy to open the hard and medium problems first and never open the easy until there are 10 minutes left is, of course, suicidal. It does not help that my rating was already trending downwards before making this decision.

Div1 hard

This problem seemed complicated. In fact, for a second I wondered if the match was going to be canceled because the problem is actually impossible.

I have not shared this but it has been decided that starting in SRM 564 I will always write the editorial, unless it is an exceptional case. Which means I now receive the editorial assignment and explanation of hard problem just half an hour after results are announced. In theory, this should make editorials arrive faster... in theory. What is important to know is that I now read the short explanation for this problem, and it turns out it was not difficult at all ...

Div1 Medium - The one with magic cards

5 minutes after opening the hard problem, I gave up and opened the medium problem. My first reaction was that it seemed approachable. And it was.

You got a list of cards from left to right. Each card has a level and a damage value. You can use a card with level L and damage D if and only if there are at least L-1 cards to its right. In case you use the card, you perform D damage and the card and the L-1 cards to its right get removed from the game. Another allowed step is to move the right-most card to the left-most place of the list of cards. What is the maximum total amount of damage you can make?

The first step is to alter the problem a bit. You actually have a circle of cards, placed in clockwise order. At every point, you can take any of the cards of level L, take the L-1 cards to its right and the card itself and perform D damage. These two variations are equivalent.

To solve the variation, consider another variation. In which you have the cards in a line. Once again, you can pick any card and remove it and the L-1 cards next to it. But this time it is not a circle (for now).

To solve this easier variation of the problem we use dynamic programming. The issue is that you can remove cards in any order and the order can alter the result dramatically. Thus the main thing to approach is how to decide their removals following a fixed order...

In fact, imagine that we decide to use the i-th card. This means that the level[i]-1 next cards to it have to be removed. But then after this decision, we decide to also use card i+1. We got to use card i+1 before using card i. When we decided to remove card i, we decided that we owe level[i]-1 cards. After deciding that we will use card i+1 before card i, we actually increase the amount of cards owed by (level[i+1]-1), so that then we can decide what to do with card i+2, and so and so, assuming an amount of owed cards.

A different case is what happens when we decide not to use card i+1, then we will remove this card when we remove the owed cards. This means we will need one less card. The number of owed cards decreases by 1.

That logic allows a dynamic programming solution. f(p, owed) finds the maximum damage you can make by using the cards with index greater than or equal to p, and you currently owe owed cards. Note that the base case is when p=n, then owed must be 0.

The next issue is what to do in the circular case. There are two clever work around to this. The first one is to try all n ways to rotate the vector of cards, and then just solve using the previous method.

The second method is to assume that there was an amount initOwed of cards that we will owe after processing the last card in the input. Then at the start of the simulation, when p=0 we already owe some cards (that we will assume we will define to owe later). The base case changes, the amount of owed cards at the end must be the same as the one that was planned in advance.

It is funny but I used both approaches at the same time. But of course, only one is necessary.

Here is the code anyways:

Div1 easy

It was worth 300 points. I opened it with 9:50ish minutes left, and I knew it was going to be difficult. For the first 5 minutes I implemented a solution that turned out to be wrong. I tried to use the remaining time to come up with a solution or a cheap trick that allowed the wrong solution to work. With no success.

Challenge phase/etc

Not much happened afterwards. I eventually passed system tests in div1 500. At least the trend towards the bottom of the ratings is not going on.

int n; 
vector<int> lvl, dmg; 
 
int dp[MAX+1][MAX+1]; 
 
int rec(int p, int owed) 
{ 
    int & res = dp[p][owed]; 
    if (res == -1) { 
        if (p == n) { 
            if (owed == 0) { 
                res = 0; 
            } else { 
                res = -INF; 
            } 
        } else { 
            res = -INF; 
            //use this? 
            if (owed + lvl[p] - 1 <= n) { 
                res = std::max(res, dmg[p] + rec(p+1, owed + lvl[p] - 1 ) ); 
            } 
            //do not use this 
            res = std::max(res, rec(p+1, std::max(owed - 1, 0) ) ); 
        } 
    } 
    return res; 
} 
 
int maxDamage(vector <int> level, vector <int> damage) 
{ 
    n = level.size(); 
    lvl.resize(n); 
    dmg.resize(n); 
    int res = 0; 
    for (int start = 0; start < n; start++) { 
        for (int i=0; i < n; i++) { 
            int j; 
            if (i < start) { 
                j = (n - start) + i; 
            } else { 
                j = i - start; 
            } 
            lvl[i] = level[j]; 
            dmg[i] = damage[j]; 
        } 
 
        memset(dp, -1, sizeof(dp)); 
        res = std::max(res, rec(0, 0) ); 
    } 
    return res; 
} 

Read More

Topcoder SRM 562 editorial preview (div1 1000)

I do not seem to finish this editorial. I am already one day after the deadline (first problems were difficult and explanations turned out be image intensive) and I still have to finish div1 250 and div2 500 (will need more images, that takes time). So here is a draft of the div1 1000 editorial. At least that should help anyone who needs it. Note that this is still a draft, and thus I guarantee you that it has far more mistakes than usual (and that is saying a lot).

----

Let us quickly quickly explain the problem statement: We are given a tree. Count the number of ways to assign labels 1,2,...n to each node in the tree such that the sets of vertices {1,2,..k,}, {2,3,...,k+1}, ... {n-k+1,...,n} are each connected components. This editorial will call these sets 'target' sets.

Small k versus large k

A good starting point is to notice that the problem can change dramatically depending on how large the value of k is. The main difference between small and large values of k is that when k is large enough, there will exist a group of labels that are common to every target set. For example, with n=10 an k = 7:

1 2 3 4 5 6 7
  2 3 4 5 6 7 8
    3 4 5 6 7 8 9
      4 5 6 7 8 9 10

The labels {4,5,6,7} exist in each of the target sets. Which does not happen with small values of k, for example n=6 and k=3:

1 2 3
  2 3 4
    3 4 5
      4 5 6

There is no vertex that is present in all of the sets. The requirement for us to consider a value of k large is that the set of the k smallest values intersects with the set of the k largest values. In other words: 2*k > n. This small difference makes a case much harder than the other. Let us begin with the small case, which is the simplest.

2*k <= n

In order to understand this case, let us think about what is needed to transition from the first target set to the next one making sure they stay connected. Imagine that we already found out the connected component of the first target set, the nodes with the k smallest labels. Since we are dealing with a tree and its subtrees, these labels will form a tree. Like in the following two examples for k=3:

The tree can so far have any shape, but with k connected elements. It is interesting what happens when we transition to the next target set. From {1,2,...k} to {2,...,k+1}. What it means is that the new tree will have {1} removed and {k+1} added, but it still must be connected. This has a consequence, in two of the examples above, there are only two super tree of 4 elements that allows the condition. The third example is simply not correct, if we add a {4} and remove {1} the tree will not remain connected.

Try making more transitions. Also consider that at the opposite part of the tree, the labels with larger values, the structure works the same when moving on from the largest k labels and removing {n} and adding {n-k}... At the end you will find that the tree must follow a specific structure. For example, when k=4 and n=10:

• In the red square, we have a formed by the k smallest labels. They must follow a proper hierarchy structure. In every branch, the smallest label must be a label and the parent of each label must always be greater, up until k (4 in this case) which must be the root of the subtree. The reason for the hierarchy is that when transitioning from each target set that contains two of the smallest labels, the smallest label has to be removed, thus this label cannot act as a bridge between any other two larger labels.
• Inside the green square, a chain of all the nodes from k to n-k+1. This must be a chain, because of how transitions work. When transitioning from {3,4,5,6} to {4,5,6,7}, 3 must be connected to 4. When transitioning from {4,5,6,7} to {5,6,7,8} then 4 must be connected to 5 and so and so...
• Inside the blue square, also a subtree. This time it is the k largest labels. This subtree must also have a proper hierarchy, this time each parent must be smaller than each of its children.

The solution for this small case is already accessible. Given the tree, we can pick the starting and ending node of the chain. We can tell the chain must contain n - 2*(k-1) elements. Thus the distance between the two picked points must be n - 2*(k-1) - 1. These end points would get labels k and n-+1, respectively. Then we also need to verify that the subtrees rooted at each of the end points contain exactly k elements. If all checks up, the result is equal to the number of ways to assign labels to the first sub-tree multiplied by the number of ways to assign labels to the second sub-tree. This number of ways can be calculated using a dynamic programming approach.

How to assign labels to a sub-tree following a hierarchy

Let us quickly sum up the dynamic programming approach. We are given a subtree rooted at a given vertex. We also need to know its parent so that we understand what direction not to go when calculating the children (For different end points, the parents of the subtree roots change).

The base case is when the subtree contains only the root. Then we can only assign one label to the root (Either the lowest or the highest, depending on which of the subtrees we want to count, but for the sub-problem it does not matter).

The remaining case is when the root has children. We can assume that we already know the ways to assign labels to each children following the hierarchy. For example, when there are two children subtrees one with n1 nodes in total and the other with n2 nodes in total, we can assume that currently the labels that were assigned to each subtree are in the form {1,2,...,n1} and {1,2,....,n2}. We want to assign labels {1,2,...,n1+n2} to the two subtrees at the same time. This is equal to, out of a total n1+n2 labels, picking n1 labels to go to the first subtree. After picking which labels go to each subtree, we replace the original labels {1,2,...n1} and {1,2,...,n2} using the same order to make sure the hierarchies are not lost, so there is only one possible order for the labels. Then we put a label to the root, it must be larger than all the other labels, so there is only one way to assign a label to the root. This means that in total there will be: That is C(n1+n2,n1) * ways(first subtree) * ways(second subtree) ways to assign labels to the larger subtree still following the hierarchy. This approach can be adapted to when there are more than 2 children: First combine the first two subtrees into one hierarchy, then combine this new hierarchy with the third subtree and so and so.

2*k > n

The harder case is harder because of the labels that are common to each of the target sets. Each of the target sets must be a connected component. It is possible to show that this common intersection must also be a connected component. This intersection will have the labels that are not the largest and not the smallest. We will calls this group of labels 'middle'.

Once again we have to see what happens when we transition from a target subset to the next one. This time considering that the middle labels are always connected and remain so. Let us go back to the case with n=10, k=7.

• The first target set is {1,2,3,4,5,6,7}. {4,5,6,7} must form a connected component. Thus we only need to add {1}, {2}, {3} to whatever structure the connected component has. We can add {1,2,3} as a single subtree. Or in separate partitions. We can connect these subtrees to any of {4,5,6,7} and the structure {1,2,3,4,5,6,7} will be connected.
• But then we transition from {1,2,3,4,5,6,7} to {2,3,4,5,6,7,8} note that we deleted the smallest label, and added a new one. We once again have a process in which the smallest label is removed when performing transitions. In short, and reusing the knowledge from the previous analysis, all the subtrees of {1,2,3} that we added to {4,5,6,7} must follow a hierarchy.
• The same will happen for {8,9,10}, all of their subtrees must follow the hierarchy.
• {1,2,3,4,5,6,7} must be connected without the help of any of the vertices in {8,9,10}, this means that the subtrees of {1,2,3} will not have vertices from {8,9,10}. Similarly, the subtrees of {8,9,10} cannot have vertices from {1,2,3}.
• Note that {4,5,6,7} can have any shape as long as it is a connected tree. It is not necessarily a chain. And the various subtrees do not necessarily have to connect to 4 or 7.

The following is a possible labelling for a large graph (n=28, k=19):

The white nodes would get middle labels. Let us call the remaining labels small or big depending on whether they are smaller than the middle labels or larger. The red nodes get small labels and the blue nodes get big labels. Thus any label assignment in which the white nodes get middle labels, the red ones get small labels (but in a correct hierarchy) and the blue ones get large labels (also in a correct hierarchy) will work. What is important is that the middle labels can make any shape as long as they are connected and once you assign a big label to a node, all of its children must have big labels too.

One thing is to know how the graph should look after assigning the labels, another is to actually count the ways to do it.

How to count them

It is a complicated process with many decisions. Which group of nodes will receive middle labels? Then which of the children will be small and which big? Then we also need to assign the labels to the big and small subtrees such that they keep a certain hierarchy.

The first simplification comes from just taking each middle node individually. For each vertex, count the number of valid labellings in which that vertex receives a middle label. If we sum these results together the total will contain each of the valid results repeated by the number of middle labels. We can just divide the sum by this number and we get the overall result.

When calculating the number of ways to assign the labels starting at a middle vertex, we can ignore the actual labels we place on middle vertices and then multiply by the factorial of the (number of middle labels).

What we have left is the following recursive logic: Let f(p,x, a,b) be the number of ways to assign a small labels and b big labels to the sub-tree with root x (and the parent of the root is p):

• In a base case, we have a = (total number of nodes in the sub-tree) and b = 0. This means that the node and all its children must be given a small label. We also know the number of ways to label this following a hierarchy, it is just the same sub-problem we solved for the easier case.
• Likewise, when a = 0 and b = (total number of nodes) then we have to make the complete sub-tree have a big label.
• Else there are plenty of options. We can know for sure that the root has to belong to the middle. Some of the children may also belong to the middle. The rest should be big or small. In order to explain the logic, let us say the root has two children y and z, and we already know the results f(x,y, ?,?) and f(x,z, ?,?) for all pairs of combinations of big and small. Then the decision involves deciding how many of the big (b) and small (a) labels to assign to each subtree and combine their hierarchies afterwards (Using the same logic as above, e.g: C(total number of big labels, big labels used in the first child).). We can extent this logic to work with more than two children.

Solution

It has been a long journey, but we have finally reached the solution:

http://pastebin.com/4NmjuNnu (sorry, blogger is once again failing to allow me to paste my code.).

Read More

Topcoder SRM 560-562: You people have stood in my way long enough. I'm going to clown college!

SRM 560

So, I did not like SRM 561, or specifically I did not like what I did in it (So much that I didn't even want to write the editorial). It is actually very tiresome to spend some little extra time debugging a solution for an easy problem and then getting penalized for solving it. Most people in that match solved only that problem, so speed was the only difference in there. And that blows.

I think made exactly the same paragraph in the past, but I am tired of this lame situation, I don't want my matches to depend only on the easy problem anymore. Therefore, from now on (or until I get bored of the strategy) I will only open div1 hard and div1 medium until 10 minutes before the end of the match, then I will open the div1 easy. If I solve div1 easy under 10 minutes, that would be a good score. If not, then so be it, 0.00 score, but knowing topcoder, if I take more than 10 minutes in div1 easy, then it is a bad result anyway.

SRM 561

So, time to apply that strategy. That match was not great for such a suicidal strategy...

I opened div 1 1000, oh so something with trees? I thought it was going to be some sort of dp. But a complicated one. The idea that rng_58 eventually shared with me is far more elegant and mathy. It was a good thing I decided not to give it a try to code my (possibly wrong) initial dp idea.

I immediately opened div1 550. And I thought I could solve it. I had most of the correct ideas to solve it (See it as a tree, if you remove a node a forest remains). But my knowledge of nimbers was ... null. Somehow I never learned that stuff. So I tried to use a game theory dynamic programming, unfortunately, without knowledge of nimbers, you do not know how to combine games into a single game in which you can play each of the sub-games at choice... For some reason I assumed that you could finish one of the games and then go on. This was a wrong assumption. I coded something that was of course wrong, although I initially thought it was wrong because of code mistakes and not because of the idea...

Until there were less than 10 minutes left... I opened the 250 points problem to find out the problem statement was huge. Once I finally understood what to do, I knew I was not going to finish in time. It required quite some long code and I had only 4 minutes left... I still tried and failed.

I wrote the editorial I wonder how noticeable it is that I had no idea what a nimber is until I had to write this editorial...

SRM 562 - HAH! canceled

This felt the same. The div1 500 was quite complex to come up with and even If I did I would not be able to solve it. I had plenty of ideas of how to solve it in O(N^3), but they were all wrong... The closest I got was to fix a black point. Then sort all the other points clock-wise. Then whenever you pick two white points, you have to make sure the angle of the third black point is between them . If in addition the distance to the black point is not too close, that is a valid quad. I tried as hard as possible to finish coding this two-pointers idea but I also needed a tree... eventually I figured that it was not viable anyway, because the too close distance depends on the two white points... so using two pointers is not that friendly.

I also opened 1000, it seemed, once again like a complicated dp on a tree. I wonder what it really is.

Less than 10 minutes and I open 250. It seems time flies while reading a problem because I only had 6 minutes left after reading it... I knew the simulation would become repetitive in at most 50 steps. But I had some difficulties at first coding the idea in a good way that took less than 6 minutes to code. In fact, I needed far more time... Once I finished coding it, the challenge phase was supposed to start... Yet I notice that it was just the end of the coding phase? So the timer reached 0:00 but nothing happened.

They canceled it! HAH!

That strategy...

I knew the strategy would be very bad for my rating. If yesterday's match was rated, I would probably be in the 1600s area.

But I think it is necessary. I think that when I started in programming competitions I was fast enough to code the division 1 problems of all these matches in less than 10 minutes. I am not sure what made me far slower... I suspect it may have something to do with the whole 4 minutes that magically disappeared after reading the statement in SRM 562... Either way - The pressure of having only 10 minutes to solve a problem will hopefully make me faster eventually. And the exposition to harder problems before that might allow me to go back to solving div1 medium or hard at least once every other match. I am giving up rating for long term improvement, I hope... Plus seriously, if I am gonna fail a match, I'd rather it not be because I scored 160 in an easy problem that everyone solved.

Read More