SRM 522: Double meh

Slow day.

Div1 450 - CorrectMultiplication
(Link to statement)
I opened it, and it first seemed like I saw the problem before. After trying to remember it I used google in topcoder, and found a problem in SRM 190 that was about correcting digits. I still find it hard to believe this problem didn't appear before. Anyway...

So, I first tried to find an upper bound for the result. If positive values are allowed for A,B and C, then we can always try A=1, B=1 and C=1. 1*1=1. This means that the result cannot be larger than (a-1)+(b-1)+(c-1) (cost to transform them into ones). Later I thought of a lower bound: If a is set to 1, then b and c must be equal and the cost to make them equal is always abs(b-c). It follows that a possible bound is : (a - 1) + abs(b - c). And another is (b - 1) + abs(a - c). If we take the lowest possible of all those three choices, I think the maximum result ever will be close to 15000000000, ergo 64 bits result was not necessary.

Knowing an upper bound is only half the battle. We need to find values A,B,C that give the result. In these cases , it may be a good idea to first fix one of the values. But with an upper bound as large as 15000000000, it means that A can be at most a + 15000000000, that gives us quite a search space.

The trick here is to notice that A*B = C. If you think about it, Either A will be less than or equal to the square root of C, or B will be. So, since C is at most (c + UPPER), we can try numbers from 1 to squareroot(c + UPPER) as either A or B. The square root of 2500000000 is a large number but small enough to use in a loop.

Then we have to solve this sub-problem: Given a fixed A (or B), find the best pair (B (or A), C) such that: (A * B = C). We are doing it inside a O(SquareRoot(UPPER_BOUND)) loop, so this should be fast. This is the part of the problem in which I got stuck.

I tried some optimizations that weren't very good, I actually passed example tests, but giving it some combinations of high and low values I failed those cases. This may me notice that it was easy to get the problem wrong. So I was expecting many solutions to fail. The large amount of submissions I could see confirmed it.

Div1 250 - RowAndCoins
(Link to statement)

After trying and trying I decided to switch to the 250 when there were less than 15 minutes left for the match.

This is a case in which a lower constraint can actually make the problem harder. If the constraint was 50, many coders would have suspected of the easy solution instead of losing time implementing the uber-messy memoized recursion solution. I was one of those who mechanically did memoization.

Bitmask dp? It sounds complicated, but really it is not that much complicated. First, let me introduce you to a friend called vector dp.

So, instead of using bitmasks, the recursion will have the state (vec, player). vec is a vector of booleans - vec[i] is true if the i-th cell is not empty. Player is 0 if it is Alice's turn or 1 if it is Bob's turn. The result is true if the player whose turn it is will win the game given those values (and assuming both players play optimally).

Now we are using a vector as part of our recursion state. It does not matter. We can use all sorts of data structures as part of our state. What really (REALLY) matters when solving dp/memoization problems is that the recurrence is not cyclic.

Using a vector as key, means that we cannot use a normal array to store the values. That is not a big problem, we have to use the language's associative arrays. In c++, that means std::map, in Java, HashSet or TreeSet or whatever. In python, use dict().

Base case: If there is only one empty cell left in the row (use the vector), then one of the players won. If the remaining empty cell is 'A', then Alice won, else Bob. Note that if player the winner must be Alice to return true, and if it is 1 Bob.

The rest: There are more than 1 empty cell in the vector. The player should pick a group of contiguous cells, we can just try all possible combinations of starting and finishing cells such that they do not overlap with non-empty cells in the vector and such that at least one empty cell is left after that.

In this case, we have to update the vector for each possible move. The new vector will be vector2. In the next turn, the player changes, so the new player is !player (the negation) . We have vector2 and player2. We can call the recurrence (vector2, player2). If the other player will lose in this new instance of the recurrence, then it is a good idea for the current player to use that move, as it will guarantee him a victory.


Bitmasks?
The idea with bitmasks, is really to use a mask to represent the vec variable. Instead of a vector of booleans, each i-th bit in the mask represents whether the i-th cell is empty or not. Since the key is now a bitmask, we can represent it as a single integer, and we can use a normal array to store the values. That makes it easier to implement (and probably faster) than using that vector of boolean values.

The problem is that using bit masks is a guaranteed way to make the code hard to read. This tutorial by bmerry is really helpful and it taught me all about using bits to represent sets (arrays of booleans)..


