CCO '97 P2 - Alien Invasion - Olympiads Online Judge

CCO '97 P2 - Alien Invasion

View as PDF

Submit solution

All submissions

Best submissions

Points: 10 (partial)

Time limit: 2.0s

Memory limit: 64M

Problem type

Canadian Computing Competition: 1997 Stage 2, Day 1, Problem 2

Earth is being invaded by space aliens. Earth defence forces have rallied a number of anti-spacecraft guns. However, they have a bug in their aiming hardware: initially they are aimed straight up, and this aim can only be adjusted downward.

Thousands of alien craft are streaking towards Earth as we speak -- and yes, some of them are even aimed at Canada. The Earth defence forces must now come into play. Each gun can fire as many shots as necessary, and can be re-fired as often and as quickly as necessary, but only to the same or lower setting. Thus if a spacecraft came in at height $3$ $3$ and then another at height $2$ $2$ , one gun could eliminate both, but could not if they came in the other order. The Earth has only a finite number of guns and it is unknown how many alien craft are coming in. Thus they need a way to minimize the number of guns for a given set of incoming alien craft. Guess what? This is where you come in!

Input Specification

The data will consist of several sets of data. The first line will contain $T$ $T$ $(1 \le T \le 5)$ $(1 \leq T \leq 5)$ , the number of test cases. The first line of each set will contain one positive integer $n$ $n$ $(1 \le n \le 10^5)$ $(1 \leq n \leq 10^{5})$ , where $n$ $n$ is the number of incoming alien craft. The next $n$ $n$ lines will contain one integer number giving the heights of the incoming alien craft in order of arrival that are less than $10^9$ $10^{9}$ (i.e., the order the guns must eliminate them).

Output Specification

For each set, output one integer specifying the minimum number of guns required to eliminate EVERY alien craft.

Sample Input

Copy

Sample Output

Copy

Comments

0

sre0x2a commented 3 days ago

How is the sample output 4? 4 > 2, 2 < 3, 3 < 4, 4 < 5, 5 > 3, 3 > 1, 1 < 4, 4 > 2, 2 < 5 If we set the gun count at 1 to start and increment it at 4 < 5, 1 < 4, and 2 < 5 that gives 4. That is not consistent though because why would we increase the gun count at all between both 5s if we did not for the increasing sequence after the first 4?

2
d commented 3 days ago
Seems like you're trying to take out the first 4 aliens with 1 gun. The gun can go from height 4 to height 2, but can't go from height 2 to height 3, so this doesn't work.

One way to take out the aliens using 4 guns is:

Copy
aliens: 4 2 3 4 5 3 1 4 2 5 gun 1: x x x gun 2: x x x gun 3: x x gun 4: x x