I recently studied this data structure, and resolved some problems, but I would like to solve other, if anyone can give me some problems, I would be grateful.
This are some problems that i solved by kdtree:
City Houses (with manhattan distance)
Counting Points (basic of kdtree)
Elizabeth's Kingdom (some dificult but very nice problem)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | jiangly | 3810 |
| 2 | Benq | 3676 |
| 3 | Kevin114514 | 3655 |
| 4 | maroonrk | 3463 |
| 5 | strapple | 3447 |
| 6 | Um_nik | 3387 |
| 7 | heuristica | 3322 |
| 8 | turmax | 3317 |
| 9 | tourist | 3307 |
| 10 | jiangbowen | 3291 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 156 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | Um_nik | 142 |
| 5 | Errichto | 139 |
| 6 | adamant | 137 |
| 7 | AmShZ | 135 |
| 8 | BledDest | 132 |
| 8 | maroonrk | 132 |
| 10 | qwexd | 129 |
It's look like COJ is not accepting submissions :( Could someone help me? I think I got a working solution for the City Houses problem.
because of the covid situation, currently, in Cuba, the universities are close, this will probably take some time before being fixed
Maybe I’m wrong, but as far as I know kd-trees can cave a complexity as bad as $$$O(N)$$$ per query for malicious inputs.
Also, what is the complexity of your solution to the third problem with KD-trees? I am pretty sure that $$$O(N^2)$$$ and even $$$O(N logN)$$$ can be achieved (it seems to me that you only have to count pairs that are neighbouring on the Voronoi diagram).
Pupils should be solving array problems, not kdtree problems.
hahahaha