th3_g0d's blog

IZHO 2013 Problems Discussion
By th3_g0d, 11 years ago, In English

Hi, everyone! :)

As you know from 13th to 20th of January The International Olympiad in Informatics, Physics and Mathematics named after Orymbek Zhautykov(hope I wrote the name correctly) will be held in Kazakhstan, Almaty.

I think that is a bit unfortunate that organisers do not post the official solutions or at least hints for the problems. I was unsuccessful in finding the test data and statements for problems too for a while. Luckily, the tasks and test data of the previous IZHO were published here. If anyone knows solutions for problems, you can help others by sharing your knowledge here.

Have fun! :)

*Regarding the first problem of DAY1 I had a solution that computed the change in x and y coordinates for Gorlum and tried to simulate the process in O(1) by adding Dx to x and Dy to y coordinates. I was also identifying whether the Gorlum converges or diverges the Laser. So there are basically three cases:

1) After going through the string of commands Gorlum returns to the position where he started. In this case, we just have to simulate the string once and find the max and min distances observed.

2) Gorlum converges the Laser. Here we just have to add dx and dy change values to our current coordinates and wait till it starts to diverge from the Laser. actually on that intersection of Gorlum and Laser we can find the nearest point.

3) Gorlum diverges from the Laser. Here we can again simulate the process and look for maximum distance.

*Note: I also simulate the last and first cycles fully because there can be the answers for the farthest and nearest points.

Here is my code.

This was my solution for this problem. However, it seems incorrect. And now I don't have an idea that would fit in time. If anyone knows the solution I would be grateful if you shared. :)

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

»
11 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

What about a sufficiently fast, but simpler idea of simulating the whole process for the string S, finding Gorlum's displacement D = (Δ x, Δ y) after that string of commands, then trying all prefixes of the last repetition of the string that he performs and computing the nearest and farthest point out of those corresponding to the given prefix by binsearch? (Those points lie on a line and are given as P + kD; P here is the position of Gorlum after processing just that prefix of S.)

Finding the nearest and farthest point on a line is quite simple, because it first converges and then diverges (it can also converge/diverge on 0 points). That means we can bin-search the largest k such that P + kD is farther from the laser than P + (k + 1)D; that P + kD will be the closest out of all points on that line. The candidates for the farthest point are just the first and last point.

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Do you mean a simulation with some optimizations? Well, first I tried to simulate completely only the processes where the Laser stays inside the path of Gorlum i.e. the cycles where the borders of Gorlum's path leave the laser inside, and as soon as the Laser leaves the path drawn by the Gorlum I will only simulate the last process and the last point where the Gorlum stops I find with the addition of dx and dy to the current positions.

    UPD1: Or maybe I got you wrong?

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      I'm not sure now, maybe we're even talking about the same algorithm :D

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        :D Maybe but mine has only a heuristic optimization that would not optimize it asymptotically.

        → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh, yeah indeed! This is much simpler and actually correct :) Thank you very much!!!

    → Reply
»
11 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Umm, I guess you've posted wrong link :) Your link is an archive of IZhO 2012) Here is correct one) Link

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Oops :$ Thanks! :) You saved me from a rush of downvotes :D

    → Reply