11454 - Very well informed domino player

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

[LayCurse]

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

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

[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]

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

[baodog]

Isn't Alberto the problemsetter?

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

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

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

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