11454 - Very well informed domino player

All about problems in Volume 114. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

11454 - Very well informed domino player

Post by baodog » 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.

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

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

Post by LayCurse » 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 :(

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

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

Post by baodog » 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).

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

Re: 11454 - Very well informed domino player

Post by baodog » Sat May 24, 2008 10:39 pm

Hi,

Can someone verify my answers or LayCurse's answers? please :-) ?
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
Location: Madrid

Re: 11454 - Very well informed domino player

Post by mpi » 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.

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

Re: 11454 - Very well informed domino player

Post by baodog » Sun May 25, 2008 7:20 pm

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

Post by baodog » 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
{
    char link,opp;
    bool valid;
    Node(char link=-1,char opp=-1,bool valid=false)
    :link(link),opp(opp),valid(valid){}
    void print()  { cout << (int)link << (int)opp << (int)valid << " ";}
} adj[4][7][7];

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
    char v=adj[p][u][n].opp;
    char nn=adj[p][u][n].link;
    adj[p][u][n].valid=false;
    adj[p][v][nn].valid=false;
    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++)
                if(adj[np][l][j].valid)
                {
                    solve(np,l,j,l,adj[np][l][j].opp);
                    played=true;
                }
            // Play on right
            for(j=0;j<cnt[np][r];j++)
                if(adj[np][r][j].valid)
                {
                    solve(np,r,j,adj[np][r][j].opp,r);
                    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
    adj[p][u][n].valid=true;
    adj[p][v][nn].valid=true;
    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];
            adj[p][u][cnt[p][u]]=Node(cnt[p][v],v,true);
            adj[p][v][cnt[p][v]]=Node(cnt[p][u],u,true);
            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;
    int v=adj[0][u][n].opp;
    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;
}

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

Re: 11454 - Very well informed domino player

Post by Christian Schuster » 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.

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

Re: 11454 - Very well informed domino player

Post by baodog » 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.

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

Re: 11454 - Very well informed domino player

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

Post Reply

Return to “Volume 114 (11400-11499)”