CCC '07 S3 - Friends

View as PDF
Submit solution
Points: 7 (partial)
Time limit: 1.0s
Memory limit: 256M
Problem type
Canadian Computing Competition: 2007 Stage 1, Senior #3

In a certain school, it has been decided that students are spending too much time studying and not enough time socializing. To address this situation, it has been decided to give every student a friend. Friendship is one-way. That is, if Janet is assigned to be Sarah's friend, Janet must be friendly to Sarah, but Sarah is not required to reciprocate.

The assignment of friends is done by computer using student numbers. Every student is assigned exactly one friend. Sometimes, a 'circle of friends' occurs. For example, if Marc is assigned Fred, Fred is assigned Lori, Lori is assigned Jean, and Jean assigned Marc, we have a circle of 4 friends containing Marc, Fred, Lori, and Jean. In the circle, we can say that Marc has a separation of 0 from Fred, of 1 from Lori, of 2 from Jean, and of 3 from Marc.

Your task is to identify, given the computer assignment of friends, whether two students are in the same circle of friends, and if so, determine their separation.

Input Specification

Input begins with a single integer n (2 \le n \le 9\,999), on a line by itself, indicating the number of students in the class. The next n lines contain the computer assignment of friendship. An assignment is of the form x y (where 1 \le x, y \le 9999, x \ne y). For example, 1234 8765 is a possible friendship assignment indicating that student 1234 must be friends with student 8765.

Following the friendship assignments, there are a series of lines containing two student numbers, separated by a single whitespace. These lines represent the pairs of students that you will determine if they are in the same circle of friends and, if so, their separation. The last line of input can be identified by the use of the 0 0 as the friend assignment.

Output Specification

For each case, you are to print, on a separate line, either Yes or No depending on whether they are in the same circle of friends. If the answer is Yes, follow the output Yes with a single whitespace and then an integer indicating the friend's separation.

Sample Input

6
1 2
2 3
3 1
10 11
100 10
11 100
1 100
2 3
0 0

Output for Sample Input

No
Yes 0

Comments


  • 5
    mangdani282  commented on Dec. 31, 2023, 5:54 a.m.

    For those of you solving this question in the future, I want to point out that when it asks for the separation between two friends that does not mean in both directions. In the sample question, if it was asking for the separation between 2 1, the answer would be 1 and not 0 because they have to go through friend 3. I know it mentions this in the second paragraph, but I spent an hour testing and troubleshooting my code and rereading the question and I still did not realize until I found a solution online, so please don't struggle like me.


  • 0
    planT_444  commented on Jan. 19, 2022, 4:16 p.m. ← edited

    I thought maybe you could have person x be assigned to y and also person y be assigned to x, since that's 2 unidirectional edges. It turns out I was wrong.


    • 0
      Spitfire720  commented on Jan. 19, 2022, 4:44 p.m.

      2 unidirectional edges connecting both nodes is really a bidirectional edge


  • 76
    Victor_Chan  commented on Nov. 7, 2020, 5:09 a.m.

    The first paragraph was so randomly sad :(


  • -2
    puppy  commented on Nov. 19, 2019, 1:55 a.m. ← edited

    Why do I keep getting out of memory error?


    • 12
      Dingledooper  commented on Nov. 19, 2019, 3:05 a.m.

      Seriously? boolean[][] a = new boolean[10000][10000]; (~100MB) is for sure to MLE.


      • -3
        c  commented on Nov. 20, 2019, 1:56 a.m.

        In theory you could use a bitset to fix this.


  • 2
    Medi  commented on Jan. 31, 2019, 5:41 p.m.

    How many queries are possible?


  • 0
    Roronoa_Zoro1540  commented on Dec. 22, 2017, 1:05 a.m.

    Why does it say RTE? can someone check my code?


    • 20
      jkguipqnjcy49979693  commented on Dec. 22, 2017, 1:42 a.m.

      Your arrays occupy around 10 GB of memory... Note that each friend is only assigned to one other friend...


  • 3
    AlexCress  commented on Nov. 25, 2017, 8:40 p.m. ← edited

    Hi, I'm having issues with the fourth test case, I get "IR (java.lang.NullPointerException)". When I download the data from here everything appears to work correctly. Can someone confirm if this is still an issue or check my code? Thanks


    • 3
      Kirito  commented on Nov. 26, 2017, 4:11 p.m.

      For some troll reason, it appears that the two student numbers which follow the friendship assignments might not have been assigned friends during the aforementioned friendship assignments.

      Additionally, I am not sure why the data on the judge differs from that of the CEMC website, but as the input specifications does not explicitly say that this is an error, I suppose we shall keep it as it is.


      • 8
        AlexCress  commented on Dec. 1, 2017, 5:14 a.m.

        Thanks for the reply. In the problem statement it states "Every student is assigned exactly one friend", so I feel it should be implied that the input will not contain invalid data. In a "real world" scenario the bug would be in the algorithm that assigns students, not in the algorithm we are writing to solve the problem, so as per method contract any invalid data should be throwing errors (i.e. undefined behavior). Besides, this is a programming challenge, not an input validation exercise. Very troll indeed.

        For anyone wondering how to fix the error- there are students not assigned a friend so a lookup in a map/dictionary/whatever will result in an error, e.g. 111 222 222 is never assigned a friend, thus the key won't exist.


  • 0
    AndrewVII  commented on May 13, 2017, 10:10 p.m. ← edited

    Hey, I am getting a key error on test case 4, but when I run that data from the CEMC website, I get no such error, and my program outputs the correct output. What's going on?

    EDIT: Never mind, I changed the way I stored my data and it ended up fixing it.


  • 15
    bruce  commented on Dec. 11, 2016, 4:03 a.m.

    The test data seems different with the official one on CEMC site https://cemc.uwaterloo.ca/contests/computing/past_ccc_contests/2007/stage1/data.zip.