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.
Got AC in 1.22s with a clumsy PyPy solution and realized there's something I need to learn to get AC in pure Python. But before investigating, I've decided to debug an earlier idea taking advantage of efficient Python idioms and was absolutely floored with the result. Learned something new afterwards, but didn't beat the time of my own adhoc =) Python has just obsoleted a bit of graph teory.
Hi , is there Russian translation??
Thomas Dybdahl Ahle:
@Filip, @aqfaridi @Ujjwal Prakash: There is a harder version (not allowing O(n^2) solutions) at VFRIEND2. I've updated this problem description with a link.Last edit: 2016-01-02 13:57:26
nice problem, learned a lot but weak test cases
a really good problem ... learned something new :)