ECOO '21 P6 - Problematic Pathways

View as PDF

Submit solution

Points: 30 (partial)
Time limit: 5.0s
Memory limit: 1G

Problem types

In ECOOville there is a neighbourhood named ECOO in which there is a street named ECOO. There are a number of children who live on ECOO street and there are a number of pensioners who live on the street. There are N children, each of whom belongs to one of K friend groups. The children's locations on the street are such that the i^{th} child lives in the i^{th} house from the left.

ECOO street is a very busy but narrow single lane street accessible to bicycles and pedestrians only. Because of this, the municipality decided to make each segment of the street (between house i and house i+1) a one-way segment of the street. This is done so that only one moving pedestrian or a bicycle can go through at a time.

However, they cannot decide on the flow of traffic on each segment. The ECOO Parents Association (EPA) wants their kids to have fun. Thus, they want the number of pairs of friends such that one friend can visit the other by taking the one-way roads (C) to be maximal.

On the other hand, the ECOO Elderly Association (EEA) does not like the noise that the children make when they are with their friends. Thus, they want to minimize C. Eventually, they came to the compromise that both parties will be happy if C=\lambda.

Is it possible for the municipality to direct the flow of traffic such that C=\lambda?


1 \le N \le 5000

1 \le K \le N

0 \le \lambda \le \frac{N(N-1)}{2}

1 \le a_i \le K

Subtask 1 [5%]

1 \le N \le 20

Subtask 2 [10%]

1 \le N \le 100

Subtask 3 [5%]

1 \le N \le 400

Subtask 4 [20%]

1 \le N \le 1000

Subtask 5 [60%]

No additional constraints.

Input Specification

The first line of input contains 3 integers N, K, and \lambda.

The next line contains N integers a_i, the friend group of the i^{th} child.

Output Specification

If it is not possible to make C=\lambda, print not happy on one line, otherwise, print happy on one line.

Sample Input 1

4 1 6
1 1 1 1

Sample Output 1


Explanation for Sample Output 1

If all the roads are directed in the same way, for all \frac{4(3)}{2}=6 pairs of friends, one can visit the other.

Sample Input 2

4 1 5
1 1 1 1

Sample Output 2

not happy


There are no comments at the moment.