Page 1 of 1

### 11454 - Very well informed domino player

Posted: Sun May 18, 2008 9:11 pm
Hi,

for (0,2), I'm getting
W 9637224 L 21213222 T 1527593
for wins, losses, ties.

Is anyone getting the same?
I think the sample IO is wrong, or the pieces shown are not correct.
Thanks.

### Re: 11454 Domino, Sample I/O also Wrong?

Posted: Sun May 18, 2008 11:50 pm
I got W=13322980, L+T=18554528 for (2,0) during the contest.
I also cannot get sample output

### Re: 11454 Domino, Sample I/O also Wrong?

Posted: Mon May 19, 2008 1:11 am
After fixing a bug, now I get

W 10244240 L 22183168 T 1577845

We both have around 32 million states total for (2,0),
whereas the problem setter has about 6.1 million (ties occur more rarely).

### Re: 11454 - Very well informed domino player

Posted: Sat May 24, 2008 10:39 pm
Hi,

Thanks. I think the judge io is likely wrong.
Here is the answers I get:
[code]
First Piece Wins Losses
--------------------------------------------
if(s=="(2,0)" || s=="(0,2)") out(10244240,22183168);
else if(s=="(6,0)" || s=="(0,6)") out(14119819,18592949);
else if(s=="(3,0)" || s=="(0,3)") out(12894112,18613176);
else if(s=="(1,1)" || s=="(1,1)") out(11688784,10675704);
else if(s=="(1,5)" || s=="(5,1)") out(8647387 ,15792346);
else if(s=="(4,3)" || s=="(3,4)") out(10782900,14392132);
else if(s=="(4,6)" || s=="(6,4)") out(12457984,15412722);
[/code]

### Re: 11454 - Very well informed domino player

Posted: Sun May 25, 2008 5:45 pm
My output is the same as LayCurse for (2,0), that is, 13322980 + 18554528
I don't think the i/o is wrong, otherwise it couldn't have been solved by Alberto.

### Re: 11454 - Very well informed domino player

Posted: Sun May 25, 2008 7:20 pm
Isn't Alberto the problemsetter?

### Re: 11454 - Very well informed domino player

Posted: Sun May 25, 2008 11:42 pm
Hi,

For some reason, I can not get the same answer as you and LayCurse.
Do you care to share your WA code, so we can compare and see if there are different
interpretations of the problem?
btw, I assume you cannot pass if you have a piece that you can play, and after no one can play the game ends.
Here is my code for generating the answers:

Code: Select all

``````#include <stdio.h>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <map>
#include <vector>
#include <queue>
#include <set>
using namespace std;

char domino[4][7][2]=
{
{{0,3},{1,1},{3,4},{1,5},{0,2},{0,6},{4,6}},
{{3,3},{4,4},{0,5},{2,4},{1,2},{3,6},{0,0}},
{{1,3},{2,6},{6,6},{2,3},{1,6},{5,6},{4,5}},
{{3,5},{2,2},{0,4},{5,5},{2,5},{0,1},{1,4}}
};

struct Node
{
bool valid;
void print()  { cout << (int)link << (int)opp << (int)valid << " ";}

char cnt[4][7];
char sum[4];
int win,loss,tie,prev;

void solve(char p,char u,char n,char l,char r)
{
// Play current piece
sum[p]-=(u+v);

// Game end check
if(sum[p]==0 && (p!=1 || (p==1 && !adj[1][0][1].valid)))
{
if(p==0) win++;
else loss++;
}
else
{
// Play Next piece
bool played=false;
for(char i=1;i<=4;i++)
{
played=false;
char np=(p+i)%4;
char j;
// Play on left
for(j=0;j<cnt[np][l];j++)
{
played=true;
}
// Play on right
for(j=0;j<cnt[np][r];j++)
{
played=true;
}
// Exit if played piece.
if(played) break;
}

// Not played -- Game ends here.
if(!played)
{
if(sum[0]==sum[1] || sum[0]==sum[2] || sum[0]==sum[3]
|| sum[1]==sum[2] || sum[1]==sum[3]
|| sum[2]==sum[3]) tie++;
else
{
if(sum[0]<sum[1] && sum[0]<sum[2] && sum[0]<sum[3]) win++;
else loss++;
}
}
}

// Unplay current piece
sum[p]+=(u+v);

// Debug Output
if(loss+win+tie>prev+1000000)
{
prev=loss+win+tie;
cout << ".";
}
return;
}

int main()
{
// Build Graph
char p,i,j;
for(p=0;p<4;p++)
for(i=0;i<7;i++)
{
char u=domino[p][i][0], v=domino[p][i][1];
cnt[p][u]++; if(v!=u) cnt[p][v]++;
sum[p]+=u+v;
}

// Solve
int u=0; int n=1; // nth block that has u.  This is (0,2).
//cout << "Enter u and n (nth domino that has u, counting from left): ";
//cin >> u >> n;
cout << "(u,v) is " << endl;
cout << "(" << u << ":" << v << ")" << endl;
solve(0,u,n,u,v);
cout << endl << "Wins Losses Ties" << endl;
cout << win << "," << loss << "," << tie << endl;
system("pause");
return 0;
}
``````

### Re: 11454 - Very well informed domino player

Posted: Sun Jun 01, 2008 2:18 pm
Hi,

my result for (0,2) matches LayCurse's. My "wins" values are:

(0,3)/(3,0): 22401389
(1,1): 11018156
(3,4)/(4,3): 24849438
(1,5)/(5,1): 9158932
(0,2)/(2,0): 13322980
(0,6)/(6,0): 21685496
(4,6)/(6,4): 20858993

Also, the problem statement is unclear about ties. Should they be considered in "loses", or are they not counted anywhere? IMHO, Bob does not lose if no one wins.

### Re: 11454 - Very well informed domino player

Posted: Fri Jun 06, 2008 7:46 am
So what's wrong with my code? Thanks! Since all pieces are different, once you put down
(a b) if a!=b, then it will be unique. If a==b to start with, you have to divide
the total by 1/2. I simply use brute force to enumerate.

### Re: 11454 - Very well informed domino player

Posted: Sat May 12, 2012 1:28 am
My AC code matches the sample I/O. Every end state I reached was either a win for Bob only or counted as a loss. My code only checks one side of the domino if it's a double, and only one side of the table if they are the same.