Saturday, March 30, 2013

SRM 574 editorial supposedly ready

The editorial for SRM 574 is in a state that can be published. https://apps.topcoder.com/wiki/display/tc/SRM+574.

I would love to say that the huge delay was because I took too long to solve div1 hard quickly (as it usually happens). But this time I had bigger issues, while I actually sort of understood all the problems in the match rather quickly (thanks to help from admins in div1 hard). My on-going recovery from health issues made me take much longer than I planned/expected. Sorry for that, but I am feeling better now.

I think the div1 1050 explanation is terrible. Maybe I will improve it.

It was a fun problem set.

Monday, March 25, 2013

SRM 574: Stupid "dp sense"

It has been a long week, I got chicken pox and had to wait a week to get better. I was lucky that there were no SRMs or anything important going on school-wise during this week. But it was still quite awful and boring.

I had some difficulties starting up the arena, was the first time in a week I used my big computer. And it was acting up. I could only open the medium problem around 10 minutes late...

Div1 450: The one with a polygon

You have a polygon of at most 18 points. Numbered in clockwise order from 1 to 18. A guy drew segments visiting points: points[0], points[1], ... , etc. You have to complete the tour of points so that all points in the polygon are visited, and the last segment finishes back to points[0]. So for example you will use segments: points[0] -> points[1] -> points[2] -> -> x > y > z > points[0]. Each point must belong to exactly two segments. And each of the new segments you add must cross a previous segment.

For most of the time I was thinking that with N <= 18, the solution was exponential dp: O(N * (2N)). The slight issue was how to find out, from just the set of already-visited points, whether or not a new segment you add will cross an already visited segment.

Turns out that it was not so hard. Let us say you currently are at point p, and that you have a set mask of points that were already visited. Can you create a segment between p and another point q? The segment p -> q will split the polygon in two parts. The trick is that if each of the two parts contains points that where already visited, then (p -> q) will intersect with something, and if either of the parts does not contain a visited point, then (p -> q) will not intersect anything. The demonstration relies on the fact that all points that were already visited HAVE to be connected, so if these two parts contained visited points, there has to be a connection between the parts.

using namespace std;
typedef long long int64;
#define long int64

struct PolygonTraversal
{
vector<int> points;
long dp[1<<18][18];

long rec(int N, int mask, int p)
{
long & res = dp[mask][p];
if (res == -1) {
if (__builtin_popcount(mask) == N) {
int d1 = ( (points[0]-1) - p + N) % N;
int d2 = (p - (points[0]-1) + N) % N;
res = ( d1 != 1 && d2 != 1);
} else {
res = 0;
for (int q=0; q<p; q++) {
if ( ! (mask & (1<<q) ) ) {
// q+1, q+2, ... p-1
int side1 = ( ( ( 1<<(p - q - 1) ) - 1) << (q+1));
int side2 = ( (1<<N)-1 ) - side1 - (1<<p) - (1<<q) ;
if ( (side1&mask) && (side2&mask)) {
res += rec(N, mask | (1<<q), q);
}
}
}
for (int q=p+1; q<N; q++) {
if ( ! (mask & (1<<q) ) ) {
int side1 = ( ( ( 1<<(q - p - 1) ) - 1) << (p+1) );
int side2 = ( (1<<N)-1 ) - side1 - (1<<p) - (1<<q) ;
if ( (side1&mask) && (side2&mask)) {
res += rec(N, mask | (1<<q), q);
}
}
}
}
}
return res;
}

long count(int N, vector <int> points)
{
this->points = points;
memset(dp, -1, sizeof(dp));
int mask = 0;
for (int i=0; i<points.size(); i++) {
mask |= ( 1 << (points[i]-1) );
}
return rec(N, mask, (*points.rbegin()) - 1 );
}
};
#undef long

So we can use a dynamic programming approach with state (p, mask) p, is the current point and mask the set of already-visited points. There is a catch, and it is that you need to verify if the two parts split by q are correct without using an extra loop. It is possible with bit operations if you are clever...

Div1 275: The one with the number game

I tried to solve div1 1050, seemed hard. So I waited till there were 10 minutes left before opening div1 275. After looking to the division scores, it seemed unlikely I would be able to solve this problem in under 10 minutes, but I have to be consistent with my strategy if I want to improve...

Two guys are playing a game. Each guy has a string (number) of up to 9 characters. In each turn, a player can either reverse his string, or remove the last character from it (divide the number by 10). The first player wins if the two strings become equal at any point of the game before 1000 turns. If after 1000 turns, the strings are still not equal, the first player loses.

