2011 Canadian Computing Competition, Stage 2

Day 2, Problem 1: Reorganization

Alice and Bob own a huge company. This company was losing money consistently over the last 30 years, since its owners spent too much time playing games with mathematicians. Alice and Bob decide to make a change.

Alice and Bob start by giving unique employee IDs to each of the n employees, consecutive positive integers starting from 1.

Then, Alice and Bob give unique ranks to each employee. Each rank is a positive integer. After this, they plan to reorganize the company, by making sure that the employees satisfy the following conditions:

1. There is exactly one director, who has no supervisor;
2. Except for the director, each employee has a supervisor, and this supervisor has a smaller employee ID and a higher rank (the value of rank is smaller); and
3. Each employee can supervise at most 2 people.

Alice and Bob are eager to know whether their company can be reorganized successfully.

Input Format

The first line contains n (1 ≤ n ≤ 100000), indicating the number of employees. On the next n lines are n distinct integers R_i (1 ≤ R_i ≤ 10⁷), one integer per line, each indicating the rank of an employee. Employees are given in increasing order of employee ID.

Output Format

Output YES if the company can be reorganized successfully; output NO otherwise.

Sample Input 1

6
1
6
5
2
3
4

Sample Output 1

NO

Explanation

Employee with rank 1 has employee ID 1, and thus, must be the director. Employees 2 and 3 (with ranks 6 and 5) can only be supervised by employee 1 (with rank 1). However, no other employee (4, 5, or 6) can be supervised by employee 2 or employee 3, since ranks of supervisors must be smaller than those of the employees they supervise.

Sample Input 2

6
1
6
2
3
4
5

Sample Output 2

YES

Explanation

Employee 1 (rank 1) supervises both employee 2 (rank 6) and employee 3 (rank 2).

Employee 3 (rank 2) supervises employee 4 (rank 3) and employee 5 (rank 4).

Employee 4 (rank 3) supervises employee 6 (rank 5).

All Submissions
Best Solutions

Point Value: 15 (partial)
Time Limit: 2.00s
Memory Limit: 256M
Added: Jun 06, 2011

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

Input files 5 through 8 each contain one integer too few. I will post an update when this is fixed.

Fixed. I've rejudged all submissions.