SRVRS - Editorial (Unofficial) & Discussion

general
, , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Alexandru Valeanu
Editorialist: Tiny Wong

DIFFICULTY:

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

5 Likes
2

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 :stuck_out_tongue:

8 Likes
3

Wow. I gave up twocoins after ~50 failed attempts. Seriously, you have a lot of patience!!

3 Likes
4

@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?

5

Not for challenge problems. Its 200 for them and 500 for regular ones :slight_smile:

1 Like
6

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 :frowning:
so I had to implement an easier solution that got 51 pts.

7

@meoow I am going to remember this always from now on. I gave up twocoins under 10 attempts :frowning:

8

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?

9

Can someone look at my submissions and tell why I was getting -1 time?

10

Yep, @vijju123 is right, unfortunately.

1 Like
11

Tweaking parameters doesn’t apply to non challenge problems, but of course, always keep trying :slight_smile:

12

@meooow I’m sorry about that. Next time I promise it will be mentioned in the statement (constraints section probably).

1 Like
13

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.

14

@prakhariitd lol never seen a negative time it must be a bug

15

@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.

1 Like
16

Wow, 200 submissions! That’s one of the reasons you are orange…

1 Like
17

A pretty decent explanation!!