Woburn Challenge 2017-18 Round 3 - Senior Division
The social network Google+ has users, with user IDs from to . Each pair of distinct users are either friends with one another, or not.
You're given an grid of values , with being the number of mutual friends which users and have in common. This corresponds to the number of other users who are friends with both and . Note that it does not depend on whether or not and are friends with one another. for each pair of users and , is considered to be for each user .
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 , followed by lines each describing one of
the friendships (with 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
In test cases worth of the points, .
The first line of input consists of a single integer, .
lines follow, the -th of which consists of integers, , for .
Either the string
Impossible, or integer followed by
lines, the -th of which contains integers describing the -th
Sample Input 1
5 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
5 1 2 2 5 5 3 3 1 2 4
Sample Input 2
3 0 1 1 1 0 0 1 0 0
Sample Output 2
In the first case, one valid set of friendships is indicated in the sample output. For this set, users and have exactly mutual friends (users and ) as required, users and have exactly mutual friend (user ) as required, and so on. Note that there exist other outputs which would also be accepted. For example, the friendship between users and could be replaced with a friendship between users and , 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 users would result in the required grid of mutual friend counts.