Note 7: Codeforces Beta round 13 E [Hard]

Revision en3, by NeoYL, 2024-01-07 10:46:16

This is my personal note and might be some kind of user editorial/learning material for some people!

This is the seventh episode of this "note" series. I will write notes on problems (normally around 2400-ish problems), that are both interesting and educational. I normally will spend a few hours on each problem so please be patient when reading the blog.

If you want to motivate me to write a continuation (aka note 8), a significant upvote from you would be well appreciated! If I received lots of downvotes (because I'm also spending a lot of time to write this and to learn latex only to express my ideas accurately to you guys), I'm probably not gonna continuing writing these blogs.

Difficulty rating
Tags

Problem link

Problem paraphrased:

You are given an array of length $$$N$$$. When you reach $$$i$$$, you will jump to $$$i+a_{i}$$$. Find the the number of jumps and the last index before jumping out if you start at $$$i$$$.

You are given $$$Q$$$ operations, to change the value of $$$a_{i}$$$ or query when you start at position $$$i$$$.

Hint 1
Hint 2
Hint 3
Solution

AC code link

Feelings

Hope you guys learnt something from the blog. Thank you for reading.

Tags sqrt_decomposition, data structures, brain, brute force

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en10 English NeoYL 2024-03-06 07:52:32 2 Tiny change: 'y around 2400-ish pro' -> 'y around 2500-ish pro'
en9 English NeoYL 2024-01-08 04:23:45 1 Tiny change: ' also $>N$ if you st' -> ' also $>N$) if you st'
en8 English NeoYL 2024-01-08 04:23:09 4 Tiny change: 'echnique! I didn't e' -> 'echnique! \n\nI didn't e'
en7 English NeoYL 2024-01-08 04:22:44 23 Tiny change: 'ce example.\n</spoil' -> 'ce example for sqrt decomposition.\n</spoil'
en6 English NeoYL 2024-01-07 15:28:59 30 Tiny change: 'mping out if you st' -> 'mping out of bounds (that is also $>N$ if you st'
en5 English NeoYL 2024-01-07 15:23:37 54
en4 English NeoYL 2024-01-07 12:33:56 8
en3 English NeoYL 2024-01-07 10:46:16 34
en2 English NeoYL 2024-01-07 10:42:33 73
en1 English NeoYL 2024-01-07 10:41:13 3075 Initial revision (published)