Take Me There

Computer Science Level 5

There are N N men gathered outside of a cinema hoping to watch the newly released movie Star Wars. The i th i^\text{th} person will only go in if at least L i L_{i} other people will go with him because he doesn't want to get lonely. Additionally, that person doesn't want to go with more than H i H_{i} other people since it would get crowded and ruin the experience.

This text contains N N spaced integers each representing the ( L i , H i ) (L_{i}, H_{i}) of the i th i^\text{th} individual. What is the maximum number of men that can get inside at one time such that no constraint is violated?

Details and assumptions:

  • The first line indicates the number of people N N .
  • For example, the maximum number of people is 3 in the case below. Each of them can take another 2 people, but not anymore. 
1
2
3
4
5
 
4
1 4
1 2
1 4
1 3


The answer is 18.

Beakal Tiliksew by Beakal Tiliksew , 24, Ethiopia

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Idea: A third party calls out the number of people who will go. Everyone raises their hand if that number agrees with their personal constraints. If the number of hands agree with the number called out, all the people raising their hands go out. It is evident the referee has to call out the numbers in descending order. 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
 
#include <iostream>
#include <vector>

using namespace std;

typedef pair<int, int> ii;

int main(){
    int N;
    cin >> N;

    vector<int> L(N);
    vector<int> H(N);
    int maxH = 0;
    for (int iii=0; iii < N; iii++){
        int Li, Hi;
        cin >> Li >> Hi;
        L[iii] = Li;
        H[iii] = Hi;
        maxH = max(maxH, Hi);
    }

    for (int people=maxH; people >= 0; people--){
        int total = 0;
        for (int iii=0; iii < N; iii++)
            if (L[iii] <= people && H[iii] >= people)
                total++;
        if (total == people){
            cout << people << endl;
            break;
        }
    }

    return 0;
}

This takes quiet a while to run. The time complexity is O ( n max ⁡ ( H i ) ) O(n \max(H_i))

Sorting the pairs by the L i L_i and then by their H i H_i values and using binary search to find the number of people who'd agree would reduce the time complexity to O ( log ⁡ n max ⁡ ( H i ) ) O( \log n \max(H_i))

2 Helpful 0 Interesting 0 Brilliant 0 Confused

How do you Binary Search? For example, take this sorted input : 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
 
10
1 1
9 9
9 9
9 9
9 9
9 9
9 9
9 9
9 9
9 9

Your first attempt is 5 5 . Then how do you approach if you should increase or decrease the bound?

Christopher Boo - 4 years, 10 months ago

Log in to reply

No, my first attempt wouldn't be 5. My first attempt would be 9, i.e, max ⁡ H i \max H_i .

By Binary Search, I will find the greatest i i such that L i ≤ 9 L_i \leq 9 . That's i = 10 i=10 . So, from 1 to i i , we are sure that the people wouldn't go because two few people are going. All the people who have index greater than i i wouldn't agree to go.

Then again, by binary search, I will find the least j j within 1 ⋯ i 1 \cdots i such that 9 ≤ H i 9 \leq H_i . That's j = 2 j = 2 . So, from j j to i i , all the people would agree to go.

If i − j + 1 i-j+1 is equal to my guess, then my guess was correct.

Agnishom Chattopadhyay - 4 years, 10 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...