CCC '13 S4 - Who is Taller?

View as PDF

Submit solution

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

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
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.

An additional subtask worth 33% of the points have been added to break incorrect solutions which AC on official test data. Data provided by Tzak.

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

yes

Sample Input 2

10 3
3 8
2 8
3 4
3 2

Output for Sample Input 2

unknown

Comments


  • -2
    aayushICS  commented on April 6, 2020, 8:20 p.m.

    Welp I passed the test sets. Can someone look at my code and check if it's the "intended" solution?


  • 3
    mathgeek008  commented on March 26, 2020, 2:37 p.m.

    Why did my solution which got AC yesterday change to a TLE, but when I resubmitted the exact same code today I once again got AC?


    • 4
      magicalsoup  commented on March 26, 2020, 3:38 p.m.

      Due to a recent complaints about the time limit, we decided to buff the weak official test-data with N = 10^6 and M = 10^7. After adding the test-data, we rejudged all AC solutions. However, it seemed that the test-data was too strong, and only C++ solutions with fast I/O passed comfortably under the time limit. We have since reverted the change and changed back the time limit and points, so now your submission has an AC verdict.


  • -3
    ross_cleary  commented on March 24, 2020, 6:23 a.m.

    The new time limit seems too strict.


    • -1
      pblpbl  commented on March 24, 2020, 4:26 p.m.

      hint: optimize


      • 1
        ross_cleary  commented on March 24, 2020, 5:05 p.m.

        They have removed the subtask that was causing the TLE.


  • -17
    aayushICS  commented on March 23, 2020, 3:26 p.m.

    This comment is hidden due to too much negative feedback. Click here to view it.


    • 7
      Kirito  commented on March 23, 2020, 3:33 p.m.

      You are confusing total runtime with maximum runtime. The Java 9 submission that previously ran in 23.896 seconds now runs in 5.904 seconds (using Java 8, as we no longer support Java 9), taking 0.852 seconds in the worst case, compared to 2.170 seconds on the older judges.

      Also I would personally advise not annoying Xyene, he is usually the kindest of the administrators :)


      • -14
        aayushICS  commented on March 23, 2020, 3:42 p.m.

        This comment is hidden due to too much negative feedback. Click here to view it.


        • 3
          wleung_bvg  commented on March 23, 2020, 4:03 p.m.

          In case it wasn't clear, the time limit is for the maximum running time for all cases. That is each case must run under the time limit.

          The time displayed on the All submissions list is for the total running time, which is the sum of all times for each test case.

          For example, on the submission status page, you might see the following:

          Case #1:    AC  [0.500s,    8.79 MB]
          Case #2:    AC  [0.900s,    8.74 MB]
          Case #3:    AC  [0.600s,    8.77 MB]
          Case #4:    AC  [0.700s,    8.73 MB]
          Case #5:    AC  [0.800s,    8.77 MB]

          Here, each case is marked as AC because it is under the current time limit of 1.0 seconds. However, the total time will be displayed as 3.5 seconds, as that is the sum of the times for each test case. You can see this at the bottom of the submission status page where it will say:

          Resources: 3.500s, 8.79 MB

          This will be the time that is displayed on the All submissions list.


        • 4
          Kirito  commented on March 23, 2020, 4:03 p.m.

          Yes, that is a relic from the old judges.

          Rejudging the roughly 2 million submissions would be quite a waste of time, do you not agree?


        • 5
          Xyene  commented on March 23, 2020, 4:02 p.m. edited

          Yes, I'm not sure which part of this we're not getting across. New judges are fast, old judges were slower; we did not rejudge 2 million submissions when we switched because that would've taken over a month of 24/7 rejudging. Nor will we. Historical submissions have larger runtimes than they would if they were to be submitted today.

          Your solution should not have passed, but did thanks to the faster judges, so we have adjusted the time limit accordingly.


  • -22
    aayushICS  commented on March 23, 2020, 1:54 p.m.

    This comment is hidden due to too much negative feedback. Click here to view it.


    • 15
      Xyene  commented on March 23, 2020, 3:10 p.m.

      We recently (~two weeks ago) provisioned new baremetal servers for the judges to run on, that have more consistent timing and grade 2-5 times faster. Problem time limits were rescaled automatically based on a randomized sample of submissions, so some may currently have time limits that are either too low or too high.

      Since you were particularly uncharitable in your remark here, I've gone and rejudged the slowest submission prior to switching the judges over. As it passes comfortably within a second, I've set the time limit for this problem to a second, and rejudged existing submissions.


  • -11
    aayushICS  commented on Feb. 17, 2020, 5:21 p.m.

    This comment is hidden due to too much negative feedback. Click here to view it.


    • 4
      qiuxinrong27  commented on Feb. 17, 2020, 5:32 p.m.

      You are initializing an array of 1000000*1000000. Try using an adjacency list instead.


      • -12
        aayushICS  commented on Feb. 17, 2020, 9:31 p.m.

        This comment is hidden due to too much negative feedback. Click here to view it.


        • 2
          Dingledooper  commented on Feb. 18, 2020, 9:23 p.m.

          I think the main reason is just that your BFS algorithm is kind of weird. I recommend looking at some standard BFS implementations.


        • 3
          AlanL  commented on Feb. 18, 2020, 7:42 p.m.

          To fix your issue with going over the time limit I suggest learning how to use a BufferedReader.


        • 5
          Plasmatic  commented on Feb. 17, 2020, 11:08 p.m.

          DMOJ has a slack workspace for a reason


      • -9
        aayushICS  commented on Feb. 17, 2020, 5:45 p.m.

        This comment is hidden due to too much negative feedback. Click here to view it.


  • 2
    hamdog  commented on Jan. 18, 2020, 4:39 p.m.

    when you TLE the last case


  • -4
    puppy  commented on Dec. 13, 2019, 8:49 p.m.

    Is the graph directional or not?


  • 3
    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?


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

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


      • 2
        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).


        • 2
          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).


          • 3
            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 sys.stdin.read().split('\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.


  • 72
    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
      349081547  commented on Aug. 9, 2019, 7:58 p.m.

      Screw doug ford!!


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

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

      I wish c++ worked in real life


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

        memset(students_marks, 0, numstudents);