Our current solutions to the problems in this volume are below. If a problem is not shown here, then we have not posted a solution yet.

#11500 - Vampires

Solved By:wesley
Theory Difficulty:medium
Coding Difficulty:easy
Algorithms Used:math
Solution Description: This is a gambler's ruin problem. The idea behind gambler's ruin is that two people have a certain amount of money, and they bet a certain amount each game, with a fixed probability of winning. The game might go on infinitely, but there is a closed form for the probability that each wins.

(The proof isn't too hard, but it's not the kind of thing you'd want to derive during a contest. See Wikipedia for more info)

Let p be the probability that player 1 wins, and let q = 1-p be the probability that player 2 wins. Let n1 be the amount of money that player 1 starts with, and let n2 be the amount of money that player 2 starts with.

The chance that player 1 wins is:

(1 - (q/p)^n1) / (1 - (q/p)^(n1 + n2))

And of course the chance that player 2 wins is 1 minus that.

Now, this assumes that each player wins/loses only 1 unit of money. In this problem though, the vampires may lose more than 1 health at once. So for this case, n1 = ceil(EV1/D), and n2 = ceil(EV2/D). That is, the number of hits it would take to kill a particular vampire. p of course is (AT / 6).

Note, however, that there is a special case when p = q = 1/2. The above formula is undefined for this case, and there is a much simpler closed form for a fair game. The probability of player 1 winning is:

n1 / (n1 + n2)


#11503 - Virtual Friends

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:other graph
Solution Description: This is a fairly standard union-find problem with two extra pieces. Firstly, you'll need to use a hash table to map nodes to their set leaders. Also, you need to keep track of the "size" of all set leaders. By size, I mean the number of elements in the set that the leader leads.

Whenever you union two elements, first check if they're in the same set. If they are, do nothing. If not, get the sizes of both set leaders, and sum them. This will be the size of the new set leader.


#11505 - Logo

Solved By:peter
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:2D geometry
math
Solution Description: Linear Algebra made things easy.

Keep a location array, two elements long. Also, keep an angle variable.

When you get lt, or rt, angle (+/-)= (input/360)*pi

when you get fd:
pos[0] += input*cos(angle)
pos[1] += input*sin(angle)

(the values on the right of the equality are the respective elements of your added coordinates)

then, output Math.sqrt(pos[0]^2 + pos[1]^2)

I'm rating it as easy, on the grounds that you don't really need Linear Algebra to do it.

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:2D geometry
math
Solution Description: This problem can be done easily with vector decomposition. Keep three variables, x, y, and theta, all initially 0. At every step:

rt q: theta -= q
lt q: theta += q
fd q: x += q*cos(theta), y += q*sin(theta)
bk q: x -= q*cos(theta), y -= q*sin(theta)

You may need to convert theta to radians depending on the library you use, so multiply by (2*pi)/360.

I made sure that my theta stayed between 0 and 360 the whole time, in/decrementing as necessary, but you probably don't have to. It's just that no bounds are given on theta.


#11506 - Angry Programmer

Solved By:wesley
Theory Difficulty:medium
Coding Difficulty:easy
Algorithms Used:max flow
Solution Description: We're trying to find the minimum cut in the graph, so we can conversely determine maximum flow. We also have vertex capacities because we can blow up computers.

So, split each node (except 1 and M) into two nodes, in and out. If you have an edge like (2, 3), connect 2out to 3in and 3out to 2in, both with the same capacity. If you have an edge like (1, 4), connect 1 to 4in and 4out to 1.

For each computer cost, draw and edge from Cin to Cout with that cost.

Connect the source to vertex 1 and connect vertex M to the sink, and run max flow to get your answer.


#11507 - Bender B. Rodríguez Problem

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:2D geometry
simulation
sorting
Solution Description: The only piece of information that you need to store is the current direction the wire is pointing in. Then, for every bend given, determine the new direction. There are only 24 possibilities (6 directions * 4 bends) so just hardcode all of them.


#11508 - Life on Mars?

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:sorting
Solution Description: What the idempotent condition means is that if a number exists in the sequence, then it must exist in the correct location (that is, 2 must be element 2, etc.) If more than one of the same number exists, then the remaining copies can go anywhere.

So keep an array of integers, initially set to -1. For each integer i you read, if a[i] is -1, set a[i] to i. If a[i] is already i, then store this extra copy of i somewhere (I used a stack). At the end of reading the input, put your extra copies wherever they can go (i.e. in spots that are still -1). If at any time you read an integer that is greater than or equal to the number of integers in the input, then the sequence has been hacked.


#11515 - Cranes

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:2D geometry
brute force
dynamic programming
Solution Description: I'm pretty sure there's a proper DP solution to this problem, but given the small bounds, brute force is fine.

First, create a boolean array where c[i][j] is true if cranes i and j conflict with each other. Two cranes conflict if the distance between them is less than or equal to the sum of their radii.

Then, just run through all possible combinations of cranes using bit shifting. Find the largest total area such that no conflicts occur.


#11518 - Dominos 2

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:recursion
simulation
Solution Description: Keep an array of Domino objects. Each one has a boolean indicating whether or not it has been knocked down, and a stack of integers that are the indices of the dominoes that it will knock down.

Then for each domino that's knocked down, run a recursive function that knocks down all dominoes that are in the first domino's stack. Don't knock down dominoes that have previously been knocked down. For each domino knocked down, increment a running total.


#11520 - Fill the Square

Solved By:wesley
Theory Difficulty:trivial
Coding Difficulty:easy
Algorithms Used:greedy
searching
Solution Description: Keep the input in an array of characters. Iterate through the array (in row major order) and for each cell with a period, replace the period with the lowest character that doesn't conflict with the cells around it.


#11530 - SMS Typing

Solved By:wesley
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:simulation
strings
Solution Description: Hardcode an array where a[i] is the number of keypresses for the character i. Then, just sum up all a[i] for each character in the string.


#11541 - Decoding

Solved By:wesley
Theory Difficulty:trivial
Coding Difficulty:easy
Algorithms Used:strings
Solution Description: Keep a counter, num, initially 0, and iterate through the string. When you encounter a digit, multiply num by 10 and add the digit.

When you encounter a character, first append the previously stored character to an output string num times. Then, reset num to 0, and store the current character.

At the end of the iterating through the string, append the last character num times.


#11547 - Automatic Answer

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:math
Solution Description: Just plug n into the function given. Floating point numbers will be involved, so don't use an int.

If n is now < 0, make it positive.

At the end, if n < 10, output 0.
Otherwise, output (String)n.charAt(n.indexOf('.')-2)

Solved By:wesley
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:math
simulation
Solution Description: Follow the instructions, but be sure to use a double, not an int. At the end, case to an int and return ((n / 10) % 10). If n is negative, make it positive.


#11554 - Hapless Hedonism

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:trivial
Algorithms Used:math
Solution Description: Three sticks form a valid triangle if the sum of the two smaller ones is strictly greater than the largest one. From this, you should be able to easily generate the first 10 or so terms by hand. The pattern is not the most obvious at first, but if you look at the number of triangles you add each time, you may see something.

Here's the terms up to 10:

3 --> 0
4 --> 1
5 --> 3
6 --> 7
7 --> 13
8 --> 22
9 --> 34
10 --> 50

Look at how much the sequence increases by each time:

1 <-- 1^2
2
4 <-- 2^2
6
9 <-- 3^2
12
16 <-- 4^2

Every other number is a square. The remaining numbers (2,6,12,...) are the triangular numbers, but doubled. From this, you should be able to formulate a closed form for pregenerating the sequence. You will need to use longs.

This problem is identical to Problem 11401 (Triangle Counting). See my solution to that problem for an alternative way of thinking about the pattern.


#11556 - Best Compression Ever

Solved By:wesley
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:math
Solution Description: If you have b bits, then you can have 1 file with 0 bits, 2 files with 1 bit, 4 files with 2 bits, 8 files with 3 bits, etc. up to 2^b files with b bits. The sum of (2^0) + (2^1) + (2^2) + ... + (2^b) is (2^(b+1)) - 1.

If n is less than or equal to this number, then the files can be compressed... theoretically.


#11560 - Fixing the Bugs

Solved By:wesley
Theory Difficulty:hard
Coding Difficulty:medium
Algorithms Used:dynamic programming
greedy
math
Solution Description: It should be clear that you will always want to work on the bug that has the highest expected value. However, if you fail it, some other bug may have the highest expected value next.

Let a[bs][t][f] be the maximum expected value when we have t hours remaining, f failed attempts on unsolved bugs, and bs is a bitstring representing which bugs have been solved. That is, "00101" means that bugs 1 and 3 have been solved so far.

This array has a maximum size of 1024x101x101 which is quite reasonable, as filling each cell is going to take O(b) time, for a total runtime on the order of 10^8.

This DP should be implemented top-down (i.e. recursively). Start with the cell a[0][T][0], because at the beginning no bugs are solved, you have T hours left, and you have made no failed attempts.

Let p[i] be the probability of fixing bug i. This array will be modified as the recursion progresses so that it always reflects the *current* probability of fixing a bug.

Let fails[i] be the number of times you've failed solving bug i. This will also be modified to remain current. We need a quick way of determining how many times each bug has been failed.

The recursion is as follows.

= Base Cases =
1) If all of the bugs have been solved, return 0. You cannot gain any severity if there are no bugs to fix.

