10819 - Trouble of 13-Dots

mratan16 · Post by **mratan16** » Wed Jul 23, 2014 7:13 am

Thank you for the advice but I honestly have no idea on how to code that..

I do not understand how to set keep[1][901] to 2 and keep[1][902] to 0.

Can you please expound?

Thanks

lighted · Post by **lighted** » Wed Jul 23, 2014 12:25 pm

I can tell you my dp algorithm.

I used one int array of length 10201 let's say cost[10201], where cost is max favour we can get with exactly price i
Set array cost to 0, and cost[0] = 1; We have only one possible price - its 0;

Now we will build new possible prices:

For every price and favour do cycle from i = m + 200 down to price and check:

if we already have price cost (if we have it will be greater than zero) then using current price we can get (or update) price cost

if (cost > 0 && cost + favour > cost) cost = cost + favour;

I do cycle in decreasing order to prevent using one clothes several times.
I look from biggest price i builded before down to smallest price (and make new price with current one).

At last we check array cost for maximal favour.
Do cycle from i = 0 to m + 200 and check:

if (i <= m || i > 2000)
if (cost > MAX) MAX = cost;

Answer will be MAX - 1, because i added to cost[0] = 1 at the beginning to make it greater than 0 and mark that we have it.

I check extra prices from m + 1 to m + 200 because if it is greater than 2000 than it is also possible price.

Hope it is not confusing

mratan16 · Post by **mratan16** » Wed Jul 23, 2014 12:43 pm

I took your suggestion and attempted to do it. It still shows the wrong answer. Can you please help?

Code: Select all

Removed

Thanks

lighted · Post by **lighted** » Wed Jul 23, 2014 1:48 pm

I sent you PM.

just_yousef · Post by **just_yousef** » Wed Jul 30, 2014 7:15 pm

My Code Satisfies All Test cases Given in the post.
But still Gives WA.
Please Help !! :/

Code: Select all

#include <bits/stdc++.h>
using namespace std;

struct node {
	int p, f;
	bool operator<(const node &a) const {
		return a.p > p;
	}
} Q[101];

int n, m;
int dp[101][11001];
int solve(int id, int x, bool f) {
	if (x > 2000 && !f)
		x -= 200, f = 1;
	if (x > m)
		return -1e9;
	if (id == n)
		return 0;
	int &res = dp[id][x];
	if (res != -1)
		return res;
	res = max(solve(id + 1, x, f), solve(id + 1, x + Q[id].p, f) + Q[id].f);
	return res;

}
int main() {
	//freopen("a.in", "r", stdin);
	while (scanf("%d%d", &m, &n) > 0) {
		for (int i = 0; i < n; ++i)
			scanf("%d%d", &Q[i].p, &Q[i].f);
		memset(dp, -1, sizeof dp);
		sort(Q, Q + n);
		printf("%d", solve(0, 0, 0));
	}
	return 0;
}

brianfry713 · Post by **brianfry713** » Wed Jul 30, 2014 7:50 pm

Print a newline char at the end of each line.

just_yousef · Post by **just_yousef** » Wed Jul 30, 2014 8:39 pm

brianfry713 wrote:Print a newline char at the end of each line.

I tried that too but still WA :/

brianfry713 · Post by **brianfry713** » Wed Jul 30, 2014 9:28 pm

It looks like you figured it out.

lighted · Post by **lighted** » Wed Jul 30, 2014 9:41 pm

just_yousef you got accepted it two hours ago, how can it be still WA?

see uhunt http://uhunt.felix-halim.net/id/202166

just_yousef · Post by **just_yousef** » Wed Jul 30, 2014 9:47 pm

lighted wrote:just_yousef you got accepted it two hours ago, how can it be still WA?
see uhunt http://uhunt.felix-halim.net/id/202166

I used Different method for the trick in this knapsack question, But this specific code is Giving WA!!

