Nov 252008
 

ZJU 3060 – Evil Game

You are given an M * N grids (1 <= M, N <= 100). You start from the most left-top cell (0, 0) and want to get to the most right-bottom cell (M-1, N-1). At any time, you can only move to left, right or down. Each cell (mij) contains an integer between -100 and 100 (inclusive) denoting the value that you will received when you visit the corresponding cell, in such manners:

  • mij = mij for the first visit to cell (i, j)
  • mij = -|mij| for each next visit to cell (i, j)

Calculate the maximum value that can be achieved to reach cell (M-1, N-1)!


There is an easier (and more popular) version, where you can only move to right or down, that can be solved by dynamic programming. You might want to try the easier version first if you’re new to dynamic programming.

To solve this problem, define a dynamic programming state as f(r, b): the maximum value that can be achieved at row r when you want to move down at column b (b is the last column that you visit at row r). Then f(M-1, N-1) is the value that you want to find. To solve f(r, b), you need to try all a from 0 to N-1 as the first visited column when you arrive at row r, in which you can use f(r-1, a) to get the optimal value for the previous state. Example of an optimal move at row r which start from column a and end at column b is shown in the figure below.

dynamic programming

L(b) and R(a) are the “expansion” moves where the cells are being visited twice, except the last cells (the end/turning point).

Then the state can be written as:
dynamic programming
warning: the above formula might contains some minor mistakes.

S(a, b) is the partial sum of each value at row r from column a to column b.
T(a, b) is the partial sum of each absolute value at row r from column a to column b.
L(k) is the maximum value that can be achieved at row r by moving left from column k and return back to column k.
R(k) is the maximum value that can be achieved at row r by moving right form column k and return back to column k.

You should notice the exception in the above formula for the first row (r = 0), i.e. you should start only from a = 0 instead of trying all a from 0 to N-1.

S, T, L and R for each r can be precalculated, so the overall time-complexity for this solution is O(M*N2), or O(N3) when N = M.

  5 Responses to “ZJU 3060 – Evil Game”

  1. Halo Pak Su. Lecture Math nya pas di pelatnas toki sangat memukau Pak…

    Btw, saya boleh minta link2 soal2 DP yg novice nggak,, mw belajar DP nih..

    Thx.

  2. Halo den,

    hee…. apanya yang memukau nih? 😀

    Soal-soal DP banyak bisa dicari di arsip TopCoder, tinggal disesuaikan tingkat kesulitannya. note: sepertinya kamu perlu login dulu buat buka arsipnya.

    Atau ke website steven halim yang bagian dynamic programming

  3. Hal2 math yg diajarkan wkt itu benar2 berguna Pak,, 😛 saya aja waktu itu baru tau ada STL nya GCD…

    Ok, thx Pak linkny!
    taun ini bkin soal bonus juga ya pak di bnpchs 😛 😛 !

  4. hohoho.. 😀

    Oh iya, kabarin ke yang lain ya ttg BNPC-HS. Kemarin pas di Bandung saya lupa kasi tau… 😀

  5. ditunggu pak write-up tentang bnpchs 😛

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)