Algorithm-Engineering Homework 5 Solution

# The description provided for this problem:

The Serpent has led a C.H.I.M.E.R.A. project to build a new type of AI system, one with a series of "smart bricks" plugged together all in a row creating a super fast and super powerful AI with a goal of reaching artificial curiosity and creativity - to come up with better ways take over Mars!.

After a successful mission, Agent Ω has stolen a chain of these AI bricks and wants to take it apart to study it.  The problem is that once any brick is removed, its two neighbors both self-destruct.  As such, Agent Ω must determine ahead of time which bricks to break into and no two can be next to each other.

Agent Ω figures out how fast each smart brick is and wants to collect the fastest possible set of them.  You must help her choose which subset of bricks she will target such that she maximizes total brick speed (the sum of bricks chosen) without chosing any two that are neighbors.

Given a series of N smart bricks where brick i, in order, has speed Si , determine the maximum total speed that can be obtained.

Input Format

The first line provides N, the number of smart bricks in the row.
The second line has N values, separated by spaces, indicating the speed of each smart brick (S0 through SN-1 ).
Constraints

1 ≤ N ≤ 106
1 ≤ Si ≤ 1010
Output Format

A single number indicating the maximum total speed possible.

Example 0
Sample Input

5
2 10 1 3 10
Sample Output

20
Explanation

There are five smart bricks, with speeds of 2, 10, 1, 3, and 10, respectively.

If Agent Ω breaks into the second and fifth bricks, we will have a total speed of 20 (no other legal combination can produce more than 20).

Example 1
Sample Input

5
20 10 1 10 20
Sample Output

41
Explanation

There are five smart bricks, with speeds of 20, 10, 1, 10, and 20, respectively.

If Agent Ω breaks into the first, middle, and last bricks, we will have a total speed of 41 (no other legal combination can produce more than 41).





Question 2




Once Agent Ω was able to isolate a collection of smart bricks, her tech team were able to reverse engineer them and build more of their own.  The main limitation they had were total power consumption.  Each power source funnels into a chain of bricks and each brick consumes power proportional to its speed.  This means that when Agent Ω puts a chain together, she has a maximum amount of total speed that the power source can handle.  If she tries to build an AI that goes too fast, the power source will burn out.

There are N types of smart bricks the engineers now know how to make.  Each Brick i has speed Bi with K being the maximum total speed before the power source burns out.  Determine that maximum total speed that can be constructed in practice the the brick types that Agent Ω has access to.

For example, if there were types of bricks that had a speed of 9 and 12 respectively, and the power source could handle a maximum total speed of 31, you would be able to produce a maximum of 30 units by pressing two of the first brick type and one of the second brick type. If there were also a brick type of speed 1, you would be able to maximize the heat to a perfect 31, but no such brick type exists so no existing combination of bricks can get you all the way to 31.

Input Format

The first line contains T, the number of test cases.
Each test comprises two lines:
The first line contains two integers, N and K, representing the number of brick types and maximum power available, respectively.
The second line consists of space separated integers, B0 through BN-1, representing the speed of each brick type.
Constraints

1 ≤ T ≤ 10
1 ≤ N, K ≤ 2000
1 ≤ Bi ≤ 2000
Output Format

Output T lines, the maximum total speed can be produced in each test case without exceeding the total speed limit ( K ).

Example 0
Sample Input

3
3 12
1 6 9
5 9
3 4 4 4 8
4 11
5 7 8 9
Sample Output

12
9
10
Explanation

In the first test case, you can use two of the speed-6 bricks to achieve the maximum total speed of 12.
In the second test case, you can use three of the speed-3 bricks to hit the maximum total speed of 9.
In the third test case, there is no way to reach the speed limit of 11, so the closest you can come is 10, by using two of the speed-5 bricks.
Example 1
input01.txt

output01.txt

Example 2
input02.txt

output02.txt

Example 3
input05.txt

output05.txt

Example 4
input06.txt

output06.txt

Example 5
Sample Input

1
8 10
11 12 13 14 15 16 17 3
Sample Output

9
Explanation

The first seven brick types are useless since they immediately exceed the limit. The best we can do is use three of the last type for a total of 9.


Questions 3


Agent Ω has discovered that The Serpent has been funneling funds to C.H.I.M.E.R.A. to build a space warship, hidden above the Martian north pole.  The biggest challenge with stopping the ship is that it has A.I. torpedoes swarming around it, controlled by smart bricks.  But if Agent Ω can figure out which bricks they are, she'll be able to deactivate them remotely, making them drift off course.

After stealing the plans for the torpedos, Agent Ω figures out exactly how long the compartment is that stores the smart chain contoller.  She knows EXACTLY how long the chain is, but not what bricks make it up.  Given that different types of bricks have different lengths, can you determine how many possible series of bricks exist that are a given total length when chained together?

