OJ Board

The Online Judge board
https://onlinejudge.org/board/

10801 - Lift Hopping

https://onlinejudge.org/board/viewtopic.php?t=7320

Page 4 of 4

Re: 10801 - Lift Hopping

Posted: Tue Sep 25, 2012 1:07 am
by brianfry713
20 seconds riding the first elevator.
http://www.uvatoolkit.com/problemssolve.php

Re: 10801 - Lift Hopping

Posted: Mon Dec 10, 2012 10:36 am
by Muftee_Ruet
Try these case:

INPUT

Code: Select all

3 2
100 5 3
0 1 2
1 2
1 2

3 2
100 5 3
0 1 2
0 1
1 2
OUTPUT

Code: Select all

163
68

Re: 10801 - Lift Hopping

Posted: Mon Dec 17, 2012 8:16 pm
by afruizc
The key to solve this problem is to model the graph successfully I think that's what I'm lacking, because I keep getting WA. Here is the idea I used: I associate a number to every floor depending on the elevator that goes over that floor. For the first elevator I give the floors numbers from 0 to 99, for the second one from 100 to 199 and so on, so the floors traversed by the fifth elevator are numbered from 400 to 499. So far there is just half of the problem solved. After this, I need to work around the issue of elevators that stop at the same floor (this part is very likely to contain mu bug). I used an array (prev) to store wether another elevator stops at floor i or not. If prev == -1, it means that no elevator so far stops at floor i, otherwise, prev contains the number of the previous floor (remember, from 0 to 499). At this point, the graph is built, so I run Dijkstra's and print the solution.

Here is my code:

Code: Select all

Cut after AC :)
Here is some I/O I've tested my program with:

Input:

Code: Select all

3 30
100 100 1
0 2 4 5 6 7 8 21 22 23 24 25 26 30
1 2 19 11 12 13 14 15 16 30
1 10 30
2 99
100 1
0 1 98 99
1 98
3 1
100 10 100
0 1
0 1
0 1
2 5
1 1
0 3
4 5
4 89
7 2 4 8
3 34 45 56 77
4 23 34 89
0 99
3 99
5 99
12 90 34 56 22
0 4 7 3 6 8 98
4 10 20 23 46 50 69 88 99
0 3 12 45 50 77 88 99
0 20 46 77 98
0 50
2 99
10 40
1 2 3 4 99 0 12 
3 4 2 0 12 99
2 2
10 5
0 1 2
1 2
3 2
100 5 3
0 1 2
1 2
1 2
3 2
100 5 3
0 1 2
0 1
1 2
2 90
1 10
0 80
80 90
Output:

Code: Select all

449
417
10
IMPOSSIBLE
1671
2826
990
20
165
68
240

Re: 10801 - Lift Hopping

Posted: Tue Dec 18, 2012 12:49 am
by brianfry713
line 9 of the output should be 163 not 165.

Try rewriting your code in a more straightforward way. In my AC code, I use a priority_queue with a struct containing the elevator number, current floor, and time. I also have a min_time[5][100] array initialized to infinity. Then insert into the priority_queue each elevator that stops at floor 0. In the Dijkstra while loop, see if the entry at the top of the priority_queue can get to another floor at an earlier time, and try switching elevators at the current floor.

Re: 10801 - Lift Hopping

Posted: Fri Dec 21, 2012 7:47 am
by afruizc
Thanks brianfry713, I did as you said and get AC. It was my first time coding Dijkstra that way, but it is indeed less error prone. Thanks for your help :D.
For those who are still stuck, here are some test cases:

Input:

Code: Select all

3 30
100 100 1
0 2 4 5 6 7 8 21 22 23 24 25 26 30
1 2 11 12 13 14 15 16 19 30
1 10 30
2 99
100 1
0 1 98 99
1 98
3 1
100 10 100
0 1
0 1
0 1
2 5
1 1
0 3
4 5
4 89
7 2 4 8
3 34 45 56 77
4 23 34 89
0 99
3 99
5 99
12 90 34 56 22
0 3 4 6 7 8 98
4 10 20 23 46 50 69 88 99
0 3 12 45 50 77 88 99
0 20 46 77 98
0 50
2 99
10 40
0 1 2 3 4 12 99
0 2 3 4 12 99
2 2
10 5
0 1 2
1 2
3 2
100 5 3
0 1 2
1 2
1 2
3 2
100 5 3
0 1 2
0 1
1 2
2 90
1 10
0 80
80 90
Output:

Code: Select all

449
417
10
IMPOSSIBLE
1671
2826
990
20
163
68
240

Re: 10801 - Lift Hopping

Posted: Thu Mar 13, 2014 11:14 am
by hpjhc

Code: Select all

delete after AC

Re: 10801 - Lift Hopping

Posted: Thu Mar 13, 2014 11:53 am
by uDebug
hpjhc wrote:What's wrong with my code, why complile error?
What's the compiler error you're getting?

Also, try submitting your code again. Looks like there might have been some minor issues with the judge earlier.

