progress

~/problems / Arrays & hashing / Prefix sums and difference arrays

When to shut the server down

On a phone? Coding is easier on a laptop: email this problem to yourself . Meanwhile: quiz this topic or fight a boss.

medium assessment 3 levels ~35 min Stripe

Level 1 The penalty of one closing time

A small service keeps a log of one day, hour by hour. Each hour is Y if customers tried to use it in that hour and N if nobody did. The team wants to switch the server off for the rest of the day at some hour, and they score each choice with a penalty:

  • every N hour before the closing time costs 1 (the server was up for nobody),
  • every Y hour at or after the closing time costs 1 (customers came and found it down).

Hours are numbered from 0. Closing at hour h means hours 0 .. h-1 run and hours h onward don't. h can be anything from 0 (never open) to the number of hours (open all day).

Write penalty(log, closing_time) -> int. log is a string of Y and N letters separated by spaces, like "Y Y N Y". It may be empty.

penalty("Y Y N Y", 0)   # 3: closed all day, three Y hours missed
penalty("Y Y N Y", 2)   # 1: hour 3 was a Y after closing
penalty("Y Y N Y", 4)   # 1: open all day, hour 2 was an N

Level 2 unlocks when level 1 passes.

Level 3 unlocks when level 2 passes.

Topic: Prefix sums and difference arrays. O(1) range sums (1D and 2D); O(1) range updates with difference arrays.

Read the visual guide
0:00
Ctrl ' run · Ctrl ↵ submit
esc