YouKnowCipher's blog

By YouKnowCipher, history, 2 weeks ago, In English

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
  • Vote: I like it
  • +15
  • Vote: I do not like it

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

orz

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Your implementation of problem G2 is really great.