### PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

**Setter:** Misha Chorniy

**Tester:** Zhong Ziqian

**Editorialist:** Taranpreet Singh

### DIFFICULTY:

Simple

### PREREQUISITES:

Implementation, Data-Structures.

### PROBLEM:

Given an array A of length N, Determine whether the array contains two positions i and j, i \neq j such that A_i \neq A_j and A_{A_i} == A_{A_j}.

Print Truly Happy, if we can find such pair of positions, otherwise print Poof Chef.

### SUPER QUICK EXPLANATION

- We can maintain a set for each distinct value, and for every position, x, insert A_i in the set corresponding to value A_{A_i}.
- This way, We can select two positions satisfying the required criteria if any set has more than one distinct value.

### EXPLANATION

First of all, let’s see the brute force solution.

We can iterate over every pair (i, j) of positions, check if A_i \neq A_j and A_{A_i} == A_j holds. If this holds for any pair, we can make the chef Truly Happy. But Sadly for us, this solution has Time Complexity O(N^2) and thus, will time out for Last Sub-task.

Now, Focus on the condition for a valid Pair (i, j), A_i \neq A_j and A_{A_i} == A_{A_j}.

Inequality is **usually** harder to handle than equality, so, focusing on Equality first tells us the following.

For the required pair of positions, if it exists, it holds that A_{A_i} == A_{A_j}. This means, that we can consider all positions having the same value of A_{A_i} together.

Now, For every distinct value of A_{A_i}, we have a number of values. The problem reduces to finding two distinct values A_i and A_j in the same set which has A_i \neq A_j.

We can see, the simplest way to do so is to make set for every distinct value A_{A_i} and add to it, the values A_i. Now, Chef will be happy, if we can select 2 elements from any one set.

This implies that Final condition for Existence of required Pair is, If any set has more than one element, It is always possible to pick at least one pair and make Chef Truly Happy.

**Alternative Implementation**

We can also replace Array of Sets with a single map, or even a single array, Implementation of which is left as an exercise.

**Challenge Problem**

Count the number of such pairs for a given array. Enjoy

### Time Complexity

Time complexity is O(N*logN) per test case. Can be optimized to O(N) too.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Setter’s solution

Tester’s solution

Editorialist’s solution

Feel free to Share your approach, If it differs. Suggestions are always welcomed.