Algorithm-Engineering Homework 3 Solution

All questions within this homework assignment were included in one file (each question is labeled as Q1, Q2, Q3, etc.).

# The following are the project descriptions that were provided:

# Q1)
Now that Ω has dectrypted many of The Goat's messages, she needs to identify which of his plans need to be stopped!  Given a list of N evil plans, pick out the top k most important plans to send the agents to foil!

Input Format

The first line has two values N and k. N is the number of plans in the decrypted messages, and k is the number of those that she can foil.

The next N lines each indicate the importance of one plan (unsorted).

Constraints

1 ≤ N ≤ 107
1 ≤ K ≤ 1000
1 ≤ plan importance ≤ 109
Output Format

 K values, indicating the K most important plans, in order (each on a new line).

Example 0
Sample Input

5 2
6
7
11
6
17
Sample Output

17
11
Explanation

There are five plan, and we need to identify the most important two. They are size 17 and size 11.

Example 1
Sample Input

10 3
7
3
19
5
3
11
13
10
3
6
Sample Output

19 
13
11
<br />
<br />
<br />
<br />
<br />
# Q2)
The Martian Secret Service has m agents available to shut down The Goat's evil plans.  Of course, they are a budget-consious agency and they want to stop C.H.I.M.E.R.A. as cost-effectively as possible.

Each mission has a base cost to send an agent on.  Each agent is willing to do one mission at that cost, but if they need to go on more than one mission they start charging more.  The second mission is twice the base cost, the third mission is triple and so on, such that the kth mission is k-times the base cost.

Given m agents and n missions, and a base cost of Ci for each mission i, find and print the minimum total cost for all of the missions to be completed.

Note: missions can be assigned in ANY ORDER.

Input Format

The first line contains two space-separated integers describing the respective values of n and m.
The second line contains n space-separated positive integers describing the respective values of c0, c1, ..., cn-1
Constraints

1 ≤ n, m ≤ 100
1 ≤ Ci ≤ 106
answer < 231
0 ≤ i < n
Output Format

 Print the total cost for all missions.

Example 0
Sample Input

3 3
2 5 6
Sample Output

13
Explanation

There are three missions and three agents. Since each agent can complete one mission, there is only a mulitple of × 1 for each. The total cost is:

(2 × 1) + (5 × 1) + (6 × 1) = 13

Example 1
Sample Input

7 3
6 1 28 10 15 3 21
Sample Output

105
Explanation

There are seven missions and three agents to complete them.

The agents can complete, in order:

first agent: 28, 10, and 1
second agent: 21 and 6
third agent: 15 and 3
The first agent would cost 28 + 10×2 + 1×3 = 51

The second agent would cost 21 + 6×2 = 33

The third agent would cost 15 + 3×2 = 21

... for a grant total of 51 + 33 + 21 = 105.

<br />
<br />
<br />
<br />
<br />
# Q3)
On one of Agent Ω's missions, she foiled a C.H.I.M.E.R.A. operative modifying files on a computer in a secret government research laboratory.  The operative excaped, but Ω was able to determine which files he had modified and saw that in most cases there were only small changes.  They were genomes of customized animals being engineered to live on Mars.

In analyzing the genomes, Ω needed to check if any genes were moved around.  Fortunately it looked like the sabatour made only a quick change, either reversing the order of a whole sequence of genes (so that they are in the reverse order of what they were) or by swapping two individual genes. Can you find a single reverse or swap operation that will restore the animal genes to their original order?

(But seriously, who would engineer a Racoon to live in space?)

Input Format

The file line contains a value N, indicating how many genes there are in the genome for this animal.

The next N values, on the next line, indicate the IDs of each gene.  Note that originally all IDs were in correct sorted order.

Constraints

2 ≤ N ≤ 105
0 ≤ file id ≤ 106
Output Format

If the array is already sorted or can be fixed with a single "swap" or "reverse" operation, write "yes" on the first line. Otherwise write "no" on the first line.

If a single operation needs to be performed, begin the second line with "swap" or "reverse" indicating either the two gene positions to swap -or- the first and last positions that need to all be reversed. (if both are possible, use the "swap" option)

