×

# SRVRS - Editorial (Unofficial) & Discussion

Author: Alexandru Valeanu
Editorialist: Tiny Wong

CHALLENGE.

# PREREQUISITES:

Greedy, k-d tree.

# PROBLEM:

Given $n$ points $(x_i, y_i)$ with a collection of CPUs of processing time $p_{ij}$. You are asked to answer $q$ queries ONLINE. Each query contains a point $(x, y)$, and you should associate it with an unused CPU, and the cost is $\sqrt{(x-x_i)^2+(y-y_i)^2}+p_{ij}$. Once a CPU of processing time $p_{ij}$ is associated, it cannot be used until $p_{ij}$ seconds passes.

# QUICK EXPLANATION:

There is a good enough greedy method, which is that we choose the minimal cost CPU that is unused currently.

# EXPLANATION:

In order to follow the greedy method declared in QUICK EXPLANATION, we can just use a k-d tree to find the nearest point.

More precisely, the CPUs are considered to be a 3-dimensional point $(x_i, y_i, p_{ij})$ with the meanings corresponding to the above, while each query point can be regarded as $(x, y, 0)$. The distance between two points is defined by $$\operatorname{dis}((x_1, y_1, z_1), (x_2, y_2, z_2)) = \sqrt{(x_1-x_2)^2+(y_1-y_2)^2}+|z_1-z_2|.$$

Just following the simple idea can make you become a top coder of this problem.

# EDITORIALIST'S SOLUTION:

EDITORIALIST's solution is here

6622211
accept rate: 12%

17.4k347486515

 8 I was not able to get a high score for a very stupid reason. Initially I did not know about the k-d tree structure. So I spent a LOT of submissions adjusting my solution based on clustering. When I came to know about k-d trees and implemented it this morning, I also came to know there is a submission limit of 200 and I had exhausted it :P answered 17 Jul, 19:44 5★meooow ♦ 5.4k●4●11 accept rate: 46% 3 Wow. I gave up twocoins after ~50 failed attempts. Seriously, you have a lot of patience!! (17 Jul, 20:11) 1 @meooow I'm sorry about that. Next time I promise it will be mentioned in the statement (constraints section probably). (19 Jul, 00:55) 1 Wow, 200 submissions! That's one of the reasons you are orange... (19 Jul, 20:04)
 1 @prakhariitd I think it implies that your code runs in time for all test cases (or it will show TLE), however, the worst case of your code appears in the hidden test cases. Codechef will run everybody's challenge code with all the test data during the active contest, but will not display the situation of hidden test cases. It is because it must guarantee that everyone's AC code must be AC at the end of the contest. answered 19 Jul, 08:08 662●2●2●11 accept rate: 12% A pretty decent explanation!! (19 Jul, 21:27)
 0 @meooow I found that I couldn't reply you unless I post another answer. I'm sorry to hear that you reached the submission limit. However, I remember that the limit is 500, isn't it? answered 17 Jul, 20:13 662●2●2●11 accept rate: 12% 1 Not for challenge problems. Its 200 for them and 500 for regular ones :) (17 Jul, 20:37) 1 Yep, @vijju123 is right, unfortunately. (19 Jul, 00:40) meooow ♦5★
 0 I tried another greedy approach. For each query we choose the nearest server to the query task that has an available CPU. Kept getting WAs :( so I had to implement an easier solution that got 51 pts. answered 17 Jul, 22:13 3★sapfire 1 accept rate: 0%
 0 @meoow I am going to remember this always from now on. I gave up twocoins under 10 attempts :( answered 18 Jul, 11:30 12●3 accept rate: 20% Tweaking parameters doesn't apply to non challenge problems, but of course, always keep trying :) (19 Jul, 00:43) meooow ♦5★
 0 Nice approach! I was trying to find a good implementation of Voronoi Diagram but couldn't find it. Did anyone solve it using Voronoi diagram? answered 18 Jul, 16:06 248●7 accept rate: 57% I have read quite a lot of the sources (not all of course). I haven't seen any Voronoi implementation. I must confess that I haven't even thought about it. Nice idea. Congrats for having it. (19 Jul, 01:14)
 0 Can someone look at my submissions and tell why I was getting -1 time? answered 18 Jul, 16:39 1.1k●1●10 accept rate: 10%
 -1 @prakhariitd lol never seen a negative time it must be a bug answered 19 Jul, 05:50 3★sonu_628 232●8 accept rate: 8%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×738
×610
×224
×21
×14