Deceitful War (Google Code Jam 2014 Qualification Round Problem D) Solution

Problem

Naomi and Ken sometimes play games together. Before they play, each of them gets Nidentical-looking blocks of wood with masses between 0.0kg and 1.0kg (exclusive). All of the blocks have different weights. There are lots of games they could play with those blocks, but they usually play something they call War. Here is how War works:



Each player weighs each of his or her own blocks, so each player knows the weights of all of his or her own blocks, but not the weights of the other player's blocks.
They repeat the following process N times:

Naomi chooses one of her own blocks, with mass ChosenNaomi.
Naomi tells Ken the mass of the block she chose.
Ken chooses one of his own blocks, with mass ChosenKen.
They each put their block on one side of a balance scale, and the person whose block is heavier gets one point.
Both blocks are destroyed in a fire.






Naomi has realized three things about War. First, she has realized that she loses a lot. Second, she has realized that there is a unique strategy that Ken can follow to maximize his points without assuming anything about Naomi's strategy, and that Ken always uses it. Third, she has realized that she hates to lose. Naomi has decided that instead of playing War, she will play a game she calls Deceitful War. The great thing about Deceitful War is that Ken will think they're playing War!

Here is how Deceitful War works, with differences between Deceitful War and War in bold:



Each player weighs each of his or her own blocks. Naomi also weighs Ken's blocks while he isn't looking, so Naomi knows the weights of all blocks and Ken only knows the weights of his own blocks.
They repeat the following process N times:

Naomi chooses one of her own blocks, with mass ChosenNaomi.
Naomi tells Ken a number, ToldNaomi, between 0.0kg and 1.0kg exclusive. Ken, who thinks they're playing War, thinks the number Naomi just told him is ChosenNaomi.
Ken chooses one of his own blocks, with mass ChosenKen.
They each put their block on one side of a balance scale, and the person whose block is heavier gets one point.
Both blocks are destroyed in a fire.






Naomi doesn't want Ken to know that she isn't playing War; so when she is choosing which block to play, and what mass to tell Ken, she must make sure that the balance scale won't reveal that ChosenNaomi ≠ ToldNaomi. In other words, she must make decisions so that:

ChosenNaomi > ChosenKen if, and only if, ToldNaomi > ChosenKen, and
ToldNaomi is not equal to the mass of any of Ken's blocks, because he knows that isn't possible.




It might seem like Naomi won't win any extra points by being deceitful, because Ken might discover that she wasn't playing War; but Naomi knows Ken thinks both players are playing War, and she knows what he knows, and she knows Ken will always follow his unique optimal strategy for War, so she can always predict what he will play.

You'll be given the masses of the blocks Naomi and Ken started with. Naomi will play Deceitful War optimally to gain the maximum number of points. Ken will play War optimally to gain the maximum number of points assuming that both players are playing War. What will Naomi's score be? What would it have been if she had played War optimally instead?

Examples

If each player has a single block left, where Naomi has 0.5kg and Ken has 0.6kg, then Ken is guaranteed to score the point. Naomi can't say her number is ≥ 0.6kg, or Ken will know she isn't playing War when the balance scale shows his block was heavier.

If each player has two blocks left, where Naomi has [0.7kg, 0.2kg] and Ken has [0.8kg, 0.3kg], then Naomi could choose her 0.2kg block, and deceive Ken by telling him that she chose a block that was 0.6kg. Ken assumes Naomi is telling the truth (as in how the War game works) and will play his 0.8kg block to score a point. Ken was just deceived, but he will never realize it because the balance scale shows that his 0.8kg block is, like he expected, heavier than the block Naomi played. Now Naomi can play her 0.7kg block, tell Ken it is 0.7kg, and score a point. If Naomi had played War instead of Deceitful War, then Ken would have scored two points and Naomi would have scored zero.

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with a line containing a single integer N, the number of blocks each player has. Next follows a line containing N space-separated real numbers: the masses of Naomi's blocks, in kg. Finally there will be a line containing N space-separated real numbers: the masses of Ken's blocks, in kg.

