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?

# | User | Rating |
---|---|---|

1 | tourist | 3565 |

2 | Benq | 3540 |

3 | Petr | 3519 |

4 | maroonrk | 3503 |

5 | jiangly | 3391 |

6 | ecnerwala | 3363 |

7 | Radewoosh | 3349 |

8 | scott_wu | 3313 |

9 | ainta | 3298 |

10 | boboniu | 3289 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 198 |

2 | Errichto | 195 |

3 | rng_58 | 189 |

4 | awoo | 186 |

5 | SecondThread | 185 |

6 | Um_nik | 182 |

7 | vovuh | 177 |

8 | Ashishgup | 176 |

9 | antontrygubO_o | 175 |

10 | -is-this-fft- | 173 |

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?

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/09/2021 04:02:04 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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

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

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.

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

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

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.

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

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];

}