Outcome
I was able to finish the 250 very fast (for me, considering it is a messy bitmask dp). I was not very sure if it would pass (A random bug is always a possibility). I had 5 minutes left so I kept trying the 450 but I couldn't do much.

For the challenge phase, I knew there were going to be many failed 450s in the room and I also knew that I had to get a successful challenge if I wanted to avoid a terrible score. So I was ready to hammer.

I am very slow when challenging and I'd rather read the code before challenging, so what I do is pick the coder with the median rating in the room. The aggressive challengers generally pick the lowest rating coders to read first. I read a code for a while and at first it seemed like it would time out. I wasn't sure but I eventually decided to challenge it. Got some lucky 50 points.


At the end those points were very helpful, I ended at position 141st. Which is not very good but at least good enough to win 8 rating points.

Div1 250 again
After the challenge phase, I wanted to see what could possibly explain the large scores in 250. It turns out there is a very easy to code solution. If there is an A in any of the extremes of the string, Alice can win in one turn. What is cooler is that this is not only a sufficient condition but also a necessary condition. If both extremes contain a B, there is nothing Alice can do to win.

If Alice covers one of the Bs in the extremes, then she will either leave only the other B empty, which means Bob wins. Or she will leave the B and some extra space contiguous to it which Bob can cover and still win.

So, Alice has to pick a space in the middle of the row to cover. After she does this, all Bob ever needs to do in any turn is to cover as many contiguous As as he can until he consumes them all. Alice will try to cover contiguous Bs, but there are more groups of contiguous Bs than As.

Commented code for division 1 250:

   1 struct RowAndCoins
   2 {
   3     string cells;
   4     int t;
   5     
   6     int mem[1<<14][2];
   7     
   8     
   9     // Will player #player win in this situation?
  10     //  the i-th cell is non-empty if and only if the i-th cell in mask is 1
  11     bool rec(int mask, int player)
  12     {
  13         int & res = mem[mask][player];
  14         if ( res == -1) {
  15             // Has the game ended? We need to count the number of empty cells
  16             // and find the type of the only empty cell if that's the case.
  17             int ec = 0;
  18             char fc = '?';
  19             for (int i=0; i<t; i++) {
  20                 if ( !(mask & (1<<i) ) ) {
  21                     ec ++;
  22                     fc = cells[i];
  23                 }
  24             }
  25             
  26             if (ec == 1) {
  27                 // only one empty cell.
  28                 // If it is Alice turn's she wins if and only if the empty cell is 'A'
  29                 // If it is Bob turn's she wins if and only if the empty cell is 'B'
  30                 res = ( (player==0) == (fc=='A') );
  31             } else {
  32                 res = 0;
  33                 // Try all possible moves.
  34                 for (int i=0; i<t; i++) {    //i is the starting cell
  35                    int taken = 0;
  36                    for (int j=i; j<t; j++) {  // j is the last cell of the group.
  37                         if ( !(mask & (1<<j) ) ) { // all the cells in the group
  38                                                    // must be empty
  39                              taken++;
  40                              if ( ec - taken >= 1) {  //one empty cell must be left.
  41                                  
  42                                  // The new mask.
  43                                  // update all the cells between i and j, inclusive
  44                                  // with 1 bits.
  45                                  int nmask = ( mask | ( (( 1<<taken )-1) ) << i );
  46                                  
  47                                  // If the next player loses with the new match,
  48                                  // the current player has found a winning move.
  49                                  res |= ( ! (rec(nmask, !player) ) );
  50                              }
  51                       } else {
  52                           break;
  53                       }
  54                   }
  55                 }
  56                 
  57             }
  58         }
  59         return res;
  60     }
  61     
  62     string getWinner(string cells)
  63     {
  64         t = cells.size();
  65         this->cells = cells;
  66         // Initialize the table
  67         memset(mem,-1,sizeof(mem));
  68         
  69         // If Alice wins when the board is empty, then return "Alice".
  70         return rec(0, 0) ? "Alice" : "Bob";
  71     }
  72 };

Div1 450 - revisited
Once you have a fixed A, you can see that there is an equation A*B = C, or actually C = A*B. Smaller values of B will yield smaller values of C. It turns out you can just assume that C will have to be close to c. You can do k = c/A, and then just know that B will be either k-1, k or k+1. Or you can also note that there are four equations, (c + cost_c) = A * (b + cost_b), (c - cost_c) = A * (b + cost_b), (c + cost_c) = A * (b - cost_b) and (c - cost_c) = A * (b - cost_b), you can try finding the lowest cost_b, cost_c for each equation.