There are several rooms in the same hall on the same side of the hall in the hotel. The distance between adjacent rooms equals 1 meter. You know which rooms are not vacant and which are. New group of tourist arrived and is waiting to check into.You want everyone to check into separate room so that the distance between the tourists' rooms would be as long as possible.
Input:First you enter the number of vacant rooms and the number of tourists
Then the vacant rooms' numbers
Output: One number- the possible maximum distance between tourists' rooms
Example:
Input:
7 4
3 6 8 12 16 21 28
Output:
7
Do not have a slightest idea how to perform that task((Maybe someone can at least think of action plan
I don't even understand the result: 7. Can you explain why is the result 7 in this case?
Yes,of course.We have 7 vaccant rooms with room numbers 3,6,8,12,16,21,28. So the distances between those rooms are 3,2,4,4,5,7 accordingly. The number of tourist is 4 as it's given in the first row of input. For example,first two tourists we check into rooms with numbers 3 and 28. Then we have to check into rooms two last tourists so that the distance between them and first two tourists would be as long as possible. The best decision is to provide the third tourist a 12th room, the fourth tourist the 21st room. All in all, tourist №1 is checked into room number 3, №2 - 12,№3 - 21, №4- 28. The distance between those rooms is 9,9,7. The minimum is 7 and that's the answer
(Sep-30-2020, 10:01 PM)Katenn Wrote: [ -> ]Output: One number- the possible maximum distance between tourists' rooms
/.../
The distance between those rooms is 9,9,7. The minimum is 7 and that's the answer
Well described problem is 80% of the solution they say. Is it minimum, maximum or arbitrary ;-)
You could brute force this by generating all the ways to accomodate the tourists in the empty rooms. For each combination you compute a score which is the smallest distance between two tourists. Finally, you select a combination with the highest score.
When there are many empty rooms and many tourists, you will need to find a more thrifty algorithm.
There are several rooms in the same hall on the same side of the hall in the hotel. The distance between adjacent rooms equals 1 meter. You know which rooms are not vacant and which are. New group of tourist arrived and is waiting to check into.You want everyone to check into separate room so that the distance between the tourists' rooms would be as long as possible.
Input:First you enter the number of vacant rooms and the number of tourists
Then the vacant rooms' numbers
Output: One number- the possible maximum distance between tourists' rooms
Example:
Input:
7 4
3 6 8 12 16 21 28
Output:
7
Explanation: We have 7 vaccant rooms with room numbers 3,6,8,12,16,21,28. So the distances between those rooms are 3,2,4,4,5,7 accordingly. The number of tourist is 4 as it's given in the first row of input. For example,first two tourists we check into rooms with numbers 3 and 28. Then we have to check into rooms two last tourists so that the distance between them and first two tourists would be as long as possible. The best decision is to provide the third tourist a 12th room, the fourth tourist the 21st room. All in all, tourist №1 is checked into room number 3, №2 - 12,№3 - 21, №4- 28. The distance between those rooms is 9,9,7. The minimum is 7 and that's the answer
I wrote code only for 4 tourists now. And here it is:
vr, t =map(int,input().split())
l=list(map(int,input().split()))
d=[] #the list with distances
for i in range(len(l)-1):
d.append(l[i+1]-l[i])
sum1 = d[0]
sum2 = d[1]
sum3 = sum(int(d[m]) for m in range(2, int(len(d))))
i=2
k=2
max = 0
for j in range(1,len(d)-1): #(1)we are increasing the distance between the second and the first room
while sum3 != d[len(d)-1]:#(2)(we are increasing the distance between the second and the third room)
sum2+= d[i]
sum3-=d[i]
i+=1
a = min(sum1,sum2,sum3)
if max < a:
max=min(sum1,sum2,sum3)
sum1+=d[j]
i = k+1
sum2=d[i-1]
sum3 = sum(int(d[m]) for m in range(i, int(len(d))))
k += 1
print(max)Now it became obvious that as the number of tourists grows so the number of inner loops on the lines which i marked as 1 and 2. As for sums we can put them in the list,I assume. But I don't quite understand yet how to make a connection between the number of tourists and the number of loops(so that the number of loops also would grow)
Some thoughts. It's usually useful to look for 'low hanging fruits'. In this particular case they could be:
- if number or tourists and number or rooms are equal then maximum separating distance is minimum distance between rooms
- if there are two tourists then distance between them is sum of distances between all rooms
If we eliminate these two cases with have situation where we have 2 < number of tourists < number of rooms. This may or may not lead to creating some algorithm.
The way I would approach it -
The first two rooms are at the extremes.
Divide the difference by the number of remaining rooms needed + 1 (which is the number of needed intervals).
Choose rooms closest to those points.
Using your example -
First 2 are 3 and 28.
Difference between = 25. 25/3 = 8.33
3+8.33 = 11.33
3+8.33+8.33 = 19.66
Closest to 11.33 is 12
Closest to 19.66 is 21
Alternative is a repetitive process - do as above to get the 12, then get the distance 12 to 28 (16), divide now by 2 (8), add (12+8 = 20), get closest room (21).
Here is another approach: it is easy to find if there is a solution where the minimal distance between tourists is at least a given number x. For this, put the first tourist in the first room with number n, then the next tourist must be at least in the first room which number is at least n+x. Continue this procedure with the remaining tourists, adding each time at least x to the last given room number until you find a solution or an impossibility.
Then use a dichotomic algorithm. If the distance x is possible (the technical term is feasable) and the distance y is not, then if y == x + 1, x is the searched optimum, otherwise try with (x+y)//2 and replace x or y by this number.
This algorithm's complexity is about n log(n) or something similar.
This is the sticks problem that is discussed in another thread. From the provided example the initial list contains the values [3,2,4,4,5,7] and the four tourists are the sticks. You need to keep the subsets, or their length, and do a little math to get the room numbers, but the same code can be used to solve both problems.