CCC '13 S4 - Who is Taller?

View as PDF

Submit solution

Points: 10
Time limit: 3.0s
Memory limit: 512M

Problem type
Canadian Computing Competition: 2013 Stage 1, Senior #4

You have a few minutes before your class starts, and you decide to compare the heights of your classmates. You don't have an accurate measuring device, so you just compare relative heights between two people: you stand two people back-to-back, and determine which one of the two is taller. Conveniently, none of your classmates are the same height, and you always compare correctly (i.e., you never make a mistake in your comparisons).

After you have done all of your comparisons, you would like to determine who the tallest person is between two particular classmates.

Input Specification

The first line contains two integers N and M separated by one space. N, the number of people in the class, is an integer with 1 \le N \le 1\,000\,000. M, the number of comparisons that have already been done, is an integer with 1 \le M \le 10\,000\,000. Each of the next M lines contains two distinct integers x and y (1 \le x, y \le N) separated by a space, indicating that person number x was determined to be taller than person number y. Finally, the last line contains two distinct integers p and q (1 \le p, q \le N) separated by one space: your goal is to determine, if possible, whether person p is taller than person q. Note that it may be the case that neither p nor q occur in the input concerning measurements between classmates, and each measurement between any two particular people will be recorded exactly once.

Output Specification

The output is one line, containing one of three possible strings:

  • yes (if p is taller than q),
  • no (if q is taller than p),
  • unknown (if there is not enough information to determine the relative heights of p and q).

Sample Input 1

10 3
8 4
3 8
4 2
3 2

Output for Sample Input 1


Sample Input 2

10 3
3 8
2 8
3 4
3 2

Output for Sample Input 2



  • 0
    Raymo111  commented on Feb. 8, 2019, 4:30 p.m.

    DFS Java doesn't work but BFS does. Interesting.

  • 5
    BigBoy  commented on Sept. 1, 2018, 7:59 p.m.

    I am short.

  • 0
    aeternalis1  commented on July 29, 2017, 10:43 p.m.

    BFS not good enough?

    I implemented a rather simple BFS for this question, but I MLE'd test case 6-1 in PyPy2 and TLE'd it in normal python. Is this meant to be a BFS question?

    • 0
      Pleedoh  commented on July 29, 2017, 11:37 p.m.

      It is solvable in Python, but maybe try C or Java?

      • 0
        aeternalis1  commented on July 30, 2017, 11:10 a.m. edited

        I'm not very familiar with other languages at the moment, so I would just like to know if the other python solutions used BFS or a different approach (or a different twist on BFS).

        • 0
          wleung_bvg  commented on July 30, 2017, 4:47 p.m. edit 2

          Most solutions used bfs or dfs. Python 3 and PyPy3 seem to be a bit more lenient on memory than Python 2 and PyPy2 for this question (for me at least).

          • 2
            aeternalis1  commented on July 30, 2017, 7:12 p.m. edited

            Ok I figured it out, the issue lay in the fact that I used'\n') to read the whole file, and since the file was huge, it took up a lot of memory. I just switched to redefining 'input()' to sys.stdin.readline. Thanks for the help!

    • 0
      Pleedoh  commented on July 29, 2017, 11:34 p.m.

      It most certainly is.

  • 32
    moladan123  commented on Feb. 17, 2015, 8:21 p.m.

    I really like the fact that this problem goes for the realism. Its something that you rarely see in a programming contest. I appreciate CCC for acknowledging the fact that class sizes in Canada have become far too large. Join this petition to create classrooms where LESS than 1 000 000 have to be crammed together. I mean, how would it be even remotely possible to personally teach all of these children. Think of the children!

    • 11
      kobortor  commented on Feb. 17, 2015, 9:22 p.m.

      std::sort(students, students + numStudents);

      I wish c++ worked in real life

      • 7
        sunnylancoder  commented on Feb. 6, 2017, 10:23 p.m.

        memset(students_marks, 0, numstudents);