Each of the masses given to Ken and Naomi will be represented as a 0, followed by a decimal point, followed by 1-5 digits. Even though all the numbers in the input have 1-5 digits after the decimal point, Ken and Naomi don't know that; so Naomi can still tell Ken that she played a block with mass 0.5000001kg, and Ken has no reason not to believe her.

Output

For each test case, output one line containing "Case #x: y z", where x is the test case number (starting from 1), y is the number of points Naomi will score if she plays Deceitful War optimally, and z is the number of points Naomi will score if she plays War optimally.

Limits

1 ≤ T ≤ 50.
All the masses given to Ken and Naomi are distinct, and between 0.0 and 1.0 exclusive.

Small dataset

1 ≤ N ≤ 10.

Large dataset

1 ≤ N ≤ 1000.



Sample



Input 
 

4
1
0.5
0.6
2
0.7 0.2
0.8 0.3
3
0.5 0.1 0.9
0.6 0.4 0.3
9
0.186 0.389 0.907 0.832 0.959 0.557 0.300 0.992 0.899
0.916 0.728 0.271 0.520 0.700 0.521 0.215 0.341 0.458






Output 
 
Case #1: 0 0
Case #2: 1 0
Case #3: 2 1
Case #4: 8 4

My solution to this problem ( C++ ):

#include <iostream>
#include <algorithm>
#include <vector>
#include <fstream>

using namespace std;

int main()
{
    ifstream input("D-large-practice.in");
    ofstream output("output2.out");
 int nCases=0;
 input>>nCases;

 for(int i =0;i<nCases;++i)
 {
  int nBlocks=0;
  input>>nBlocks;

  vector<float> nVec;
  vector<float> kVec;
  vector<float>::iterator itN = nVec.begin();


  for(int j=0;j<nBlocks;++j)
  {
   float push;
   input>>push;
   nVec.push_back(push);
  }

  for(int j=0;j<nBlocks;++j)
  {
   float push;
   input>>push;
   kVec.push_back(push);
  }

  vector<float>::iterator itK = kVec.begin();
  int nPoints=0;
  int mark=-1;

 //if Naomi plays Decietful war
  sort(nVec.begin(), nVec.end());
  sort(kVec.begin(), kVec.end());
  int nPointsDW=0;
  int k =0;
  for(int i =0;i<nVec.size();++i)
  {
            for(int j = k;j<kVec.size();++j)
            {
                if(nVec[i]>kVec[j])
                {
                  k++;
                  nPointsDW++;
                  break;
                }
            }
        }

        //if naomi plays War
  reverse(nVec.begin(), nVec.end());
  for(unsigned int i=0;i<nVec.size();++i)
  {
   mark=-1;
   for(unsigned int j=0;j<kVec.size();++j)
   {
    if(nVec[i]<kVec[j])
    {
     mark = 1;
     break;
    }
    itK++;
   }

   if(mark==-1)
   {
    nPoints++;
   }
   else
   {
    kVec.erase(itK);
   }
   itK=kVec.begin();
  }
  output<<"Case #"<<i+1<<": "<<nPointsDW<<" "<<nPoints<<endl;
 }
 return 0;
}

Minesweeper Master (Google Code Jam Qualification Round: Problem C) : My attempt

Problem

Minesweeper is a computer game that became popular in the 1980s, and is still included in some versions of the Microsoft Windows operating system. This problem has a similar idea, but it does not assume you have played Minesweeper.

In this problem, you are playing a game on a grid of identical cells. The content of each cell is initially hidden. There are M mines hidden in M different cells of the grid. No other cells contain mines. You may click on any cell to reveal it. If the revealed cell contains a mine, then the game is over, and you lose. Otherwise, the revealed cell will contain a digit between 0 and 8, inclusive, which corresponds to the number of neighboring cells that contain mines. Two cells are neighbors if they share a corner or an edge. Additionally, if the revealed cell contains a 0, then all of the neighbors of the revealed cell are automatically revealed as well, recursively. When all the cells that don't contain mines have been revealed, the game ends, and you win.