NOTE: You should assume the first position is 1 (not 0) for the purposes of this question.

Example 1
Sample Input

2
4 2
Sample Output

yes
swap 1 2
Explanation

The two genes have IDs 4 and 2. These are out of order, but can clearly be fixed by swapping the two positions. As such we print "yes" since it's possible to fix, and indicate that the needed fix is swapping position 1 and positions 2 (remember, that indexing starts at 1).

Example 2
Sample Input

3
3 1 2
Sample Output

no
Explanation

The original gene IDs are not in order and no single swap or reverse can put them back into sorted order.

Example 3
Sample Input

6
1 5 4 3 2 6
Sample Output

yes
reverse 2 5
Explanation

The six genes are out of order, but can clearly be fixed by reversing the middle four positions. As such we print "yes" since it's possible to fix, and indicate that the needed fix is reversing everything between position 2 and positions 5.

Example 4
Sample Input

4
20 30 42 60
Sample Output

yes
Explanation

There are four gene IDs that are already in sorted order. As such we print "yes", but do not need to provide any additional details.

<br />
<br />
<br />
<br />
<br />
# Q4)
After all of the initial C.H.I.M.E.R.A. plots were foiled, Agent Ω teamed up with a set of other agents to break into the Goat's lair.  The mission initially goes well, but the group falls into a trap!  The Goat plays a loud noise so that the agents can't talk and then shoots them each with a tranquilizer dart in the backs of their necks.

Fortunately the agents planned for this!  Each dart is color-coded to indicate the type of tranquilizer used.  While agents cannot see the dart in themselves, they can see the colors that everyone else was hit with.  They have just enough time to inject themselves with one antidote.

Given that there are N agents and N possible colors of darts, can you devise a strategy (a program) for each agent to follow to guarantee that at least one agent uses the correct antidote based on looking at the others?

NOTE: Not all possible dart colors may be used, and multiple agents may have the same dart color.

For this problem, your program will be evaluated differently than in other problems. For every test case, we will run your program N times, once for each agent. Each time, we will provide the same N (the number of possible dart colors and the number of agents) but a different X (the current agent's ID).  We will also provide the same set of possible colors as well as the dart colors the current agent sees. You will pass a test case if, for at least one of the agents, your program outputs the correct dart color in their own nexk.

Credit for this problem is all or nothing. You must pass all tests to receive credit.

Input Format

The first line contains two space-separated integers, N (the number of agents/dart colors) and X (the current agent ID)
The second line contains a space separated list of strings where each string is a possible dart color.
The third line contains a space separated list of strings where each string represents the dart colors the current agent sees stuck out of the other N-1 agents.
Constraints

1 ≤ N, X ≤ 865
Output Format

Output the (string) dart color that the current agent uses and antidote for.

Example
In this example, there are five agents and five possible dart colors. Each agent's strategy (i.e., the program you submit) is run independently and given as input N = 5 (the number of dart colors and number of agents), X = 0 through 4 (the current agent's ID), and the current agent's view of everyone else's darts.

In this example, the true dart color assignment is as follows:

Agent 0: orange_peel
Agent 1: orange_peel
Agent 2: orange_peel
Agent 3: gainsboro
Agent 4: yellow
The colors fawn and white_smoke were possible dart colors, but were not used.

Agent 0

5 0
gainsboro orange_peel fawn yellow white_smoke
orange_peel orange_peel gainsboro yellow
Agent 1

5 1
gainsboro orange_peel fawn yellow white_smoke
orange_peel orange_peel gainsboro yellow
Agent 2

5 2
gainsboro orange_peel fawn yellow white_smoke
orange_peel orange_peel gainsboro yellow
Agent 3

5 3
gainsboro orange_peel fawn yellow white_smoke
orange_peel orange_peel orange_peel yellow
Agent 4

5 4
gainsboro orange_peel fawn yellow white_smoke
orange_peel orange_peel orange_peel gainsboro
Explanation

In this example, your program would be run five times, once for each agent. Each time your program is run, you must output the agent's guess. In this example, your program would be correct if at least one of the following was true:

