Page 1 of 1

11454 - Very well informed domino player

Posted: Sun May 18, 2008 9:11 pm
by baodog
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
by LayCurse
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
by baodog
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
by baodog
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]

Re: 11454 - Very well informed domino player

Posted: Sun May 25, 2008 5:45 pm
by mpi
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
by baodog
Isn't Alberto the problemsetter?

Re: 11454 - Very well informed domino player

Posted: Sun May 25, 2008 11:42 pm
by baodog
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;
}

Re: 11454 - Very well informed domino player

Posted: Sun Jun 01, 2008 2:18 pm
by Christian Schuster
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
by baodog
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
by brianfry713
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.