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. #11202  The least possible effortSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  trivial  Algorithms Used:  sorting
 Solution Description:  The idea here is to find all of the sets of cells that are rotationally/vertically/horizontally symmetric, as shown in the example picture. There are two separate cases, squares and rectangles. Rectangles are the easiest.
If we have a rectangular board, we need to check one of the four quadrants. The other cells are just flips and rotations of these cells. For instance:
6x7
XXXX...
XXXX...
XXXX...
.......
.......
.......
We must check all the cells with X's. So output ceil(m/2)*ceil(n/2).
For squares, we can cut corners:
7x7
XXXX...
.XXX...
..XX...
...X...
.......
.......
.......
We only need to check a triangle of cells, because the other triangle is symmetric. So, output the ceil(n/2)th triangular number: Let X = ceil(n/2), output (X*(X+1))/2. 
#11203  Can you decide it for ME?Solved By:  wesley  Theory Difficulty:  trivial  Coding Difficulty:  easy  Algorithms Used:  sorting strings
 Solution Description:  With just a bit of examination, you can see that M is actually the addition operator, and E is the equals operator. Check that your string contains no invalid characters, and that the M comes before the E. Then, count the number of question marks before the M (call this x), between the M and E (y), and after the E (z).
Check that x > 0, y > 0, and x + y = z. If so, then the string is a theorem. If anything doesn't work out, then the string is not a theorem. 
#11204  Musical instrumentsSolved By:  peter  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  math
 Solution Description:  I completely overthought this problem the first time, and the second time.
It's simply a combinatorics solution. Create an instruments array, and increment the elements corresponding to the students' first choices. The other choices are irrelevant.
Now, just go through the array, and multiply all the elements > 1 together. There's your answer!
This is because for each instrument in competition, there are n students that could have it (where n is the number of students with it as a first priority).
From there it's simply the combinations of students for each instrument.
At first I thought this was a DP  although I'm sure you could probably think one up. Then I misread the question, and thought that in addition to the correct solution above, you had to multiply THAT by all the combinations of students who didn't get the instrument they wanted  getting instruments they don't want. 
Solved By:  wesley  Theory Difficulty:  trivial  Coding Difficulty:  trivial  Algorithms Used:  sorting
 Solution Description:  The only thing that matters in the input is which instrument is priority 1 for each student. We want the number of ways to maximize how many priority 1 instruments get assigned.
If there are no conflicts for priority 1 instruments, then there is only 1 way to assign them: give everybody what they want. When more than one student wants the same instrument though, then we can choose any of them.
So, if 2 students want instrument A, 4 students want instrument B, and 3 want instrument C, then we must pick one student from each group. There are 2*4*3 ways of doing this, so the answer is 24.
Keep an array, a[], where a[i] is the number of students that have priority 1 for instrument i. Output the product of all nonzero cells in a[]. 
#11205  The broken pedometerSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  brute force
 Solution Description:  There are up to 15 different LEDs, so there are 2^15 different ways in which they might be active/broken. We can easily test all 100 * 2^15 possibilities.
