Given a $$$N \times N$$$ table, each cell $$$(x,y)$$$ has a value $$$a[x][y]$$$.

From cell $$$(x, y)$$$ we can jump to cell $$$(x_1,y_1)$$$ if both of these satisfy:

• $$$a[x_1][y_1] > a[x][y]$$$

• $$$($$$$$$|x - x_1|=1$$$ and $$$|y - y_1| > 1)$$$ or $$$($$$$$$|x - x_1|>1$$$ and $$$|y - y_1| =1)$$$.

Find the longest path (number of jumps) we can make, if we start at cell $$$(X_0, Y_0)$$$.

Input is $$$N, X_0, Y_0$$$ and the array $$$a$$$. $$$(N \leq 1500, a[i][j] \leq 10^6)$$$

Example:

4

1 1

1 2 3 4

2 3 4 5

3 4 5 6

4 5 6 7

Output: $$$3$$$ (The path is $$$(1,1) \Rightarrow (2, 3) \Rightarrow (4,2) \Rightarrow (3,4)$$$).

My current solution works in about $$$O(4 * N * N * log(N) + 10^6 * log(10^6))$$$, and it didn't pass the time limit in $$$1$$$ second.

Please show me a faster (possibly fastest) solution or some improvements that I can make to my algorithm. Thank so much <3 <3.

Let's read this: 97352553.

Look at those non-sense ~ sophisticated if and variable declaration. I wonder what is going on inside their head :<

Recently I came across a problem:

Given an undirected graph $$$n$$$ vertices with $$$m$$$ weighted edges. Find a simple cycle with the value "Max weighted edge" + "Min weighted edge" maximized and print that value.

So my algorithm is:

• Build a Maximum Spanning Tree

• With an edge $$$u-v$$$ weight $$$w$$$ that is not in the MST, take max answer $$$w$$$ + Max weighted edge on that path $$$u-v$$$ on the MST.

In the second point, I could not prove if "Max weighted edge on that path $$$u-v$$$ on the MST" is maximized. What if there is another path from $$$u$$$ to $$$v$$$ with "Max weighted edge" larger.

I tried to prove that the Maximum Spanning Tree guarantees that the path $$$u-v$$$ have "max weighted edge" maximized but it turned out quite wrong in my mind as we can use edges that is not belong to the current MaxST to lead $$$u$$$ to a large edge then lead to $$$v$$$.

So how my algorithm actually guarantees with an edge $$$u-v$$$ weight $$$w$$$ that is not in the MST, the "Max weighted edge on that path $$$u-v$$$ on the MST" is the maximum "Max weight edge" path from $$$u$$$ to $$$v$$$?

How to prove that from $$$u$$$ to $$$v$$$ there is not any other path that have "Max weighted edge" larger than the one in the MST which will make the answer better?

Thanks in advanced.