There are **1 billion** stars and you are standing at earth. Form the earth you know the distance of all **1 billion** stars. Find the nearest **1 million** stars from the earth.

Thanks in advance.

# | User | Rating |
---|---|---|

1 | Benq | 3783 |

2 | jiangly | 3666 |

3 | tourist | 3611 |

4 | Um_nik | 3536 |

5 | inaFSTream | 3477 |

6 | fantasy | 3468 |

7 | maroonrk | 3464 |

8 | QAQAutoMaton | 3428 |

9 | ecnerwala | 3427 |

10 | Ormlis | 3396 |

# | User | Contrib. |
---|---|---|

1 | Um_nik | 185 |

2 | adamant | 178 |

3 | awoo | 177 |

4 | nor | 169 |

5 | maroonrk | 165 |

6 | -is-this-fft- | 164 |

7 | antontrygubO_o | 153 |

8 | ko_osaga | 151 |

9 | dario2994 | 150 |

10 | SecondThread | 149 |

There are **1 billion** stars and you are standing at earth. Form the earth you know the distance of all **1 billion** stars. Find the nearest **1 million** stars from the earth.

Thanks in advance.

↑

↓

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/02/2023 01:59:24 (j2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

If all stars are in an array, we assign each star a value equal to the distance of that star to earth. Then the median of medians algorithm finds the k-smallest element in O(n) time worst-case, and also partitions the array such that all elements smaller than the k-smallest element are left of it, and the elements larger are right of it (i.e. the k-smallest element is in position k in a 0-based array).

Note that this is asymptotically optimal, not necessarily faster in practice. An easier approach would be to just sort the array in O(n lg n).

Firstly, I wanna thank you for your comment.Secondly, 1 billion is still a large number to store it in an array So i thought about another solution and I found this one out UsingBinary Search Tree.Cause I'm newbie with the

Binary Search TreeI think this algorithm's complexity will be`O(nlog(n))`

(Without printing)I dunno if This algorithm and its complexity are right or not.

O(m log(n)) where m is 1 billion, n is 1 million. Also, it's better to use a priority queue because it has O(1) access to the largest element, so some loop iterations will take O(1) instead of O(log n). Best case time (when all n largest elements are already in the beginning) will be O(m + n log(n)).

Have a sliding window of size 1 million and imagine it to be a max-heap. The problem boils down to finding K smallest elements from N elements where K is 1e6 and N is 1e9. When we slide the max heap over the billion distances, at the end of scan we will have nearest 1 million distances.

Steps : a) Add first K(1 million) distances into max-heap. b) For K+1 element, to add this into the heap, it needs to be smaller than the max heap root. If yes, extract-max and add this (K+1)th element into the heap and heapify. Else, continue scanning. c) At the end of scan, max heap has the answer.

Please correct me if I am wrong.

Complexity(worst case) : (N-K) extracts from Max heap and heapify = (N-K) log(K) plus O(K) for build Heap with K elements to begin with. => O(K+ (N-K) logK)

You may do it in O(n). Add elements one by one. When there's 2k elements run nth_element and remove k of them

I can't understand what you want to say.

Could you write a Pseudocode for your idea, please?! riadwaw

http://www.cplusplus.com/reference/algorithm/nth_element/

nth_element itself only o(n) in average but afaik it's possible to find median in O(n) in worst case too (and if you have a median you may easily rearrange elements as nth_elements do.