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.

#11103 - WFF 'N PROOF

Solved By:peter
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:greedy
sorting
Solution Description: Use an arraylist to hold your primitives and an arraylist to hold your functions. You'll also need an int to hold the number of NOT's you have.

When you take your input it, split the characters up into their appropriate areas, and afterwards add as many "N"s to your primitives as you can (limited by either the # of primitives or nots available).

Then, as long as you've got at least one function and 2 primitives, you can put the three together and push the result back onto your primitives list.

Also, use a custom comparator to constantly sort your primitives list by length, and always use the largest ones in the list.

At the end, if there aren't any primitives, output "impossible", otherwise output the largest one you have.

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:greedy
Solution Description: Keep two stacks, one for operands and one for operators that aren't 'N'. Iterate through the string, and whenever you encounter any non-'N', push it onto the appropriate stack. When you encounter an 'N', increment a running count of 'N's.

If your operand stack is empty, then no formula can be formed. Otherwise, greedily build your output string as follows:

out = operands.pop()

while(both stacks have elements remaining)
{
out = operators.pop() + operands.pop() + out
}

So we just constantly take two operands and combine them with an operator, forming a new operand.

At the end, add all the 'N's to the beginning of the string.


#11108 - Tautology

Solved By:wesley
Theory Difficulty:medium
Coding Difficulty:easy
Algorithms Used:brute force
Solution Description: With only 5 variables, there are only 32 different variable assignments, so you can brute force every combination.

Use a bitstring (or array of 5 booleans) to keep track of the variables' values, and increment it every iteration.

The input is in prefix notation, so it can be easily evaluated with a stack of booleans. Read from the end of string to the beginning, and for each character:

- if it's an operand, push that operand's value onto the stack
- if it's an operator, pop two booleans, w and x, off the stack (or just one for N), evaluate the expression, and push the result back onto the stack

At the end, there will be one boolean on the stack. If it's false for any assignment of variables, then the expression is not a tautology. Otherwise, it is.



#11110 - Equidivisions

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:other graph
Solution Description: Just a simple floodfill problem. Use an integer array and set each partition to a different number. Scan through the grid and floodfill from every point you haven't visited yet. If the size of the fill is not n, then fail.

One thing to note is that you are *not* guaranteed n pairs of co-ordinates on each line of the input. You might get more, and you might get less. Obviously, less is an instant failure, but more may not be because some of the points may be duplicates of others.


#11111 - Generalized Matrioshkas

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:sorting
Solution Description: This is a parsing / bracket matching sort of problem. Use a stack to parse each line. On the stack, negative numbers represent unclosed matrioshkas, and positive numbers represent closed matrioshkas.

When you see a negative number, push it onto the stack. When you see a positive number, N, pop all numbers off of the stack until you hit the equivalent negative number, -N. If the sum of the popped numbers is >= N, fail. If any of the popped numbers are negative, fail. If everything is OK, then push N onto the stack (in place of the -N that was there before).

Once you've gone through all of the input, the stack should contain only positive numbers. Note that it may contain more than one. That is, the following input is a valid matrioshka:

-9 -7 7 9 -2 2

This isn't clear in the problem statement.


#11115 - Uncle Jack

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:math
Solution Description: Output n^p, and use BigIntegers.

I thought that perhaps you could use doubles, since the bounds are well within 2^1024, however I checked and there are horrible precision errors in the bounds we're dealing with - so you're stuck with BigInt.

Solved By:wesley
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:math
Solution Description: Just use BigIntegers and output n^d.


#11121 - Base -2

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:math
Solution Description: Converting a number to a negative base is fairly similar to converting to a positive base, with one catch. If the remainder is negative, then you need to convert it to the positive remainder. So, here's some psuedocode. Let n be the number in base 10, and let b be the base you're converting into.

str = ""

while(n != 0)
... r = n - ((n/b) * b)
... if(r < 0) r = r - b
... str = r + str
... n = (n-r) / b


#11137 - Ingenuous Cubrency

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:dynamic programming
Solution Description: This is a staright-forward coin change DP problem. Generate an array of coins where d[i] is the value of the ith coin:

And now the recurrence:

a[i][j] is the number of ways of making change for j cents with coins up to i.

a[i][0] = 1 for all i
(there's always one way to get 0 cents: no coins)

a[0][j] = 0 for all j>0
(you can't make change for more than 0 cents with no coins)

a[i][j] = a[i-1][j] (if d[i] > j)
(if you can't use the coin, then the answer is to not use it)

a[i][j] = a[i-1][j] + a[i][j-d[i]] (if d[i] <= j)
(if you can use the coin, then you have two possibilities: using it, and not using it)

You should pregenerate a[][] beforehand, and just print out a[21][n] for any input n.


#11150 - Cola

Solved By:wesley
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:ad hoc
simulation
Solution Description: Firstly, you will never need to borrow more than one bottle. If you borrow two or more, you'll never be able to repay them. Imagine you have one empty bottle. If you borrow two, trade for a cola, and drink it... you only have one empty bottle left.

On the other hand, you will *always* end up with at least one empty bottle at the end. Putting these two facts together, you may as well always borrow a bottle whether you need it or not.

So start with n full bottles, and 1 empty bottle, and just simulate the process.


#11152 - Colourful Flowers

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:trivial
Algorithms Used:2D geometry
Solution Description: There are three pertinent geometry theorems for this problem:

Heron's Formula:
Let s = (a+b+c)/2. The area of the triangle, A, is sqrt(s(s-a)(s-b)(s-c)).

Circumradius:
The radius of the circumscribed (outside) circle is (a*b*c)/(4*A).

Inradius:
The radius of the inscribed (inside) circle is A / s.

From these, it should be pretty simple to find the areas of the three pieces.


#11168 - Airport

Solved By:wesley
Theory Difficulty:medium
Coding Difficulty:medium
Algorithms Used:2D geometry
brute force
Solution Description: As all the points must lie on one side of the line, the best line must be coincident with a side of the convex hull.

Generate the convex hull, and then try every side of the convex hull with every point to determine the lowest average distance.

(Thanks to A. Henrey)


#11172 - Relational Operator

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:math
Solution Description: Check each condition and output as suitable.

Doable in 20 seconds or less if you're rushing.

Solved By:wesley
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:math
Solution Description: There's not much to say. Just print out the appropriate character.


#11181 - Probability|Given

Solved By:wesley
Theory Difficulty:medium
Coding Difficulty:easy
Algorithms Used:brute force
math
Solution Description: We want P(xi buys something | r people buy something). We can manipulate this a bit:

P(A|B) = P(A AND B) / P(B)

We can use a bitstring to represent which people bought something. So, 10010 means that persons 1 and 4 bought something, and the rest didn't.

P(r people buy something) is the sum of the probability of all bitstrings that have r 1's. You can use a nextPermutation function to cycle through all of the possible strings.

The probability of a given bit string is the product from 1 to n of either pi or (1-pi) depending on whether the ith bit is a 1 or 0 respectively.

P(xi buys something AND r people buy something) is the sum of the probabilities of all bitstrings that have r 1's, and a 1 in the ith position. You can keep track of this while you calculate the above piece.


#11185 - Ternary

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:math
Solution Description: You can do it two ways - I'll explain the hard way:

Iterate from where the left of where the output would be, by calculating:

log(n)/log(3) = index of leftmost digit

Iterate 'to the right', outputting the current value of n % 3^i and subtracting each time

Solved By:wesley
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:math
Solution Description: Convert n into a base 3 string, rtn, as follows:

while(n > 0)
{
rtn = (n%3) + rtn
n /= 3
}
return rtn

Note that the input ends with any negative value, not just a -1.


#11192 - Group Reverse

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:strings
Solution Description: Use StringBuffers for output and reversing the groups.

Given a string input a and int b:

Just iterate from 0 to a.length, incrementing for for loop by (a.length/b) and taking the substring of length (a.length/b) from that point.

You can then use a string buffer for each substring to reverse it, and append it to an output stringbuffer.

Also, pay close attention to the sample output - it's sort of funny. I mean 'ha ha' funny, not incorrect funny.

Solved By:wesley
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:strings
Solution Description: Read in one group of letters at a time, reverse them, and append them to an output string.





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