You are not logged in. Please login at www.codechef.com to post your questions!

×

BSTN - Editorial

PROBLEM LINK:

Practice
Contest

Author: Michael Nematollahi
Tester: Teja Vardhan Reddy
Editorialist: Michael Nematollahi

PREREQUISITES:

DP, range query data structures (like segment trees)

EXPLANATION:

Let’s call the dissatisfactions of the first type, the dissatisfactions of type ‘A’ and the dissatisfactions of the second type, the dissatisfactions of type ‘B’. For the sake of simplicity, let’s assume both $t$ and $s$ are increasing.

It’s not hard to see that it’s optimal for any passenger to board a bus as soon as they can. This is to avoid gaining type ‘B’ dissatisfactions. This means that for some array $z$ of length $M$, the first $z_1$ persons board the first bus, the next $z_2$ persons board the second bus and so on.

The second observation to make is that once the last passenger of a bus gets on, it’s optimal for that bus to leave immediately to avoid raising type ‘A’ dissatisfactions. This implies that we only need to consider the times that are given in the input.

Let’s insert all the times given in the input in an array $r$ and sort it. Note that every time has a corresponding person or bus. Let’s define $dp[i]$ as the answer for the first $i$ times. By this, I mean what would the answer be if the only buses were the ones among the first $i$ times and the only persons were the ones among the first $i$ times? It’s obvious that the answer to the original problem is $dp[n+m]$.

Let’s find out how to calculate $dp[i]$. Note that we know what the last bus among the first $i$ times is. Let’s call it $last$ and the bus before it $prev$. To calculate $dp[i]$, we need to choose a $j$ where $prev \leq j \lt i$, which means $last$ will take care of passengers with times from $j+1$ up to $i$ and the rest of the passengers should be taken care of by the previous buses. For this choice of $j$, $dp[i]$ would be $dp[j]$ + the dissatisfaction of those that get on $last$. So a trivial solution with a bad complexity is to loop over $j$ and find the minimum value.

Consider a passenger $k$ where $j \lt k \leq i$. $k$ will gain dissatisfaction of type ‘A’ iff the time of $j$ is greater than $s_k - a_k$ and less than $s_k$. Note that this represents a range.

$k$ will gain dissatisfaction of type ‘B’ iff the $i^{th}$ time is at least $s_k + c_k$. In other words, $d_k$ should be added to all $dp$s that are before $k$ once the $i^{th}$ time exceeds that amount (note that we’re looping over $i$).

Both of the above cases add dissatisfactions to a range of $dp$s. Hence, we can keep the $dp$ values in a segment tree that supports range addition and minimum queries and use addition queries to take care of the dissatisfactions. This enables us to calculate $dp[i]$ with a range minimum query in $O(log(n+m))$

The total complexity of this solution is $O((n+m) \times log(n+m))$. Refer to the setter’s code to see the implementation.

AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution can be found here.
Tester's solution can be found here.

This question is marked "community wiki".

asked 24 Jan, 03:49

watcher's gravatar image

7★watcher
35
accept rate: 0%

edited 27 Jan, 20:57

admin's gravatar image

0★admin ♦♦
19.8k350498541

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,678
×2,169
×1,755
×1,404
×39

question asked: 24 Jan, 03:49

question was seen: 252 times

last updated: 27 Jan, 20:57