6. Match the group

In Computer Science branch of ABC College of Engineering, there are n students; numbered 0 through n-1(where n is an odd number). As usual, each of the student has some friends within the same branch, and each of them knows how many friends each of the other student has. Friendship is symmetric, so if a student 0 is a friend of student 1, then student 1 is also a friend of student 0.

An assignment is given to the students by Prof. XYZ, for which groups of 2 are to be formed within the classroom, for which each student has been asked to submit the name of the student with whom they want to form their assignment group. Each student ‘i’ has got the freedom to choose exactly 1 other student (i+k)%n as his/her partner for the assignment, not necessarily a friend; and each student is free to select anyone. For example, if a student 0 selects student 1 then too student 1 can select any student other than 0 as his group-mate.

You being the Prof. XYZ ask each student to submit the "sum of the number of friends each of the student in class have, other than the student himself and the one he chose for the assignment group”. For example, if student 0 selects student 1 for his group, he should submit (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 vector sumFriends, where the i-th element (0-indexed) is the answer given to you by student i. To make the things complicated for you, some of the students might not be telling the truth. Return "IMPOSSIBLE" if it is impossible for all the given answers to be accurate. Otherwise, return "POSSIBLE".

Note: all quotes for clarity

Instructions to use Open PBT Client:

1. Specify the work directory path in the 'Work Directory Path' field. The path should correspond to your solution work directory.
2. Download the Support files by clicking the Get Support Files

.

3. You will find the problem directories containing:
   • problem.h file
   • problem.c file

in your work directory.

4. Write your solution in .c file

Step 1:

In your Solution File:

1. For C++ : string findFriends(vector<int> sumFriends, int k)
2. For C      : char* findFriends(int sumFriends[],int N, int k)

Step 2:

1. Pass the following parameter to the method findFriends()

sumFriends is an integer array, represents the answer given by each students as mentioned in the problem description.
k is the minimum number of freind a student had.

Step 3:

Write the appropriate code as mentioned in the problem description by following the below given Constraints.

1. The input should be the two dimension integer array provided to the method with some entries in the matrix.
2. The entries specify the position of the Queens and Knights in the chess board (matrix). 1 for Queen and 2 for Knight
3. You need to figure out the position of the Queens and Knights in the chess board, which can be additionally added to the board so thus no peices will attack anyone
4. Your method should return the chess board that is the two dimension array with some additional entries.
5. If your method will able to add atleast one pair of Queens and Knights, you will get the 50% credit.
6. Read Constraints carefully.

The Prototype of the function is defined below as per the language:

For C++ : string findFriends(vector<int> sumFriends, int k)
For C      : char* findFriends(int sumFriends[],int N, int k)

• Where the function takes sumFriends and k as the input and returns a string ("IMPOSSIBLE" or "POSSIBLE") that is case sensitive

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.

Example 1

Input

{8, 9, 8, 8, 9}
2

Output

Function returns "POSSIBLE"

Explanation:

We can get such sums only if student 1 has 2 friends and all other students have 3 friends. Such a situation is possible. For example:

Student      His/her friends

0               1, 3, 4

1               0, 2

2               1, 3, 4

3               0, 2, 4

4               0, 2, 3

Example 2

Input

{7, 6, 5, 4, 4}
2

Output

Function Returns "IMPOSSIBLE"

Example 3

Input

{5, 6, 5, 4, 4}
1

Output

Function Returns "POSSIBLE"

Example 4

Input

{1, 2, 3}
1

Output

Function Returns "IMPOSSIBLE"

Explanation:

Here student 2 selects student 0, so he tells us the number of friends of student 1. But it's obviously impossible for student 1 to have 3 friends.

For C solutions

For C++ solutions

General Instructions