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 effort

Solved 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 instruments

Solved 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 non-zero cells in a[].


#11205 - The broken pedometer

Solved 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 way

Solved 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 non-space, 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 Stars

Solved 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 - One-Handed Typist

Solved 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;=\\789aehtdck-0zx,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 Loowater

Solved 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 PHPGraphLib - Click For Official Site