Problem from Div1+Div2 Contest (July 20, 2025) — Tighter Constraints, Better Order

Revision en3, by ender_shayan, 2025-07-20 18:46:47

Hi everyone Hope you're doing great!

Yesterday, in the Div1+Div2 contest held on July 20, 2025, the E problem had an interesting path to optimize the constraints and ordering of computations.
With tighter constraints and better prefix handling, I managed to push the solution down to ~62ms, even for (n, k) limits. 330003602

If there’s enough interest, I’ll share the full theoretical explanation for this code as well.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en11 English ender_shayan 2025-07-20 19:12:59 2 Tiny change: 'roblem:2126E] problem' -> 'roblem:2122E] problem'
en10 English ender_shayan 2025-07-20 19:12:29 1 Tiny change: 'lem:2126E]problem ha' -> 'lem:2126E] problem ha'
en9 English ender_shayan 2025-07-20 19:12:18 15 Tiny change: 'the **E** problem ha' -> 'the **E** [problem:2126E]problem ha'
en8 English ender_shayan 2025-07-20 19:09:17 2 Tiny change: 'wn to **~61ms** and *' -> 'wn to **~62ms** and *'
en7 English ender_shayan 2025-07-20 19:04:50 17 Tiny change: ' **~61ms**, even f' -> ' **~61ms** and **O(n * k)**, even f'
en6 English ender_shayan 2025-07-20 19:01:01 6 Tiny change: 'sion:330003602]\n\n## So' -> 'sion:330006746]\n\n## So'
en5 English ender_shayan 2025-07-20 18:58:28 2 Tiny change: 'wn to **~62ms**, even' -> 'wn to **~61ms**, even'
en4 English ender_shayan 2025-07-20 18:56:28 2238
en3 English ender_shayan 2025-07-20 18:46:47 103
en2 English ender_shayan 2025-07-20 18:44:48 2236
en1 English ender_shayan 2025-07-20 18:44:06 2690 Initial revision (published)