10801 - Lift Hopping

All about problems in Volume 108. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

Re: 10801 - Lift Hopping

Post by brianfry713 » Tue Sep 25, 2012 1:07 am

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

Post by Muftee_Ruet » Mon Dec 10, 2012 10:36 am

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

Post by afruizc » Mon Dec 17, 2012 8:16 pm

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

Post by brianfry713 » Tue Dec 18, 2012 12:49 am

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

Post by afruizc » Fri Dec 21, 2012 7:47 am

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

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

Re: 10801 - Lift Hopping

Post by hpjhc » Thu Mar 13, 2014 11:14 am

Code: Select all

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

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

Re: 10801 - Lift Hopping

Post by uDebug » Thu Mar 13, 2014 11:53 am

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!

Find us on Facebook. Follow us on Twitter.

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

Re: 10801 - Lift Hopping

Post by nbacool2 » Sun Aug 17, 2014 11:08 pm

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

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

Re: 10801 - Lift Hopping

Post by brianfry713 » Mon Aug 18, 2014 9:42 pm

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

Post by kokx » Fri Nov 07, 2014 4:04 am

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

Post by brianfry713 » Wed Nov 19, 2014 1:13 am

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

Post by hquilo » Fri Mar 27, 2015 8:38 pm

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

Post Reply

Return to “Volume 108 (10800-10899)”