10664 - Luggage

[mf]

[quote="ImLazy"]By the way, what means "1

[Kallol]

Would someone plz explain me the algorithm ?
What is the algorithm for partitioning an array into two or more parts according to the conditions like one we have here?

For parttioning into two parts I can imagine a way ... that is to convert the number to binary representation and then check all possible combination ... but it is exponential in order :-s ....Whats goin to be a better algorithm ?

[asif_rahman0]

.......For parttioning into two parts I can imagine a way .......Whats goin to be a better algorithm ?

But i think 0/1 knapsack. You can try with it. From ranklist its not better
algorithm. Mine is 0.00.248 with memory (10152). So lowest.

[Marin]

Brute force can handle it easily in 0.01s.

[george3456]

This piece of code is accepted.....
but I am sure it shows wrong output for this input:

3 3 3 3 2 2 2 2 2 2 2 2 2

output should be: YES
but this code shows : NO and however ACCEPTED. WHY???

Code: Select all

#include<stdio.h>
#include<stdlib.h>

int comp(void const * a, void const * b)
{
	return ( *(int*) b - *(int*)a);
}

int main()
{
	int tcase;

	scanf("%d",&tcase);

	while(tcase--)
	{
		int a[100],i=0;
		int sum = 0;

		while(scanf("%d",&a[i]))
		{
			sum += a[i++];
			if((getchar())=='\n') break;
		}

		qsort(a,i,sizeof(int),comp);
		
		int n = i,tot,val,j,flag;

		if(sum % 2==0)
		{
	         In this section I just checked if the 
				}

			if(flag==1)
				printf("YES\n");
			else printf("NO\n");

		}
		else printf("NO\n");
		
		//for(i=0;i<n;i++)
			//printf("%d ",a[i]);

	}

	return 0;

}

[mostafa_angel]

can anybody help me !?
I got WA but my programme in all of my testcases are true !
my code :

Code: Select all

#include <iostream>
#include <algorithm>
#include <string>
#include <sstream>
using namespace std;

bool dp[201];
int a[201];

int main()
{
	int n;
	string s;
	stringstream str;
	cin >> n;
	getline(cin , s);
	for(int pp =0 ; pp < n ; pp++)
	{
		fill(a, a+201 , 0);
		getline(cin , s);
		str.str(s);
		int tmp;
		long long int total = 0;
		int ind = 0;
		while(str >> tmp)
		{
			a[ind] = tmp;
			ind++;
			total+=tmp;
		}
		
		if(total%2 == 1)
		{
			cout << "NO" << endl;
			continue;
		}
		
		int final = total/2;
		fill(dp , dp+201 , false);
		sort(a , a+ind );
		dp[0] = true;
		for(int i = 0 ; i < ind ; i++)
		{
			for(int j = final ; j>= a[i] ; j--)
			{
				if(j-a[i] >= 0 && dp[j-a[i]] == true)
					dp[j] = true;
			}
		}
		if(dp[final])
			cout << "YES" << endl;
		else
			cout << "NO" << endl;

		str.clear();
	}

	return 0;
}