After doing contests, specially TopCoder contests for a while, you develop a "dp sense" you can quickly notice when a problem can be solved using dynamic programming. And this is one of those problems. But I also knew that the dynamic programming approach would have been very long to code. I also suspected there was going to be a simpler approach... But with 10 minutes, I didn't have much time to think (I think I was wrong, it was possible to think of the simpler, faster to code approach in 10 minutes, I think). So I started coding the dynamic programming approach. I was too slow. I could only finish debugging it after the intermission phase...

string sa, sb;
char dp[1002][9][10][9][10][2][2];

bool rec(int t, int a1, int a2, int b1, int b2, int ad, int bd)
{
char & res = dp[t][a1][a2][b1][b2][ad][bd];
if (res == -1) {
// compare
res = 0;
if (a2 - a1 == b2 - b1) {
res = 1;
for (int i=0; i < a2 - a1; i++) {
char ch1 = sa[a1 + i];
char ch2;
if (ad ^ bd) {
ch2 = sb[ b2 - 1 - i];
} else {
ch2 = sb[ b1 + i];
}
res &= (ch1 == ch2);
}
}
if (res != 1) {
if (t < 1001) {
if (t % 2 == 1) {
if( (a1 != a2) ) {
if (!ad) {
res |= rec(t+1, a1, a2-1, b1,b2, ad,bd);
} else {
res |= rec(t+1, a1+1, a2, b1,b2, ad,bd);
}
}
res |= rec(t+1, a1, a2, b1,b2, !ad,bd);
} else {
res = 1;
if( (b1 != b2) ) {
if (!bd) {
res &= rec(t+1, a1, a2, b1,b2-1, ad,bd);
} else {
res &= rec(t+1, a1, a2, b1+1,b2, ad,bd);
}
}
res &= rec(t+1, a1, a2, b1,b2, ad,!bd);
}
}
}
}
return res;
}

string determineOutcome(int A, int B)
{
{ ostringstream st; st << A; sa = st.str(); }
{ ostringstream st; st << B; sb = st.str(); }
memset(dp, -1, sizeof(dp));
return rec(1,0,sa.length(), 0, sb.length(), 0,0) ? "Manao wins" : "Manao loses";
}

As you can see, the approach is VERY complicated.

The simpler approach is nicer: 1000 steps is a lot of time. It is enough for player 1 to remove all of the digits of the string. (Note that at any time, the strings in the game are substrings (possibly reversed) of the original strings).

Imagine if the second player's string (or its reverse) was a substring of the first player's string. The first player can eventually remove enough characters. The second player cannot stop the first player from winning. If the second player removes a character, the second string will still be a substring. If it is reversed, it will also still be a substring. The first player will eventually be able to remove enough characters and reverse if necessary.

In the other case, if the second player's string is not a substring and neither a reverse of a substring of the first player's string, the second player can just constantly reverse his own string. The first player can never reach a good string, because the second player will always have some extra characters.

A STL implementation of this solution looks like this:

string determineOutcome(int A, int B)
{
string s, t;
{ ostringstream st; st<<A; s = st.str(); }
{ ostringstream st; st<<B; t = st.str(); }
bool r = 0;
if ( s.find(t) != string::npos ) {
r = 1;
}
reverse(t.begin(), t.end());
if ( s.find(t) != string::npos ) {
r = 1;
}
return (r ? "Manao wins" : "Manao loses" );
}

Outcome, Comments? Etc.

I passed div1 450. I got 38 rating points. It is nice that I am actually winning rating points using the "suicidal" strategy. This was a good problem set, although I think the unusual problem scores were not necessary.

Saturday, March 16, 2013

SRM 573 Editorial supposedly complete

It is there: http://apps.topcoder.com/wiki/display/tc/SRM+573.

I think that besides of the hard problems of each division, the other problems were the perfect anti-editorial storm. Actually easy problems, with difficult proofs...

I think that the proof for div2 500 is currently really poor. To add insult to injury, the div1 250 explanation relies on it. I will hopefully improve it when I am feeling better - currently my brain is at 50% capacity.

SRM 573 editorial WIP: Div1 850: WolfPack

Div1 850's explanation is ready.

Link to problem statement | Link to editorial

This was a great problem. Unfortunately it is also the kind of problem that has a trick that you either see or you don't. I would love to know what in the minds of target / red coders allows them to think of such creative ideas. But I don't.

My current plan is to finish the rest of the editorial tonight. Unfortunately my deteriorating health (I am not kidding) might get in the way and require me to add a whole day delay. But I will still try.

Thursday, March 14, 2013

SRM 573: Lack of speed

It is another day to use the suicidal strategy , this time having less than 10 minutes to solve div1 250 has really affected me.

