CCC '13 S4 - Who is Taller?

View as PDF
Submit solution
Points: 7
Time limit: 1.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 100\,000. M, the number of comparisons that have already been done, is an integer with 1 \le M \le 1\,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


  • 1
    Ankit_04  commented on Feb. 10, 2022, 2:21 p.m.

    I'm getting TLE on 6 and 7 (python 3). I tried submitting with pypy3 but I still seem to time out. I have no idea how to make it faster. Appreciate any help.


    • 1
      Spitfire720  commented on Feb. 10, 2022, 4:48 p.m.

      Try using a deque instead of a list. Popping will then take constant time.


      • 1
        Ankit_04  commented on Feb. 10, 2022, 10:08 p.m.

        Thanks for the tip, switching my input functions to sys readline ended up solving it.


  • 1
    mahes0640  commented on Jan. 9, 2022, 6:52 p.m.

    Does anyone know why this submission is TLE'ing at the 6th and 7th batch? https://dmoj.ca/src/4193355 I don't know how to make it faster, could someone help me?


    • -1
      uselessleaf  commented on Jan. 10, 2022, 1:03 p.m.

      Submitting with PyPy3 instead of Python 3 solves the TLE issue. In the future, you can join the DMOJ Discord for help.


      • -1
        mahes0640  commented on Jan. 10, 2022, 4:14 p.m.

        Ok I will, thank you by the way!


  • 0
    MarksonChen  commented on May 30, 2021, 5:43 p.m.

    Help... I constantly got TLE on the last two subtasks. To reduce the time, I tried BFS, I tried HashSet, I tried BufferedReader, but the first task in the second last subtask always gives me TLE. Here's my code (java). I looked up solutions online, and they are all super similar to mine. Anyone knows what's wrong with my code?


    • 2
      Dan13llljws  commented on June 1, 2021, 6:08 p.m.

      Your method of storing the graph is very inefficient. Due to the high constraint, your code would be too slow. However, you are pretty close to the TL.


    • 7
      EpicChadGamer  commented on May 31, 2021, 7:43 p.m.

      It's too slow.


  • -3
    OneYearOld  commented on Nov. 14, 2020, 9:21 p.m. ← edited

    Did you know that switching to C++ from Python could cut down your time by 80% and give you 10 points?

    EDIT: Never mind.


    • 8
      julian33  commented on Nov. 15, 2020, 4:50 p.m. ← edited

      The issue isn't with python, your code just isn't very efficient. First of all, using "not in" to check if something is visited already is very slow. I'm pretty sure it just brute forces the entire array to check if the element is in there which makes it O(n) when checking if something is visited should be O(1). A better alternative is to check if the index of the element has already been marked as true. You also used "in" to check if person p/q is in the queue when instead you can just terminate bfs as soon as you encounter them. Also, you need to mark something as visited immediately after adding it to the queue rather than after retrieving it from the queue. This way you won't add the same element to the queue multiple times.


    • 5
      AlanL  commented on Nov. 15, 2020, 2:26 p.m.

      Not sure about that 80% calculation, but if you did any sort of checking over AC submissions, you'll see that there are many ACs in Python, so using it would not prevent you from getting your 10 points.


  • 14
    tappbros  commented on Aug. 30, 2020, 6:17 p.m.

    Feel like it would be weird if you came up to someone and started just measuring their height, but what do I know.


    • 25
      nikos  commented on Oct. 18, 2020, 5:02 p.m. ← edited

      I think it's weirder that your class can have 100000 students.


      • 1
        tappbros  commented on May 31, 2021, 7:34 p.m.

        Agreed


  • -1
    herro  commented on Aug. 12, 2020, 8:51 p.m. ← edited

    My code printed "unknown" but for some reason it "tle"d.

    Plz check.


    • 3
      Jonathan_Uy  commented on Aug. 12, 2020, 9:00 p.m.

      HashSets are pretty slow. If you change all your HashSets to ArrayLists you won't TLE anymore.


      • 0
        MarksonChen  commented on May 30, 2021, 4:02 p.m.

        I thought HashSets has O(1) time while ArrayList has O(n)? I tried to convert HashSets into ArrayLists, but the time is not faster nor slower.


      • -3
        herro  commented on Aug. 12, 2020, 9:02 p.m.

        thx but i already switched to linkedlists.


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

    This comment is hidden due to too much negative feedback. Show it anyway.


    • 3
      qiuxinrong27  commented on Feb. 17, 2020, 5:32 p.m. ← edited

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


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

        This comment is hidden due to too much negative feedback. Show it anyway.


        • 1
          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.


        • 2
          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
    puppy  commented on Dec. 13, 2019, 8:49 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • 84
    moladan123  commented on Feb. 17, 2015, 8:21 p.m. ← edited

    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 100 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!


    • 14
      349081547  commented on Aug. 9, 2019, 7:58 p.m.

      Screw doug ford!!


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

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

      I wish c++ worked in real life


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

        memset(students_marks, 0, numstudents);