Note 7: Codeforces Beta round 13 E [Medium]

Правка en10, от NeoYL, 2024-03-06 07:52:32

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 2500-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 of bounds (that is also $$$>N$$$) 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.

Теги sqrt_decomposition, data structures, brain, brute force

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en10 Английский NeoYL 2024-03-06 07:52:32 2 Tiny change: 'y around 2400-ish pro' -> 'y around 2500-ish pro'
en9 Английский NeoYL 2024-01-08 04:23:45 1 Tiny change: ' also $>N$ if you st' -> ' also $>N$) if you st'
en8 Английский NeoYL 2024-01-08 04:23:09 4 Tiny change: 'echnique! I didn't e' -> 'echnique! \n\nI didn't e'
en7 Английский NeoYL 2024-01-08 04:22:44 23 Tiny change: 'ce example.\n</spoil' -> 'ce example for sqrt decomposition.\n</spoil'
en6 Английский 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 Английский NeoYL 2024-01-07 15:23:37 54
en4 Английский NeoYL 2024-01-07 12:33:56 8
en3 Английский NeoYL 2024-01-07 10:46:16 34
en2 Английский NeoYL 2024-01-07 10:42:33 73
en1 Английский NeoYL 2024-01-07 10:41:13 3075 Initial revision (published)