mit-room
You probably are familiar with the classic problem where n dining philosophers have to choose how to grab two forks to eat their meal.
This problem deals with the more important issue of seating the philosophers on the table. Suppose there are n = 2k > 0 philosophers and they have to be seated around a round table placed in a round room. However, there are several considerations that complicate the matter:
- Each philosopher is assigned a seat from 1 to n. For simplicity, we assume that all philosophers are assigned numbers corresponding to their seats.
- All seats are arranged in a sequential circular order: 1, 2, ..., n.
- There are two diametrically opposite doors(A and B) from which the philosophers can enter the room. Door A is between seats numbered 1 and n and door B is between seats n/2 and n/2 + 1, so there are exactly n/2 seats between the doors in each direction.
- Exactly k philosophers line up in front of each door and no philosopher is willing to give up their place on the line or move to the line at the other door, so no further rearrangements are possible.
- However, the room is not large enough and the space between the table and the wall is very small. When somebody wants to pass somebody else who has already taken their seat, the latter must stand up (temporary) allowing the former to pass.
- All philosophers enter the room one by one. The door from which the next philosopher enters is not specified. Upon entering the room, a philosopher chooses whether to go left or right and starts walking in that direction, until reaching her assigned seat. Of course, everybody on the way must stand up to allow the philosopher to pass.
The philosophers do not like to have to stand up again once they have been seated, so they decided to do the seating in such a way as to minimize the number of times a philosopher has to stand up. They can do this by choosing from which door to let the next philosopher enter and also in which direction she moves.
Your task is to calculate the minimum number of times a philosopher has to stand up in an optimal solution, given the initial
line up of the philosophers in front of each door.
The first line of the input contains one integer, k (k <= 1500).
Line 2 contains k integers from 1 to n=2k: the order in which the philosophers line in front of door A. The first integer, is the number of the philosopher who is first in the line.
Line 3 contains the order in front of door B in the same format as Line 2.
There should be one integer on a line by itself:
the minimum number of times somebody has to stand up to allow somebody else to pass.
3
4 5 3
6 2 1Sample Output:
3Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.