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 PROOFSolved 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  TautologySolved 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  EquidivisionsSolved 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 coordinates 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 MatrioshkasSolved 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 JackSolved 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 2Solved 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 = (nr) / b 
#11137  Ingenuous CubrencySolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  dynamic programming
 Solution Description:  This is a starightforward 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[i1][j] (if d[i] > j)
(if you can't use the coin, then the answer is to not use it)
a[i][j] = a[i1][j] + a[i][jd[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  ColaSolved 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 FlowersSolved 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(sa)(sb)(sc)).
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  AirportSolved 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 OperatorSolved 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  ProbabilityGivenSolved 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(AB) = 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 (1pi) 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  TernarySolved 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 ReverseSolved 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
