You are not logged in. Please login at www.codechef.com to post your questions!

×

HOB2 - Editorial

6
1

PROBLEM LINKS

Practice
Contest

DIFFICULTY

EASY

PREREQUISITES

Greedy

PROBLEM

There is a hotel that has R rooms, numbered 0 through R-1. The hotel has this following scheme of allocating rooms to guests. If a guest prefers room K, then the hotel manager checks rooms in order K, K+1, ..., R-1, 0, 1, ..., K-1 and allocates the guest in the first free room in this list or report the guest that all rooms are occupied. The number of occupied rooms that are checked is called the inconvenience of the guest.

There were N guests that came to the hotel, numbered 0 through N-1. For each guest i, we know his time of visit (time[i]) and his inconvenience (inconv[i]). However, we lose the information of his preferred room and his stay time.

Determine the preferred room (room[i]) and the stay time (stay_time[i]) of each guest i such that all information are consistent.

EXPLANATION

The problem statement says that an answer is always guaranteed to exist. We will show that an answer exists if and only if 0 ≤ inconv[i] ≤ min(i, R) for all 0 ≤ i < N. We will prove the implication in both directions as follows.

First, the condition is necessary because when the i-th guest comes, the hotel can only have at most i rooms occupied already, so inconv[i] cannot be larger than i. Of course, inconv[i] cannot be larger than R as well because the hotel only has R rooms.

Second, the condition is sufficient because we can always construct a consistent answer as follows. We will separate the answer into two phases.

Phase 1. Allocating guests 0 through R-1

We can always make guest i finally stay in room i for 0 ≤ i ≤ R-1 as follows. First, guest 0 will have zero inconvenience, so we can set room[0] = 0. Next, guest 1 can have 0 or 1 inconvenience. If inconv[1] = 0, then we can set room[1] = 1. If inconv[1] = 1, then we can set room[1] = 0 so that when the manager checks room 0, the room has already been occupied and finally he is allocated to room 1.

In general, we can set room[i] = i - inconv[i]. For this to work, all previous guests must still stay when we process guest i, so we can set stay_time[i] = 31415926 (i.e. the maximum allowed duration).

for i := 0; i ≤ R-1; i++:
    room[i] = i - inconv[i]
    stay_time[i] = 31415926

Phase 2. Allocating guests R through N-1

If the number of guests is less than or equal to R, then we are done. Else, we have to allocate guests R through N-1. Here we can always allocate the remaining guests as follows. Note that now all rooms are occupied with the maximum possible stay times. There are two possible conditions for guest i, i ≥ R.

inconv[i] = R

Since all R rooms are occupied, we can set room[i] to any room as guest i's inconvenience will be R. We can simply set room[i] = 0. We can also set stay_time[i] to any value, so let's set stay_time[i] = 31415926.

inconv[i] < R

We can always make guest i finally stay in room R-1. Here is how to do this. Let last_guest be the index of the last guest that finally stayed in room R-1 (initially it is R-1). Then, we can set room[i] = R - 1 - inconv[i] and stay_time[last_guest] = time[i] - time[last_guest]. In this way, guest last_guest will leave at the same time guest i arrives, so we can still have available room for guest i at room R-1. We also set stay_time[i] = 31415926 and also update last_guest = i.

last_guest := R-1
for i := R; i ≤ N-1; i++:
    if inconv[i] == R:
        room[i] := 0
    else:
        room[i] = R - 1 - inconv[i]
        stay_time[last_guest] := time[i] - time[last_guest]
        last_guest := i
    stay_time[i] := 31415926

In conclusion, we have a very simple O(N) solutions that always allocates all guests consistently.

SETTER'S SOLUTION

Can be found here.

TESTER'S SOLUTION

Can be found here.

This question is marked "community wiki".

asked 18 Feb '13, 00:05

fushar's gravatar image

3★fushar ♦♦
16345853
accept rate: 0%

edited 18 Feb '13, 16:09

anton_lunyov's gravatar image

6★anton_lunyov ♦
6.7k62119138

During phase 1, If inconv[1] = 1, shouldn't we set room[1] = 0 instead of room[0] = 0?

(18 Feb '13, 09:35) kartikkukreja5★

It is fixed.

(18 Feb '13, 16:37) anton_lunyov ♦6★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,643
×3,748
×1,000
×8
×1

question asked: 18 Feb '13, 00:05

question was seen: 3,491 times

last updated: 18 Feb '13, 16:37