Problem C
Cu Chi Tunnels

The tunnels of Cu Chi are an immense network of underground tunnels connecting rooms located in the Cu Chi District of Ho Chi Minh City. The Cu Chi tunnels were the location of several military campaigns in the 1960s. Nowadays, it is a popular tourist destination.

There are documents from trusted sources about a private network of tunnels in this area used by a secret forces unit but it has not been discovered. According to the documents, this private network has $N$ rooms (numbered from $1$ to $N$) connected by $N-1$ bidirectional tunnels. Room $1$ is the entry point from the ground surface to this underground network. From room $1$, you can follow the tunnels to go to any of the rooms. The rooms are numbered in such a way that, if you follow the shortest path from room $1$ to any room $X$, the sequence of visited rooms’ indices will be increasing. The image below shows a valid map of this network.

\includegraphics[width=0.5\textwidth ]{example1.png}

The network below is invalid, since the path from $1$ to $4$ is $1$ - $3$ - $2$ - $4$, which is not increasing:

\includegraphics[width=0.5\textwidth ]{example2.png}

There is also an old article from an unknown source mentioning about $D_ i$ which is the number of rooms directly connected to room $i$.

Given an array $D$ of size $N$, your task is to verify if it is possible to have such a network.


  • The first line contains an integer $N$ - the number of rooms in the network $(2 \leq N \leq 1\, 000)$.

  • The second line consists of $N$ integers $D_ i$ - the number of rooms that are directly connected to room $i$ $(1 \leq D_ i \leq N - 1)$.


Print YES/NO if it is possible/impossible to have such a network, respectively.

Sample Input 1 Sample Output 1
3 2 2 1 1 3 1 1
Sample Input 2 Sample Output 2
3 3 3 3

Please log in to submit a solution to this problem

Log in