BledDest's blog

By BledDest, 4 years ago, In English

First of all, I would like to thank all of the testers: elizarov, darnley, IlyaLos, _overrated_, SergeyMelnikov, winger, FieryPhoenix, infinitepro, Sho, GrandDaddy, bfs.07, spookywooky. Also huge thanks to co-authors of the contest: MikeMirzayanov, Neon, Roms, adedalic, vovuh and awoo.

I hope you enjoyed participating in the round!

Okay, now for the editorial itself:

1346A - Color Revolution

Idea: BledDest, preparation: awoo

Tutorial
Solution (elizarov)

1346B - Boot Camp

Idea: BledDest, preparation: Neon

Tutorial
Solution (elizarov)

1346C - Spring Cleaning

Idea: vovuh, preparation: vovuh

Tutorial
Solution (elizarov)

1346D - Constructing the Dungeon

Idea: MikeMirzayanov, preparation: Neon

Tutorial
Solution (elizarov)

1346E - Magic Tricks

Idea: BledDest, preparation: Neon

Tutorial
Solution (elizarov)

1346F - Dune II: Battle For Arrakis

Idea: vovuh, preparation: vovuh

Tutorial
Solution (elizarov)

1346G - Two IP Cameras

Idea: adedalic, preparation: adedalic

Tutorial
Solution (elizarov)

1346H - Game with Segments

Idea: Roms, preparation: Roms

Tutorial
Solution (tourist)

1346I - Pac-Man 2.0

Idea: Neon and BledDest, preparation: Neon

Tutorial
Solution (Ne0n25)
  • Vote: I like it
  • +67
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    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 years ago, # |
  Vote: I like it +31 Vote: I do not like it

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

My screencast

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

Explanation
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
4 years ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

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

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