HCI '16 - Boxception

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 2.0s
Memory limit: 32M

Authors:
Problem type

"Animals generally form groups. Carnivores have a hierarchy, and those that don't manage to get to the top of the food chain will live a life of constant stress. Herbivores have their own problems, like being forced to abandon their own survive enemy attacks. As you can see, being in a group brings no advantages to the individual. Thus, I choose to be the bear, a beast that refuses to form groups with others. It's an animal of isolation that's not at all worried about its solitary lifestyle. Let's not forget that bears get to hibernate as well. Oh, what a wonderful existence. If I'm ever reincarnated, I most certainly would like to be reborn as a bear."

Such are the sentiments of Nate, a nihilistic teenager who shuns the company of others. In fact, the above paragraph was something he wrote for one of his school assignments. Nevertheless, Nate finds some things in the world interesting, such as movies. One day, he watched the movie "Inception" online and proceeded to ask Siri, "What is inception?" to which she replied, "Inception is about dreaming about dreaming about dreaming about dreaming about something or other. I fell asleep." Now Nate wonders, "What if I had a box in a box in a box in a box in a box…" and helplessly fell asleep. After waking up from a short sleep, in his dazed state, Nate forgot the fact that he had no friends (or anyone he even considers an acquaintance), and thought, "Oh yes! I can put a box in a box in a box in a box and troll people!" (One day he realizes his grave mistake and momentarily falls into a state of depression, but that story is a few months away, so let's not get to that right now)

Nate searches his house for boxes, and finds N boxes of varying heights and widths. Conveniently, each box i has a square base of width W_i and a height of H_i. A box i can be put into box j if and only if W_i < W_j and H_i < H_j. Also, from opening one box, there must be at most 1 other box immediately visible. In other words, he cannot have two boxes i and j both in a box k when i does not contain j and j does not contain i. While smirking to himself, Nate thinks, "Heheheh… People are going to be mad when they open so many boxes only to find the last box contains nothing…" While admiring his own genius, he comes up with a more evil scheme – to maximize the average number of boxes a person has to open for each giant box. In other words, he wants to find how to store all the boxes in other boxes such that the number of boxes visible from an outsider's point of view is minimal (minimize the number of boxes not contained in another box). As Nate finds this to be a tedious task, he seeks the help of a computer programmer – you.

Input Specification

The first line will contain an integer N, the number of boxes Nate has.

The following two lines will each contain N integers W_1, \dots, W_N and H_1, \dots, H_N respectively.

Output Specification

The output should contain one line with one integer, the minimum number of boxes that are not put into another box, while following the other conditions Nate has set.

Constraints

For all subtasks:

0 \le W_i, H_i \le 2^{31}-1

Subtask 1 [26%]

1 \le N \le 2\,000.

Subtask 2 [33%]

1 \le N \le 100\,000

Subtask 3 [41%]

1 \le N \le 1\,000\,000

Subtask 4 [0%]

Sample test cases.

Sample Input

6
10 20 10 40 23 53
20 30 10 30 43 31

Sample Output

2

Explanation for Sample Output

Put box 1 in 4 in 6, box 3 in 2 in 5, then only boxes 5 and 6 are visible (not contained in another box).


Comments

There are no comments at the moment.