907 - Winterim Backpacking Trip

[nymo]

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.

[mf]

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]

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...

[newkid]

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;
}

[newkid]

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

[mf]

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

[shubhamgoyal]

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]

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

[anando_du]

well I've solved this using dp ... simple recursive formula ...
btw thanks to mf for suggesting BS solution

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)