Div1 850

You have up to 50 pebbles in points (x,y). In each step you can move a pebble one unit up, down, left or right in the coordinate system. Count the total number of ways in which you can move all the pebbles to the same position in at most m steps.

This sounds like an "optimize the dp" problem. I was actually able to reduce plenty of things.

For example, it is possible to first solve this problem: Given x[] and m, how many ways are there to make all elements of x equal in at most m steps by reducing or increasing each element by one in each step? (The coordinates are almost independent)

I switched to div1 450. When I solved div1 450 I returned to this problem. But it is not so easy. Actually, I can't remember the last div1 850 points problem that was actually easy :P

Div1 450 - The one with skying

You got a bidirectional graph/network of some locations. You want to be able to reach location n-1 starting up from location 0. The locations have heights. It is only possible to move from location i to location j if the height at i is greater than or equal to the height at j. Fear not, because you can change any location's height from p to q with a cost |p - q|. Return the minimum cost required to change the locations so you can move from 0 to n-1.

The first observation was that, if you define your current position as (location, height), defining the current location you are standing at, and the height (possibly changed) it has, then you can move to (location2 , height2), with a cost of abs(height2 - initialAltitude[ location2 ] ) as long as height2 is less than or equal to height.

This approach is correct. It might appear possible to move to the same location twice and change the height twice. But it is possible to prove by contradiction that such sequence of moves will not be the minimum. So we can use Dijkstra to solve this.

The problem is that the heights can be very large. But not really. You just have to notice that it never makes sense to set the height of a mountain to a height that does not already exist in initialAltitude. There are only O(n) such values.

As I write this, the system test ended and I pass!

typedef long long int64;
#define long int64

const char B_INF = 0x7F;
const long INF = 0x7F7F7F7F7F7F7F7FLL;

#define var(q, s) typeof(s) q = (s);

struct SkiResorts
{

long dist[50][50];
set< pair<long, pair<int,int> > > Q;
// I do Dijkstra by using a set<> instead of a priority queue, because it
// is possible to remove larger elements. Makign the memory complexity
// O( log( |V| ) ) as opposed to O( log( |E| ) )
//
// The downside is that the code is horrible. But you really had to learn STL
// anyway :P
void Dijkstra_push(long d, int p, int height)
{
if ( dist[p][height] > d ) {
var(iter, Q.find( make_pair( dist[p][height], make_pair(p, height) ) ) );
if (iter != Q.end() ) {
Q.erase(iter);
}
dist[p][height] = d;
Q.insert( make_pair(d, make_pair(p, height) ) );

}
}


long minCost(vector <string> road, vector <int> altitude)
{
memset(dist, B_INF, sizeof(dist));
int n = road.size();
for (int i=0; i<n; i++) {
long dif = abs( altitude[i] - altitude[0] );
Dijkstra_push( dif, 0, i );
}
while ( Q.begin() != Q.end() ) { // O ( log(n*n) * n * n * n * n )
var(iter, Q.begin());
long d = iter->first;
int p = iter->second.first;
int height = iter->second.second;
Q.erase(iter);

// You can move from p to i...
// with some cost...
for (int i=0; i < n; i++) {
if (road[p][i] == 'Y') {
for (int newheight = 0; newheight < n; newheight++) {
if ( altitude[newheight] <= altitude[height] ) {
long newd = abs( altitude[newheight] - altitude[i] ) + d;
Dijkstra_push( newd, i, newheight);
}
}
}
}
}
long res = INF;
for (int fh = 0; fh < n; fh++) {
res = std::min(res, dist[n-1][fh] );
}
return (res >= INF) ? -1 : res;


}
};
#undef long

Div1 250 - The one with teams of three

There is an array of 3*N strengths of team members. Your team has strengths 0, 1 and 2. There are other teams N-1 teams, but you have no idea of which team members go to each team. Return 1 + the maximum number of teams with a strength greater than yours. The strength of a team is equal to the minimum of its strengths + the maximum of its strengths.

With only 5 minutes left and not thinking of anything, I decided to implement the easiest greedy approach, sort the strengths and make teams with the 3 largest strengths, second 3 largest strengths and so on.

This turned out to fail the last example case.

I had 3 minutes left, when I finally thought of the solution:

After you sort the strengts, you have a maximum strength, if you find the minimum possible strength such that minimum + maximum > your strength, then this is a good team to create. Repeat until all teams are created or there are no good teams anymore.