Given N types of bricks where brick type i has length Li , how many ways are there to lay them in a line with total length of exactly Ltotal ?  Note that order DOES matter.

Input Format

The first line of the input provides T, the total number of test cases.
The next T pairs of lines describe a single test case:
The first line in a test case privides the number of brick types (N) and the total target length ( Ltotal ).
The second line has N values, each position i indicating the length of brick brick type i.
Constraints

1 ≤ T ≤ 10
1 ≤ N ≤ 50
1 ≤ Ltotal ≤ 106
1 ≤ Li ≤ 106
Output Format

T lines, one per test case, each indicating the number of combinations possible to make a line of that total length. Some of the values are quite large, so mod your answer by 1000000009.

Example 0
Sample Input

2
2 5
1 2
2 7
1 3
Sample Output

8
9
Explanation

There are 2 test cases.  In the first we have 2 brick types, one of length 1 and the other of lenth 2.  We must make a chain of length five using these two types.  Let's call the first brick A and the second BB (since it's length two).  We can then figure out all of the possible brick layouts of length 5:

A A A A A
A A A BB
A A BB A
A BB A A
BB A A A
A BB BB
BB A BB
BB BB A
For a total of 8 different options.
For the second test case, there are again 2 types of bricks.  The first one is length 1 and the second is length 3.  We need them to have a total length of 7.  If we call the bricks A and CCC, the options this time are:

A A A A A A A
A A A A CCC
A A A CCC A
A A CCC A A
A CCC A A A
CCC A A A A
A CCC CCC
CCC A CCC
CCC CCC A
For a total of 9 different options.



Question 4


Once Agent Ω figured out how to shut down the torpedo A.I. system, she was ready to invade the C.H.I.M.E.R.A. warship and stop The Serpent once and for all.  After scanning the warship she figures out that she'll need a team of agents with her with a particular set of skills.  Can you help her decide which agents to take to make sure that the team is as small as possible, but all of the needed skills are represented?

NOTE: For this problem, your program must be guaranteed to output the correct answer (or timeout in the process of searching). If your program outputs an incorrect response for any test case, it will receive 0 credit on this problem (regardless of how many other test cases it passes). Timing out is allowed, however. Test cases on which you time out will not provide points, but will also not zero out points earned on test cases where your program returned the correct output. You do not need to complete all of the test cases within the time limit to get full credit (400 points counts as full credit for this problem - any points beyond that are extra credit). Note also that the test cases get substantially more difficult as you go into the extra credit range.

Input Format

The first line has two values,  N and K.

N represents the number of candidate agents for the mission, and K  is the number of distinct skills that (combined) the candidates must possess.

The second line has K words on it, listing the specific skills that are required.

The next N pairs of lines each provide information about a single person.

The first line in the pair for person i indicates the number of skills that person knows (Pi ), and the second line lists those Pi  specific skills.

Constraints

1 ≤ N ≤ 200
1 ≤ K ≤ 200
0 ≤ Pi  ≤ K

Output Format

You must output a single value indicating the fewest people that you can choose for the mission while having all of the needed skills rerpesented.

Example 0
Sample Input

5 6
Botany Neuroscience ArtificialLife Batteries Metals InformationTheory
3
Botany Neuroscience ArtificialLife
2
Botany Batteries
1
Botany
4
Botany Batteries Metals InformationTheory
3
Neuroscience Batteries InformationTheory
Sample Output

2
Explanation

Five people are available to cover six required skills.

Only two of the people are needed. The first person (who provides Botany, Neuroscience, and ArtificialLife) and the fourth person (who provides Batteries, Metals, and InformationTheory, as well as duplicating Botany). No smaller answer is possible since no single person has all six skills.

Example 1
Sample Input

10 8
Plastics Fermentation Ceramics InformationTheory CloudComputing EnvironmentalScience Biometrics PlasmaPhysics
4
Plastics Fermentation Ceramics InformationTheory
4
Plastics Fermentation CloudComputing EnvironmentalScience
4
Plastics Ceramics Biometrics PlasmaPhysics
4
Plastics Fermentation Ceramics CloudComputing
4
Plastics Fermentation Ceramics EnvironmentalScience
4
Fermentation Ceramics InformationTheory CloudComputing
4
Fermentation InformationTheory EnvironmentalScience PlasmaPhysics
4
Ceramics InformationTheory CloudComputing Biometrics
4
InformationTheory CloudComputing Biometrics PlasmaPhysics
4
InformationTheory CloudComputing EnvironmentalScience PlasmaPhysics
Sample Output

2
Explanation

10 People are available to cover eight skills.

It is possible to use only two people: The fifth person knows Plastics, Fermentation, Ceramics, and EnvironmentalScience. The ninth person knows InformationTheory, CloudComputing, Biometrics, and PlasmaPhysics. No tasks are duplicated across both selected people.