darijan2002's blog

By darijan2002, history, 5 weeks ago, In English,

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.

 
 
 
 
  • Vote: I like it  
  • +11
  • Vote: I do not like it  

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Try to think why K ≤ 100 and use it somehow.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I noticed that, but I don't know how to use it. I'll give it some brain power and I'll see. Thanks for the tip!

»
5 weeks ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

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:

Solution

Some ideas for faster solutions exist, but you they are much more difficult.

Faster Solutions
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    • »
      »
      »
      5 weeks ago, # ^ |
      Rev. 4   Vote: I like it +5 Vote: I do not like it

      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.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      To rephrase, what will you consider a starting point for T in the binary search?

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          That's what I thought, just wanted to make sure. Thanks btw