omgmynamedoesntfi's blog

IOI 2014
By omgmynamedoesntfi, 10 years ago, In English

Are there IOI 2014 tasks somewhere on the internet or someone can upload them?

Thanks in advance.

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

Comments Comments (16)
| Write comment?
»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Here: IOI Tasks

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

I've an algorithmic solution to both Game and Rail.

game — O(n^2) time and space rail — O(nlogn) with 2n-3 calls to the function

I'm pretty proud of myself for solving those questions, too bad I didn't qualify to my national team :/

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

    Where are u from?

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

    Could you please provide me the details of your solution to Rail? I can use no more than 3N-5 queries (or something like that) and I really would like to know if it can be done in an even more optimal way ;)

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

      I have two distance ararys, one is sorted by distance from station 0 to the other stations, the second is a sorted by index from the closest station to station 0, let's call it station i(which is D type of cours).

      in total 2n-3 quries(because d(a,b)=d(b,a)).

      d(a,b) — the distance as they define it

      D(a,b) — the number of blocks from a to b.

      now for every station j which is not 0 or i:

      if d(j,i)<d(j,0) than j is a C type to the left of station 0, D(j,0)=d(0,j)-d(0,i)

      if d(j,i)<d(0,i) than j is a C type to the right of station 0, D(j,0)=d(0,i)-d(j,i)

      if d(0,j)<d(i,j) than j is a D type to the right of station 0, D(0,j)=d(0,j)

      there might be a factor of +1/+2/-1/-2 in the caculation of D.

      the lower bound might be a little bit lower(because we know that the most left and most right stations are C type and D type respectivly)

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

        This does not work without additional queries.

        For example, in your first case, consider the following situation:

        • station 0, type C, in block 0
        • station 1, type D, in block 100 (the closest one from 0)
        • station 2, type C, in block 99
        • station 3, type D, in block 101

        the distance from station 3 to station 1 is way smaller than the distance from station 3 to station 0, but this does not mean that station 3 is a type-C to the left of station 0.

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

        if d(j,i)<d(j,0), then it could be of type C and be between station 0 and station i. It could also be of type D and be left from station 0, so how do you know the case?

        if d(j,i)<d(0,i), then it could be of type C to the right of station 0, however if it is right from station i then this doesn't hold.

        if d(0,j)<d(i,j), then it could also be some C to the right of station i.

        Also, I don't see you mentioning anything about type D to the left of station 0?

        I just can't seem to get your idea, I did participate in the IOI myself (256 points) and this problem was quite tough, even though the author solution seemed to be just a lot of cases.

        → Reply
»
10 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

nvm

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

    "If we apply an operation to a node whose children don’t have the same value then we apply this operation to each of its 2 children, and update the value of the node."

    I don't understand something.

    Let's say N=500000. In 250000 queries we can make a wall in which every other height is equal to 100000, that is, (0,100000,0,100000,0,100000,...,0,100000). Then we make 100000 max-queries acting on all columns and successively increasing height (first query makes maximum with all columns and 1, then 2, 3 and so on). Won't your algorithm give then O(n) time per query?

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

      Indeed, a bug in my solution, if we just change the given interval's node minimum/maximum value and keep this in mind when traversing the tree the bug should be fixed.

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

Looks like problem B can be solved simply by an interval tree. But I don't know the exact time limit.

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

    The problem B is solved by an interval tree. I think the exact time limit is 3 seconds.

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

Where score board????

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

EDIT: Sorry, didn't see someone had posted a solution blog

→ Reply