VFRIENDS - Very Friends
NOTICE: The test cases for this problem are not as hard as intended. If you've solved this problem, and think your solution is up for it, try VFRIEND2!
You are creating a new soical network for dogs. Wow. The dogs don't have many possibilities for interacting with your website, but they can bark how many friends they want. E.g. if a dog wants to have much 8 friends it will bark 8 times, and if it doesn't want any friends, it'll just stay quiet.
After spending a good year of your life collecting these barks, you are finally ready to assign a friend list for each dog. The only problem is: You are not sure whether it is actually possible. Thus before you proceed you would like to write a program, that given a list of N wishes wi, outputs HAPPY if it is possible to make a friend list for each dog i of length wi, or SAD if some dog will have to get more or fewer friends than it wished for.
Notice: Being friends is considered an irreflexive, symetric relation.
Update: If you manage to solve this problem much efficiently, have a look at VFRIEND2, which is a so harder version of this problem.
Input
The first line will contain a single integer T - the number of test cases to process.
Each following lines will start with an integer 0 ≤ N ≤ 105 followed by an ordered list of N wishes 0 ≤ wi ≤ 105.
Output
Write the answer - HAPPY or SAD - for each test case on a separate line.
Example
Input: 3
3 0 1 1
5 0 1 2 3 4
6 1 1 2 2 3 3 Output: HAPPY
SAD
HAPPY
Explanation
In the first case we can make dog 2 and 3 be friends.
In the second case no assignment that works, since dog 5 would have to be friends with everyone, but dog 1 doesn't want that.
hide comments
Sivakumaran M:
2014-02-18 16:20:38
@thomas: can you provide a test case where my soln fails? id: 11087727
|
|
Kevin Sebastian:
2014-02-18 16:20:38
@author any tricky test cases |
|
|RAMSDEN|:
2014-02-18 16:20:38
@author can u pls check my soln id 11082248
|
|
anurag garg:
2014-02-18 16:20:38
@thomas thank you for your response
|
|
Thomas Dybdahl Ahle:
2014-02-18 16:20:38
@anurag garg: You are right about symetric. I've fixed the statement. You are wrong on "0 1 3 3 3 4 4 5 5 8" Last edit: 2014-02-17 17:47:03 |
|
anurag garg:
2014-02-18 16:20:38
@thomas
|
|
Thomas Dybdahl Ahle:
2014-02-18 16:20:38
RAM§DEN: Yes
|
|
|RAMSDEN|:
2014-02-18 16:20:38
@author is the wishlist sorted in a non decreasing order?? Last edit: 2014-02-17 16:20:45 |
|
Bhavik:
2014-02-18 16:20:38
@thomas: can you kindly chk id:11081408...i am unable to find test case where my algo fails...
|
|
Thomas Dybdahl Ahle:
2014-02-18 16:20:38
If n=0 no doges will be sad. |
Added by: | Thomas Dybdahl Ahle |
Date: | 2014-02-17 |
Time limit: | 1s-2s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 GOSU |