AMnu's blog

IOI 2019 output only problem
By AMnu, history, 5 years ago, In English

I wonder, what is the percentage of ioi 2019 contestant that attempt problem line without any randomization?

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

»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

I did not use randomisation, my solution used heuristics somewhat based on the input data (such as the diagonals). I'm unsure what other contestants did.

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

    May be I need to change my question.

    "solving problem line without any heuristic approaching"

    Because with some (pure) greedy solution, I got >70 points.

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

    And you got >90

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

      My heuristics also led to an (unproven) purely greedy solution. I'd be interested to see whether there are solutions which provably work in the general case and get a good number of points, other than the n+3 full solution and the basic 2n solution.

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

        Is the visualization useful for your heuristic solution?

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

          It helped me improve from 60-70 points to around 90. My first heuristic solution was spiralling on the diagonal case (specifically, in the test case which formed an X I noticed my code was doing squares rather than two staircase-like things, which was more optimal in that test case), so I modified my heuristics to better tackle diagonals and it improved the score on a number of the cases. That was the main way visualisation helped me.

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

          By the way, we can see some national flag on some visual inputs.

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

        I came up with some other proven solutions.

        $$$n+2*\sqrt{2n}$$$: you can try to split the points into some increasing/decreasing sequences and connect the points in each sequence with a "staircase". You can then connect every pair of consecutive staircases with 2 segments. The problem now turns to 1097E - Egor and an RPG game.

        $$$n+2*log(n)$$$ (I think): the sequences don't have to be monotonic; you can change the direction every other point (at points with even indices in the sequence. In other words, you can increase twice or decrease twice). For example, the sequence $$$[(1,3),$$$ $$$(2,4),$$$ $$$(3,5),$$$ $$$(4,2),$$$ $$$(5,1)]$$$ is connectable with a "staircase". We want to split the input into valid subsequences and connect each of them with a staircase. To split it to subsequences, we can take the longest valid subsequence each time and remove it. I think that there's always a valid subsequence with half the points. I couldn't prove it, but I couldn't find a corner case either, and it was true for all of the given cases.

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

          Anyway, I like your idea. As long as you use neither heuristic nor randomization.

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

I tried implementing a LIS approach. however i did not include LDS (because i am stupid) so i only got arnd 50. But how much does LIS + LDS give? Details :

we order the points as follows. Find LIS/LDS (which ever is larger), and place append this to the end of your current list, and delete them from the set of unused points. Thm : in a sequence of length n, atleast a LIS/LDS of root(n) exists. So after root(n) such selections, set of unused points is empty. Also, while traversing a LIS/LDS, we need to make n turns only, and need extra terms only when we move to another LIS sequence. So overall expected points is iguess n + root(n) ?

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

    Not bad. Your solution is creative enough.

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

I used a completely randomised solution, where I would chose the next point so that the directions from the previous point match up with the new point. I got 39 points using this method after adding a few heuristics and improving the randomization.

→ Reply