For example, an initial configuration of the board may look like this ('*' denotes a mine, and 'c' is the first clicked cell):

*..*...**.
....*.....
..c..*....
........*.
..........

There are no mines adjacent to the clicked cell, so when it is revealed, it becomes a 0, and its 8 adjacent cells are revealed as well. This process continues, resulting in the following board:

*..*...**.
1112*.....
00012*....
00001111*.
00000001..

At this point, there are still un-revealed cells that do not contain mines (denoted by '.' characters), so the player has to click again in order to continue the game.

You want to win the game as quickly as possible. There is nothing quicker than winning in one click. Given the size of the board (R x C) and the number of hidden mines M, is it possible (however unlikely) to win in one click? You may choose where you click. If it is possible, then print any valid mine configuration and the coordinates of your click, following the specifications in the Output section. Otherwise, print "Impossible".

Input

The first line of the input gives the number of test cases, T. T lines follow. Each line contains three space-separated integers: R, C, and M.

Output

For each test case, output a line containing "Case #x:", where x is the test case number (starting from 1). On the following R lines, output the board configuration with C characters per line, using '.' to represent an empty cell, '*' to represent a cell that contains a mine, and 'c' to represent the clicked cell.

If there is no possible configuration, then instead of the grid, output a line with"Impossible" instead. If there are multiple possible configurations, output any one of them.

Limits

0 ≤ M < R * C.

Small dataset

1 ≤ T ≤ 230.
1 ≤ R, C ≤ 5.

Large dataset

1 ≤ T ≤ 140.
1 ≤ R, C ≤ 50.

Sample

Input	Output
5 5 5 23 3 1 1 2 2 1 4 7 3 10 10 82	Case #1: Impossible Case #2: c . * Case #3: Impossible Case #4: ......* .c....* ....... ..*.... Case #5: ********** ********** ********** ****....** ***.....** ***.c...** ***....*** ********** ********** **********

So here's the code that I wrote: (Algorithm applied: http://stackoverflow.com/questions/23039471/minesweeper-master-from-google-code-jam2014-qualification-round )

Algorithm

Let's first define N, the number of non-mine cells:

N = R * C - M

A simple solution is to fill an area of N non-mine cells line-by-line from top to bottom. Example for R=5, C=5, M=12:

c....
.....
...**
*****
*****

That is:

• Always start in the top-left corner.
• Fill N / C rows with non-mines from top to bottom.
• Fill the next line with N % C non-mines from left to right.
• Fill the rest with mines.

There are only a few special cases you have to care about.

Single non-mine

If N=1, any configuration is a correct solution.

Single row or single column

If R=1, simply fill in the N non-mines from left-to-right. If C=1, fill N rows with a (single) non-mine.

Too few non-mines

If N is even, it must be >= 4.

If N is odd, it must be >= 9. Also, R and C must be >= 3.

Otherwise there's no solution.

Can't fill first two rows

If N is even and you can't fill at least two rows with non-mines, then fill the first two rows with N / 2non-mines.

If N is odd and you can't fill at least two rows with non-mines and a third row with 3 non-mines, then fill the first two rows with (N - 3) / 2 non-mines and the third row with 3 non-mines.

Single non-mine in the last row

If N % C = 1, move the final non-mine from the last full row to the next row.

Example for R=5, C=5, M=9:

c....
.....
....*
..***
*****

Here's the code that I wrote in C++:

#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream input;
ofstream output;
int **board;
int index=0;

