Блог пользователя t0rto1se

Автор t0rto1se, история, 2 года назад, По-английски

Problem Name — "Group Photo"

There are $$$N$$$ people, each with a unique height. The height of the $$$i^{th}$$$ person is $$$i (1 \leq i \leq N)$$$. The $$$i^{th}$$$ person will smile in the photo if at least $$$A[i]$$$ people in the photo are shorter than him and at most $$$B[i]$$$ people in the photo are taller than him.

Find the largest group such that everyone will smile in the photo of this group. A group is a collection of randomly selected people from the given $$$N$$$ people.

Constraints:

  • $$$1 \leq N \leq 10^5$$$

  • $$$0 \leq A[i], B[i] \leq N$$$

Example Test Case
My O(N^2) approach

I cannot come up with a better solution for this. Any help would be greatly appreciated, thanks!

  • Проголосовать: нравится
  • +19
  • Проголосовать: не нравится

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Binary Search on the number of people. Also this is a Codeforces problem.

»
2 года назад, # |
Rev. 2   Проголосовать: нравится +9 Проголосовать: не нравится
Hint
Solution
Code
  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Plzz share the code in spoiler tag. Thanks in advance

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Wow, it seems so easy now, yet it never occurred to me during the contest to use binary search. Thanks a lot!

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    ohh means loop [1..n] --> check for i that A[i] >= no. of choosen before and B[i] < (avilable space) Right??