## 907 - Winterim Backpacking Trip

Moderator: Board moderators

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

### 907 - Winterim Backpacking Trip

Hello there,
I think that it is a DP problem. But I can not figure out the recurrence, can someone please give me the idea to attack this/ this kind of problem? thanks in advance.
regards,
nymo

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Well probably there's a DP solution, but it's easier and faster to solve it with binary search.
Read misof's excellent analysis of a similar problem ("Turnpike" in that link)

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

### Thanks mf.

mf, thanks. Analysis done by misof looks excellent at the first glance, I will read it properly and try to solve this problem. Thanks again and it was a real fast reply

EDIT: I get ACC, thanks mf. I 've tried DP...
regards,
nymo

newkid
Learning poster
Posts: 73
Joined: Fri Dec 12, 2008 3:06 am

### Re: 907 - Winterim Backpacking Trip

Hi,
I am getting WA on this problem. Can anyone help.. Here is my code..
Thanks
*code edited.. Got TLE

Code: Select all

``````// Winterim Backpacking Trip
// UVA : 907

#include <stdio.h>
#include <string.h>

#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))

const int NN = 601;
const int MAXK = 301;

int sum[NN];
int dist[NN];

void init(int n) {
sum[0] = dist[0];
for (int i = 1; i <= n; i++)
sum[i] = sum[i-1] + dist[i];
}

int memo[NN][NN][MAXK];

int go(int i, int j, int k) {
if (memo[i][j][k] != -1) return memo[i][j][k];

int& ret = memo[i][j][k];

if (k == 0) {
ret = sum[j];
if (i)
ret -= sum[i-1];
return ret;
}

if (i == j) {
ret = dist[i];
return ret;
}

if (i > j) {
ret = (1<<30);
return ret;
}

ret = max(go(i + 1, j, k-1), dist[i]);
ret = min(ret, max(go(i, j-1, k-1), dist[j]));
ret = min(ret, max(dist[i] ,dist[j]) + go(i + 1, j - 1, k));

return ret;
}

int main() {
int n, k;

while (scanf("%d %d", &n, &k) == 2) {
for (int i = 0; i <= n; i++)
scanf("%d", &dist[i]);

init(n);
memset(memo, -1, sizeof(memo));

if (k > n + 1)
k = n + 1;
printf("%d\n", go(0, n, k));
}

return 0;
}``````
Last edited by newkid on Mon Feb 02, 2009 10:33 am, edited 1 time in total.
hmm..

newkid
Learning poster
Posts: 73
Joined: Fri Dec 12, 2008 3:06 am

### Re: 907 - Winterim Backpacking Trip

Found my mistake.. Got TLE now..
Any idea how to improve the runtime.. my solution uses O(n^2 x k)
hmm..

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

### Re: 907 - Winterim Backpacking Trip

With binary search the complexity would be only O(N log U), where U is range of coordinates (U < 2^32).

shubhamgoyal
New poster
Posts: 3
Joined: Tue May 03, 2011 5:34 am

### Re: 907 - Winterim Backpacking Trip

Hi,
Not sure if you managed to get AC till now or not but I too got TLE initially and here is my DP code which managed to get AC (the code is quite shabby Not following any variable naming or modularity conventions).

Code: Select all

``````import java.io.IOException;
import java.util.Scanner;

public class Main {
static int table[][];
static int a[];
static int b[];
static int sum[][];

public static void main(String args[])throws IOException {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
int N = sc.nextInt();
int K = sc.nextInt();
a = new int[N + 1];
b = new int[N + 1];
for(int i = 0; i < (N + 1); i ++) {
a[i] = sc.nextInt();
}
sum = new int[N + 1][N + 1];
table = new int[N + 1][K + 1];
for (int i = 0; i < (N + 1); i ++) {
for(int j = 0; j < (K + 1); j ++) {
table[i][j] = -1;
}
}
for(int i = N; i >= 0; i --) {
b[i] = a[N - i];
}
for(int i = 0; i < N + 1; i ++) {
int sum = 0;
for(int j = 0; j <= i; j ++) {
sum = sum + b[j];
}
table[i][0] = sum;
}
for(int i = 1; i < (K + 1); i ++) {
table[0][i] = b[0];
}
for(int i = 0; i < (N + 1); i ++) {
for(int j = i - 1; j >= 0; j --) {
int s = 0;
for(int k = i; k > j; k --) {
s = s + b[k];
}
sum[i][j] = s;
}
}
System.out.println(DP(N, K));
}
}

public static int DP(int n, int k) {
if (table[n][k] != -1)
return table[n][k];
else {
int min = Integer.MAX_VALUE/2;
for(int i = n - 1; i >= 0; i --) {
int temp = Math.max(sum[n][i], DP(i, k - 1));
if(temp < min)
min = temp;
}
table[n][k] = min;
return table[n][k];
}
}
}
``````

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

### Re: 907 - Winterim Backpacking Trip

We're not supposed to post a AC code here..