CareerCup

#include<iostream>
using namespace std;

int main(){
	int t;
	cin>>t;

	while(t--){
		int n;
		cin>>n;

		int arr[n+1];

		for(int i=1;i<=n;i++)
			cin>>arr[i];

		int dp[1005][1005];
		int dp1[1005][1005];

		for(int i=0;i<=1000;i++){
			for(int j=0;j<=1000;j++)
				dp[i][j]=0;
		}


		

		dp[0][0]=1;



		for(int i=1;i<=n;i++){
			for(int j=0;j<=1000;j++){
				for(int k=0;k<=1000;k++){
					if(j>=arr[i]){
						if(dp[j-arr[i]][k]){
							dp1[j][k]=1;
						}
					}
					if(k>=arr[i]){
						if(dp[j][k-arr[i]]){
							dp1[j][k]=1;
						}
					}
					if(dp[j][k]){
						dp1[j][k]=1;
					}
				}
			}

			for(int j=0;j<=1000;j++){
				for(int k=0;k<=1000;k++){
					dp[j][k]=dp1[j][k];
					dp1[j][k]=0;
				}
			}
		}

		int ans=0;

		for(int i=1;i<=1000;i++){
			if(dp[i][i]){
				ans=i;
			}
		}
		

		cout<<ans<<endl;


	}
}

#include <bits/stdc++.h>
using namespace std;
int dp[1000][1000];
int A[1000];
int mini,ans,tot;

int ABS(int x)
{
    if(x<0)
        x=-1*x;
    return x;
}

int MAX(int a,int b)
{
    if(a>b)
        return a;
    return b;
}

int solve(int i,int curr,int n)
{
    if(i==n)
    {
        int x=ABS(tot-2*curr);
        if(x<mini)
        {
            mini=x;
            ans=MAX(curr,tot-curr);
        }
        return 1;
    }
    if(dp[i][curr]!=-1)
        return dp[i][curr];
    return dp[i][curr]=solve(i+1,curr+A[i],n)+solve(i+1,curr,n);
}

int main()
{
	int n;
    cin>>n;
    mini=INT_MAX;
    ans=tot=0;
    for(int i=0;i<n;i++){
        cin>>A[i];
        tot+=A[i];
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
            dp[i][j]=-1;
    }
    solve(0,0,n);
    cout<<ans;
}

Maybe This will help

#include "stdafx.h"
#include "stdio.h"

static int bar_data[50];
static int max_length;
static int num_of_bars;
static int total_length;

int FindSum(int length, char* IsUsed)
{
	int i;

	printf("\n FindSum: [%d] ", length);

	for (i = 0; i < num_of_bars; i++)
	{
		printf("%d ", IsUsed[i]);
	}
	printf("\n");

#if 0
	for (i = num_of_bars - 1; i >= 0; i--)
	{
		if ((IsUsed[i] == 0) && ((length - bar_data[i]) == 0))
		{
			IsUsed[i] = 1;
			return 1;
		}
	}
#endif

	for (i = num_of_bars - 1; i >= 0; i--)
	{
		if ((IsUsed[i] == 0) && ((length - bar_data[i]) >= 0))
		{
			IsUsed[i] = 1;
			length -= bar_data[i];

			if (length == 0)
			{
				return 1;
			}

			if (FindSum(length, IsUsed) == 0)
			{
				IsUsed[i] = 0;
			}
			else
			{
				return 1;
			}
		}
	}
	return 0;
}

int CalculateHeight()
{
	int i = 0, j = 0, h1 = 0, h2 = 0;

	int max_height = 0;

	char IsUsed[51];

	for (i = num_of_bars - 1; i > 0; i--)
	{
		if (bar_data[i] > total_length)
		{
			j++;
			total_length -= bar_data[i];
		}
	}
	max_height = total_length / 2;
	num_of_bars -= j;

	j = 0;

	for (i = max_height; i > 1; i--)
	{
		memset(IsUsed, '\0', sizeof(IsUsed));

		h1 = FindSum(i, IsUsed);
		if (h1)
			h2 = FindSum(i, IsUsed);

		if (h1 & h2)
		{
			j = i;
			break;
		}
	}

	return j;
}


