CCC '13 S4 - Who is Taller? - DMOJ: Modern Online Judge

CCC '13 S4 - Who is Taller?

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$ ~N~ and $M$ ~M~ separated by one space. $N$ ~N~, the number of people in the class, is an integer with $1 \le N \le 1\,000\,000$ ~1 \le N \le 1\,000\,000~. $M$ ~M~, the number of comparisons that have already been done, is an integer with $1 \le M \le 10\,000\,000$ ~1 \le M \le 10\,000\,000~. Each of the next $M$ ~M~ lines contains two distinct integers $x$ ~x~ and $y$ ~y~ ( $1 \le x, y \le N$ ~1 \le x, y \le N~) separated by a space, indicating that person number $x$ ~x~ was determined to be taller than person number $y$ ~y~. Finally, the last line contains two distinct integers $p$ ~p~ and $q$ ~q~ ( $1 \le p, q \le N$ ~1 \le p, q \le N~) separated by one space: your goal is to determine, if possible, whether person $p$ ~p~ is taller than person $q$ ~q~. Note that it may be the case that neither $p$ ~p~ nor $q$ ~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$ ~p~ is taller than $q$ ~q~),
no (if $q$ ~q~ is taller than $p$ ~p~),
unknown (if there is not enough information to determine the relative heights of $p$ ~p~ and $q$ ~q~).

Sample Input 1

Output for Sample Input 1

yes

Sample Input 2

Output for Sample Input 2

unknown

Comments

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?

1

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.

0

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

It's too slow.

0

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.

6

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.

4

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.

11

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.

16

nikos commented on Oct. 18, 2020, 5:02 p.m.

I think it's weirder that you class can have 1000000 students.

0

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.

-5

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?

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

4

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?

5

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$ ~N = 10^6~ and $M = 10^7$ ~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.

1

Evan commented on April 29, 2021, 6:39 p.m.

ok wait, so if you guys buffed the test data and then reverted the change, what are the constraints for N and M now?

1

Evang commented on April 30, 2021, 3:51 p.m. ← edit 2 →

now it appears that $n\leq10^5$ ~n\leq10^5~ and $m\leq10^6$ ~m\leq10^6~ (I tested the constraints by submitting a bunch of times)

-1

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

The new time limit seems too strict.

-9

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

hint: optimize

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

4

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

They have removed the subtask that was causing the TLE.

-23

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

bruh y u being so petty rn. There are people who passed with programs that take 24+ seconds to pass the problem tests.

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

10

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 :)

-20

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

PPVNX had 24.5 seconds using Java 8...

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

5
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.

-33

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

LMFAOOOO. I submit the exact same code a few weeks later and it turns out to be well below time constraints. Great judges over here trolling harder than trump.

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

20

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.

My code got an abnormal termination for the last batch. What does that even mean?

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

3

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

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

-14

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

Wait adjacency list gives RTE too. WTF help

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

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.

4

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.

bruh imma have to revamp my whole code now. Thanks though.

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

-5

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

Is the graph directional or not?

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

7

TimothyW553 commented on Dec. 13, 2019, 9:27 p.m.

directional

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?

2

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

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

1

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

1

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

-1

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

It most certainly is.

81

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!

13

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

Screw doug ford!!

22

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

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

I wish c++ worked in real life

27

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

memset(students_marks, 0, numstudents);