Algorithm-Engineering Homework 2 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)
Interplanetary super spy, Agent Ω, has learned that the evil organization C.H.I.M.E.R.A. is planning a sinister mission to seize control over a cutting-edge research base on Mars (using the Martian Olympics as cover!)  In order to identify who the C.H.I.M.E.R.A. operatives are, Ω identifies their satellites in geosynchonous orbit to break into.  Unfortunately she must do this in person.

Ω has a flight pod with just enough power to propel her to a satellite of her choice.  From that satellite she must steal power to get to the NEXT satellite and beyond.  Can you identify which satellite she should start at so that she'll have enough power to get to all of the others?

The satellites are arranged in a ring.

Input Format

The first line will provide the number of C.H.I.M.E.R.A. satellites around Mars (N).
The next N lines will each contain a pair of integers, indicating (1) the amount of power Ω will be able to draw from each satellite and (2) how much power is needed to get to the next satellite.

Constraints

1 ≤ N ≤ 105
1 ≤ energy gained, energy needed ≤ 109
We guarantee that there is a solution.
Output Format

 A single value indicating the index of the first satellite from which she can start her investigations.

Example 1
Sample Input

3
1 5
10 3
3 4
Sample Output

1
Explanation

There are three satellites to infiltrate. The satellite at position 0 provides only one unit of energy, but we need five just to get to the next satellite so we can't start there.

We CAN, however, start at satellite 1. This satellite would give 10 energy, three of which would be used to get to satellite 2. That leaves us with 7 energy, plus we would get three more at satellite 2, for a total of 10 again. Now we need to use four of those to get back around to satellite 0. We've now claimed all three satellites!

As such satellite 1 is the first one we can start at to infiltrate all of the other satalites as well.

Figure making(1).png

Example 2
Sample Input

20
1 11
2 12
3 13
4 14
5 15
6 16
7 17
8 18
9 19
10 20
11 1
12 2
13 3
14 4
15 5
16 6
17 7
18 8
19 9
20 10
Sample Output

10
Example 3
Sample Input

20
5 15
16 6
2 12
3 13
14 4
7 17
1 11
13 3
20 10
15 5
6 16
4 14
9 19
11 1
8 18
17 7
18 8
12 2
10 20
19 9
Sample Output

7
<br />
<br />
<br />
<br />
<br />
# Q2)
Agent Ω examines the information that she collected from the satellites in an effort to decode the identity of C.H.I.M.E.R.A.'s local coordinator.  Specifically, Ω has collected the communication IDs for everyone contacted by operatives through the satellites.  Her goal is to identify which ID is contacted the most.

Input Format

The first line contains a single value N, indicating the number of communication IDs being tracked.

The next N lines each contain the ID number of one contact. Note that ID numbers may not be consecutive and can be large values.

Constraints

1 ≤ N ≤ 106
0 ≤ ID ≤ 1012
1 ≤ number of unique IDs ≤ 1000
Output Format

Print the ID number that occurs most frequently. If two communication ID's were used equally frequently, print the one with the lowest value.

Example 0
Sample Input

8
63
63
63
8
3
8
63
3
Sample Output

63
Explanation

Eight communication signals are identified:

ID #3 was contacted 2 times
ID #8 was contacted 2 times
ID #63 was contacted 4 times
As such, communicator #63 was contacted the most, and thus, '63' is the correct output.

Example 1
Sample Input

15
97
97
29
68
68
97
97
83
97
68
29
97
68
83
83
Sample Output

97
<br />
<br />
<br />
<br />
<br />
# Q3)
Agent Ω has identified the Martial Coordinator for C.H.I.M.E.R.A. (who calls himself "The Goat") and tapped into his e-mail.  He treats his e-mail as a stack, always dealing with the most recent e-mail first.  On the other hand, Ω finds it more important to keep track of the MOST IMPORTANT e-mail in the stack.

Given the inflow and outflow of e-mails and importance of each, can you track the most important e-mail in the stack?

Input Format

The first line is an integer N, indicating the number of e-mail activtities to track in The Goat's stack.

The next N lines contain a number and possibly an importance level (x) in the format:

1 x - A new e-mail of value x has arrived into The Goat's inbox.
2   - The Goat has dealt with the top e-mail in his stack.
3   - Print the value of the most important e-mail still in the stack.
Constraints

1 ≤ N ≤ 105
1 ≤ x ≤ 109
Output Format

 For each type 3 action, print the value of the most important e-mail still in the stack, each on a new line.

Example 0
Sample Input

10
1 97
2
1 20
2
1 26
1 20
2
3
1 91
3
Sample Output

26
91
Explanation

We take 10 different operations:

1) Push an e-mail of importance 97 onto the stack. Current: [97]
2) Remove the top e-mail from the stack; now empty.
3) Push an e-mail of importance 20 onto the stack. Current: [20]
4) Remove the top e-mail from the stack; now empty.
5) Push an e-mail of importance 26 onto the stack. Current: [26]
6) Push an e-mail of importance 20 onto the stack. Current: [26, 20]
7) Remove the top e-mail from the stack. Curent: [26]
8) Print the value of the most important e-mail in the stack (which is 26)
9) Push an e-mail of importance 91 onto the stack. Current: [26, 91]
10) Print the value of the most important e-mail in the stack (which is 91)

Example 1
Sample Input

4
1 83
3
2
1 76
Sample Output

83
<br />
<br />
<br />
<br />
<br />
# Q4)
As Agent Ω starts hacking into more C.H.I.M.E.R.A. files, she needs to make sure that her online activity doesn’t look suspicious.  She decides to limit herself to always have her activity level be the same as the median users.  To do so, she monitors all of the other users as they join and leave the system and updates the median level of activity as she goes.  Warning: You might be working with a LOT of data!

