I also couldn't solve this problem (I calculated by brute force the small
case just for making sure I advance to the next round but I couldn't solve
C-large because my solution wasn't accepted for C-small).
What I did was:
if R = 1 and C = 1 return "c"
else if R = 1 or C = 1 return something like "c...****" (or the transpose
if C = 1)
else if m = R*C-1 then c in [0][0] and * everywere else
else if m = R*C - k with k in {2,3,5,7} return impossible
else if m%2 = (R*C)%2 fill the last R-2 rows with * until I get m times '*'
and then from C-1 to to 0 fill with '*' in the first two rows until I get m
times '*'
else if R = 2 or C = 2 return impossible
else fill the last R-3 rows until m * are reached then fill the first 3
rows until I get m *
This is my code in case anyone wants to read it and tell me what's wrong
with it:
char board[5][5];
bool calc()
{
int m2 = m;
if(r==1&&c==1)
{
board[0][0] = 'c';
return true;
}
if(c==1)
{
forn(i,r)
board[i][0] = '.';
board[0][0] = 'c';
int pos = r-1;
while(m2>0)
{
board[pos][0] = '*';
m2--;
pos--;
}
return true;
}
if(r==1)
{
forn(i,c)
board[0][i] = '.';
board[0][0] = 'c';
int pos = c-1;
while(m2>0)
{
board[0][pos] = '*';
m2--;
pos--;
}
return true;
}
int sz = r*c;
if(m == sz-1)
{
forn(i,r)
forn(j,c)
board[i][j] = '*';
board[0][0] = 'c';
return true;
}
if(m == sz-2 || m == sz-3 || m == sz-5 || m == sz-7)
return false;
if((sz-m)%2 == 0)
{
forn(i,r)
forn(j,c)
board[i][j] = '.';
board[0][0] = 'c';
int posx = r-1, posy = c-1;
while(m2>0)
{
board[posx][posy] = '*';
m2--;
if(posx == 1 && m > 0)
{
board[posx-1][posy] = '*';
m2--;
}
posy--;
if(posy==-1)
{
posx--;
posy = c-1;
}
}
return true;
}
else
{
if(r==2||c==2)
return false;
forn(i,r)
forn(j,c)
board[i][j] = '.';
board[0][0] = 'c';
int posx = r-1, posy = c-1;
while(m2>0)
{
board[posx][posy] = '*';
m2--;
if(posx == 2 && m2 > 1)
{
board[posx-1][posy] = '*';
board[posx-2][posy] = '*';
m2-=2;
}
posy--;
if(posy==-1)
{
posx--;
posy = c-1;
}
}
return true;
}
}
On Sun, Apr 13, 2014 at 8:26 AM, Leopoldo Salvo <[email protected]>wrote:
> HI,
>
> I could not get this one to pass either, i still don't understand why, it
> must be the way i fill the board (I ran the actual recursion algorigthm on
> both failures and successes and checked the number of cells left to be
> revealed and they were consistent with my results)
>
> If R or C == 1 then it is always possible
>
> otherwise, i calculate a rectangle top left of the board with width C-2
> and height R-2, i call that a buffer zone, as long as M fits in that buffer
> zone it is possible (I fill it column by column: from top to bottom and
> from left to right)
>
> If M > bufferzone then i start filling the rectangle underneath it, so at
> max 2 rows height, and at most C-2 columns width. In this area i say the
> board will be ok as long as the number of mines in this container is even.
> I fill this rectangle from top to bottom and from left to right.
>
> after this lower rectangle is filled, if there are more mines remaining i
> do the same thing with the rectangle right of the buffer zone (this is a
> rectangle with at most 2 columns and R-2 rows). I fill this from top to
> bottom, from left to right. As long as the number of mines in this
> rectangle is even, it is ok.
>
> at this point there could be at most 3 more mines (requirements say M <
> R*C.
>
> IF remaining = 3 then it is possible (all mines except the clicked c),
> otherwise it is impossible.
>
> I am still baffled why it didn't pass, there must be some corner case or
> the way i fill it is not correct, any ideas?
>
> I suppose ill have to just run the data set against one of the passed ones
> and compare
>
> --
> You received this message because you are subscribed to the Google Groups
> "Google Code Jam" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to [email protected].
> To post to this group, send email to [email protected].
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/google-code/e0086e83-64ae-47d6-a070-2c9ccc3fb602%40googlegroups.com
> .
> For more options, visit https://groups.google.com/d/optout.
>
--
You received this message because you are subscribed to the Google Groups
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/CA%2BE_-jRH-5iFo_vP-yyRsujJKMVRH8-Thp0d4KxKpBWk9GrFBQ%40mail.gmail.com.
For more options, visit https://groups.google.com/d/optout.