int worstRank(vector <int> strength)
{
int n = strength.size();
int you = 0;
int mx = strength[0];
int mn = strength[0];
for (int i=1; i<3; i++) {
mx = std::max(mx, strength[i]);
mn = std::min(mn, strength[i]);
}
you = mx + mn;
// maximize the number of teams with a better score than you
sort( strength.begin() + 3, strength.end() );
int rank = 1;

vector<bool> seen(n , false);
for (int i = strength.size() - 1; i >= 3 ; i --) {
if (! seen[i]) {
for (int j = 3; j < i; j++) {
if (! seen[j]) {
if (strength[i] + strength[j] > you) {
int k = j + 1;
while( k < i && seen[k]) {
k++;
}
if (k >= i) {
return rank;
}
seen[i] = seen[j] = seen[k] = true;
rank ++;
break;
}
}
}
}
}

return rank;

}

By the time I finished debugging this implementation ,the challenge phase started.

Update: Turns out it was still wrong, replaced n with i in some conditions and it passes.

Comments, etc?

It was an ok match, I wish I solved div1 250, but I am fine with only solving div1 450. Plenty of coders managed to get 450 wrong.

TopCoder SRM 572, editorial for div1 hard: NextAndPrev

Finally! , this one was hard. Since I couldn't finish it during the 48 hours window I usually reserve, I had to use small portions of free time during the week to finally understand the very helpful comments that rng_58 added to tourist's passing code. Yesterday I finally got it. But I had to do homework so I waited till today to finish it.

Link to problem statement | Link to editorial

This was tough, but in hindsight it doesn't look so hard. I think it was important to have a good starting point with the easy division 2 version of the problem. I had to update the explanation for that problem so I can use it as a base.

I have to add the summary to the editorial (did I mention how much I hate writing the summary?), I will also do language corrections and those things and then the editorial will be ready to publish.

Sunday, March 10, 2013

TCO 2013 Round 1C editorial

Round 1C editorial is in a state that can be called "ready to publish". I will probably still do some more fixes and so and so

Read it here

This was a interesting round. according to practice rooms I would have gotten around 690 points. 250 took me longer than it took to your average high rated coder, that is because it occurred me to use binary search and it took some extra time to code. 500 was easier, I had an overflow bug but I still passed, later I was able to find proof that the implementation is such that the overflow cannot happen.

Contrary to my expectations, this match had the hardest problem out of the 3 round 1s. 1000 was quite hard. Even though I could think of a solution in time for my 75 minutes coding phase simulation, It took me a couple of hours to finish the code. And a couple of more hours and external to understand how to come up with those simpler-looking approaches. This is the reason I needed a day instead of half a day to solve finish this match's editorial.

Both 500 and 1000 are interesting in that experience could have actually been a liability instead of an asset. In 500, I think many coders may have failed a challenge or two trying to challenge a solution that seems to overflow but doesn't. In 1000, I think that solving HyperKnight before had an effect in me that lead me to a complicated solution instead of trying harder to find simplifications. Sometimes our experience behaves more like preconception than experience.

I still remember that SRM in which the division 2 version of a problem had larger constraints than the division 1 version. Because people in division 1 version would take those small constraints as a hint to implement a complicated exponential time solution. Meanwhile, division 2 coders easily noticed the two-lines greedy solution (and most likely didn&apot; prove it).

-----------------------------

