Randomization and BOI23 Staring Contest [help pls]

Revision en1, by sparsetable, 2024-09-16 07:57:48

TL;DR: I shuffled the array, got 100 points, and have no idea why.
(every instance of BOI here refers to the Baltic Olympiad in Informatics.)

I was working on BOI23 d1p2 yesterday, and came up with the following solution for 50 pts:

spoiler

Here, there were 2 obvious optimizations:

  1. Since I only need the value of $$$\min(b, c)$$$ if $$$\min(a, c) = \min(a, b)$$$, we can throw out some unnecessary queries

  2. Might as well randomize the array since it might reduce such occurrences, idk ¯\_(ツ)_/¯

code

And to my surprise...it got 100 points!

Looking at the official code, this seems to be the intended solution. However, even after thinking on it, I'm not really sure why it works. Why is shuffling the array so effective? (only applying optimization 1 without 2 gets you 58 points.)

Tags boi2023, baltic, day1, randomization

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English sparsetable 2024-09-16 07:57:48 3285 Initial revision (published)