# Problem: World Bus Driving Championships

Want to try solving this problem? You can submit your code online if you log in or register.

## World Bus Driving Championships

Input File: busin.txt
Output File: busout.txt
Time Limit: 1 second
Memory Limit: 32 MB

The most exciting moment of your entire life is almost here. The 2011 World Bus Driving Championships (WBDC) are coming to Australia, giving you a once-in-a-lifetime opportunity to watch the incredible skills of bus driving greats such as Stan Butler, Otto Mann, Ernie Prang and of course the one and only eight-time world bus driving champion Jim Thomas.

The WBDC runs the enormous competition in a knock-out tournament format. The organisers select the top N bus drivers from a series of national competitions around the world, then bring them to the finals to compete in a series of one-on-one matches involving a display of bus racing, bus demolition derby and buses flying over lines of motorcycles.

Each bus driver has a competitor number and a unique skill level, which you have carefully calculated from exhaustive analysis of every bus driving competition since 1953. In any match, you are certain that the driver with the higher skill level will win.

The competition is split into a number of rounds. In each round of the competition,

• all bus drivers are sorted by their competitor number;

• the first bus driver is paired with the second, third with the fourth, fifth with sixth, etc.; and

• the winner of each one-on-one match (i.e. the one with the higher skill level) will progress through to the next round.

This continues until only one bus driver is remaining: the 2011 World Bus Driving Champion. There will always be an even number of drivers in any round of the competition, as N is always chosen to be a power of two.

Due to the phenomenal demand for seats at WBDC matches, tickets are extremely expensive. You have made a list of the bus drivers that you wish to see compete, and now need to determine the minimum number of matches you need to attend in order to see each of these bus drivers at least once.

### Input

The input file will consist of three lines.
• The first line of input will contain two integers N and K. N represents the total number of bus drivers competing, while K represents the number of bus drivers you wish to see compete (1 ≤ K ≤ N and 2 ≤ N ≤ 219).

• The second line of input will contain N integers, each between 1 and 1,000,000 inclusive. The ith integer is the skill level of the bus driver with competitor ID i, starting from 1.

• The third line of input will contain K integers, the competitor ID numbers of the bus drivers you wish to see compete.

### Output

Your output should contain one line with a single integer: the minimum number of matches you must attend in order to see all your favourite bus drivers compete at least once.

```8 4
2 5 3 6 4 7 8 1
2 4 5 8
```

```3
```

### Explanation

The matches in the first round will be:

• 1 vs 2 (won by 2)
• 3 vs 4 (won by 4)
• 5 vs 6 (won by 6) Attend this match to see 5
• 7 vs 8 (won by 7) Attend this match to see 8

The matches in the second round will be:

• 2 vs 4 (won by 4) Attend ths match to see 2 and 4
• 6 vs 7 (won by 7)

The final match in the third round will be:

• 4 vs 7 (won by 7, the 2011 World Bus Driving Champion)

By attending the three marked matches, all your favourite bus drivers can be seen at least once. This is the fewest number of matches needed to see all your favourite bus drivers.

### Scoring

The score for each input scenario will be 100% if the correct answer is written to the output file, and 0% otherwise.

For 30% of the available marks, N ≤ 20.

Privacy statement
© Australian Mathematics Trust 2001-2024

Contact: training@orac.amt.edu.au
`Page generated: 13 April 2024,  6:25am AEST`