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

Автор YouKnowCipher, история, 2 недели назад, По-английски

This is the first contest where I solved the full problem set. That's why, to celebrate this achievement, I am writing an editorial about my implementations. If I made any mistakes or typos, please let me know.

1999A — A+B Again?

Hint
Tutorial
Implementation

B — Card Game

Hint
Tutorial
Implementation

C — Showering

Hint
Tutorial
Implementation

D — Slavic's Exam

Hint
Tutorial
Implementation

E — Triple Operations

Hint
Tutorial
Implementation

F — Expected Median

Hint
Tutorial
Implementation

G1 — Ruler (easy version)

Hint
Tutorial
Implementation

G2 — Ruler (hard version)

Hint
Tutorial
Implementation
  • Проголосовать: нравится
  • +15
  • Проголосовать: не нравится

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

This editorial offers numerous hints, whereas the official one lacks any. Thus, this unofficial editorial is superior to the main one.

It also should be attached to the main contest page as "Tutorial #3".

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

orz

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

Hello!

For problem F, lets say that the array is not binary. Let $$$k$$$ still be odd.
For array $$$a$$$ size $$$n$$$, we have $$$1 ≤ a[i] ≤ N$$$. $$$N$$$ is not specific, lets say $$$2 * 10^{5}$$$. How should we go about calculating the median ?. Any ideas ?.

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

    This is a complex one, but hopefully it works:

    Treat each array element as a candidate median. For each candidate, count the subsequences in which it can be the median using combinatorics on the elements to its left and right. Use prefix sums for efficient counting and precompute factorials and modular inverses for large calculations. then, just sum the contributions of all candidates and take the result modulo $$$10^9 + 7$$$.

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

Your implementation of problem G2 is really great.