obocheton's blog

By obocheton, history, 2 years ago, In English

I was trying this problem CSES 1084.

I greedily choose the lowest sized valid apartment for every applicant (sorted both lists ascendingly).

But it turns out to be a wrong approach.

Why my approach is wrong?

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

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Inserting the apartment sizes into the set may remove some apartments with the same size. Try using a multiset or a regular vector

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    what about erasing an element from vector, isn't it O(n)?

»
2 years ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it

There can be multiple apartments with same size so instead of using set use multiset. And use inbuilt lowerbound function of set as thats faster .And to remove only one element from the multiset use s.erase(it) instead of s.erase(*it) as the later will remove all occurrences of *it.

Spoiler
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks. I was searching for this one. Your code was helpful for me.

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

    would you describe a bit, that lower bound part? I'm having some problem there.

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

    I am still getting tle bruh!`

    my soln

    Can you help me out?

»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Here was my idea previously.

Maintain two pointers, left and right. Sort both lists, lets call them A and B.

Then the answer is just the number of points of the arrays that match up together (by x).

Many people are looking at multi set, but to be honest, I think two pointers is a really easy to understand approach, and it's just as efficient / effective.

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

    Yes finally I understood that... And did by that method:)

»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

FYI, lower bound on sets is O(n), so you should probably use -> (set name).lower_bound(iterator).

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

    LOL, This means I used the wrong syntax. Thanks for correcting :>

»
19 months ago, # |
  Vote: I like it -9 Vote: I do not like it

given problem is not clear that why its take lot of tym to solve. but now i have solution for this.

include <bits/stdc++.h>

using namespace std;

define int long long

signed main(){ int n , m , k ; cin >> n >> m >> k; int a[n] ; for(int i = 0 ; i < n ; i++) cin >> a[i]; int b[m] ; for(int i = 0 ; i < m ; i++) cin >> b[i];

sort(a , a+n);
sort(b , b+m);

int i = n - 1 , j = m - 1;

int applicants = 0;

while(i >= 0 && j >= 0){

    if (b[j] < a[i] - k)
        i--;
    else if (b[j] > a[i] + k)
        j--;
    else
    {
        applicants++;
        i--;
        j--;
    }
}
cout << applicants << endl;

}

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

The algorithm is obvious to guess. The proof that it works is a little tricky.

Assume that it's true for $$$n \ge 1$$$ people. We'll show that it's true for $$$n+1\ge 2$$$ people.

Let the $$$n+1$$$ people be $$$p_1,\dots,p_{n+1}$$$ and let the $$$m$$$ apartments be $$$a_1,\dots,a_m$$$. Let the configuration of the $$$n+1$$$ people be $$$C = {(p_{i_1}, a_{j_1}),\dots, (p_{i_{|C|}}, a_{j_{|C|}})}$$$. We'll also assume that each $$$p$$$ s and $$$a$$$ s is distinct. We basically want to maximize $$$|C|$$$.

Let $$$C'$$$ be a configuration such that $$$|C'|$$$ is maximal. Note that $$$C'$$$ isn't necessarily the greedy algorithm, however, the greedy algorithm always gives $$$|C'|$$$.

If $$$|C'| = 1$$$, the greedy algorithm obviously works.

Otherwise $$$|C'| \ge 2$$$ and we let $$$p_{min}$$$ and $$$p_{max}$$$ be the minimum value of $$$p$$$ and the maximum value of $$$p$$$ in $$$C'$$$. Let the corresponding $$$a$$$ s be $$$(p_{min},a_0)$$$ and $$$(p_{max}, a_1)$$$. With respect to $$$(p_{max}, a_1)$$$, the other $$$n$$$ people can be greedy (such that $$$|C'|$$$ is still the same) and thus $$$(p_{min},a_0)$$$ is greedy. Similarly, with respect to $$$(p_{min},a_0)$$$, the other $$$n$$$ people can be greedy (such that $$$|C'|$$$ is still the same). And thus the greedy algorithm for $$$n+1$$$ people gives $$$|C'|$$$.