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 | Benq | 3783 |

2 | jiangly | 3666 |

3 | tourist | 3611 |

4 | Um_nik | 3536 |

5 | inaFSTream | 3477 |

6 | fantasy | 3468 |

7 | maroonrk | 3464 |

8 | QAQAutoMaton | 3428 |

9 | ecnerwala | 3427 |

10 | Ormlis | 3396 |

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

1 | Um_nik | 185 |

2 | adamant | 177 |

2 | awoo | 177 |

4 | nor | 169 |

5 | maroonrk | 165 |

6 | -is-this-fft- | 164 |

7 | antontrygubO_o | 153 |

8 | ko_osaga | 151 |

9 | dario2994 | 150 |

10 | SecondThread | 149 |

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-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/31/2023 21:39:18 (l1).

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

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.

I am still getting tle bruh!`

my solnCan you help me out?

same doubt

Same solution But get tle . So, much tight bounds in simple problem . https://cses.fi/paste/f28396ef9920770e4c50e2/

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