void display(int r, int c)
{
 cout<<"Case #"<<index+1<<": \n";
 output<<"Case #"<<index+1<<": \n";
 for(int i=0;i<r;++i)
  {
   for(int j=0;j<c;++j)
   {
    if(board[i][j]==0)
    {
     cout<<"c";
     output<<"c";
    }
    if(board[i][j]==1)
    {
     cout<<"*";
     output<<"*";
    }
    if(board[i][j]==2)
    {
     cout<<".";
     output<<".";
    }
   }
   output<<endl;
   cout<<endl;
  }
}

int main()
{
 input.open("d:\\C-large-practice.in");
 output.open("d:\\out.txt");

 int nCases=0;
 input>>nCases;

 for(;index<nCases;++index)
 {
  output.flush();
  int r, c, m, n;
  input>>r>>c>>m;

  n = r*c-m;

  board = new int *[r];
  for(int j=0;j<r;++j)
  {
   board[j] = new int[c];
  }

  if(n==1)
  {
   //output<<"Case 1\n";
   for(int i = 0;i<r;++i)
   {
    for(int j=0;j<c;++j)
    {
     board[i][j]=1; //mine
    }
   }
   board[0][0]=0; //click
   display(r, c);
   continue;
  }

  if(r==1)
  {
   //output<<"Case 2\n";
   int tNM = n; //temporary non mine counter
   for(int i =0;i<c;++i)
   {
    if(tNM==0)
    {
     board[0][i]=1; //mine
    }
    else
    {
    board[0][i]=2;
    tNM--;    //non-mine
    }
   }
   board[0][0]=0;   //click
   display(r, c);
   continue;
  }
  if(c==1)
  {
   //output<<"Case 3\n";
   int tNM = n; //temporary non mine counter
   for(int i =0;i<r;++i)
   {
    if(tNM==0)
    {
     board[i][0]=1; //mine
    }
    else
    {
    board[i][0]=2;
    tNM--;    //non-mine
    }
   }
   board[0][0]=0;   //click
   display(r, c);
   continue;
  }

  if((n%2==0 && n<4) || (n%2==1 && ((r<3||c<3)||n<9)))
  {
   cout<<"Case #"<<index+1<<": \nImpossible\n";
   output<<"Case #"<<index+1<<": \nImpossible\n";
   output.flush();
   continue;
  }

  if(n%2==0 && ((n/c)<2))
  {
   //output<<"Case 4\n";
   for(int i = 0;i<2;++i)
   {
    for(int j =0; j<n/2;++j)
    {
     board[i][j]=2;
    }
   }

   //rest are mines
   for(int i=0;i<r;++i)
   {
    for(int j =0;j<c;++j)
    {
     if(board[i][j]!=2)
      board[i][j]=1;
    }
   }
   board[0][0]=0; //click
   display(r, c);
   continue;
  }

  if(n%2==1 && ((n/c<2) ||((n-2*c)<3)))
  {
   //output<<"Case 5\n";
   int tNM = n;
   for(int i = 0;i<2;++i)
   {
    for(int j =0; j<(n-3)/2;++j)
    {
     board[i][j]=2;
    }
   }

   board[2][0] = 2;
   board[2][1] = 2;
   board[2][2] = 2; //the three non mines

   //rest are mines
   for(int i=0;i<r;++i)
   {
    for(int j =0;j<c;++j)
    {
     if(board[i][j]!=2)
      board[i][j]=1;
    }
   }
   board[0][0]=0; //click
   display(r, c);
   continue;
  }

  //else the last case:
  int tNM = n;
  for(int i =0;i<r;++i)
  {
   //output<<"Case 6\n";
   for(int j =0;j<c;++j)
   {
    if(tNM!=0)
    {
    board[i][j]=2;
    tNM--;
    }
    else
     board[i][j]=1;
   }
  }
   if(n%c==1)
   {
    board[n/c-1][c-1] = 1;
    board[n/c][1] = 2;
   }
   board[0][0] = 0; 
  display(r, c);
 }
}

It looks a lot like "write-only" code but it does work.