lighted · Post by **lighted** » Thu Jul 31, 2014 2:32 am

just_yousef your code avove gives wrong output for one case of Brianfry's test.

brianfry713 wrote:Input:

Code: Select all

AC output:

Code: Select all

Your output

Code: Select all

Acc output

Code: Select all

..
49
34
18
..

Your output

Code: Select all

..
49
35
18
..

just_yousef · Post by **just_yousef** » Thu Jul 31, 2014 2:36 pm

Solved,, Thank you

raj · Post by **raj** » Wed Sep 03, 2014 5:40 pm

Is this problem solvable with top-bottom techniques? If not then why?

brianfry713 · Post by **brianfry713** » Thu Sep 04, 2014 1:07 am

raj wrote:Is this problem solvable with top-bottom techniques?

yes

raj · Post by **raj** » Fri Sep 05, 2014 12:10 am

Need Help.

Getting Time Limit Exceeded

Code: Select all

import java.io.*;
import java.util.*;
public class Main{
	public static BufferedReader k;
	public static int dp[][];
	public static int[] weight,value;
	public static int budget;
	

	
	public static int knapSack(int i,int w){
			
			if(i==weight.length){
				return 0;
			}
			else{
				int max1 = 0,max2 = 0;
				if(dp[i][w]!=-1) return dp[i][w];
				
				if(w+weight[i]>2000){
					if(w+weight[i]-200<=budget){
						max1 = value[i]+knapSack(i+1,w+weight[i]);
						max2 = knapSack(i+1,w);
					}
					else{
						max2 = knapSack(i+1,w);
					}
				}
				else{
					if(w+weight[i]<=budget){
						max1 = value[i]+knapSack(i+1,w+weight[i]);
						max2 = knapSack(i+1,w);
					}
					else{
						max2 = knapSack(i+1,w);
					}
				}
				
				return dp[i][w] = Math.max(max1, max2);
				
				
			}
			
			
	}
	
	
	public static void fill(int [][] array, int element) {
	    for(int[] subarray : array) {
	        Arrays.fill(subarray, element);
	    }
	}
	

	
	public static void main(String [] args)throws IOException{
		k = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter z = new PrintWriter(System.out);
		
		String line;
		while((line = read())!=null){
			StringTokenizer s = new StringTokenizer(line);
			budget = Int(s.nextToken());
			int n = Int(s.nextToken());
			weight = new int[n];
			value = new int[n];
			if(n!=0){
				int total = 0;
				for(int c = 0;c<n;c++){
					StringTokenizer ss = new StringTokenizer(read());
					weight[c] = Int(ss.nextToken());
					value[c] = Int(ss.nextToken());
					total += weight[c];
				}
				
				dp = new int[n][total+500];
				fill(dp,-1);
				
				knapSack(0,0);
				z.println(dp[0][0]);
			}
			else{
				z.println(0);
			}
		}
		z.flush();
	}
	
	
	
	
	
	
	
	
	
	
	
	
	public static int Int(String line){
		return Integer.valueOf(line);
	}
	
	
	
	
	public static String read() throws IOException{
		return k.readLine();
	}
}

UVa OJ Board

10819 - Trouble of 13-Dots

Re: 10819 - Trouble of 13-Dots

Re: 10819 - Trouble of 13-Dots

Re: 10819 - Trouble of 13-Dots

Re: 10819 - Trouble of 13-Dots

Re: 10819 - Trouble of 13-Dots

Re: 10819 - Trouble of 13-Dots

Re: 10819 - Trouble of 13-Dots

Re: 10819 - Trouble of 13-Dots

Re: 10819 - Trouble of 13-Dots

Re: 10819 - Trouble of 13-Dots

Re: 10819 - Trouble of 13-Dots

Re: 10819 - Trouble of 13-Dots

Re: 10819 - Trouble of 13-Dots

Re: 10819 - Trouble of 13-Dots

TLE: 10819 - Trouble of 13-Dots