Castle Invasion

View as PDF

Submit solution

All submissions

Best submissions

Points: 10 (partial)

Time limit: 1.0s

PyPy 2 2.5s

PyPy 3 2.5s

Memory limit: 64M

PyPy 2 256M

PyPy 3 256M

Authors:

yanda, 4fecta

Problem type

Bob is planning an attack on a suspicious castle owned by the evil villain Joe! The castle can be thought of as an $N$ ~N~ by $N$ ~N~ grid of towers, with each tower having an integer height. To scout for this attack, Bob sent his only drone that can instantly transmit pictures to take photos of the castle. However, the drone only managed to take 2 photos before critically running out of battery and tumbling into the forest. One photo was taken of the front side of the castle, while the other captured its right side. It was also discovered (slightly too late) that the drone's camera cannot capture depth! Since Bob does not want to fail this attack, he would like to know the maximum possible volume of the castle, or if the photos are incorrect and a castle cannot be reconstructed. Can you help him find out?

Input Specification

The first line of the input will contain an integer $N$ ~N~, representing the dimensions of the castle.

The second line will contain $N$ ~N~ integers $c_i$ ~c_i~ $(1 \le i \le N)$ ~(1 \le i \le N)~, representing the height of the tallest tower in the $i^\text{th}$ ~i^\text{th}~ column.

The third line will contain $N$ ~N~ integers $r_j$ ~r_j~ $(1 \le j \le N)$ ~(1 \le j \le N)~, representing the height of the tallest tower in the $j^\text{th}$ ~j^\text{th}~ row.

Output Specification

A single integer, representing the maximum possible volume of the castle, or -1 if it is impossible to reconstruct a castle.

Constraints

For all subtasks:

$1 \le N, c_i, r_j \le 10^6$ ~1 \le N, c_i, r_j \le 10^6~

Subtask 1 [30%]

$1 \le N \le 1\,000$ ~1 \le N \le 1\,000~

Subtask 2 [70%]

No additional constraints.

Sample Input 1

4
1 3 4 2
2 2 1 4

Sample Output 1

Sample Input 2

4
1 2 6 2
5 3 3 3

Sample Output 2

-1

Explanation for Sample Output 2

No matter how you assign heights to each tower, it is impossible to reconstruct a castle that satisfies both photos.

Comments

0

Daniel_Alp commented on Dec. 26, 2021, 2:23 a.m. ← edit 2 →

Any hints how to optimize? I thought it would be fast enough but it's TLEing for the second last case. Edit: thank you to 4fecta and joelfu for speeding up my input, I will use this for future problems instead of scanner if needed. :) Andrew template is so convenient.

3

4fecta commented on Dec. 26, 2021, 2:37 a.m.

Your code looks more or less correct. Try using a faster input method such as BufferedReader, since Scanner becomes quite slow when reading in large amounts of data (around 2 million integers for this problem). More details about the syntax of BufferedReadercan be found here.

0

Daniel_Alp commented on Dec. 26, 2021, 3:12 a.m.

Thanks 4fecta, much appreciated.

0

Mark123 commented on Oct. 12, 2020, 5:39 a.m.

can someone help me, I keep getting the second last case wrong.

0

AlanL commented on Oct. 18, 2020, 12:00 a.m.

Your multiplication on line 50 is overflowing, as mentioned below.

0
HenryYi commented on Oct. 17, 2020, 9:41 p.m. ← edited →
if you get out of memory error, then try different input stream.

static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

0

ross_cleary commented on March 19, 2020, 8:41 p.m.

Can someone take a look at my code, I am wrong answering on the second last case.

1

4fecta commented on March 19, 2020, 10:55 p.m.

Some of your variables declared as int are overflowing.

0

ross_cleary commented on March 19, 2020, 11:12 p.m.

Thank you!

9

pblpbl commented on Oct. 19, 2019, 1:56 p.m.

I finally got this after 3 days! This is a good problem.

5

4fecta commented on Oct. 19, 2019, 6:25 p.m.

I admire your persistence.

0

pblpbl commented on Oct. 16, 2019, 5:57 p.m. ← edit 2 →

Is an $N$ ~N~ by $N$ ~N~ grid required to solve this problem? I am getting a memory error at the second last test case.

8

d commented on Oct. 16, 2019, 7:22 p.m. ← edit 3 →

no, it is not necessary to create an n by n grid

0

pblpbl commented on Oct. 17, 2019, 9:34 p.m.

i'm still stuck on the second last case... hint pls?

3

4fecta commented on Oct. 18, 2019, 3:31 a.m. ← edit 2 →

Your code has a time complexity of $\mathcal{O}(N^2)$ ~\mathcal{O}(N^2)~, which is too slow to pass the second subtask. Try thinking of how you can optimize your algorithm to a better complexity.