You are not logged in. Please login at www.codechef.com to post your questions!

×

# CHHAPPY - EDITORIAL

Setter: Misha Chorniy
Tester: Zhong Ziqian
Editorialist: Taranpreet Singh

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 :P

# Time Complexity

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

# AUTHOR'S AND TESTER'S SOLUTIONS:

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

This question is marked "community wiki".

asked 09 Nov '18, 23:08 4.0k31103
accept rate: 22% 19.8k350498541

 1 My O(n) approach Using Hash tables answered 20 Nov '18, 19:10 2★kunnu120 518●9 accept rate: 5% Way to go kunnuuuuuu :D :) (22 Nov '18, 21:21)
 0 If set of distinct values of $A_i$ is greater than the set of distinct values of $A_{A_i}$, Chef will be truly happy, because there must be two (or more) different values of $A_i$ somewhere mapping on the same $A_{A_i}$. ans = ["Poor Chef","Truly Happy"] for ti in range(int(input())): n = int(input()) ays = list(map(int,input().split())) # unq = set(ays) aas = set(ays[a-1] for a in unq) print( ans[len(aas) < len(unq)] )  answered 15 Nov '18, 08:58 5★joffan 948●8 accept rate: 13%
 0 why this solution is getting AC? https://www.codechef.com/viewsolution/21455834 for (n>10000) I am not able to understand the approach... answered 16 Nov '18, 01:56 3★bk54 9●3 accept rate: 0% @vijju123 please reply (22 Nov '18, 21:14) bk543★ His approach is wrong, he somehow got lucky with the larger TCs. Dont look at his code for correct approach. (22 Nov '18, 21:24)
 0 Tester's solution is giving wrong output for the following input 2 12 45 12 58 82 48 66 64 3 11 85 55 90 9 55 22 52 33 23 46 24 35 1  The expected output is Poor Chef Poor Chef  Solution's output is Poor Chef Truly Happy  answered 17 Nov '18, 22:27 1 accept rate: 0%
 0 Hi , can some one please explain how so many different people have same approach exactly with same variables also ? in this link from 2nd solution to next page few other people also has exactly has same solutions with exact variables also. Looks like code chef has some loop hole so they are cheating others. i have verified for submissions which submitted during contest. answered 01 Dec '18, 20:59 12●1 accept rate: 0%
 0 Poor me, thought bruteforce was the only way. Thank you, kind sir Taranpreet answered 06 Dec '18, 20:39 2★shardic 2●2 accept rate: 0% No problem :) (07 Dec '18, 18:16)
 0 The Tester solved the problem without using Set. Can someone please explain his approach? answered 20 Dec '18, 10:55 0 accept rate: 0%
 0 The Tester solved the problem without using Set. Can someone please explain his approach? answered 20 Dec '18, 10:55 0 accept rate: 0%
 0 where is my code wrong i used set @vijju123 https://www.codechef.com/viewsolution/21543167 answered 26 Dec '18, 10:13 3★shivam51 1 accept rate: 0%
 0 Solution to challenge problem : 1)Sort the given array,and also maintain its earlier indices by its side. 2)Whenever we find a segment of numbers which are equal, for example, lets consider '2' here, in my example, 1 2 2 2 2 3--->The sorted array with original indices maintained by their side. I check the count of their indices and see if, they occurred at all, for example, 2 2 2 2--> 0 1 0 1 So, 1+1=2 and number of pairs in this segment are k*(k-1)/2=1 and add all such pairs over such special segments and get the final answer :) Nice problem, indeed :) answered 21 Jan, 21:37 -863●9 accept rate: 0%
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,409
×1,191
×849
×721
×154
×6

question asked: 09 Nov '18, 23:08

question was seen: 1,684 times

last updated: 21 Jan, 21:37