Last updated on: 04 May 2009 04:00:34 PM

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

Then, the other hints for this volume are contributed by my CS3233 students:
11400-11449: Nguyen Duc Phong (DP)
11450-11499: Nguyen Hoanh Tien (HT)

Total hints in this volume: 41

11400 - Lighting System Design

Sort+DP. Categories are sorted according to their voltage.
f[MAXN][MAXC]: F[i][j] = Considering categories 1..i, using max. voltage source at j, return the optimal cost.

11401 - Triangle Counting

A 3 nested for-loop solution will time out, but the formula can be figured out from its pattern.

11404 - Palindromic Subsequence

d[l][r] = length of optimal palindromic subseq of the substring [l..r]. The first character of the solution is kept tract
while DP to help choosing the smaller sequence.

11405 - Can U Win

BFS among the possible states. Each state consists of the knight's position and a boolean vector to keep track of the killed pawns. Complexity O(N^2 * 2^M) with N being the size of the board, M being the number of pawns.

11407 - Squares

DP. d[i] = smallest number of square factors of i

11408 - Count DePrimes

DP. d[i] = number of DePrime numbers from 1..i. To check if i is a DePrime or not, factorize and calculate the sum of its
divisor.

11410 - LAEncoding

Encode the input text into an int64 number, then decode it using the defined scheme. Those processes are similar to converting integers among bases.

11411 - MiniMice

Initialize the number of divisors for all integers from 1 -> 5000000 (O(N)). For each query, count all mouses into an a[400] array. Binary search on the result difference. For each difference, see if there is a possible solution by DP. We have two lines of mouse being elongated. d[i] is the distance between the last mouse of line 1 and the last mouse of line 2, provided that one of them ends at i. At the end, we see if it's possible to link the two lines together to form a cycle. Total Complexity: Q*O(N).

11412 - Dig the Holes

Brute Force. Go through all the possible sequences and compare it with the input.

11413 - Fill the Containers

Binary search on the capacity of the largest container and see if such number of containers is enough to contain all the milk according to the stated rules.

11415 - Count the Factorials

Count the number of factors for each integer. Use that result to find the number of factors for each integer factorial. For each query, search in the initialized array to find the first element with that value.

11417 - GCD

DP. d[i] = the value of G for corresponding i.
d[i] is calculated from d[i-1] by adding all the gcd of i with smaller j.

11418 - Clever Naming Patterns

Maximum bipartite match problem. However, brute force with pruning branches runs very fast.

11420 - Chest of Drawers

DP: int64 d[maxn][2][maxs]; d[n][0/1][s] keep track of the number of ways one can arrange the chest with n drawers with s secured ones, ending with a locked/unlocked chest. Complexity: O(n*s) + Q

11424 - GCD - Extreme (I)

Initialize the result array (O(Nlog log N)). Querying is just a matter of read-and-write. Initialization reduces to finding the sum of gcd of x with all smaller integers. Done by considering all prime factors of x and combinations of those factors. For each combination, take the sum of gcd of numbers less than x that divides the combination.

11426 - GCD - Extreme (II)

Same as above problem, bounds changed to match the problem specification.

11428 - Cubes

Try all factorization of the query N. From each factorization, calculate x and y. See if that x and y are the results.

11430 - ETS Problem setting

Combinatorics. Fix the size of AB, then there will be limited number for A and B that satisfies AB.n = A.B
For each (A,B,AB,n) tuple, count the number of set assignment that satisfies the description.

11437 - Triangle Fun

The result is always 1/14 of the area of the input triangle.

11450 - Wedding Shopping

Dynamic programming:
f[i][j] = true, if there is possible to buy j the first class of garments by an amount of money i
f[i][j] = false, otherwise.
Fomular: f[i][j] = true if f[i-1][j - p[i][k]];
with p[i][k] = price of model k of class i

11452 - Dancing the Cheeky-Cheeky

Brute-force:
Try all possible lengths of the sequence.
For each length, we check whether s[1..length] is a right sequence or not.

11455 - Behold my quadrangle

Simple mathematics:
A square consists of four equal sides
A rectangle has two pairs of equal sides
A quadrangle has four sides that each side is shorter than half of the perimeter.

11461 - Square Numbers

Trivial problem, just generate all the possible square numbers and count such square numbers within [a .. b].
Ad hoc: Number of square numbers from a to b equals to [sqrt(b)] - [sqrt(a-1)].

11462 - Age Sort

You will get Time Limit Exceeded if you do not use O(n) sorting algorithm. Since the age range is just [1 .. 100], we can use counting sort algorithm. Do one pass in O(n) to count the frequency of each age. Then, after we obtained these frequencies, output the occurrence of each age according to its frequency, starting from age 1, ending at age 100, skipping age that has 0 frequency. This is also another O(n).

