ECOO '21 Practice P3 - Turin's Thrifty Threads

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 2.0s
Memory limit: 64M

Problem type

Note this problem was originally intended for the cancelled 2020 Girls Invitational Competition.

Turin is a seamstress who has received a special order from a client to hem skirts in time for prom season! Since prom dresses are very fancy, this client has sent Turin equal numbers of dresses and special threads in pre-cut lengths to use to hem each skirt. However, Turin has run into a problem. The length of threads that were sent don't entirely match the length of the fabric of each skirt! In order to hem a skirt, Turin can use thread that is a length strictly greater than the length of the fabric. Turin wants to maximize the number of skirts she can properly hem, even if it means leaving skirts with longer lengths to be left unhemmed using thread that is too short.

Given the lengths of each thread and skirt, can you determine the maximum number of dresses Turin can properly alter?

Input Specification

The first line of input will contain an integer, N (1 \le N \le 10^5), the number of dresses and thread.

The next line will contain N space-separated integers, with each integer denoting a length of thread, l_i.
The final line will contain N space-separated integers, with each integer denoting a length of fabric that must be altered, l_i.

It is guaranteed that 1 \le l_i \le 10^6.

Output Specification

Output the maximum number of dresses she can alter.

Sample Input 1

4 1 2
5 2 3

Sample Output 1


Explanation For Sample 1

If she pairs the lengths of thread and dresses such that:

1 2 4
5 2 3

She can hem exactly one dress (the last one).

Sample Input 2

8 4 7 5
2 1 8 9

Sample Output 2



There are no comments at the moment.