Hi everyone,
I wanted to share a problem I came across during a recent interview. I have also shared my attempts and experice during the interview and a possible solution I came up with after the interview.

The description of the question is:

DESCRIPTION

Problem Statement

It is high alert at the SPD-quarters. Emperor Gruumm has sent his newly recruited team of villains. The specialty of this team is that each villain has an associated amount of power.
Red and Blue rangers are sent to fight this new team of villains. Since the rangers have no information about these villains, Cruger has given each ranger a range of power. Each ranger can only kill the villains who have powers in their range.
More precisely, Red-ranger is given a range 1 to A, both inclusive and Blue-ranger is given a range B to C, both inclusive. To make sure that villains don’t predict this range easily, Gruumm has made sure that the following constrains hold:

1 <= B <= C
B <= A <= C

and if a ranger fights a villain with power x, only he should fight all the villains who have power x, that is, if Red-ranger decides to fight a villain with power 2 then, Red-ranger has to fight with all the villains who have power 2.
Both the rangers have reached the attacked area. They observe that the villains are coming one-by-one, so they decide that they’ll also fight one at a time. So, at any given time, one ranger will fight and other will rest.
It takes 1-minute to kill a villain and 2-minutes to switch places, that is, the ranger who is fighting goes to rest and the ranger who is resting comes to fight.

Rangers would like to kill all the villains as-fast-as-possible. Please find the minimum time that is needed to kill all the villains.

Input Format

The first line contains an integer C.
The next line contains an integer B.
The next line contains an integer A.
The next line will contain V, the number of villains.
The next V lines will contain V integers, the power of each villain in order.

Constraints

1 <= C <= 103
1 <= B <= C
B <= A <= C
1 <= V <= 103
1 <= power of any villains <= C

Output Format

A single line containing the minimum time needed to kill all the villains.
Evaluation parameters

Sample Input

3
2
2
6
1
2
3
2
1
2

Sample Output

10

Explanation

1. Red-ranger can kill villains with power 1 and 2
2. Blue-ranger can kill villains with power 2 and 3
3. So, Red-ranger kills 1st and 2nd villains, it takes time 2 minutes.
4. They switch places, 2 minutes.
5. Blue-ranger kills 3rd villain, 1 minutes.
6. They switch places, 2 minutes. Since Red-ranger has killed 2nd villain (power = 2), Red-ranger is compelled to kill 4th villain (power = 2).
7. Red-ranger kills 4th, 5th and 6th villains, 3 minutes.
8. A total of 10-minutes.

My Experience

During the interview I tried using a greedy approach, but I soon realised that it would not work as once a power ranger fights a villan of a certain power, the same power range must fight this villan every time in the future as well, so a greedy choice would be suboptimal. I then tried thinking of a DP approach I was not able to come up with the solution in time.

Question

After thinking about it for a while, would using a breadth first seach approach work here? As in each recursive step we keep track of the villan number we are at, the power range of the each of the ranger and a dictionary containing the villans that each of the power rangers fight (this dictionary is what we fill in each recursive step).

I wanted to know if this solution is correct or if a more optimal solution exists.

Thanks.