## 10801 - Lift Hopping

Moderator: Board moderators

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10801 - Lift Hopping

20 seconds riding the first elevator.
http://www.uvatoolkit.com/problemssolve.php
Check input and AC output for thousands of problems on uDebug!

Muftee_Ruet
New poster
Posts: 10
Joined: Fri Sep 16, 2011 6:36 am

### Re: 10801 - Lift Hopping

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
``````

afruizc
New poster
Posts: 15
Joined: Sat Oct 13, 2012 2:04 am

### Re: 10801 - Lift Hopping

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
``````
Last edited by afruizc on Tue Jan 08, 2013 2:32 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10801 - Lift Hopping

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.
Check input and AC output for thousands of problems on uDebug!

afruizc
New poster
Posts: 15
Joined: Sat Oct 13, 2012 2:04 am

### Re: 10801 - Lift Hopping

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

hpjhc
New poster
Posts: 17
Joined: Wed Jun 26, 2013 10:35 am

### Re: 10801 - Lift Hopping

Code: Select all

``delete after AC``
Last edited by hpjhc on Thu Mar 13, 2014 12:27 pm, edited 1 time in total.

uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

### Re: 10801 - Lift Hopping

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.
Check input and AC output for over 7,500 problems on uDebug!

nbacool2
New poster
Posts: 24
Joined: Fri Jul 25, 2014 4:31 pm

### Re: 10801 - Lift Hopping

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];
{
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);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
while(cin >> N)
{
cin >> K;
}
for(int i = 0; i < answers.size(); ++i)
{
//cout<<"CASE: "<<i<<endl;
cout<<'\n';
}
return 0;
}
``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10801 - Lift Hopping

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.
Check input and AC output for thousands of problems on uDebug!

kokx
New poster
Posts: 1
Joined: Fri Nov 07, 2014 3:52 am

### Re: 10801 - Lift Hopping

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?

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10801 - Lift Hopping

If k = 0 print 0.
Check input and AC output for thousands of problems on uDebug!

hquilo
New poster
Posts: 13
Joined: Fri May 02, 2014 9:45 pm

### Re: 10801 - Lift Hopping

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
``````