MyFriends

SRM 398 · 2008-04-15 · by boba5551

SRM 398 · 2008-04-15 · by boba5551 · Graph Theory, Greedy, Math

Show categories

Class Name: MyFriends

Return Type: String

Method Name: calcFriends

Arg Types: (vector<int>, int)

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).

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

{8, 6, 4, 7, 5}
2
Returns: "IMPOSSIBLE"

{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

{7, 6, 5, 4, 4}
2
Returns: "IMPOSSIBLE"

{5, 6, 5, 4, 4}
1
Returns: "POSSIBLE"

{11, 10, 12, 10, 11}
2
Returns: "POSSIBLE"

68)

{4, 4, 4, 3, 2}
1
Returns: "IMPOSSIBLE"

If in the solution of ivan_metelsky, line if (tot % (N - 2) != 0) return "IMPOSSIBLE"; is commented this example passes.

69)

{6, 0, 0, 0, 0}
1
Returns: "IMPOSSIBLE"

if (res[0] != 0) return "IMPOSSIBLE"; for (int i=0; i<N; i++) if (res[i] < 0 || res[i] >= N) return "IMPOSSIBLE"; if (sum[i] > tot) return "IMPOSSIBLE";

71)

{6, 6, 6, 6, 6}
1
Returns: "POSSIBLE"

With only one sort in Havel-Hakimi this examples give IMPOSSIBLE, but it should give POSSIBLE - 2-regular graph with 5 vertices; cycle.

72)

{15, 15, 15, 15, 15}
3
Returns: "IMPOSSIBLE"

if (res[i] < 0 || res[i] >= N) return "IMPOSSIBLE"; into if (res[i] < 0 || res[i] > N) return "IMPOSSIBLE"; and without if (res[i] > i) return "IMPOSSIBLE"; "solution" fails

73)

{2, 1, 2}
1
Returns: "IMPOSSIBLE"

Without if (res[0] != 0) return "IMPOSSIBLE"; and if (res[j] == 0) return "IMPOSSIBLE"; fails

74)

{16, 17, 15, 15, 18, 17, 10, 16, 17}
6
Returns: "IMPOSSIBLE"

without if (res[j] == 0) return "IMPOSSIBLE"; and check about is something divisible if (tot % 2 != 0) return "IMPOSSIBLE"; if (tot % (N - 2) != 0) return "IMPOSSIBLE"; it fails

75)

{16, 15, 15, 12, 16, 17, 10, 16, 16}
6
Returns: "IMPOSSIBLE"

without if (tot % 2 != 0) return "IMPOSSIBLE"; if (res[j] == 0) return "IMPOSSIBLE"; fails

76)

{12, 11, 11, 11, 12, 14, 10, 13, 11}
6
Returns: "IMPOSSIBLE"

Without only if (tot % 2 != 0) return "IMPOSSIBLE"; it fails

78)

{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.

79)

{6, 7, 7, 7, 6}
1
Returns: "IMPOSSIBLE"

Breaks max-flow algorithm (that is for directed graphs) described http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlow2

Submissions are judged against all 117 archived test cases, of which 15 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class MyFriends with a public method string calcFriends(vector<int> sumFriends, int k) · 117 test cases · 2 s / 256 MB per case