11459 - Snakes and Ladders

[Robert Gerbicz]

This problem has been solved by only 2 peoples on the contest, but it has been attempted by lots of peoples and it should be an easy problem. Just a simulation task. What is wrong by my method:
0. Read the number of test cases. While there is a testcase do:
1. Read the number of players, ladders, dices.
2. Read the ladders/snakes
3. Setup position=1 for every player
4. Read the dices, one at a time
4a. If the game has been finished then goto step=5
4b. Add the value of the dice to the player, who is at that turn.
4c. If it is >100 then let the player's position=100
4d. If it is the first number of a ladder/snake then move to the second number of that ladder/snake (it is implemented easily, that it costs only O(1) time to check if it is a first number of a ladder/snake pair)
4e. If we are at position=100 then the game is finished
5. While we haven't proceeded all dices
6. Print out the result (there is no blank line and also no blank lines between different input sets).
7. Wend (there is a testcase)

[jah]

Yes, there is something definitely wrong with the testcases.

[baodog]

Your algo is not right. Notice it says No square contains more than one endpoint of ***any*** (any one) snake or ladder --- that
means diffrent snakes can share end points. ... maybe that's why so few acs. I checked the dataset and found that many squares have both end point and starting point. Also I checked the dataset and find that you can jump out of [1,100], it's unclear what one should do here... whether set to 100, or wait for next dice throw to go to 100. I tried both ways, both get wa. I cover the case where you jump to arbitrary indices. All wa. My code is below, let me know if you find any mistakes...

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;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()

map<int,int> into,G;
set<int> parent;

int DFS(int u)
{
    if(G.find(u)==G.end()) return u;
    else return into[u]=DFS(G[u]);
}

int main()
{
    int t;
    scanf("%ld",&t);
    while(t--)
    {
        int players,snakes,rolls,u,v;
        cin >> players >> snakes >> rolls;
        vector<int> p(players+10,1);
        
        G.clear(); into.clear(); parent.clear();
        set<int> all_verts;
        for(int s=0;s<snakes;s++)
        {
            int u,v;
            scanf("%ld",&u);
            scanf("%ld",&v);
            if(u>=100 || u<1 || v<1) while(1);
            G[u]=v;
            parent.insert(v);
            all_verts.insert(u);
            all_verts.insert(v);
        }
        FOR(ii,all_verts)
            if(parent.find(*ii)==parent.end() &&
               G.find(*ii)!=G.end()) DFS(*ii);
            
        int curr=0,r=0,d;
        for(;r<rolls;r++)
        {
            scanf("%ld",&d);
            p[curr]+=d;
            if(p[curr]>100) p[curr]=100;
            if(into.find(p[curr])!=into.end()) p[curr]=into[p[curr]];
            if(p[curr]==100) {r++; goto endgame;}
            curr=(curr+1)%players;
        }
        endgame:
        for(;r<rolls;r++) scanf("%ld",&d);
        for(int i=0;i<players;i++)
            printf("Position of player %d is %d.\n",i+1,p[i]);
    }
    return 0;
}

