Solution to SGU #167 I-country

The problem description can be found in . It asks to find the connected blocks which meet the requirements and own the largest value. The requirement is that we can move only in two directions from arbitrary block to another. For example, the following one doesn’t meet the requirement because A needs to move in right, down and left directions to reach B.

A********
******
B********

Here I introduce one of the solutions. I have put my source code on GitHub (yuhc/sgu-solution).

Let f[i][j1][j2][dl][dr][k] be the maximum oils could be get when occupying k squares in the first i rows and columns j1 to j2. dl and dr mean the direction of the i-th row. dl == 0 when the left side in (i+1)-th row could expand towards left or right; dl == 1 when the left side in (i+1)-th row could expand towards only right. dr == 0 when the right side of the next row could expand towards both left and right, while dr == 1 when the right side of the next row could expand only towards left.

Consider the possible situations of state transition, there are only four cases:

(dl, dr) =     (0,0)       (0,1)       (1,0)        (1,1)

***         ****       ****        *******
*******     ****           ****        ***
next line
(dl, dr) =     (x,x)       (x,1)       (1,x)        (1,1)

x means either 0 or 1.

f[][][][][][] occupies totally 15*15*15*2*2*15^2*4 = 12150000 bytes = 11.6 MiB. But notice that we should also print the blocks we select. To find the path in the state transitions, we need record j1, j2, dl, dr from which we obtain f[i][j1][j2][dl][dr][k]. So extra 11.6 * 4 = 46.4 MiB is required.

However, this consumes too many memory resources and we had better find a less memory-consuming method to store j1, j2, dl, dr at the same time. Bit-compression is a good solution. Notice all the variables are smaller than 16, which means they can be represented by 4-bit integers. So we can use a 16-bit integer to represent these four integers: (j1<<12) + (j2<<8) + (dl<<4) + dr.

The implementation of this dynamic programming algorithm is not too long, but needs some time to think about. The source code is here:

/* SGU ID:  #167
* Type  :  Dynamic Programming
* Author:  Hangchen Yu
* Date  :  04/22/2015
*/
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <cmath>

using namespace std;

int  n, m, k;
int  a;
long f;
long pre;
long best = -1;
int  besti, bestj1, bestj2, bestdl, bestdr;

void update_next_row(int i, int j1, int j2, int dl, int dr, int s);

void dp() {
memset(f, -1, sizeof(f));
for (int i = 1; i <= n; i++)
for (int j1 = 1; j1 <= m; j1++)
for (int j2 = j1; j2 <= m; j2++)
for (int dl = 0; dl < 2; dl++)
for (int dr = 0; dr < 2; dr++) {
f[i][j1][j2][dl][dr][j2-j1+1] = a[i][j2] - a[i][j1-1];
for (int s = j2-j1+1; s <= k; s++)
if (f[i][j1][j2][dl][dr][s] >= 0) {
update_next_row(i, j1, j2, dl, dr, s);
if (s == k && f[i][j1][j2][dl][dr][k] > best) {
best = f[i][j1][j2][dl][dr][k];
besti = i; bestj1 = j1; bestj2 = j2; bestdl = dl; bestdr = dr;
}
}
}
}

void update_next_row(int i, int j1, int j2, int dl, int dr, int s) {
if (i == n) return;

int next_dl, next_dr;
for (int l = (dl==0?1:j1); l <= j2; l++)
for (int r = max(j1, l); r <= (dr==0?m:j2); r++) {
if (l == j1) next_dl = dl;
else next_dl = (l<j1 ? 0 : 1);
if (r == j2) next_dr = dr;
else next_dr = (r>j2 ? 0 : 1);

if (s+(r-l+1) <= k && f[i+1][l][r][next_dl][next_dr][s+(r-l+1)] < f[i][j1][j2][dl][dr][s] + a[i+1][r]-a[i+1][l-1]) {
f[i+1][l][r][next_dl][next_dr][s+(r-l+1)] = f[i][j1][j2][dl][dr][s] + a[i+1][r]-a[i+1][l-1];
pre[i+1][l][r][next_dl][next_dr][s+(r-l+1)] = (j1<<12) + (j2<<8) + (dl<<4) + dr;
}
}
}

void getPath(int i, int j1, int j2, int dl ,int dr, int s) {
if (i == 0 || s == 0) return;
for (int j = j1; j <= j2; j++)
printf("%d %d\n", i, j);

long t = pre[i][j1][j2][dl][dr][s];
getPath(i-1, t>>12, (t>>8)%16, (t>>4)%16, t%16, s-(j2-j1+1));
}

int main() {
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
scanf("%d", &a[i][j]);
a[i][j] += a[i][j-1];
}

dp();
printf("Oil : %ld\n", best);

getPath(besti, bestj1, bestj2, bestdl, bestdr, k);

return 0;
}