Hi cf,

I'm trying to solve this problem:

You have a budget B and you want to form a team of 11 players such as it has:

• 1 goalkeeper
• At least 3 defenders and at most 5.
• At least 3 midfielders and at most 5.
• At least 1 attackers and at most 3.

There's a list of players (max 50) to choose from, with each player has a:

• type: goalkeeper, defender, midfilder or attacker
• cost: price of the player
• points: represent how good the player is

What is the maximum of total points that we can get from a team that fulfill the conditions without exceeding the budget B

it is guaranteed that the maximum number of players per type in the input doesn't ecxeed 15.

Example of input:

20
Defender 22 7
Attacker 40 9
...

Constraints

N (nomber of input players) <= 50

Cost of a player is an integer <= 10

budget <= 100

Each type in the input will not exceed 15 (ex: at most 15 defender)

All I can think of is recurssive dp with bitmask dp(chossenGkmask, chossenDefmask, chosseMidmask, chossenAttmask, totalCoast)

Is there a better approach ?

Hello cf community,

I use memoization ( recurssive dp ) to solve dynamic programming, however it's not effecient in some cases, so I'm willing to change to bottom up dp or tabulaire dp, however I find it a bit difficult to understand, so is there anyone who was able to switch from one to another so he can share the steps to follow to switch between the two, something like:

I solved a dp problem using memoization follow these steps to transform it to a tabulaire dp.

Thanks.

I'm trying to solve this problem 514C, in simple terms you are given n strings and m queries, each query consist of a string s, can you find an equal string in the given n strings by changing only one character in s, (all strings consist only of 'a','b', and 'c')

My solution is brute force based: for each query change each character and try to find if it exist in the given strings using a HashSet, but I got a WA in pretest 6 can any one tell me what I'm doing wrong.

submission

This solution is O(n) right? is it because java i/o ?

submission

Hi everyone.

I was trying to solve small input for this problem using recursive dp.

But it gives a strange runtime error when n >= 180000.

this my code

Any helps.

The problem look like this : we have n object each object have a weight .

We want to create 2 groups of these objects so the number of objects on the two groups must not differ by more than 1 and the total weight of the objects on each group should be as nearly equal as possible.

examples :

n = 4 : 1 2 3 4 => ans : 5 5

n = 4 : 1 2 3 11111 => ans : 5 11112

n = 3 : 100 90 200 => ans :190 200

my code works fine for small input how ever it gives negative values for large input (n >= 25 ) . My code

You should now that n<=100 and the sum of weights is <= 1e6 .

I just solved this dp problem , i compared my code to an accepted code by trying random test cases , and it gives correct results , how ever it gives MLE in the onligne judge ( only 32M of memory )

So my question is how to prevent this ??

My code

Problem statement :

A tug of war is to be arranged at the local office picnic. For the tug of war, the picnickers must be divided into two teams. Each person must be on one team or the other; the number of people on the two teams must not differ by more than 1; the total weight of the people on each team should be as nearly equal as possible.

Input

Input starts with an integer T (≤ 100), denoting the number of test cases.

The first line of each case is a blank line. The next line of input contains an integer n (2 ≤ n ≤ 100), the number of people at the picnic. n lines follow. The first line gives the weight of person 1; the second the weight of person 2; and so on. Each weight is an integer between 1 and 100000. The summation of all the weights of the people in a case will not exceed 100000.

Output

For each case, print the case number and the total number weights of the people in two teams. If the weights differ, print the smaller weight first.

Sample Input

2

3 100 90 200

4 10 15 17 20

Output for Sample Input

Case 1: 190 200 Case 2: 30 32

I just solved this problem in uva.onlignejudge 10664 a classical dp problem ( you have n weights and you want to find a way to distribute these weights equally between 2 people ) so you only need a simple dp to find (total sum of weights ) / 2 using given weights .

but what if we decided to shares these weight between k people how to solve that ? do we have to keep track on the chosen weights ??

I was trying to solve K-Tree 431C But i'am getting WA in protest 5 , the input is 0 , this is my 12482418 any helps ??

If any one could explain or give me a good tutorial (c++) to understand the approach of dfs . thanks.