About SRM 572's editorial, I really wouldn't hold my breath :(. Still trying to solve that division 1 hard. But remember that you can see the editorial preview for the other problems here.

Friday, March 08, 2013

SRM 572, d2 250 - NextOrPrev editorial (WIP)

And the editorial now has explanations for the easier problems of SRM 572. Language corrections and tweaks not done yet.

Problem statement

Link to editorial explanation.

This problem was a bit harder than usual for division 2 Medium. I mean, it is not exactly easy to figure out greedy works. And when you do, you might miss one of the conditions necessary for the case to be solvable and fail system tests ( Like what happened to me when I tried it in the practice room.).

It was fun making pictures for this problem. Today I was thinking about how natural using Inkspace became to me. Truly, when you do something plenty of times you start getting good at it. I have been writing editorials for years now and I remember not knowing as many Inkscape tricks as I do know.

The whole Inkscape thing became such a fluid thing that on Wednesday, when I was asking to make flow charts for a college assignment (Really? Flow charts? What are we, eight?). I preferred to grab Inkscape than do it by hand or with a diagram designer.

I am still horribly clueless about the division 1 hard. Which is a much, much, much, much harder version of this problem. Letters are allowed multiple times, and it is possible to move from 'z' to 'a' and from 'a' to 'z'.

Thursday, March 07, 2013

SRM 572 Editorial WIP : Div1 500 and div2 1000 (and div1 250)

Development for this editorial is a bit in difficult waters. Solving the div1 hard problem might take a while. But here are some explanations for the easier (less hard) problems.

DistinctRemainders: Div2 Hard | Link to problem statement

EllysBulls: Div1 Medium | Link to problem statement

Update: NewArenaPassword: Div1 Easy | Link to problem statement

Finding out the division 1 medium solution was a bit embarrassing. Meet in the middle was actually one of the first ideas I had for the problem. But something made me believe that meet in the middle wouldn't work because of memory. It makes no sense, the limit on the number of things to store in memory is O(105), it does not matter if the number of valid keys that could be generated is O(550), because we will use a std::map anyway.

The remaining problems (except for div2 250) are looking to be tougher to explain. Div2 500 and div1 250 are not too easy to prove. Div1 1000 is looking undoable right now and I am yet to receive the usual help message from admins about it. Codeforces is as always the only place to have explanations for these div1 hard problems and as usual the explanations are in Russian and very short ^^.

Div2 500 is much harder than it should have been. I think using the problem that was div1 250 would have been ok for this slot.

As you can see, the editorial is so preliminary right now it doesn't even have the usual problem statistics and links. It will be fixed soon, I hope.

Wednesday, March 06, 2013

SRM 572: hmnn

As I write this around the end of the challenge phase. I can tell for sure that I solved the easy problem correctly. The medium one is a bit more of a mystery.

Div1 500: The one with digits

You have a set of guesses for a number of at most 9 digits. For each guess, you also know the number of correctly guessed positions it had. If there is a unique result for the number, return it. If there are no results, return "Liar", else return "Ambiguity".

This was looking tough until I noticed that the number of digits is at most 9. It is large for trivial brute force, but not TOO MUCH larger.

My first approach was optimized backtracking. Makings sure to crop the search whenever there is certainty a digit position would be wrong.

It is also necessary to cut the search whenever you find more than one result.

First tests seemed promising. But I was able to come up with a test case that made it time out. (A Liar case).

But it seems unlikely that a non-"Liar" case would require many steps. So I added something that stops the search if it had too many iterations. Then it instantly returns "Liar".

This makes the approach at least hard to challenge. I wonder if it can beat system tests. To reduce the probability of a crafted case laying in the system tests, I made it randomize the order in which it picks the characters ^^.

Update: As I write this post, I failed this problem in the system tests. The writer found a case that is not Liar and has a solution further away from the ones I try.

Div1 250: The one with strings

Your oldPassword must be changed in a way that the K first characters are equal to the K last characters. Return the minimum number of characters to change.

When the K first and last characters do not overlap, this is kind of trivial, you got two strings that have to be the same.

When they overlap, it is a bit different. For example: "lol" and K=2. This time all of the characters have to be the same.

I think that because I once wrote a problem that had a similar solution, I decided to use DFS right away. Each letter belongs to some group of letters that must be made equal. Then for each group, it is easy to pick a letter that minimizes the cost - the one that appears the maximum number of times.

It works as follows:

For each i (Between first K or last K characters): If i is less than K, it is connected to another character in the last K characters. And vice versa. Each connected component must be equal. We can use a Depth-First search to find each of these components.

This problem was enough to have a relatively good result. My prior experience writing for that netease contest receives all the credit.

Challenge phase, comments, etc

I found a submission for the medium problem that had the simple brute force I tried at first. The one without cutting the number of tries. Even though I had the challenge case prepared, I took too long to paste it. A red coder got those 50 points.

It was a good match. Good to see optimized brute force does not pass easily in the medium problem.

Saturday, March 02, 2013

Another week another TCO 2013 editorial: 1B

The editorial is "ready" (I am legally bound to put ready between quotes).

Check it out at: http://apps.topcoder.com/wiki/display/tc/TCO+2013+Round+1B

It was a fine problem set. It was easier than 1A as expected. But I still managed to make a very lame mistake in the hard problem in my first try (Forgot about the last character in odd strings). I would have scored 245 + 433. This is not counting for the usual nervousness that strikes me during a real match. I am not sure if it would make my scores worse or better. I solved 500 with dynamic programming the first time, it was overkill.

I spent all my clear-brain time this afternoon trying to think of a good argument to prove 250. Everyone seems to know to use that solution. But at least to me it is hard to find out why it works. It is *not* something as simple as pairing min with max minimizes the maximum" , because in an example like: 1,7,7,8, the pairs are 1+8, 7+7, note how the maximum is in the middle this time.

I am also going through tons of stress related to a loved one being sick. So I thought it was better to finish the editorial quick and maybe later when/if I find the proof update the editorial, instead of waiting too much before releasing it (Must focus). Hopefully the editorial is not awful.