2) If t = 0, return 0. You cannot fix any bugs if you have no time.

3) If a[bs][t][f] is already computed, return it.

= Recursion =

Firstly, calculate the expected value (p[i]*s[i]) of each unsolved bug to find the bug with the highest expected value. Call this bug B.

Now there are two cases. Either you fix the bug, or you don't. The case where you fix the bug is fairly simple:

p[B] * (s[B] + a[newbs][t-1][f-fails[B]])

This is the expected value that results from solving bug B. newbs is the new bitstring that results from solving bug B. f-fails[B] is the new number of failures on unsolved bugs. Bug B has been solved, so we remove its failures from the number. t-1 is simply that you have 1 less hour to work.

In the case where you fail to solve the bug, you must do a bit more work. Firstly, store the current value of p[B]. Then, multiply p[B] by f, and increment fails[B]. Now these arrays are ready for the recursive step.

(1-p[B]) * a[bs][t-1][f+1]

This is the expected value that rsults from failing to solve the bug. The bitstring hasn't changed, you've used one hour, and you've added one more failed attempt.

After calling this line, set p[B] back to its previous value and decrement fails[B]. Add the two expected values together, store them in a[bs][t][f], and return a[bs][t][f].

(Thanks to A. Henrey for bug finding and a 10x improvement in speed)





Copyright 2008 (c) QuestToSolve.Com - Graphs Powered By PHPGraphLib - Click For Official Site