TAP2013G - War

no tags 

[The original version of this problem (in Spanish) can be found at http://www.dc.uba.ar/events/icpc/download/problems/tap2013-problems.pdf]

War, an event worthy only of appearance in literature, movies or perhaps programming contests, has reached the Nlogonian empire, which is facing the neighboring empire of Quadradonia.

War protocols agreed upon by both parties indicate that the war will be waged in successive battles, in each of which a different soldier from each empire will face one another, so that each soldier will take part in exactly one battle. The empire that wins more battles will then win the war.

Each empire has an army formed by S soldiers, and each soldier has a certain combat skill. In each battle between two soldiers, the one with greatest combat skill wins the battle. If both soldiers have the same combat skills, the battle is declared a draw and technically no side claims victory. The spies of Nlogonia have intercepted secret information concerning the combat skill of each soldier of Quadradonia's army, so Nlogonia's queen requires your assistance in order to calculate the maximum number of battles that can be won during the war if her soldiers are sent in the appropriate order.

 

Input

The first line contains an integer number S representing the number of soldiers in each army (1 ≤ S  105). The second line contains S integer numbers Qi representing the combat skills of the different soldiers of Quadradonia's army, in the order in which the battles shall take place ( Qi  109 for i = 1, ..., S). The third line contains S integer numbers Ni representing the combat skills of the different soldiers in Nlogonia's army, in an arbitrary order ( Ni  109 for i = 1, ..., S).

 

Output

Print a line containing a single integer number representing the maximum number of battles that Nlogonia can win during the war.

 

Example 1

Input:
3
2 1 1000000000
1 1 2

Output:
1

Example 2

Input:
4
6 3 1 4
2 7 4 3

Output:
3

hide comments
akshayvenkat: 2016-06-10 10:35:32

O(2*n*log n)+ O(n) [separated loops] -> 0.31 AC

MAYANK NARULA: 2015-12-13 17:19:40

I used Binary Search for computational part with vectors,iterators and got tle....
Had to resort to Linear Search ... unexpectedly AC !!!

[Mayank Pratap]: 2015-07-22 17:39:19

Author has chosen funny names of empires .... O(nlogn) vs O(n^2)....

Gaurav sharma: 2015-07-19 13:31:33

easy one :) century completed :P

vipul sharma: 2015-07-16 19:24:16

sort
sort
2 pointers :)

Akshat Mathur: 2015-07-08 18:58:05

AC in one go :-)
Think simple.

SRC: 2015-06-16 10:25:30

Getting a wrong answer in 35th running, can someone provide some tricky test cases?

---@@@----: 2015-06-04 16:44:21

Easy .. :)

Sayak Haldar: 2015-01-02 06:51:38

I got ac with O(nlogn)+O(n) approach,but when is comes to O(nlogn)+O(logn) approach it is giving so much wa..:/

Last edit: 2015-01-02 07:01:20
Prajval Prabhakar: 2014-09-29 17:03:31

ac in first go :)


Added by:Fidel Schaposnik
Date:2013-10-07
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Argentinian Programming Tournament 2013