[RC's]

If we use an array data[101], with index as starting point and its value as end point, I don't think it will be a problem if a square shares more than one endpoint of snake and ladder. Suppose there are 2 snakes, 60 20 and 40 20 which share the same endpoint, we can store it like data[60] = 20 and data[40] = 20, and I think it's not a problem. If we get into square number 40 or 60, we will get to square number 20.
Am I wrong ?

[Robert Gerbicz]

Your algo is not right. Notice it says No square contains more than one endpoint of ***any*** (any one) snake or ladder --- that
means diffrent snakes can share end points. ... maybe that's why so few acs. I checked the dataset and found that many squares have both end point and starting point.

And why is it interesting? I'm checking only if the square is the bottom of the ladder or mouth of a snake, if it's then I move the token to the second number of that pair. So it is only required that on each square there is at most one bottom of a ladder or mouth of a snake.

maybe that's why so few acs.

Currently there is no AC for this problem. (102 submission, 18 users tried this so far).

[RC's]

Robert, during the contest, there are 2 people who got AC on this problem.
You can refer to http://icpcres.ecs.baylor.edu/onlinejud ... ontest=201
and you will find it.

This is the detail :
98 acmita08 D - Snakes and Ladders Accepted C++ 2.090 2008-06-21 09:56:43
108 Rupak_Harmony D - Snakes and Ladders Accepted C++ 1.080 2008-06-21 10:00:19

[Robert Gerbicz]

Robert, during the contest, there are 2 people who got AC on this problem.
You can refer to http://icpcres.ecs.baylor.edu/onlinejud ... ontest=201
and you will find it.

It's very few, and proves nothing. See for example problem 11272, it has been solved by two peoples, one of them is the problemsetter, and another people. But the problem is totally broken, I've proved it on this board.

Another possible annoying problem: who starts the game?! I and probably everbody assumed that in every game the first player starts, but there are at least 3 other different implementations for that (for example G-th game starts by the 1+(G-1)%numberofplayer), but on the problem there is 0 information about it. I've tried these 3 other cases, all of them WAs.

[baodog]

Code: Select all

2


3 5 4
4 5
6 7
5 6
7 5000000000000000000000000000000000000000000000000000000000000000000000
5000000000000000000000000000000000000000000000000000000000000000000000 3000
3
4
5
9


3 1 3
4 20
3
4
5

Should give the following based on the problem description, because
you only move to 100 after throwing the dice!! Not by tunneling to >100.
I think you fail this case.

Code: Select all

Position of player 1 is 100.
Position of player 2 is 3000.
Position of player 3 is 3000.
Position of player 1 is 20.
Position of player 2 is 5.
Position of player 3 is 6.

[Robert Gerbicz]

Should give the following based on the problem description, because
you only move to 100 after throwing the dice!! Not by tunneling to >100.
I think you fail this case.

Yes, probably, but in that case the problem's description would be totally broken, because it says:

Code: Select all

The ***squares*** of the grid are numbered 1 to 100....
the token must be moved to the ***square*** containing the top of the ladder....
the token must be moved to the ***square*** containing the tail of the snake.

So it would be out of game field. But the input doesn't contain such tests, I've checked:

1. For all ladders/snakes for the x starting square: 1<=x<=99 and for the ending square: 1<=y<=100 (used character array to check this)
2. No ending square is the starting square for different snake/ladder. So it isn't possible multiple slides, what you've posted.

[RC's]

Code: Select all

2


3 5 4
4 5
6 7
5 6
7 5000000000000000000000000000000000000000000000000000000000000000000000
5000000000000000000000000000000000000000000000000000000000000000000000 3000
3
4
5
9


3 1 3
4 20
3
4
5

if there is really a case with snake / ladders like
7 5000000000000000000000000000000000000000000000000000000000000000000000
5000000000000000000000000000000000000000000000000000000000000000000000 3000
my program will get RE instead of WA.. I only use an array of size 101 to accommodate all snakes and ladders.
And I'm sure many people will use that kind of array..

[jurajz]

I tried solve this problem too. In my opinion it is straightforward, but I cannot find mistake in my code. Only 2 AC during contest and no AC here after 148 submission, maybe there is a mistake in problem description.

I checked the input. I find out this:

- No string length (string= set of consecutive no-blank characters separated by eoln or space) of input is more than 7. So there is no number like "5000000000000000000000000000000000000000000000000000000000000000000000", etc.
- all values of dice throw are between 1 and 6 (i.e. no zero, negative or more than 6)
- all values labeled as bottom of ladder/mouth of snake or top of ladder/tail of snake are between 1 and 100.
- somewhere in input is the bottom of ladder at position 1.
- somewhere in input is the top of ladder at position 100.
- but there is no ladder with bottom at position 1 and top at position 100.

I think about bottom of ladder at position 1. When can a player climb the ladder? Before his dice throw or only after? Or in the beginning of the game?

For example, the input

Code: Select all

1
2 1 2
1 99
2
3

What output is correct?

Output No. 1: (When all players can climb the ladder at the beginning of the game - before any dice throw)

Code: Select all

Position of player 1 is 100.
Position of player 2 is 99.

Output No. 2: (When only one player can climb the ladder before his own dice throw)

Code: Select all

Position of player 1 is 100.
Position of player 2 is 1.

Output No. 3: (When one player can climb the ladder only after his own dice throw)

Code: Select all

Position of player 1 is 3.
Position of player 2 is 4.

[Robert Gerbicz]

Today there was a rejudge for the problem. Now I've got AC, proving that my posted algorithm is good. Among the 26 users who tried it there are 16 users who got AC.

[jurajz]

Today there was a rejudge for the problem. Now I've got AC, proving that my posted algorithm is good. Among the 26 users who tried it there are 16 users who got AC.

Thank you Robert, I have AC too. But now I don't know, what is AC code. (I made 14 submissions, only one, 13th, is AC )

[shiplu_1320]

I am getting WA in this problem since contest and most shocking for me is that, after rejudge my code is not AC.
Am i missed anything?
Please help.........

Code: Select all

Removed After AC.
Thanks a million jurajz.

Thanks in advance.

[jurajz]

Hi shiplu_1320,

I think, that I found a mistake. After this two lines

Code: Select all

while(lad[pl[j]]!=0)
            pl[j]=lad[pl[j]];

you should add some more lines.

Player can reach position 100 by ladder and after this, the game ends immediately. But you don't check this and you continue with the next roll. Try to fix it.

One sample input:

Code: Select all

1
3 1 5
2 100
1
2
3
4
5

Your actual program gives

Code: Select all

Position of player 1 is 100.
Position of player 2 is 3.
Position of player 3 is 4.

My AC program gives

Code: Select all

Position of player 1 is 100.
Position of player 2 is 1.
Position of player 3 is 1.

Hope you will get AC now.