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.


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.


Write the answer - HAPPY or SAD - for each test case on a separate line.


3 0 1 1
5 0 1 2 3 4
6 1 1 2 2 3 3 Output: HAPPY


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
Bhavik: 2014-02-18 16:20:38

what if n=0?

Thomas Dybdahl Ahle: 2014-02-18 16:20:38

Problem levl 2: http://www.spoj.com/problems/VFRIEND2/ So scare!

Jacob Plachta: 2014-02-18 16:20:38

Such happy solution, many excite.

newbie: 2014-02-18 16:20:38

@author.can u tell will my approach work

Thomas Dybdahl Ahle: 2014-02-18 16:20:38

Jacob you have so happy solution!

Jacob Plachta: 2014-02-18 16:20:38

Wow, much linear solution.

Thomas Dybdahl Ahle: 2014-02-18 16:20:38

Intended solution is very linear time. I will try to update the problem to reflect this.

Last edit: 2014-02-17 08:06:26

Added by:Thomas Dybdahl Ahle
Time limit:1s-2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU