Last updated on: 04 May 2009 02:59:35 PM

Comment on this volume: The hints for this volume are contributed by my CS3233 students:
11200-11249: Aditya Kristanto Goenawan (AK)
11250-11299: Ahmed Shafeeq bin Mohd Shariff (AS)

Total hints in this volume: 40

11201 - The problem of the crazy linguist

The idea is to permute and precompute the average of SBC of the words starts with letter X with size N. Thus, we have a table of PRE[X][N]. Then, for every string inputs, you need to compute the SBC value of the corresponding input and compare it with the Pre-computed table.

11202 - The least possible effort

There are 2 cases that we must consider:
1. the board is a square of size N
- There always be Floor(N/2) sets of 4-symmetrical unit squares
- If the side are ODD, there exist another Floor(N/2) sets of 4-symmetrical unit squares
- The rest of the area should be sets of 8-symmetrical unit squares
2. the board is NOT a square
- If the side are ODD, there exist Floor(N/2) sets of 2-symmetrical unit squares
- The rest of the area should be sets of 4-symmetrical unit squares

11203 - Can you decide it for ME?

From the complex definition of theorem, it actually can be reduced to:
Let s = the string that we input
1. M = s.find_first_of('M'); E = s.find_first_of('E')
2. If 'M' or 'E' is not found or M > E, it is not a theorem.
3. s1 = substring of s from index (0, M-1); s2 = substring of s from index(M+1, E-1); s3 = substring of s from index(E+1) onwards;
4. if s1, s2 and s3 only contains '?' AND s1.size() + s2.size() == s3.size() then it is a theorem. Otherwise, it is not a theorem.

11204 - Musical instruments

To solve this problem, a table of INST[idx]. The content of INST[idx] indicates the number of students whose favorite is instrument No. (idx) e.g. INST[1] = 2, means there are 2 students whose favorite is instrument No. 1
From the permutation formula, the number of possible arrangement is:
Let N = number of musical instruments
Let total = number of possible arrangement

total = 1
for i = 1 to N
if not INST[i] = 0 then total = total * INST[i]
next
return total

11207 - The easiest way

There are 2 possible arrangements for maximum size of 4-squares for a given size of paper
X X
X X

AND

X X X X

Thus, we get the formula:
let l = longer side of the rectangular paper
let s = shorter side of the rectangular paper
max square size = MAX(MIN(l/4.0, s), s/2.0)

Iterate through the answer and search for the first maximum.

11218 - KTV

For this problem, dynamic programming technique is used. Bit manipulation is used for storing all the possible positions for all 9 people.
Let PJ[X] indicates the maximum score for the X position. X position can be break down to 9 bits. Every bit indicate whether the corresponding people has been picked up.
e.g. PJ[0] = 0, corresponds to 000000000 (no person have been picked up as a group) has the maximal score of 0
PJ[511] = 100, corresponds to 111111111 (all person have been picked up as a group) has the maximal score of 100

PJ[511] (111111111) can be filled by combining the previous memorized state.
i.e. = MAX(PJ 111111000 + GROUP 000000111, PJ 111110100 + GROUP 000001011, etc)

The answer will be stored in PJ[511]

11219 - How old are you?

Let cdate, cmonth, cyear = current date month and year respectively
Let bdate, bmonth, byear = birthday date month and year respectively

The formula is:
age = byear - cyear
if cmonth < bmonth OR (cmonth = bmonth AND cdate < bdate) age = age - 1

11220 - Decoding the message.

Quite straight forward, just follow the instructions of the problem.

11221 - Magic square palindromes.

The steps:
- First, the string must be filtered out from all non-alpha characters.
- Second, if the string size is not a perfect square, it is not a magic palindrome
- Third, the string must be reversed by this formula:
let s = the filtered string
let inv = the reversed string
let side = Floor(sqrt(s.size()))

for i = 0 to side-1
for j = 0 to side-1
inv = inv + s[j*side+i]]
next
next
- Fourth, the reversed string must be the same as the original string and both of them must be palindrome. Otherwise, it is not a magic palindrome.

11222 - Only I did it!

Array of size 10000 (let it be SOL) can be used to store the number of times a particular problem has been solved and who solved it.
Count up all the 1s in the SOL array and print out as necessary.

11223 - O: dah dah dah!

A pure simulation and coding problem. Try to put the morse code into STL map for easier implementation.

11225 - Tarot Scores.

Ad-hoc problem with some string manipulation. Use STL Map to help implementing the string manipulation (e.g. MAP["one"] = 1, etc).

11226 - Reaching the fix-point.

To solve this problem, first pre-calculate the prime numbers from 2 to 500000. After getting the prime numbers, using backtrack generate all the Sum of Prime Factors for all the numbers. After getting the table of Sum of Prime Factors for every numbers, getting the value of lsof can be done linearly with reading the input.

11227 - The silver bullet.

This problem can be solved by pure brute-force technique with complexity of O(N^3). Some tricks that can help in implementing the solution:
- Make the 2-decimal digit floating point into integer by multiplying it to 100
- Be careful with the floating precision point when reading the input, when the input is +ve add +ve epsilon (e.g. 1e-10), when the input is -ve add -ve epsilon (e.g. -1e-10).
- vector cross product can be used easily to check the alignment (observe that cross product will be 0 for aligned vector).

11231 - Black and white painting

After some observation, a formula can be derived to get the answer in O(1) time.
Let A = (R-8+1)*(C-8+1), where R and C are rows and cols respectively.
P(R,C,W) = (A/2) + (A % 2)*W
Beware of the limit of signed integer.

11233 - Deli Deli

A simulation problem. Trace all the words and do as what the requirements have stated. map<string, string> can be used to help on getting the irregular plural words.

11239 - Open Source

String processing and sorting problem. Implementation-wise, try to get the unique student ids for every single project. While doing that, a blacklist table consisting of students that registered for more than one project is filled. Later, based on the unique student ids for each project and the blacklist table the answer can be derived.

11241 - Humidex

With some algebra, the formula for getting dewpoint from h can be derived.
DEW(h) (1/(1/273.16 - log((h/0.5555 + 10.0)/6.11)/5417.7530)-273.16), where log is the natural logarithm.
After that, the rest of the problem is quite simple.

11244 - Counting Stars

Ad-hoc problem. Trace through the map of the stars and check the surrounding to determine whether a '*' is a star. We can use flood fill algorithm for this.

11247 - Income Tax

Math problem. By some observation, it can be derived that:
v < (M-1)*100/(100-X).
Tricky cases: beware of the upper limit, int32 limit (use long long), M=1, X=0, X=100

11254 - Consecutive Integers

Using the formula for summation of an arithmetic progression, 2T = 2na + n^2 - n, we need to find maximum n. From this formula, we can see the maximum possible value of n is sqrt(2T). Since T is given, we only need to try all values of n to get a value for a. The value for a is valid if (2T + n - n^2) is divisible by 2n and is not negative. We can then know that a is the starting value in the progression and n is the number of items in the progression.

11258 - String Partition

This problem is a dynamic programming problem. A scanned number is not a 32-bit integer if it has a length greater than 10 or it is greater than INT_MAX (use long long). For a given, substring, split the substring in such a way that there are at most 10 digits on the left. Use the precalculated value to find the maximal value on the right. Find the maximum of all these sums and that is the answer. 2-dimensional DP will time out.

11262 - Weird Fence

This is a bipartite matching question combined with binary search. Basically we want to search for the minimum integer length of the chains so as to form at least k matchings. Therefore, for every midpoint in the binary search, form a graph such that every red pole is joined to a blue pole if their distance is less than or equal to the midpoint. From there, carry on the bipartite matching. If such a length cannot be found, print Impossible.

11264 - Coin Collector

This is quite a difficult greedy problem because it depends on the person attempting it to spot the pattern. counter is set to n. Start with the total equaling the first coin. Then start the loop from the second coin onwards. If the sum of the total and the current coin value exceeds or equals the value of the coin right after the current coin, the current coin's value is not taken into the total and counter is decremented by one. Output counter at the end of the loop.

11267 - The Hire-a-Coder Business Model

This problem tests on bipartite testing and MST. Firstly, after reading in all the edges, test if the graph is bipartite to ensure that the data is valid. If the graph is not bipartite, exit with the "Invalid data, Idiot!". Otherwise, continue on with Kruskal. However, there is a twist. Since there are negative edges and the company wants to minimize loss, the program must also pick edges that are not in the MST but are negative so that the total sum of loss is as little as possible.

11269 - Setting Problems

This is a greedy problem though there is a known algorithm for it called the Johnson's scheduling algorithm. Basically partition the tasks into two. Those with s <= g put into list 1 and those with s > g put into list 2. Sort list 1 in ascending values of S and sort list 2 in descending values of G. Then add up all the S values together to a total. For the G values, it is slightly more complicated. If a G value is greater than the S value of the task after it, then add the difference to the G of the task that comes after it.

11270 - Tiling Dominoes

This problem seems like a difficult problem at first sight. However, there is a closed form to the possibly recursive solution that is needed. The formula is found at http://en.wikipedia.org/wiki/Domino_tiling. However, because there are roots and PI involved, care has to be taken when handling the long doubles. For some cases, the number 0 is actually computed as a very small number and not as 0 itself. To handle such cases, ensure that if a number is smaller than a certain precision required by the program, the number is actually representing zero.

11275 - 3D Triangles

This question is quite crazy. Many algorithms from Möller to Held to even Guigue were tried but they all took more than 2 seconds and TLEd. Only the algorithm from Hao Shen, Pheng Ann Heng and Zesheng Tang worked and was the only one which took less than a second to complete. Amazing stuff. Who knew that calculating the intersection of two triangles in 3D space would take so much work. Here is an
implementation of the algorithm: http://jgt.akpeters.com/papers/ShenHengTang03

11278 - One-Handed Typist

This problem is a simple linear search problem. Simply place the matching keys of the QWERTY and DVORAK keyboards in the same position inside their respective strings. Once done, a linear search is done for every key read in the input and the DVORAK character from the position of the QWERTY key found is output instead resulting in a mapping between the QWERTY and DVORAK keyboards.

11279 - Keyboard Comparison

This is a simulation/math problem. Firstly, all keys must be mapped to a coordinate. If the x, y coordinates start from the bottom left, then for example, the key z on the QWERTY keyboard will have the coordinate (1.5, 0.5). Using this information, the coordinates of the respective home keys must then be stored in arrays. From there, for every statement read in, every character of the statement must have its distance between every home key calculated and the shortest distance found will be added to the total. The formula used for calculating distance is the math formula for calculating distances between two Cartesian points i.e. sqrt ((x1 - x2)^2 + (y1 - y2)^2).

11280 - Flying to Fredericton

This is a special case of Bellman-Ford. Take note that the same set of edges can be produced as input twice. Thus, if the same set of edges is encountered again, take the set with the lowest cost amongst them. For the modification of Bellman-Ford, take note that when Bellman-Ford is run |V| - 1 times, it is actually finding the shortest path in which the shortest path consists of at most |V| - 1 edges. Therefore, for this problem, Bellman-Ford has to be run numberOfStops + 1 times to retrieve the answer.

11281 - Triangular Pegs in Round Holes

For this problem, what is needed is the minimum bounding circle for all the triangles given as input. There is a formula to find the diameter of the minimum bounding circle which is (2.0 * abc) / sqrt((a + b + c) * (b - a + c) * (a - b + c) * (a + b - c)) where a b and c are the lengths of the sides of the triangle. However, this formula does not apply to obtuse triangles. For obtuse triangles, the diameter of their
minimum bounding circle is the length of the longest side in the triangle. For such a case, use Pythagoras' theorem which states that a^2 + b^2 < hypotenuse^2 is true when the triangle is obtuse. If so, use the hypotenuse's length as the length of the minimum bounding circle. Also take care to allow for errors up to 1e-6 since floating point numbers are used.

11282 - Mixing Invitations

This problem falls under derangements in the field of combinatorics. There is a formula to find a derangement for a given N. That value represents the number of ways of mixing up everyone in that whole set such that no one gets the right card. So, to get the number of ways for everyone but EXACTLY k people to get the wrong card, we use the corollary, (N choose k) * D[N - k] where D is the array of derangements.

11283 - Playing Boggle

This is a problem concerning DFS. Basically for every word that is given as input, a DFS must be done to search the Boggle grid whether that word exists in the grid. If the DFS returns with the word found, then the score for that word is added to the total score. At the end, the total score is sent to output.

11286 - Conformity

This problem first requires a sort of each row of course data given. The solution then requires that this sorted data be the key in a map. However, since the data is in the form of an integer array, what needs to be done is to convert this data into a number. As there are only 400 represent-able values for each position (plus an additional 0 to represent courses that are not chosen), the base of the system should be 401. Thus, after the sort, the new number's value can be easily calculated and mapped as a key. Using the map, it can then be determined which choices occur most frequently. Whichever choices occur at the same maximum frequency will have the student counts for those choices added into the final total.

11287 - Pseudoprime Numbers

This question basically requires primality testing and an application of Fermat's little theorem. A little knowledge of modular arithmetic is needed. Basically (a*a) mod p = ((a mod p) * (a mod p)) mod p. Thus, for every number in the input. First test if it's prime (this can be done by dividing by all the numbers smaller than its square root). If it is prime, then the answer is automatically no. Otherwise, apply Fermat's little theorem on it. If it is successful, the input number is a pseudoprime and yes has to be output.

11289 - Friend or Foe?

This is a gradient descent/ascent search problem. We start with a random possible solution. Then, we progress the search by comparing with every system given. For all alliance systems, we want to minimize f(x) so that the inequality holds false. Thus for every alliance system to which the current solution set makes the equality hold true, we move the solution by the negative gradient of that alliance system. The opposite is done for all empire systems. Stop when the solution set is not modified anymore.

11291 - Smeech

This problem requires recursion to be done. The function recurse() will return the value of the Smeech expression read in. Inside recurse, all whitespaces are first eliminated. Then the input is tested to see if the next character is part of a number or part of an 'inner' Smeech expression. If it is a number, the number is just read in and returned. Otherwise, the opening bracket of the Smeech expression is consumed and the p in the expression is read in. For the e1 and e2 values, recurse() will be called to handle them as they can themselves be either integers or inner Smeech expressions. After that, calculations are done and returned to the caller.

11292 - Dragon of Loowater

This is a simple greedy problem. Sort the diameter of the heads in descending order while the heights of the knights are sorted in ascending order. For every dragon head, find the smallest knight height that just meets the diameter of the dragon head and make sure not to reuse this knight once he's taken.

11296 - Counting Solutions to an Integral Equation

The hint comes from the equation. When rearranged, it becomes x = n - 2(y + z). Since n is given and 2(y + z) must always be even, then there are only two cases to consider, namely when n is odd or even. If n is odd, then x can only take on odd values. If n is even, then x can only take on even values. How to count the number of y,z pairs? For any integer k = 2(y + z), there are always k/2 + 1 such pairs.