Represent each symbol as an integer in binary. So, 1 1 0 1 0 is stored as 26 (or 11 if you start from the left; doesn't matter which way you do it). For i from 1 to 2^p, AND together each symbol with i. Then, check if every symbol is unique under this bitmask. We can't afford to do an O(N^2) comparison, so make a boolean array of 2^p cells, b[], and set b[j] to true if j is some symbol under the bitmask i. If the cell is already set to true, then you don't have a unique representation.
Take the minimum number of LEDs needed across all unique representations, and output it. 
#11207  The easiest waySolved By:  peter  Theory Difficulty:  easy  Coding Difficulty:  trivial  Algorithms Used:  2D geometry
 Solution Description:  Keep a maxlength variable, and loop through your input. Given sides a and b:
maxlength = Math.max(maxlength, Math.min(a, b/4));
maxlength = Math.max(maxlength, Math.min(b, a/4));
maxlength = Math.max(maxlength, Math.min(a, b)/2);
if maxlength changed, set a 'best' variable to the current index. Output. 
Solved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  trivial  Algorithms Used:  2D geometry
 Solution Description:  There are 3 different ways in which we could cut out the 4 squares: all in a row along the height, all in a row along the width, or in a 2x2 pattern. The maximum side length of these patterns are, respectively:
min(w,h/4)
min(h,w/4)
min(h,w)/2
So calculate these three quantites, then take the largest one. You need only keep track of the side length, not the entire area of the square. Make sure not to use integer division. 
#11219  How old are you?Solved By:  peter  Theory Difficulty:  trivial  Coding Difficulty:  easy  Algorithms Used:  math
 Solution Description:  Use Scanner and the useDelimiter function to parse the input with / and newlines, etc, as your delimiters.
Be careful about all the little boundaries. Given current year, cy, and birth year, by, and current month, cm, and etc..:
if(cy < by  (cy == by && cm < bm)  (cy == by && cm == bm && cd < bd)
output invalid.
else
years = cy  by
subtract 1 as appropriate.
Output 'Check Birth Date' or years as appropriate 
Solved By:  wesley  Theory Difficulty:  trivial  Coding Difficulty:  trivial  Algorithms Used:  math
 Solution Description:  Start with age = (current year  birth year). If the current month is less than the birth month, or if both are the same but the current day is less than the birth day, then subtract 1 from the age.
If age is negative, return "invalid", and if it's over 130 return "check". Otherwise, just print the age. 
#11220  Decoding the message.Solved By:  peter  Theory Difficulty:  trivial  Coding Difficulty:  trivial  Algorithms Used:  strings
 Solution Description:  Use scanners, and take the input line by line.
For each line, use another scanner and a counter to go through the terms of the line. If the term is long enough to grab a character at the current (counter)ith place, then add that character onto a stringbuffer that you can later output, and increment the counter. 
Solved By:  wesley  Theory Difficulty:  trivial  Coding Difficulty:  easy  Algorithms Used:  strings
 Solution Description:  For each line, keep a counter (initially 0) that marks what index you should take a character from. Read each word on the line, and if the index is less than the length of the word, append that character to an output string and increment the counter. 
#11223  O: dah dah dah!Solved By:  wesley  Theory Difficulty:  trivial  Coding Difficulty:  easy  Algorithms Used:  searching strings
 Solution Description:  Hardcode an array of strings with all of the Morse representations of the characters. Store a string of characters such that the index of each character is the same as the index of its Morse representation. So, if a[0] = "." and a[1] = "...", then your string should be "AB ...etc... "
For each line, search through the string character by character. When you encounter a nonspace, append it to a temporary string. When you encounter a space and the temporary string is not empty, search the Morse array for the temporary string and output the corresponding character. When you encounter a space and the temporary string is empty, output a space. 
#11244  Counting StarsSolved By:  wesley  Theory Difficulty:  trivial  Coding Difficulty:  easy  Algorithms Used:  searching
 Solution Description:  Keep the input in a character array. Iterate through the array, and for each asterisk you encounter, check for asterisks in all 8 surrounding squares. If none are asterisks, increment a running count. Output the count at the end. 
#11278  OneHanded TypistSolved By:  peter  Theory Difficulty:  trivial  Coding Difficulty:  trivial  Algorithms Used:  strings
 Solution Description:  You'll need four strings to map everything. Two for the normal keyboard layout (caps and non caps) and two for the messed up keyboard layout. I've pasted mine below to save you time:
String map = "`1234567890=qwertyuiop[]\\asdfghjkl;'zxcvbnm,./";
String caps = "~!@#$%^&*()_+QWERTYUIOP{}ASDFGHJKL:\"ZXCVBNM<>?";
String weird = "`123qjlmfp/[]456.orsuyb;=\\789aehtdck0zx,inwvg'";
String weirdcaps = "~!@#QJLMFP?{}$%^>ORSUYB:+&*(AEHTDCK_)ZX<INWVG\"";
All you need now is good use of indexOf, charAt, contains, and a stringbuffer to append characters as you iterate through your input, and you'll be fine. 
Solved By:  wesley  Theory Difficulty:  trivial  Coding Difficulty:  trivial  Algorithms Used:  strings
 Solution Description:  Just set up an array (or two strings) such that a[qwerty] = dvorak, and then use this to convert every character in every line. 
#11292  Dragon of LoowaterSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  greedy sorting
 Solution Description:  Keep an array of heads h[i], and an array of knights k[j]. Sort both ascending.
Start with i=0, j=0. While i < size(h), see if the current knight, k[j], can deal with the current head, h[i]. If it can, then hire the knight and incremement i and j. Otherwise, just increment j.
If you run out of knights, then Loowater is doomed. Otherwise, output the total cost once you run out of heads. 
Copyright 2008 (c) QuestToSolve.Com  Graphs Powered By
