PANDEPIC's blog

Please help me solve this problem!
By PANDEPIC, history, 18 months ago, In English

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

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
18 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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$$$).

→ Reply
  • »
    »
    18 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    if possible could you please provide me with the code?

    → Reply
    • »
      »
      »
      18 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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)
      → Reply
»
18 months ago, # |
  Vote: I like it -8 Vote: I do not like it

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.

→ Reply
  • »
    »
    18 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    if possible could you please provide me with the code?

    → Reply