Блог пользователя BledDest

Автор BledDest, 4 года назад, перевод, По-русски

Во-первых, я бы хотел поблагодарить всех тестеров раунда: elizarov, darnley, IlyaLos, _overrated_, SergeyMelnikov, winger, FieryPhoenix, infinitepro, Sho, GrandDaddy, bfs.07, spookywooky. Также огромная благодарность моим соавторам: MikeMirzayanov, Neon, Roms, adedalic, vovuh and awoo.

Надеюсь, вам было интересно участвовать в контесте!

Окей, теперь сам разбор:

1346A - Цветовая революция

Идея: BledDest, подготовка: awoo

Разбор
Решение (elizarov)

1346B - Сборы по программированию

Идея: BledDest, подготовка: Neon

Разбор
Решение (elizarov)

1346C - Весенняя уборка

Идея: vovuh, подготовка: vovuh

Разбор
Решение (elizarov)

1346D - Построение подземелья

Идея: MikeMirzayanov, подготовка: Neon

Разбор
Решение (elizarov)

1346E - Фокусы

Идея: BledDest, подготовка: Neon

Разбор
Решение (elizarov)

1346F - Dune II: Battle For Arrakis

Идея: vovuh, подготовка: vovuh

Разбор
Решение (elizarov)

1346G - Две IP-камеры

Идея: adedalic, подготовка: adedalic

Разбор
Решение (elizarov)

1346H - Игра с отрезками

Идея: Roms, подготовка: Roms

Разбор
Решение (tourist)

1346I - Pac-Man 2.0

Идея: Neon и BledDest, подготовка: Neon

Разбор
Решение (Ne0n25)
Разбор задач Kotlin Heroes: Episode 4
  • Проголосовать: нравится
  • +67
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

As I don't know kotlin, can I solve these problems in other languages and submit?

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

    Turns out that you can (in a sense)! Go to Gym → Create Mashup Contest and add the problems to a mashup contest; submissions would then be available in all the usual languages.

    It's also a pretty handy tool for benchmarking solutions that are just over the time or memory limits.

»
4 года назад, # |
  Проголосовать: нравится +31 Проголосовать: не нравится

Thank you for the problems! 2:30 seemed like a perfect duration for me.

My screencast

»
4 года назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

В G есть более простое, как мне кажется, решение — заметим, что одной из камер мы сфотографируем не менее половины всех интересных моментов. Тогда это значит, что период этой камеры * (n/2 — 1) не более x_n. Переберем все такие периоды, рассмотрим все остатки по модулю периода и найдём тот, на который выпадает не менее половины моментов. Остальные можно после этого решить так же, как в решении выше

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

NICE TIME TO CHECK FOR MULTIPLE ACCOUNT , JUST MATCH WITH THE IP ADDRESS OF EACH DIFFERENT PROFILE SUBMISSION. :)

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

My (weird, and probably counterintuitive) solution to G: 81912387

Explanation
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I had similar idea using the same "harmonic series" observation, but ran out of time while implementing it :(

»
4 года назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

For F, $$$\sum_{i=1}^{n}{|x - i| xs_i}$$$ for the fixed $$$x$$$ can be computed as sum of two parts:

  1. Cost of moving the right part to $$$x$$$ is $$$\sum_{i=x+1}^{n}{i \cdot xs_i} - x \cdot \sum_{i=x+1}^{n}{xs_i}$$$
  2. Cost of moving the left part to $$$x$$$ is $$$x \cdot \sum_{i=1}^{x-1}{xs_i} - \sum_{i=1}^{x-1}{i \cdot xs_i}$$$

Using two arrays of prefix sums for $$$xs_i$$$ and $$$i \cdot xs_i$$$ we can compute the given sum in $$$O(1)$$$ for the fixed $$$x$$$.

This approach doesn't improve the time complexity: we still need $$$O(n + m)$$$ to compute the answer for each query. But not we have two arrays $$$cost_{row}[i], i=1..n$$$ — cost of moving everything to row $$$i$$$, $$$cost_{col}[j], i=1..m$$$ — same for columns. The cost of moving everything to cell $$$i, j$$$ is just $$$cost_{row}[i] + cost_{col}[j]$$$ .

So we can just find minimum element in each array and don't worry about off-by-one bugs when computing the center of mass.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In problem D can I consider the minimum number of coins for node i among all the connected tunnels to i? Will this work?