Last updated on: 04 May 2009 03:50:14 PM

Comment on this volume: The hints for this volume are contributed by:
NUS SoC team 1 (HT: Nguyen Hoanh Tien, DP: Nguyen Duc Phong, MD: Ngo Minh Duc)
NUS SoC team 2 (AK: Aditya Kristanto, AS: Ahmed Shafeeq, VL: Victor Loh)
NUS SoC team 3 (GC: Gaurav Chandrasekar, BR: Bi Ran, GY: Guan Yizheng, ZC: Zhao Cong)
Me (SH: Steven Halim 4)

Then, the other hints for this volume are contributed by my CS3233 student:
11350-11399: Tay Wei Liang (WL)

Total hints in this volume: 30

11340 - Newspaper

There is a speed difference if you read char by char versus reading line by line!
If you always get TLE, try to change your input reading function.
By solving this problem, you will learn which input method is the best in your preferred programming language.

I received several TLEs using read char by char (>1s). This code is 0.09s in judge's machine:

scanf("%d\n", &M);
while (M--) {
  gets(buffer); // buffer is of size 10100 (larger than 10000 to avoid unnecessary problem)
  .. bla bla ...
}

11341 - Term Strategy

This is a Dynamic Programming problem, with this formulation:

f[i][T] = max score when passed subjects 1..i with time T = max( f[i-1][T-t]+L[i][t] where L[i][t]>=5)

Note: when taking the result of f[n][m]/n, we need to add an epsilon amount because the actual result would be trimmed to yield the printed one.

11342 - Three-square

Use a clever brute force solution.

11343 - Isolated Segments

If your segment intersection algorithm is correct, then this problem is straightforward.
As computational geometry problems tend to appear at least once in almost programming contest,
it is good to have some basic comp geo algorithms in hand.

11344 - The Huge One

To solve this, you can either use number theory, or do a simple check.
Since the set of divisors are [1, 2, .., 12], there are special properties that you can use:
e.g.
1 = all numbers are divisible by 1
2 = check if last digit is even
3 = ...
5 = check if last digit is 0 or 5
...

But following this rule will lead to a long program. Not suitable for contest.
You can just do a simple check:
e.g.
To check what is 1259 % 7, do left to right scan:
1%7 = 1
12%7 = 5
55%7 = 6
69%7 = 6 <- answer is 6.

11345 - Rectangles

Set the first rectangle to be the "union rectangle".
Iterate through the other rectangles and keep the union!
Similar with 11343, your segment intersection algorithm must be correct...

11346 - Probability

Integral.

11347 - Multifactorials

Find all factors.
Use number of divisors property.

11348 - Exhibition

A simple ad hoc problem. Follow the instruction carefully.

11349 - Symmetric Matrix

Straightforward problem. Use long long as data type!
Be careful with the definition of "mirror around center", e.g. for n = 4
1 2 1 1
1 1 1 1
1 1 1 1
1 1 2 1
This is "Symmetric."

11350 - Stern-Brocot Tree

A simple simulation.
Start with left 0/1, mid 1/1, and right 1/0.
Then if you are instructed to go left, set right to be previous mid, and then compute new mid using the given formula.
It is the other way around if  you go right.
Just be careful with blank line: output "1/1" and use long long since the numerator/denominator can be very large.

Alternative: This problem can be solved by computing the branch of the tree traversed on the fly. First, three fractions are stored as
numerator and denominator pairs. These fractions are the left, middle, and right fraction. Each time a left transversal is made, the right fraction is replaced with the middle fraction, and the middle fraction is recomputed. For a right transversal, the left fraction is replaced with the middle fraction, with the middle fraction recomputed. This process continues until the path is fully traversed, in which case the middle fraction is displayed.

11351 - Last Man Standing

This is a Josephus problem. Refer to http://en.wikipedia.org/wiki/Josephus_problem for detailed explanation. This will be easy if you have done similar problem before. It can be solved without simulation by using the Josepheus recurrence relation. Otherwise, the problem might be difficult to solve within the time limits.

11352 - Crazy King

This is a basic graph problem.
The vertices are each cell in 2-D grid.
Filter/block some vertices that are occupied by 'Z' (enemy horse) or any other vertices that are reachable by any of the 'Z' (L shape).
Then, this problem is reduced to a simple shortest path problem from 'A' to 'B'.
As the graph is unweighted, a simple BFS() is enough.

11353 - A Different Kind of Sorting

This problem requires each number to be sorted by the number of prime factors. Since the number range is large, a modified sieve method is used. Also, a vector of structure, consisting of the number and the number of factors it has, is used as a table to store the number of factors a number has.

The algorithm behaves like a normal sieve, but instead of crossing out numbers, the table value is incremented to indicate that it has one more prime factor. An additional loop is present to increment the table for repeated prime factors.

After the vector is populated, the vector is sorted according to number of factors first, and then by the size of the number as a tie breaker.

11354 - Bond

This problem can be easily solved by finding the smallest and largest store position, and returning 2*(Largest - Smallest). This is because it is necessary to transverse the distance between these extremes twice.

11355 - Cool Points

This is a computational geometry where it is required to find what percentage of points on the circumference of a circle are not occluded by line segments lying in the circle. This problem is simplified by the fact that all line segments lie entirely within the circle; hence, it is possible to map each line segment onto the circumference of the circle as pairs of angles (arcs). Line segments extending across 0 deg are broken into two parts. Then, the arcs are sorted by starting angle, such that by comparing neighboring arcs, it is possible to find out the union of the arcs, and hence the parts of the circumference that are not arcs.

11356 - Dates

This is an ad hoc/simulation question where it is required to find the date in the calendar after K days from the given date. Since K * number of test cases is small, it suffices to iterate through the valid dates incrementally (day by day) until the desired number of days has passed.

