I wonder, what is the percentage of ioi 2019 contestant that attempt problem line without any randomization?
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
37:31:46
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
37:31:46
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 22.11.2024 04:03:16 (k2).
Десктопная версия, переключиться на мобильную.
При поддержке
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.
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.
And you got >90
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.
Is the visualization useful for your heuristic solution?
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.
By the way, we can see some national flag on some visual inputs.
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.
Anyway, I like your idea. As long as you use neither heuristic nor randomization.
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) ?
Not bad. Your solution is creative enough.
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.