Appleby Contest '19 P5 - Matrix Operation - Olympiads Online Judge

Appleby Contest '19 P5 - Matrix Operation

View as PDF

Submit solution

All submissions

Best submissions

Points: 10 (partial)

Time limit: 2.0s

Python 4.0s

Memory limit: 1G

Author:

Plasmatic

Problem types

Plasmatic is writing a problem for a programming contest. However, there is one issue: he can't solve it and needs your help.

The problem goes as follows:

Given an $N \times N$ ~N \times N~ matrix of numbers, what is the longest strictly increasing path through the matrix, assuming that you can only move horizontally or vertically?

Being the good friend that you are, can you help him do it?

Note: If you are using Python 2/3, submit using PyPy 2/3 instead because it is significantly faster

Input Specification

The first line contains $N$ ~N~.

The next $N$ ~N~ lines each contain $N$ ~N~ space separated integers $x$ ~x~ that denote the matrix.

Output Specification

On a line, output the longest strictly increasing path in the matrix.

Constraints

For all subtasks:

$1 \le x \le 10^9$ ~1 \le x \le 10^9~

Subtask 1 [5%]

$1 \le N \le 2$ ~1 \le N \le 2~

Subtask 2 [20%]

$1 \le N \le 50$ ~1 \le N \le 50~

Subtask 3 [75%]

$1 \le N \le 1500$ ~1 \le N \le 1500~

Sample Input 1

Sample Output 1

Explanation for Sample Output 1

To get the longest strictly increasing path you can traverse the values of the matrix in the following order: $1, 2, 3, 4, 8, 9$ ~1, 2, 3, 4, 8, 9~. Since path length is calculated by how many movements you have to make and not by the amount of values that you touch, the answer is $5$ ~5~ instead of $6$ ~6~.

Note that the values aren't guaranteed to be unique in the actual test data.

Sample Input 2

Sample Output 2

Explanation for Sample Output 2

The longest path is a spiral starting from $1$ ~1~ and ending at $9$ ~9~.

Comments

4

rangerN commented on Jan. 3, 2021, 4:36 p.m.

Does "strictly increasing" mean that a value must be greater than the previous value, or greater than/equal to?

8

BalintR commented on Jan. 3, 2021, 5:21 p.m.

All the numbers must be greater than the previous one. E.g the sequence $1, 3, 4, 5$ ~1, 3, 4, 5~ is strictly increasing, but the sequence $1, 2, 2, 4, 6$ ~1, 2, 2, 4, 6~ is not.

2

andrewtam commented on Oct. 27, 2020, 8:13 p.m.

Why does this submission (https://dmoj.ca/submission/3096627) using ArrayList and Collections.sort pass while this identical submission (https://dmoj.ca/submission/3096626) using a normal array fail? Aren't ArrayLists generally slower?

4

Plasmatic commented on Oct. 27, 2020, 11:05 p.m.

Looks like it might be due to a difference between sorting algorithms.

13

ross_cleary commented on March 6, 2020, 9:48 p.m.

This problem seems more like dp than graph theory.