Finally, try changing the array called "time" (on Line #29) to something else. The word "time" may be a keyword.

Re: 10801 - Lift Hopping

Posted: Sun Aug 17, 2014 11:08 pm
by nbacool2
Hi, guys. For some reason on the test cases my code produces 90% right answers and on the rest 10% it gives a lower answer than the correct one. I'm using Dijkstra's algorithm. I construct the graph by pairing each elevator's reachable floors with eacho ther and also keep for each edge which elevator we're using.
So in the priority Q I also keep for the current edge the elevator with which we are reaching the current floor and when I explore the children of the current floor I add 60 second extra time if the elevator we're using from the current floor to its child is different from the elevator that was stored in the priority queue. Any ideas what could be wrong?

Code: Select all

#include <iostream>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <cstdio>
#include <stack>
#include <utility>
#include <cmath>
#include <sstream>
using namespace std;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
const int MAXN = 100;
int elevatorCost[6];
vector<int> floorsForElevator[6];
int N, K;
vector<iii> G[MAXN];
int dist[MAXN];
vector<int> answers;
void read()
{
    memset(dist, 127, sizeof dist);
    for(int i = 0; i < MAXN; ++i) G[i].clear();
    for(int i = 0; i < 6; ++i) floorsForElevator[i].clear();
    //all set
    for(int i = 0; i < N; ++i)
    {
        cin >> elevatorCost[i];
    }
    string emptyStr;
    getline(cin, emptyStr);
    for(int i = 0; i < N; ++i)
    {
        string line;
        getline(cin, line);
        istringstream iss(line);
        int floor;
        while(iss >> floor)
        {
            floorsForElevator[i].push_back(floor);
        }
    }
    for(int i = 0; i < N; ++i)
    {
        for(int j = 0; j < floorsForElevator[i].size(); ++j)
        {
            for(int k = j+1; k < floorsForElevator[i].size(); ++k)
            {
                int f1 = floorsForElevator[i][j];
                int f2 = floorsForElevator[i][k];
                int cost = elevatorCost[i]*(abs(f1-f2));
                G[f1].push_back(iii(cost, ii(f2, i)));
                G[f2].push_back(iii(cost, ii(f1, i)));
            }
        }
    }
    //now run Dijkstra
    priority_queue<iii> Q;
    Q.push(iii(0, ii(0, -1)));
    dist[0] = 0;
    while(!Q.empty())
    {
        iii triple = Q.top(); Q.pop();
        int current = triple.second.first;
        int currentElevator = triple.second.second;
        for(int i = 0; i < G[current].size(); ++i)
        {
            int child = G[current][i].second.first;
            int childElevator = G[current][i].second.second;
            int cost = G[current][i].first;
            if(currentElevator != childElevator && currentElevator != -1) cost += 60;

            if(dist[current] + cost <= dist[child])
            {
                dist[child] = dist[current] + cost;
                Q.push(iii(-dist[child], ii(child, childElevator)));
            }
        }
    }
    if(dist[K] > (1 << 20)) answers.push_back(-1);
    else answers.push_back(dist[K]);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    while(cin >> N)
    {
        cin >> K;
        read();
    }
    for(int i = 0; i < answers.size(); ++i)
    {
        //cout<<"CASE: "<<i<<endl;
        if(answers[i] == -1) cout<<"IMPOSSIBLE";
        else cout<<answers[i];
        cout<<'\n';
    }
    return 0;
}

Re: 10801 - Lift Hopping

Posted: Mon Aug 18, 2014 9:42 pm
by brianfry713
For input:

Code: Select all

2 99
100 1
0 1 98 99
1 98
Your code is printing 357 instead of 417, so you are probably not adding 60 for one of the times you switch elevators. Try adding in temporary debug print statements in your code and go step by step to try to figure out where your issue is.

Re: 10801 - Lift Hopping

Posted: Fri Nov 07, 2014 4:04 am
by kokx
Hi Everyone. For some reason, my code is working perfectly on all inputs given here (as in, gives the same output as udebug and as told here). However, I still get WA. Does anyone know what is wrong?

https://gist.github.com/kokx/e55475fce0bc835bdf45

I've also added my entire input file and output for convenience.

So, does anyone have an idea what is wrong with my code? Or some more tricky inputs?

Re: 10801 - Lift Hopping

Posted: Wed Nov 19, 2014 1:13 am
by brianfry713
If k = 0 print 0.

Re: 10801 - Lift Hopping

Posted: Fri Mar 27, 2015 8:38 pm
by hquilo
Hi,

It seems like the judge input does not have test cases in which no elevator stops at floor 0. Given this, for a test case such as (posted previously in this thread)

Code: Select all

2 99
10 40
1 2 3 4 99 0 12
3 4 2 0 12 99
it is OK to output

Code: Select all

IMPOSSIBLE
All times are UTC+02:00
Page 4 of 4

Powered by phpBB® Forum Software © phpBB Limited