dang_252's blog

By dang_252, history, 3 years ago, In English

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.

Full text and comments »

  • Vote: I like it
  • +52
  • Vote: I do not like it

By dang_252, history, 4 years ago, In English

Let's read this: 97352553.

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

Full text and comments »

  • Vote: I like it
  • +49
  • Vote: I do not like it

By dang_252, history, 4 years ago, In English

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.

Full text and comments »

  • Vote: I like it
  • +29
  • Vote: I do not like it