Agent 0 output 'orange_peel'
Agent 1 output 'orange_peel'
Agent 2 output 'orange_peel'
Agent 3 output 'gainsboro'
Agent 4 output 'yellow'
Remember, you DO NOT need to get more than one true (and indeed, in an optimal answer you will always get exactly one true).

<br />
<br />
<br />
<br />
<br />
# Q5)
Fortunately for Agent Ω, she was the one to take the correct antidote and proceeded to find an chase the Goat.  He is now fleeing his underground mansion to the surface of Mars and Ω needs to catch him there.

There are N escape tubes to the surface, all in a line evenly-spaced 1 meter apart.  The goat has rigged a subset of those tubes to explode, so Agent Ω needs to avoid those tubes or any other tubes even near them, if possible.   Given a list of tubes set to explode, can you identify the distance of the tube furthest from the nearest explosion?

Input Format

The first line has two values: N (the number of tubes, labeled 0 through N-1) and K (the number of tubes set to explode). The next K values indicate the tube numbers that will explore. For example, if there are 100 tubes with tubes 10, 60, and 95 set to explode, then Agent Ω would take tube 35, which would be 25 meters away from the nearest exploding tube.

Constraints

1 ≤ N ≤ 109
1 ≤ K ≤ 105
0 ≤ explosion positions < N
Output Format

Output a single number indicating the farthest Agent Ω can be to the nearest exploding tube.

Example 1
Sample Input

5 2
0 4
Sample Output

2
Explanation

Five tubes are available (0, 1, 2, 3, 4), with explosions at tubes 0 and 4. If Agent Ω attempts to take tube 2, she will be two meters away from any explosion, which is the best possible.


Example 2
Sample Input

6 6
0 1 2 4 3 5
Sample Output

0
Example 3
Sample Input

20 5
13 1 11 10 6
Sample Output

6
Example 4
Sample Input

90 17 
4 76 16 71 56 7 77 31 2 66 12 32 57 11 19 14 42
Sample Output

12

<br />
<br />
<br />
<br />
<br />
# Q6)
Agent Ω has successfully captured The Goat! Through interrogating him, she learns that C.H.I.M.E.R.A. is planning to rig the vote for where to hold next year's Martian Olympics, so that they can use them as cover for another evil plot.

Because the Martian Olympics are such an important cultural event, every citizen of Mars casts one vote for their preferred location. But C.H.I.M.E.R.A. has hacked the system and is planning to duplicate some of the votes this evening. Agent Ω has a list of the IDs of people who have already voted in each region of Mars and is able to access the IDs of people currently voting. To uncover C.H.I.M.E.R.A.'s scheme, she just needs to compare the IDs coming in this evening to the list of people who have already voted. 

But there's a catch. The regional lists of people who have already voted are huge! Worse, Agent Ω doesn't have time to get back to her office before this evening, so she must work from a portable computer with very limited RAM. Can you help her design an algorithm to scan each region for duplicate votes?

Input Format

The first line has one value: M, the size of the list of martians in this region who have already voted. The next M lines are the IDs of all of the martians in this region who have already voted. IDs are sequence of letters and numbers.

The following line has one value: N, the number of new votes coming in in this region tonight. The following N lines are the IDs of all martians voting in this region tonight.

Constraints

1 ≤ M ≤ 10000000
1 ≤ N ≤ 10000
1 ≤ length of IDs ≤ 100
40 MB of RAM are available
Output Format

Output a single number indicating the number of duplicate votes (i.e. IDs which are present both in the list of people who have already voted and in the list of people voting tonight) .

Example 1
Sample Input

5
a
b
c
d
e
4
f
b
c
o
 

Sample Output

2
Explanation

b and c are both duplicate votes - they appear in both the first list and the second list.

 

Example 2
Sample Input

5
asfsf34
sahsdg2
ln2hr4r
fhdsd42
325sdd3
3
sahsdg2
fjfdry4
sdgnjl5
 

Sample Output

1
Explanation

Only sahsdg2 appears in both lists.