Woburn Challenge 2017-18 Round 3 - Senior Division

Problem 1: Mutual Friends

The social network Google+ has N (2 ≤ N ≤ 6) users, with user IDs from 1 to N. Each pair of distinct users are either friends with one another, or not.

You're given an N×N grid of values M, with Mi, j (0 ≤ Mi, jN) being the number of mutual friends which users i and j have in common. This corresponds to the number of other users which are friends with both i and j. Note that it does not depend on whether or not i and j are friends with one another. Mi, j = Mj, i for each pair of users i and j, Mi, i is considered to be 0 for each user i.

Given the above information, you'd like to guess which users are friends with one another. If there exists a valid set of friendships which result in the given grid of mutual friend counts, then please output the number of friendships F, followed by F lines each describing one of the friendships (with 2 integers, the IDs of the two users involved in the friendship). No two friendships should involve the same unordered pair of users. If there are multiple valid sets of friendships, you may output any of them. If there are no valid sets of friendships, output "Impossible" instead.


In test cases worth 4/13 of the points, N ≤ 3.

Input Format

The first line of input consists of a single integer, N.
N lines follow, the i-th of which consists of integers, Mi, 1..N, for i = 1..N.

Output Format

Either the string "Impossible", or 1 integer F followed by F lines, the i-th of which contains 2 integers describing the i-th friendship

Sample Input 1

0 0 0 1 2
0 0 2 0 0
0 2 0 0 0
1 0 0 0 1
2 0 0 1 0

Sample Output 1

1 2
2 5
5 3
3 1
2 4

Sample Input 2

0 1 1
1 0 0
1 0 0

Sample Output 2


Sample Explanations

In the first case, one valid set of 5 friendships is indicated in the sample output. For this set, users 1 and 5 have exactly 2 mutual friends (users 2 and 3) as required, users 1 and 4 have exactly 1 mutual friend (user 2) as required, and so on. Note that there exist other outputs which would also be accepted. For example, the friendship between users 2 and 4 could be replaced with a friendship between users 3 and 4, the friendships could be outputted in any order, and the users in each friendship could be swapped.

In the second case, no set of friendships amongst 3 users would result in the required grid of mutual friend counts.

All Submissions
Best Solutions

Point Value: 10 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: Mar 23, 2018
Author: SourSpinach

Languages Allowed:

Comments (Search)

It's quiet in here...