Has anyone tried solving "Particles" from EJOI 2017. http://ejoi.org/wp-content/themes/ejoi/assets/pdfs/tasks_day_1/EN/particles_statement-en.pdf I started solving it using a formula in which I derive t, calculate all t values in O(n^2) and keep the values with the specific x and y particles. Then, I get the first K pairs of particles with lowest t value, where both the x and y particles still exist, i.e. are not collided with another of their counterpart. The time limit is 3s, memory limit is 256 MB and I'd like some help with this task.
→ Pay attention
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3831 |
| 3 | Radewoosh | 3646 |
| 4 | jqdai0815 | 3620 |
| 4 | Benq | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | gamegame | 3386 |
| 10 | ksun48 | 3373 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 5 | -is-this-fft- | 158 |
| 6 | awoo | 157 |
| 7 | adamant | 156 |
| 8 | TheScrasse | 154 |
| 8 | nor | 154 |
| 10 | Dominater069 | 153 |
→ Find user
→ Recent actions
Codeforces (c) Copyright 2010-2024 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Nov/06/2024 02:46:07 (h1).
Desktop version, switch to mobile version.
Supported by
Try to think why K ≤ 100 and use it somehow.
Your solution is supposed to get 30 points (the subtask with N ≤ 1000).
If you just want a hint, then it's as ppavic said — you should think why the constraint on K is low and somehow incorporate K in your complexity.
The intended solution is as follows:
Let's fix a specific moment of time T and see how everything looks after time T, if we imagine that no particles ever collide. We can easily enough calculate the position of each particle in total of O(N) time. We can then check if the x-particle that went the furthest and the y-particle that went the furthest have passed each other. If so, then at least one collision must have occurred — otherwise no collisions have occurred yet. Thus by fixing a specific moment of time T we know whether the first collision was before or after T. We can hence do a binary search on T and find the exact time of the first collision. Note that we do not care about the time — we care about the pair that collided. This means that once we have some moment T for which the furthest x-particle and the furthest y-particle have passed each other, but neither of them has passed another particle of the opposite type, then we know this is the pair that collided first. We can thus find the first collision in about O(N log L). We can then simply remove the two particles that the first collision consists of and repeat everything again — hence finding the next collision. We repeat the whole thing K times, yielding O(N * K * log L) in total.
Some ideas for faster solutions exist, but you they are much more difficult.
The authors found a more complicated O(N log N + N * K) solution based on convex hull, but it was deemed too difficult for EJOI. The authors also theorise that a O(N log N + K log^2 N) or O(N log N + K log N) solution might exist, based on dynamic convex hulls, but clearly such approaches weren't thoroughly investigated at all since they are very clearly too difficult for EJOI.
I wanted to do something similar with binary search, but I had a wrong approach to the problem. Can you further explain the O(NK) solution with convex hull. I'm interested, merely intrigued. Thank you for the heads-up, btw
The O(NlogN + K * N) solution is as follows:
Imagine the number line along which the particles are being shot. The x-particles are being shot from 0 to the positive direction and the y-particles from L to the negative direction.
Let's examine a given x-particle i. The position of this particle at time T is
posXi = (T - txi) * vxi
and is defined for T ≥ txi. We can, however, use this definition for arbitrary moments T, as if T < txi, then clearly no collision may occur.
Similarly, the y-particle j can be defined at time T with the position:
posYj = L - (T - tyj) * vyj
Once again, we can ignore restrictions on T and allow T < tyi as this does not affect collisions.
We can open the brackets and reorder those expressions into a form that will be more useful:
The key thing is to imagine those as lines with T being the y-coordinate and the position of the particle being the x-coordinate. An intersection of two lines indicates a collision of the corresponding particles. Since we want to identify the first collision, we want to find the collision between a line of x-particle and a line of y-particle that has the smallest y-coordinate value.
We can notice that since vxi > 0 and vyj > 0 then the slope of lines for x-particles are always positive and the slopes of lines for y-particles are always negative.
Let's find the lower convex envelope of the set of lines. Since the slopes of x-particle lines are positive and those of y-particle lines are negative, then somewhere on the lower envelope there is an intersection of a x-particle line with a y-particle line. Furthermore, it is easy to see that there is exactly one such intersection on the lower envelope. From the definition of lower envelope it also follows that this intersection is the one with the smallest y-coordinate.
So all we need is a way to build the lower envelope quickly. This is a famous problem and if we sort all lines by slope in decreasing order, we can then linearly build the lower envelope using a stack.
Once we find the colliding lines, we remove them from the set and rebuild the lower envelope. Since simply removing lines does not obstruct the sorted slopes, we can sort only once in the beginning. Building the envelope and finding the intersection takes O(N) per iteration, hence we end up with O(NlogN + K * N) (I updated my original answer).
Searching for the intersection once the envelope is built is easy and can be sped-up in many ways. The slow part is the rebuilding of the envelope after each step. It naturally feels like removing just 2 lines shouldn't force a rebuild from scratch — however there are no simple ways to keep a dynamic envelope that supports line removals. I have heard of such structures but do not know their running time or difficulty.
A quick question, what will be the lower and the upper bounds of the binary search used to find values for T? And can T be an integer, or a double for bigger time precision?
To rephrase, what will you consider a starting point for T in the binary search?
You can start at a lower bound T = 0. A good upper bound can be the time for the fastest particle to be shot and travel distance of L. Something like 2 * 10^9 should also work as an upper bound.
You have to use double as integer might not be precise enough. That is, between moment T and moment T+1, many overtakes could happen (imagine very speedy particles) and hence you might never identify the moment where just 1 overtake has happened, which is what you're looking for.