907 - Winterim Backpacking Trip

All about problems in Volume 9. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

907 - Winterim Backpacking Trip

Post by nymo » Fri Jul 06, 2007 8:53 am

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:

Post by mf » Fri Jul 06, 2007 8:57 am

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.

Post by nymo » Fri Jul 06, 2007 9:08 am

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 :D

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

Post by newkid » Mon Feb 02, 2009 9:48 am

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

Post by newkid » Mon Feb 02, 2009 10:32 am

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

Post by mf » Tue Feb 03, 2009 1:05 am

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

Post by shubhamgoyal » Fri Dec 09, 2011 7:33 am

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 :P 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

Post by helloneo » Fri Dec 09, 2011 9:28 am

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

anando_du
New poster
Posts: 10
Joined: Sun Mar 01, 2015 3:11 pm

Re: 907 - Winterim Backpacking Trip

Post by anando_du » Thu Jan 14, 2016 6:52 pm

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)

Post Reply

Return to “Volume 9 (900-999)”