11459 - Snakes and Ladders

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

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

11459 - Snakes and Ladders

Post by Robert Gerbicz » Sat Jun 21, 2008 2:50 pm

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)
Last edited by Robert Gerbicz on Sat Jun 21, 2008 3:01 pm, edited 4 times in total.

jah
New poster
Posts: 38
Joined: Wed Apr 20, 2005 12:23 am

Re: 11459 - Snakes and Ladders

Post by jah » Sat Jun 21, 2008 2:53 pm

Yes, there is something definitely wrong with the testcases.

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

Re: 11459 - Snakes and Ladders

Post by baodog » Thu Jun 26, 2008 11:55 am

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
Learning poster
Posts: 65
Joined: Fri Jul 13, 2007 3:17 pm

Re: 11459 - Snakes and Ladders

Post by RC's » Thu Jun 26, 2008 12:26 pm

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
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

Re: 11459 - Snakes and Ladders

Post by Robert Gerbicz » Thu Jun 26, 2008 1:39 pm

baodog wrote: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.
baodog wrote: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
Learning poster
Posts: 65
Joined: Fri Jul 13, 2007 3:17 pm

Re: 11459 - Snakes and Ladders

Post by RC's » Thu Jun 26, 2008 3:01 pm

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
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

Re: 11459 - Snakes and Ladders

Post by Robert Gerbicz » Thu Jun 26, 2008 3:30 pm

RC's wrote: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
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

Re: 11459 - Snakes and Ladders

Post by baodog » Thu Jun 26, 2008 8:24 pm

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
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

Re: 11459 - Snakes and Ladders

Post by Robert Gerbicz » Fri Jun 27, 2008 2:12 am

baodog wrote: 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
Learning poster
Posts: 65
Joined: Fri Jul 13, 2007 3:17 pm

Re: 11459 - Snakes and Ladders

Post by RC's » Fri Jun 27, 2008 5:04 am

baodog wrote:

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
Learning poster
Posts: 69
Joined: Sat Sep 02, 2006 7:30 pm
Location: Slovakia

Re: 11459 - Snakes and Ladders

Post by jurajz » Sat Jun 28, 2008 8:25 am

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. :roll:

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
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

Re: 11459 - Snakes and Ladders

Post by Robert Gerbicz » Thu Jul 24, 2008 1:43 pm

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
Learning poster
Posts: 69
Joined: Sat Sep 02, 2006 7:30 pm
Location: Slovakia

Re: 11459 - Snakes and Ladders

Post by jurajz » Thu Jul 24, 2008 11:02 pm

Robert Gerbicz wrote: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 :D)

shiplu_1320
New poster
Posts: 32
Joined: Sat Dec 29, 2007 9:08 pm
Location: CSEDU , Dhaka
Contact:

Re: 11459 - Snakes and Ladders

Post by shiplu_1320 » Sat Jul 26, 2008 10:09 pm

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.
Last edited by shiplu_1320 on Sun Jul 27, 2008 10:00 pm, edited 1 time in total.
A learner......

jurajz
Learning poster
Posts: 69
Joined: Sat Sep 02, 2006 7:30 pm
Location: Slovakia

Re: 11459 - Snakes and Ladders

Post by jurajz » Sun Jul 27, 2008 9:51 pm

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

Post Reply

Return to “Volume 114 (11400-11499)”