Woburn Challenge 2016-17 Round 4 - Senior Division

Problem 3: Night Howlers

"Ugh. Timber wolves. Look at these dum-dums. Bet ya a nickel one of them's gonna howl."
"And there it is. I mean, what is it with wolves and the howling?"

Judy and Nick's search for a group of kidnapped animals has led them to the abandoned Cliffside Asylum. The building is being guarded by a pack of N (1 ≤ N ≤ 200,000) wolves, who will all need to somehow be distracted if Judy and Nick are to sneak by and investigate the premises.

The wolves are all standing in a row, which can be represented as a number line. The i-th wolf is at position P_i (1 ≤ P_i ≤ 10⁹) on the line, and has an alpha rank of A_i (1 ≤ A_i ≤ 10⁹), with the pack's most respected members having the smallest ranks. All of the wolves are standing at distinct positions, and have distinct ranks.

Wolves sometimes like to howl out of the blue, and they sometimes like to howl when they hear other wolves howling. If wolf i decides to start a howl, then each wolf with a larger alpha rank standing within some howling radius R of wolf i will be obligated to join in (in other words, each wolf j such that A_j > A_i, P_j ≥ P_i − R, and P_j ≤ P_i + R). Each wolf j which joins the howl in this fashion may in turn cause even more wolves to start howling themselves (wolves k which have larger alpha ranks than wolf j and are standing close enough to him), and so on.

Judy and Nick figure that they can trick any K (1 ≤ K < N) wolves of their choice into starting to howl. They're hoping that this plan can result in all N wolves joining the howl, allowing them to sneak by. Unfortunately, they don't know how large the howling radius R is, only that it's some positive integer, so they can't predict how things will go! Still, they'd like to get an idea of how likely their plan is to work, by determining the minimum howling radius R which would be necessary to allow them to get all N wolves to join a howl initially started by some K of the wolves.

In test cases worth 12/30 of the points, N ≤ 2000.

Input Format

The first line of input consists of two space-separated integers N and K.
N lines follow, the i-th of which consists of two space-separated integers P_i and A_i (for i = 1..N).

Output Format

Output a single integer – the minimum howling radius R necessary such that all N wolves can be made to join a howl started by K of them.

Sample Input

7 2
6 8
10 12
12 10
8 1
3 5
13 7
5 4

Sample Output

3

Sample Explanation

If R = 3 and wolves 4 and 6 start a howl, all 7 wolves will end up joining it.
On the other hand, if R = 2, then no 2 initial wolves can be chosen such that all 7 wolves will end up howling.

All Submissions
Best Solutions

Point Value: 14 (partial)
Time Limit: 7.00s
Memory Limit: 64M
Added: Apr 09, 2017
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)