TopCoder problem "MyFriends" used in SRM 398 (Division I Level Three)



Problem Statement

    

There is a group of n kids, numbered 0 through n-1, where n is an odd number. Each kid has some friends within the group, and each kid knows how many friends each of the other kids has. Friendship is symmetric, so if kid 0 is a friend of kid 1, then kid 1 is a friend of kid 0. Each kid i also supports exactly one other kid (i+k) % n, not necessarily a friend.



You ask each kid to answer the following question: Consider each kid in the group except yourself and the kid you support. What is the sum of the number of friends each of them has? For example, if you ask kid 0 this question, and kid 0 supports kid 1, he should tell you (the number of friends kid 2 has) + (the number of friends kid 3 has) + ... + (the number of friends kid n-1 has).



You are given a int[] sumFriends, where the i-th element (0-indexed) is the answer given to you by kid i. Some of the kids might not be telling the truth (they are just kids, forgive them). Return "IMPOSSIBLE" if it is impossible for all the given answers to be accurate. Otherwise, return "POSSIBLE" (all quotes for clarity).

 

Definition

    
Class:MyFriends
Method:calcFriends
Parameters:int[], int
Returns:String
Method signature:String calcFriends(int[] sumFriends, int k)
(be sure your method is public)
    
 

Constraints

-sumFriends will contain odd number of elements.
-sumFriends will contain between 3 and 49 elements, inclusive.
-Each element of sumFriends will be between 0 and 9999, inclusive.
-k will be between 1 and (number of elements in sumFriends)-1, inclusive.
 

Examples

0)
    
{8, 9, 8, 8, 9}
2
Returns: "POSSIBLE"
We can get such sums only if kid 1 has 2 friends and all other kids have 3 friends. Such a situation is possible. For example: 
Kid             His/her friends
0               1, 3, 4
1               0, 2
2               1, 3, 4
3               0, 2, 4
4               0, 2, 3
1)
    
{7, 6, 5, 4, 4}
2
Returns: "IMPOSSIBLE"
2)
    
{5, 6, 5, 4, 4}
1
Returns: "POSSIBLE"
3)
    
{1, 2, 3}
1
Returns: "IMPOSSIBLE"
Here kid 2 supports kid 0, so he tells us the number of friends of kid 1. But it's obviously impossible for kid 1 to have 3 friends.

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8144

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=12170&pm=8144

Writer:

boba5551

Testers:

PabloGilberto , legakis , Olexiy , ivan_metelsky

Problem categories:

Graph Theory, Greedy, Math