int main()
{
	int i;

	printf("\n Enter Number of Bars: ");
	scanf_s("%d", &num_of_bars);

	printf("\n Enter Bar Code Length's: ");
	total_length = 0;

	for (i = 0; i < num_of_bars; i++)
	{
		scanf_s("%d", &bar_data[i]);
		total_length += bar_data[i];
	}

	printf("\n Max Height: %d", CalculateHeight());

	getchar();

	return 0;
}

O(S^2 * N) time, where S is sum of the input pipes' lengths, and N is number of the pipes.

#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;

void LargestPipes(vector<int> const &a, vector<int> &p1, vector<int> &p2, vector<int> &p1_out,
	vector<int> &p2_out, int16_t &len_out, unordered_set<uint64_t> &memo,
	int16_t len1 = 0, int16_t len2 = 0, int idx = 0)
{
	if (idx < 0 ||
		idx > a.size())
	{
		return;
	}
	if (len1 == len2 &&
		len1 > len_out)
	{
		len_out = len1;
		p1_out = p1;
		p2_out = p2;
	}
	if (idx == a.size()) {
		return;
	}

	uint64_t memo_key = (static_cast<uint64_t>(len1) << 48) | (static_cast<uint64_t>(len2) << 32) | idx;
	if (memo.find(memo_key) != memo.end()) {
		return;
	}
	memo.insert(memo_key);

	p1.push_back(a[idx]);
	LargestPipes(a, p1, p2, p1_out, p2_out, len_out, memo, len1 + a[idx], len2, idx + 1);
	p1.pop_back();

	p2.push_back(a[idx]);
	LargestPipes(a, p1, p2, p1_out, p2_out, len_out, memo, len1, len2 + a[idx], idx + 1);
	p2.pop_back();

	LargestPipes(a, p1, p2, p1_out, p2_out, len_out, memo, len1, len2, idx + 1);
}

int main()
{
	vector<int> p1, p2, p1_out, p2_out;
	int16_t len_out;
	unordered_set<uint64_t> memo;
	LargestPipes({1, 2, 3, 4, 6}, p1, p2, p1_out, p2_out, len_out, memo);

	for (int n : p1_out) {
		cout << n << ", ";
	}
	cout << "\n";
	for (int n : p2_out) {
		cout << n << ", ";
	}
	cout << "\n";
}

can you please tell the idea behind this code?
i don't understand the question properly.

@vmkaabhirami. I'm also not sure if I understand the question correctly. I assume that out of the set of pipes I should build two pipes (by connecting them) as long as possible. Also, I assume that the lengths of the two long pipes should be equal.

@Alex can you explain the logic you used, I am unable to get it

is this samsung's professional or above level test question

This question had been asked recently in samsung r&d test. ! NoName solution will not pass all test case(s).

#include <bits/stdc++.h>
using namespace std;
int dp[1000][1000];
int A[1000];
int mini,ans,tot;

int ABS(int x)
{
    if(x<0)
        x=-1*x;
    return x;
}

int MAX(int a,int b)
{
    if(a>b)
        return a;
    return b;
}

int solve(int i,int curr,int n)
{
    if(i==n)
    {
        int x=ABS(tot-2*curr);
        if(x<mini)
        {
            mini=x;
            ans=MAX(curr,tot-curr);
        }
        return 1;
    }
    if(dp[i][curr]!=-1)
        return dp[i][curr];
    return dp[i][curr]=solve(i+1,curr+A[i],n)+solve(i+1,curr,n);
}

int main()
{
	int n;
    cin>>n;
    mini=INT_MAX;
    ans=tot=0;
    for(int i=0;i<n;i++){
        cin>>A[i];
        tot+=A[i];
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
            dp[i][j]=-1;
    }
    solve(0,0,n);
    cout<<ans;
}

Maybe this will help.
Time Complexity:- O(N*S)