PROBLEM LINK:Author: Alexandru Valeanu DIFFICULTY:CHALLENGE. PREREQUISITES:Greedy, kd 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{(xx_i)^2+(yy_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 kd tree to find the nearest point. More precisely, the CPUs are considered to be a 3dimensional 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_1x_2)^2+(y_1y_2)^2}+z_1z_2. $$ Just following the simple idea can make you become a top coder of this problem. EDITORIALIST'S SOLUTION:EDITORIALIST's solution is here asked 17 Jul '17, 19:38

I was not able to get a high score for a very stupid reason. Initially I did not know about the kd tree structure. So I spent a LOT of submissions adjusting my solution based on clustering. When I came to know about kd 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 '17, 19:44
3
Wow. I gave up twocoins after ~50 failed attempts. Seriously, you have a lot of patience!!
(17 Jul '17, 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 '17, 00:55)
1
Wow, 200 submissions! That's one of the reasons you are orange...
(19 Jul '17, 20:04)

@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 '17, 08:08

@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 '17, 20:13

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 '17, 22:13

Can someone look at my submissions and tell why I was getting 1 time? answered 18 Jul '17, 16:39

@prakhariitd lol never seen a negative time it must be a bug answered 19 Jul '17, 05:50
