dang_252's blog

By dang_252, history, 2 months ago,

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.

Details of my solution

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

• +52

By dang_252, history, 9 months ago,

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

• +49

By dang_252, history, 9 months ago,

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?