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

×

SRVRS - Editorial (Unofficial) & Discussion

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

asked 17 Jul, 19:38

liouzhou_101's gravatar image

7★liouzhou_101 ♦♦
6622211
accept rate: 12%

edited 18 Jul, 14:49

admin's gravatar image

0★admin ♦♦
17.4k347486515


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

link

answered 17 Jul, 19:44

meooow's gravatar image

5★meooow ♦
5.4k411
accept rate: 46%

edited 17 Jul, 19:49

3

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

(17 Jul, 20:11) vijju123 ♦4★
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) alexvaleanu4★
1

Wow, 200 submissions! That's one of the reasons you are orange...

(19 Jul, 20:04) akashbhalotia3★

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

link

answered 19 Jul, 08:08

liouzhou_101's gravatar image

7★liouzhou_101 ♦♦
6622211
accept rate: 12%

A pretty decent explanation!!

(19 Jul, 21:27) vijju123 ♦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?

link

answered 17 Jul, 20:13

liouzhou_101's gravatar image

7★liouzhou_101 ♦♦
6622211
accept rate: 12%

1

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

(17 Jul, 20:37) vijju123 ♦4★
1

Yep, @vijju123 is right, unfortunately.

(19 Jul, 00:40) meooow ♦5★

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.

link

answered 17 Jul, 22:13

sapfire's gravatar image

3★sapfire
1
accept rate: 0%

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

link

answered 18 Jul, 11:30

vis_24_hal's gravatar image

3★vis_24_hal
123
accept rate: 20%

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

(19 Jul, 00:43) meooow ♦5★

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?

link

answered 18 Jul, 16:06

shubham_bits's gravatar image

6★shubham_bits
2487
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) alexvaleanu4★

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

link

answered 18 Jul, 16:39

prakhariitd's gravatar image

6★prakhariitd
1.1k110
accept rate: 10%

-1

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

link

answered 19 Jul, 05:50

sonu_628's gravatar image

3★sonu_628
2328
accept rate: 8%

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:

×738
×610
×224
×21
×14

question asked: 17 Jul, 19:38

question was seen: 951 times

last updated: 19 Jul, 21:27