### BledDest's blog

By BledDest, 5 months ago,

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

I hope you enjoyed participating in the round!

Okay, now for the editorial itself:

1346A - Color Revolution

Idea: BledDest, preparation: pikmike

Tutorial
Solution (elizarov)

1346B - Boot Camp

Idea: BledDest, preparation: Ne0n25

Tutorial
Solution (elizarov)

1346C - Spring Cleaning

Idea: vovuh, preparation: vovuh

Tutorial
Solution (elizarov)

1346D - Constructing the Dungeon

Idea: MikeMirzayanov, preparation: Ne0n25

Tutorial
Solution (elizarov)

1346E - Magic Tricks

Idea: BledDest, preparation: Ne0n25

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: Ne0n25 and BledDest, preparation: Ne0n25

Tutorial
Solution (Ne0n25)

• +67

 » 5 months ago, # |   +6 As I don't know kotlin, can I solve these problems in other languages and submit?
•  » » 5 months ago, # ^ | ← 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.
•  » » » 5 months ago, # ^ |   0 Wow!! I swear, It's great. God bless you.
 » 5 months ago, # |   +31 Thank you for the problems! 2:30 seemed like a perfect duration for me.My screencast
 » 5 months ago, # |   0 NICE TIME TO CHECK FOR MULTIPLE ACCOUNT , JUST MATCH WITH THE IP ADDRESS OF EACH DIFFERENT PROFILE SUBMISSION. :)
 » 5 months ago, # |   0 My (weird, and probably counterintuitive) solution to G: 81912387 ExplanationCreate a segment tree that supports the querying of two pieces of information: the GCD of all distances between all points on a range, and a single point on that range. Then try all possible periods for the first camera, assuming it starts at the time of the first point of interest. For each range in between the points covered by the first camera, query the range on the segment tree, GCD its total GCD value with a global GCD, and also GCD the global GCD with the distance between the returned point and any other previous point (It's probably provable that this is enough) If this overall GCD is a multiple of any valid period, then it'll work for the second camera.Let $C = 10^6$ (really $\dfrac{10^6}{3}$ because a period of $1$ or $2$ is an automatic win), then because of the harmonic series, at most $O(C\log{C})$ queries are made, and each segment tree query is amortized $O(\log{C})$ because of how GCD works (this can also be optimized to $O(n\log{C})$ queries, but there's still $O(C\log{C})$ overhead).Did anyone else solve it this way, or similar?
•  » » 5 months ago, # ^ |   0 I had similar idea using the same "harmonic series" observation, but ran out of time while implementing it :(
 » 5 months ago, # |   0 And why I just sorted in reverse order in problem C :) Got TLE, always so
 » 5 months ago, # | ← 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: 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}$ 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.
 » 5 months ago, # |   0 not able to understand magic trick i/o # input 4 5 1 3 4 2 1 4 1 3 1 3 1 output can anyone help?
 » 5 months ago, # |   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?