11463 - Commandos

This is a graph problem. The simplest and fastest implementation will be O(n^3) Floyd Warshall algorithm, since n <= 100. After we generate all pairs shortest paths in this graph, we just answer this formula: max(cost[s][i] + cost[i][d]), for all i in {0 .. n-1}. The troop that takes the most time from building 's' to building 'i' (plant a bomb) and then go from building 'i' go to destination building 'd' is the bottleneck of this problem and hence the answer.

11464 - Even Parity

Brute force: try all 2^n states of the first row. Notice that the other cells can be calculated just by knowing the first row.

11466 - Largest Prime Divisor

Firstly, generate all prime numbers which are smaller than 10^7 by using sieve of Erathosthene.
After that, factorize n and keep the maximum prime factor.

11467 - Pythagorean Triangles

Use N^3 algorithm to generate an array of results for n from 1 to 2000 and use it in your code as a constant array.

11470 - Square Sums

A coding practice problem. You need to count elements in the array according to 'concentric ring' rule...
Cell (i,j) belongs to the min(i,j,n-i+1,n-j+1)'th sum.

11471 - Arrange the Tiles

Brute force: If you brute-force normally, the number of possible ways will be 12!.
However, if we group all same tiles into one group before brute-force, it will be much smaller than 12!.

11475 - Extend to Palindrome

We need to find the longest suffix of S which is a palindrome. Let S' = S[0]+S[1]+..+S[n-1]+S[n-1]+S[n-2]+..+S[1]+S[0]. To check a suffix S[i]S[i+1]S[i+2]...S[n-1] is a palindrome or not, we can use the condition: 2*LCP(i,n) >=n-i. To find LCP (Longest Common Prefix) of any two suffxes of S', we can use the data structures Suffix Array and Range Minimum Query.

11479 - Is this the easiest problem?

Ad hoc: Just follow the problem's text. There are some cases to consider.

11480 - Jimmy's Balls

Simple mathematics:
We are going to solve an system:
(1) 0 < r < b < g
(2) r + b + g = n

Suppose r is constant, we have:
(1) --> 0 < (b - r) < (g - r)
(2) --> (b - r) + (g - r) = n - 3*r;

So (b - r) & (g - r) is the solution of the following system:
(3) 0 < x < y
(4) x + y < n - 3*r
The number of solutions of this system is (n - 3*r - 1)/ 2

In short, just try all values of r. For each value r, we add (n - 3*r - 1)/2 to the result.

11481 - Arrange the Numbers

This problem is not solved yet.

11482 - Building a Triangular Museum

It is more simple if we use a 2-dimensional array to fill the shape.

11483 - Code Creater

Follow the problem's text.

11489 - Integer Game

Simple mathematics:
After the first turn, two players can only remove the digits which is divisible by 3.
So we just count the number of this kind of digits and check it is odd or even.

11491 - Erasing and Winning

This problem is not solved yet.

11492 - Babel

Can model this problem as graph and perform a modified Dijkstra on it. I got AC once but now the same code gets TLE.

11494 - Queen

Try to enumerate the answers for several scenarios. You will realize that there will be only three possible answers... 0, 1, or 2...
Just figure out when to answer 0, answer 1, or answer 2... :)
Ad hoc: Just one line: cout << ( (i == u && j == v) ? 0 : (i == u || j == v || abs(i - u) == abs(j - v)) ? 1 : 2 ) << endl;

11495 - Bubbles and Buckets

Simply count the "bubble sort" swaps.
If it is even, Carlos win. If it is odd, Marcelo win (because Marcelo starts first).

However, since there are 10^5 = 100.000 numbers, we cannot use "bubble sort" as it will take (10^5)^2 = 10^10...
This problem is called counting "inversion index" and can be solved in O(n log n) by modifying merge sort.
In the merge process, if an item in the right side is merged first, then it can be inverted with anyone in the current left side.

11496 - Musical Loop

Another easy problem in this problem set.
To simplify the problem, store these N magnitude samples in index [1 .. N], as shown in the problem.
Add "sentinels", H[0] = H[N] and H[N+1] = H[1]!
Then, simply iterate through [1 .. N] to see whether you see /\ pattern or \/ pattern, count this as 1 peak.
Output the total peaks.

11498 - Division of Nlogonia

Straightforward problem. Should be solve-able in under 10 minutes if nothing goes wrong!
Just make sure you write NO and SO instead of NW and SW! (Portuguese language) and no coding error...

11499 - Longest Increasing Sequence

Dynamic programming: For each j and k (1 <= j <= k <= n), we try rectangles staring at column j and ending at column k. If we try all rectangles, the complexity of this method is n^4. However, it can be improved to n^3 because by taking advantage of the previous steps, we only need to try n rectangles.