Wednesday, October 10, 2012

TopCoder SRM 557 - finally

SRM 557


It feels like it has been ages since the last SRM. Here we go again.

It began with a bang. The 250 points problem reminds me a bit of a problem I wrote in the past, but I cannot remember its name. Something with black and white squares. They are very different problems, but I do remember that that problem was very tricky. This 250 points problem had like 8 examples, so I sort of felt it was going to have tricky written all over it. And decided to be careful rather than fast.

Div1 250: FoxAndMountainEasy

So, you start at height h0, is there is a sequence of n up and down moves such that:

  • Each up move increases height by 1
  • Each down move decreases height by 1. It is invalid to go bellow height 0.
  • The given string history is a substring of the sequence of moves.
  • The height after all of that stuff is hn

n is at most 100000. This problem gave me the feeling that it was initially intended for the TCO finals, but later they adapted it to SRM difficulty by reducing the constraints and adding plenty of examples.

The solution goes as follows: First process the history substring. After executing this series of moves, how much will be the netChange of the current height? (This is just equal to (number of Us) - (number of Ds). So if your current height is b before starting the sub-sequence of moves, the height after doing so will be b+netChange.

There is a catch though, if there are many D characters in the history sequence and not preceded by enough U characters, then the starting height before running the sequence, b, cannot be too small. b has to be large enough such that the current height while executing the subsequence is never bellow 0. (This can be calculated with a simple for loop - just simulate the movement starting at height 0, and remember the lowest height, if this lowest height is negative, then -lowest height is the minimum height value for b). We will call this required height before the subsequence - minStart.

After you have two things: netChange and minStart. We just need to do some extra things. There are (n - size(history)) moves left that we have to pick. Now here is the thing, the order of the moves does not matter a lot. We really only care about the height before the sub-sequence being at least minStart. Let us say that we are going to make u up moves, this means we will do d = (n - size(history) - u) down moves (in addition to the moves in history). Since we want the height before running the steps of the subsequence to be as large as possible, then it is better to first run all the u up moves before the sub-sequence and then all the d moves.

Due to the small constraints, we can just loop for a possible value of u between 0 and n-size(history). Then verify a couple of conditions: a) Is the height after running the first u moves at least minStart? . and b) Is the height after running all the moves, including the u up moves, the moves in history and the d down moves equal to exactly hn?. If you find a value of u for which the conditions are true, the result is YES.

#define for_each(q, s) for(typeof(s.begin()) q=s.begin(); q!=s.end(); q++)
struct FoxAndMountainEasy
{
string possible(int n, int h0, int hn, string history)
{
int netChange = 0;
int minStart = 0;
for_each(ch, history) {
// just simulate the movement, if ch=='U', increase
netChange += ( (*ch == 'U') ? 1 : -1);
// too low? remember this for minStart
minStart = std::max(minStart, -netChange);
}
// Pick a value for u, the number of up moves done right at the start
// and before the moves in the history string:
for (int u = 0; u <= n - history.size(); u++) {
// the number of down moves to do later:
int d = n - history.size() - u;
// Do things work out?
if ( (h0 + u >= minStart) && (h0 + u + netChange - d == hn) ) {
return "YES";
}
}
return "NO";

}
};

I took my time. Also , I made a couple of mistakes. It is a good thing the examples were so strong. (At first, I was first running all the up moves , then the down moves and finally the history moves. That is not correct.). I knew though that even with the strong examples, there were going to be many challenge opportunities. (And I also was not sure I was not missing a corner case).

Happened later

Then I opened the 550 points problem. Tried many things but faced some dead ends. Went back to 250, trying to think of corner cases. Opened 1000 5 minutes before the end of the coding phase and it seemed interesting.

The challenge phase was interesting because some people had very different solutions , and some were extra clever (or perhaps too clever?). I knew many of those solutions were going to have bugs, but it is not really easy to read them.

I was lucky though, because I caught a solution with an obvious bug. It began by checking if (hn - h0) % 2 != n % 2 and returning "NO". This logic is correct, and perhaps the approach needed this extra check. But there is something very wrong about the languages like c++ and Java that we love so much. Some language designers thought it is a useful convention to make the % operator return a negative number if the dividend is also negative. In my opinion, this feature is never useful and almost always just a cause of bugs. Modular arithmetic works by stating -1 belongs to 1 modulo 2. So it does not make sense. This bug with % operator has caught me in the past, so this time I could sense it and gained 50 points. Then I tried to find more instances of that mistake, but other coders doing this parity check took better previsions (In some cases though, I am not sure if intentionally).

Comments / etc?

Feel free to post your own opinions and accounts. I liked this match. It was a bit tough. But it is good to be back at competition. I am tired of watching people compete.

6 comments :

Smit Hinsu said...

I think you were pointing to your this question with parity :

http://community.topcoder.com/stat?c=problem_statement&pm=11808

vexorian said...

It was something with black and white squares. You had to put black and white squares, and I think two consecutive squares of the same color meant decrease size and two different squares meant increase. Then you are given a substring like BWWBWB...B and then return if it is possible to have it as a substring of a sequence that ends in a certain height. Still can't remember the problem name.

vexorian said...

Oh boy, I was so close to solve the 550-points problem. I got the transitive closure, knew I had to ignore girls that would eventually protect themselves. I just got stuck when I started to see it as independent set rather than path cover. Oh well.

prashant said...

Hi,
This is for Incubator srm 557 div 1 500.
i have been trying this question and i think i have got the logic right , but it still fails the system test i.e. gives wrong ans on some questions. Below is my code . It would be very helpful if you out the bug in my logic/code.
Basically i am making a girl magical only if she doesn't have a direct/indirect path to any other magical girls in the set (including herself).



import java.util.*;
import static java.lang.Math.*;
public class Incubator
{
int l=0;
long luv[];
public int maxMagicalGirls(String[] love)
{
l=love.length;
luv=new long[l]; // represents the graph love
for(int i=0;i// floyad warshall
return get(0,0,0);
}
// m=magical , p=protected we make girl i magical only if it doesnt has path to any of the existing magical girls
int get(int i,long m,long p)
{
if(i>=l)return 0;
if((m&1L< // not eligible (either already magical or already protected or loves itself)
if(luv[i]==0)return 1+get(i+1,m|1l<// has no friend , so wont affect the protected set , so we add it simply
int max=get(i+1,m,p);
if(check(i,m,p))max=max(max,1+get(i+1,m|1l<<i,mark(i,p)));
return max;
}
// checks if a girl can be turned magical or not (possible if and only if it has no path to any of already eligible magical girls)
boolean check(int i,long m,long p){ return (m&luv[i])==0;}
long mark(int i ,long p){ return p|luv[i];} // marks all girls as protected which are loved by girl i (directly or indirectly)
}

If my code seems a bit complex to read , please comment , i want to improve it

prashant said...

sorry i think my last post got deformed .. i have posted it at topcoder forums here http://apps.topcoder.com/forums/?module=Thread&threadID=766152&start=0&mc=1#1623413 .. please see it

vexorian said...

Usually, when you have no proof that an approach is correct, we should assume it isn't. Your approach is greedy and the question is if the order in which two magical girls that don't have any path to any of the already-set magical girls could affect the result. I am quite sure it does.

For example, consider this graph:

1 -> 2
1 -> 3
3 -> 2

In the first step, we can pick 1, 2, 3 as the first magical girl following your rule. If you pick 1, you will gain two points (2 and 3) . If you pick 2, you will gain 0 points and if you pick 3, you will get 1 point.

When posting code in blog comments, it is probably best to use a pastebin: http://pastebin.com/