zoooma13's blog

By zoooma13, 6 years ago, In English

IOI 2018 tasks webpage (multiple languages).

Tasks : doll highway meetings (English).

Live Scoreboard

Live Broadcast

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

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Isn't it possible to solve the first task with only N — 1 switches?

By making a heap-like tree of switches and connecting output of leaf switches to the corresponding triggers, and connecting output of triggers to the root of the tree.

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

    Switches need to be returned to X by the end.

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

    Since all the switches have to return back to state X we will need a perfect binary tree. This will result in 2n switches. With this approach I got 53 points in contest

»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

What's the solution for Meeting Points

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +74 Vote: I do not like it

    The task is quite hard. You need some nice ideas and it took me quite long to implement. My solution can probably be simplified.

    Ideas and rough solution overview
    Solution description
»
6 years ago, # |
  Vote: I like it -9 Vote: I do not like it