The median of M numbers is defined as the middle number after sorting them in order if M is odd. Or it is the average of the middle two numbers if M is even. You start with an empty number list. Then, you can add numbers to the list, or remove existing numbers from it. After each add or remove operation, output the median.

Input Format

The first line is an integer, N, that indicates the number of operations. Each of the next N lines is either "a x" or "r x", with 'x' being an integer. An "a x" indicates that the value x is inserted (added) into the set, and "r x" indicates that the value x is removed from the set.

Constraints

1 ≤ N ≤ 106
-2,147,483,649 ≤ x ≤ 2,147,483,648
Output Format

For each operation:

If the operation is remove and the number x is not in the list, output "Wrong!" in a single line, but make not other modfiications to the set of numbers.
If the operation is remove and the number x is in the list, output the median after deleting x in a single line.
NOTE: If your median is 3.0, print only 3. And if your median is 3.50, print only 3.5. Whenever you need to print the median and the list is empty, print "Wrong!".

Example 0
Sample Input

7
r 1
a 1
a 2
a 1
r 1
r 2
r 1
Sample Output

Wrong!
1
1.5
1
1.5
1
Wrong!
Explanation

The list starts out empty, so the first input fails to remove anything and "Wrong!" is output.

The value 1 is then added, so the median is 1, which is printed.

The value 2 is then added, making the set [1, 2], and the median is 1.5.

Another 1 is added, making the set [1, 1, 2]. The median is now 1.

One of the 1's is removed, bringing the set back to [1, 2].

The 2 is removed, leaving only a single 1.

The final 1 is removed, meaning that there are no values left, resulting in a "Wrong!"

Example 1
Sample Input

50
a -2147483648
a -2147483648
a -2147483647
r -2147483648
a 2147483647
r -2147483648
a 10
a 10
a 10
r 10
r 10
r 10
r 100
r 100
r 100
r -2147483648
r 2147483647
r 10
a 1
a -1
a 1
a -1
r 1
r -1
r -1
r -1
r -1
r 1
r 1
r 0
a 0
a 1
a 2147483647
a 2
r 1
a 2147483646
r 2
a 2147483640
a 10
r 2
r 2
r 2
r 1
r 1
r 1
a 2147483640
a 2147483640
a -2147483648
a -2147483640
r 2147483640
Sample Output

-2147483648
-2147483648
-2147483648
-2147483647.5
-2147483647
0
10
10
10
10
10
0
Wrong!
Wrong!
Wrong!
Wrong!
-2147483647
Wrong!
-1073741823
-1
0
-1
-1
-1
-1073741823
Wrong!
Wrong!
-2147483647
Wrong!
Wrong!
-1073741823.5
0
0.5
1
1
2
1073741823
2147483640
1073741825
Wrong!
Wrong!
Wrong!
Wrong!
Wrong!
Wrong!
2147483640
2147483640
2147483640
1073741825
10
<br />
<br />
<br />
<br />
<br />
# Q5)
Once Agent Ω was able to access all of The Goat’s communications, she needed to setup a program to crack his encoded messages as quickly as possible.  Given a list of when each message first arrives and how long it will take to crack, Ω will always start on the quickest message that she currently knows about.  You must determine the average time between message arrival and when the message is actually cracked.  The challenge is that only one message can be processed at a time, so others will often have to wait in the queue.
 
Note: Some input files are NOT sorted.
 
Input Format

The first line provides the value N, the total number of job request coming in.
The next N lines each have two values: the time the job arrives (Ti) and how long the job will take (Li)
Note that the job list may be unsorted.

 

Constraints

1 ≤ N ≤ 105
0 ≤ Ti ≤ 109
1 ≤ Li ≤ 109
 

Output Format

Display the integer part of the minimum average time that the job took.  Do not include any decimal places.

Example 0
 Sample Input

3
0 3
1 9
2 6
Sample Output

9
Explanation

Three encrypted messages come in at time 0, time 1, and time 2, and they will take 3, 9, and 6 seconds to decrypt respectively. Agent Ω will start on the first message at time zero (it's the only one she knows about) and will take 3 seconds to finish it.  At time 3 she'll start on the third message (since it's the shortest one) and finish it at time 9 (3+6). Since this message came in at time 2, she would have taken 7 seconds to complete it (9-2). Finally at time 9 she will start decrypting the second message, finishing it at time 18, for a total of 17 seconds spent on it since it first arrived (18-1).
Given that the completion times for the three decryptions were 3 seconds, 7 seconds, and 17 seconds, Ω would have spent an average of (3+7+17)/3 = 9 seconds per job, which is what you would output.
 
Example 1
Sample Input

4
2 5
11 2
1000 12
10 10
Sample Output

9
Explanation

At the start, Agent Ω doesn't have any messages, so she must wait.  At 2 seconds in, she finds out about the first message which takes her 5 seconds to decrypt.  When she is done with that (at 7 seconds) no new messages have come in, so she must wait another 3 seconds before the fourth message arrives.  That one takes her 10 seconds to finish, and she is done at time 20.  By that point the second message has arrived, which she can decrypt in 2 seconds, finishing it at time 22.  Since it came in at time 11, it took her 22-11 = 11 seconds to complete.  Finally she has to wait all the way to 1000 seconds for the final message to arrive, but completes the decryption process of it in only 12 seconds.
 
The messages took an average of (5 + 10 + 11 + 12)/4 = 9.5 seconds to decode.  Since we are supposed to output only the integer portion of a number, we output 9.