JOIN
Get Time

   Problem Statement  

 Problem Statement for CloneGauntlet2

Problem Statement

    

Fenrir is playing the last stage of a video game. In this stage he has to face the Clone Gauntlet! The gauntlet consists of N rooms, numbered 0 to N-1. The rooms are connected by N-1 doors. Each door can only be traversed in one direction: from a room with a smaller number to a room with a larger number.



At the beginning of the stage Fenrir was magically transported into room 0. He wins the game if he reaches room N-1.



The doors are placed in such a way that each room other than room 0 has exactly one entrance. (I.e., for each room x > 0 there is exactly one room y < x such that there is a door from room y to room x.) Each room can have arbitrarily many exits, possibly zero.



To complicate matters, each room contains exactly one pressure plate. Each pressure plate is linked to at most one of the doors. (Multiple pressure plates may be linked to the same door. There may be some doors that aren't linked to any pressure plate.) A door can only be traversed if at least one of its linked pressure plates is depressed.



Fenrir's situation seems bleak: In order to use a door, he has to stand on a corresponding pressure plate. But if he stands on the plate, he cannot go through the door. And if he leaves the plate, it will no longer be depressed and the door won't open.



Luckily for Fenrir, this is the Clone Gauntlet. At any point in time Fenrir can create a clone of himself. The clone will appear in the same room as Fenrir. Fenrir can have arbitrarily many clones at the same time, and he can control each of them independently, even if they are no longer in the same room as he is. The clones can move between rooms, but they must follow the same rules for movement as Fenrir himself. However, there is one exception: if a clone steps onto a pressure plate, it remains locked in that position until the end of the game. Clones never disappear: once Fenrir makes a clone, the clone will exist until the end of the game.



You are given a int[] parent with N-1 elements, and a int[] connection with N elements. For each i between 0 and N-2, inclusive, there is a door from the room parent[i] to the room i+1. For each i between 0 and N-1, inclusive, the pressure plate in room i is linked to the door that can be used to enter the room connection[i]. (If connection[i] is 0, this pressure plate is not linked to any door, as there is no door that leads to room 0.)



Return the smallest number of clones Fenrir needs to create to complete the gauntlet. If Fenrir cannot complete the gauntlet no matter how many clones he makes, return -1 instead.



 

Definition

    
Class:CloneGauntlet2
Method:minClones
Parameters:int[], int[]
Returns:int
Method signature:int minClones(int[] parent, int[] connection)
(be sure your method is public)
    
 

Constraints

-N will be between 2 and 50, inclusive.
-parent will contain exactly N-1 elements.
-For each valid i, 0 <= parent[i] <= i.
-connection will contain exactly N elements.
-Each element of connection will be between 0 and N-1, inclusive.
 

Examples

0)
    
{0,0}
{1,2,0}
Returns: 1
This is how the stage looks like:
  • There are two doors: from room 0 to room 1, and from room 0 to room 2.
  • The pressure plate in room 0 unlocks the door from room 0 to room 1.
  • The pressure plate in room 1 unlocks the door from room 0 to room 2.
  • The pressure plate in room 2 does nothing.
One clone is enough to win this stage. Here is one possible way to reach the last room with the help of a single clone:
  1. Fenrir stands on the pressure plate in room 0.
  2. Fenrir clones himself.
  3. The clone uses the door from room 0 to room 1.
  4. The clone stands on the pressure plate in room 1, unlocking the door to room 2.
  5. Fenrir leaves the pressure plate in room 0, thereby locking the door from room 0 to room 1.
  6. Fenrir uses the door from room 0 to room 2 and wins the game.
1)
    
{0}
{0,0}
Returns: -1
The pressure plate in room 0 does nothing. Fenrir is unable to open the door to room 1.
2)
    
{0}
{1,1}
Returns: 1
3)
    
{0,0,0,0}
{1,2,4,4,4}
Returns: 2
4)
    
{0,1,2,3,0,5,6,7}
{1,5,6,7,8,2,3,4,0}
Returns: 4

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       2016 TCO Algorithm Russia Regional - Division I, Level Two