## 11454 - Very well informed domino player

Moderator: Board moderators

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

### 11454 - Very well informed domino player

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.

LayCurse
New poster
Posts: 11
Joined: Sun Feb 25, 2007 3:14 pm
Location: Kyoto, Japan

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

I got W=13322980, L+T=18554528 for (2,0) during the contest.
I also cannot get sample output

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

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

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).

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

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

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]

mpi
New poster
Posts: 46
Joined: Fri Nov 03, 2006 7:53 pm

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

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.

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

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

Isn't Alberto the problemsetter?

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

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

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;
}
``````

Christian Schuster
Learning poster
Posts: 63
Joined: Thu Apr 04, 2002 2:00 am

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

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.

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

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

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.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

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

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.
Check input and AC output for thousands of problems on uDebug!