11360 - Have Fun with Matrices

This is an ad hoc/simulation question where simple matrix operations are performed. Though the implementation of the matrix can be naive since the matrix size is small, it is possible to speed up some operations by performing them only at the output. Instead of transposing the matrix every time the transpose operation appears, the output and operation order (rows or columns) can be switched internally such that the n^2 element by element transposition can be avoided. Similarly, the increment and decrement mod 10 operations can be avoided by keeping a total count, and only including this during the output stage.

11362 - Phone List

This is a string processing/sorting problem where given a list of phone numbers, it is required to determine whether any phone number is a prefix of another. To solve this, the phone numbers are sorted by lexographical order, and each element is checked with the next item to determine if there is a common prefix.

11369 - Shopaholic

To solve this problem, first sort all the items available, largest first. Then, every third element in the list is summed to obtain the maximum discount possible.

11371 - Number Theory for Newbies

To solve this problem, it is necessary to sort the order of the digits forming the number. The maximum difference possible is the difference between the digits sorted largest first, and the digits sorted smallest first.

Since no leading zeros are allowed, when the digits are sorted smallest first, if there are any zeros in the number, these zeros should be shifted right such that they are to right of a non-zero number.

11378 - Bey Battle

This problem is a computational geometry/closest pair problem. It can be solved by using a variant of the divide-and-conquer approach to solving closest pair.

The divide-and-conquer variant works by sorting the points according to their x-coordinate, and then recursively splitting the points into a left and right half. For each half, the minimum distance between two points is found (base case).

Then, a search is done points within a radius distance equal to the minimum distance about the centre line.

The key modification required to solve the problem is to use Chebyshev distance rather than Euclidean distance. In other words, when calculating the distance between a pair of points, the distance is computed as the greatest difference between any coordinate dimension.

11384 - Help is needed for Dexter

This is an ad hoc/mathematical problem. The main difficulty is understanding the complicated problem statement and working out the mathematical relation behind the problem. The simplest way to do this is to output the first 10 or 20 results and to try to look for the trick. The trick is that the output will be the smallest power of two that is larger than the given number.

11385 - Da Vinci Code

This is an ad hoc/simulation problem. The first step is to initialize an array of the first 45 Fibonacci numbers; this is up to 2^31. Then, the remaining steps can be implemented according to the question. An easy mistake to make would be to forget that some numbers may exceed int range; an unsigned long or long long would be enough to avoid this mistake.

11387 - The 3-Regular Graph

This is a mathematics problem. The first condition to check for is to determine whether a graph with a given number of vertices is valid for making a 3-regular graph. Since the number of edges a 3-regular graph has is n*3/2, this clearly means that graphs with odd number of vertices cannot be 3-regular graphs, hence "Impossible" should be printed for graphs with odd vertices (and also for n == 2).

Then, in order to generate a 3-regular graph, note that if all vertices were connected in a ring (i.e., 1 to 2, 2 to 3, 3 to 4, 4 to 1 etc), each vertex would already have degree 2. Then, to make the graph 3-regular, we can pair each vertex once to make each vertex have degree 3.

11388 - GCD LCM

This is a mathematics problem. The key is solving the problem is in realizing that there is no valid solution if the LCM is not divisible by the GCD. Otherwise, a simple search is performed to find a valid pair satisfying the LCM and GCD.

11389 - The Bus Driver Problem

This is an ad hoc/sorting problem, where one is required to minimize the total deviation. This can be solved by a greedy pairing algorithm, where the elements are sorted then matched pairwise, highest and lowest together.

11392 - Binary*3 Type Multiple

This is a difficult mathematical/ad hoc problem where it is required to find a multiple of the given number such that the multiple is of format 3....0...(X number of 3's then Y number of 0's; Y can be 0). To simplify the problem, the problem can be considered equivalent to finding a number 3......3 such that 3...3 mod N is 0. Similarly, if the multiple ends with 0's, this can be considered equivalent to taking the subtraction of 3...3 and 3..3, ie, 33300 = 33333 - 33. Hence, one needs to keep track of the remainders mod N of various digit lengths, and stop when the remainder is either 0 or has been previously encountered.

While the basic algorithm is simple to describe, there are many complications. Firstly, the digit length of the multiple is very long, up to thousands of digits in extreme cases. Hence, it is impossible to compute the entire number as any prefined data type. Rather, it is only neccessary to remember the total number of digits iterated, and the number of 3's. Rather than keeping the entire multiple and performing the modulus operation, only the remainder component is retained; hence the numbers are always within integer range.

Another item to take note of is that when checking whether a remainder has previously been encountered, the immediately obvious approach, using an STL map, is too inefficent, as the find() step is performed in each iteration, resulting in O(nlogn) complexity, which gives TLE since n can be hundred thousand and above for special cases. To avoid TLE, instead of using STL map, a simple array can be used. The indices of the array represent the remainders, while the values represents the digit length that has this remainder. Hence, if the array element is empty, this means that the remainder does not exist. This modification makes search O(1), hence total complexity is O(n) only.

11393 - Tri-Isomorphism

This is a graph/ad hoc problem where it is asked to determine whether a complete graph can be decomposed to three pairwise isomorphic graphs. This problem is difficult to understand without some background knowledge of graph terminology. However, the problem turns out to be simple to solve if the problem is understood. The simple algorithm is to check whether the number of edges in the graph is divisible by three; if not, then clearly it cannot be decomposed into three pairwise isomorphic graphs. Conversely, if the edges are divisible by three, then since the graph is complete, there will be some configuration that results in three pairwise isomorphic graphs (as the complete graph is symmetric).

11398 - The Base-1 Number System

This is a straightforward simulation problem. There should be no difficulties if the instructions are followed.