CATSRATS - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest

Author: Erfan alimohammadi
Tester & Editorialist: Hussain Kara Fallah

DIFFICULTY:

Easy

PREREQUISITES:

None

PROBLEM:

There are N cats (numbered 1 through N) and M rats (numbered 1 through M) on a line. Each cat and each rat wants to move from some point to some (possibly the same) point on this line. Naturally, the cats also want to eat the rats when they get a chance. Both the cats and the rats can only move with constant speed 1.

For each valid i, the i-th cat is initially sleeping at a point a_i. At a time s_i, this cat wakes up and starts moving to a final point b_i with constant velocity and without any detours. After it arrives at the point b_i,it falls asleep again.

For each valid i, the i-th rat is initially hiding at a point c_i. At a time r_i, this rat stops hiding and starts moving to a final point d_i in the same way as the cats ― with constant velocity and without any detours. After arrival it hides.

If a cat and a rat meet each other (they are located at the same point at the same time), the cat eats the rat, the rat disappears and cannot be eaten by any other cat. A sleeping cat cannot eat a rat and a hidden rat cannot be eaten.

Your task is to find out which rats get eaten by which cats. It is guaranteed that no two cats will meet a rat at the same time. It’s guaranteed that all starting\ending positions of rats and cats are mutually distinct.

1\leq N,M \leq 1000

EXPLANATION

Due to small constraints, we will solve it in O(N*M). Let’s examine each pair (cat,rat) and find out for each rat the earliest moment it will meet a cat and which one.

Let’s assume we are holding a pair right now (cat,rat) let:

st_{cat} the starting point of the cat

en_{cat} the ending point of the cat

wakeup_{cat} the moment when the cat wakes up

hide_{cat} the moment when the cat will hide

Let’s define the same variables for the rat as well.

First of all let’s check if one of them will be inactive during all moments which the other one will be active. Shortly if :

wakeup_{cat} > hide_{rat} \,\,\, OR \,\,\, wakeup_{rat} > hide_{cat}

In such case, they never meet.

Since all starting positions and final positions are distinct, we don’t need to worry about checking at them.

We need to check as well if the rat and cat are moving such that they get further from each other. In such case they won’t meet as well.

Now we have the normal case, when they move towards each other. Let’s take the first moment they will be both active which is max(wakeup_{rat},wakeup_{cat}) and update their positions to the ones they will be in at this specific moment. Let the distance between them at this moment be dist

After that, it’s obvious that they will meet in the middle of the line segment between them. We just need to check if one of them won’t reach that point (stops before it and sleeps).

In case both of them will reach that point then they will meet at the moment max(wakeup_{rat},wakeup_{cat}) + \frac{dist}{2}

If the rat won’t be eaten before this moment, then we update its death time and set the killing cat to the current one.

AUTHOR’S AND TESTER’S SOLUTIONS:

AUTHOR’s solution

TESTER’s solution

2

@admin

Since the whole problem feels discreet, this instruction is quite confusing.
When i first read the problem i thought that:
a cat starting at location 1, at time 1, going to location 2
AND
a rat starting at location 2, at time 1, goint to location 1
will never meet, as at time 1 cat will be at location 1 and rat at 2, and at time 2 the cat will be at location 2 and the rat at location 1, meaning they “passed by eachother”.
Again as the instruction says “they are located at the same point at the same time”

I think a small clarification would help.

exept for that, an awsome problem.

2 Likes
3

Difficulty : -EASY!
LO AND BEHOLD!
Only 8 people were able to solve it during the contest :slight_smile: So easy!!! I screwed up in this one because I forgot 11th standard physics :slight_smile:

2 Likes