UTPC_Admin's blog

By UTPC_Admin, history, 5 weeks ago, In English

Hope you enjoyed our contest! The editorial is below:

A — Skipping Songs

Author: sg2themax

Solution

B — 6th heaven

Author: blueberryJam

Solution

C — A Noteworthy Debut

Author: mwen

Solution

D — Counting Records

Author: Daveeed

Solution

E — Is It Vinyl?

Author: jxin31415

Solution

F — Lost in the Album Store

Author: isaac18b

Solution

G — Making Records

Author: DylanSmith

Solution

H — Prefix Tower

Authors: nwx, Daveeed

Solution

I — Record Compression

Author: zekigurbuz

Solution

J — Record The Record Record

Author: tn757

Solution

K — Sample Heat

Author: fishy15

Solution

L — Two Pizzas

Author: DylanSmith

Solution
  • Vote: I like it
  • +16
  • Vote: I do not like it

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

what is generalized pigeonhole principle? you mentioned it but didn't provide any further references.

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

    The base pigeonhole principle states that if we have $$$n$$$ objects and $$$m$$$ boxes where $$$n > m$$$, then at least one of the boxes has more than one item. The generalization is that at least one box has $$$\lfloor n / m \rfloor$$$ items for any value of $$$n$$$ and $$$m$$$.

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

I think there's a typo in the solution for H. It should be x-i+k-1 choose k-1. Or x-i+k-1 choose x-i

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Hi, great catch! We had written this formula with $$$i$$$ being 0-indexed, as it was in our code. The formula you gave is correct when $$$i$$$ is 1-indexed, which would be consistent with the rest of the solution.

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

A solution that doesn't involve hasing for K is using eertree. You only add to the answer when you create a new node on the tree