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.

By Shayan

Before stream
03:41:14

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

1 | tourist | 3845 |

2 | jiangly | 3707 |

3 | Benq | 3630 |

4 | orzdevinwang | 3573 |

5 | Geothermal | 3569 |

5 | cnnfls_csy | 3569 |

7 | jqdai0815 | 3532 |

8 | ecnerwala | 3501 |

9 | gyh20 | 3447 |

10 | Rebelz | 3409 |

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

1 | maomao90 | 171 |

2 | adamant | 163 |

3 | awoo | 162 |

4 | nor | 153 |

5 | maroonrk | 152 |

6 | -is-this-fft- | 151 |

7 | TheScrasse | 150 |

8 | Petr | 145 |

9 | atcoder_official | 144 |

9 | pajenegod | 144 |

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-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/22/2024 16:18:46 (h2).

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.