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

Please help me solve this problem!
Автор PANDEPIC, история, 17 месяцев назад, По-английски

Could anyone from the codeforces community help me solve this problem? Any kind of help will be appreciated. Thankyou in anticipation. https://mirror.codeforces.com/gym/101149/problem/E -> This is the problem link.

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

»
17 месяцев назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

You are only allowed to assign scores within the range of each contestant.

You want to maximize the number of contestants with the maximum score.

So consider the result if you decide the maximum score is the max $$$r_i$$$ value at first.

Then try lowering it by one repeatedly and each time consider which contestants can join the group of winners. At a certain point you cannot lower it any further without breaking the scoring conditions of at least one of the contestants.

Generally when working with intervals it can be helpful to view them after sorting them by starting point, end point, size or slack ($$$r_i - l_i$$$).

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

    if possible could you please provide me with the code?

    → Ответить
    • »
      »
      »
      17 месяцев назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      You gain more by implementing yourself. But here it is:

          n = int(input())
    A = []
    for i in range(n):
        l,r = map(int, input().split())
        A.append((l,r))
    A.sort()
    result = 0
    for i in range(n):
        if A[i][1] >= A[-1][0]:
            result += 1
    print(result)
      → Ответить
»
17 месяцев назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

It is rather easy to solve if you know what dynamic segment tree is. In fact, this is segment tree which supports the same operations as per usual segment tree do, but you can expand value's bounds (in this task you can store all segments from -1e9 to 1e9). If you have such a structure, all you have to do is to add +1 to each number of each segment (using lazy propagation in segment tree) and take maximum over all values in your tree which are bigger than smallest bound of all segments.

P.S. dynamic segment tree usually works like a coordinate compression, but if you're using first way, you should simply copy-paste structure, while in the second way you should "integrate" compression into your code.

→ Ответить