Last updated on: 04 May 2009 02:34:27 PM

Comment on this volume: The hints for this volume are contributed by my CS3233 students:
11100-11149: Bi Ran (BR)
11150-11199: Nguyen Viet Cuong (VC)

Total hints in this volume: 35

11101 - Mall Mania

My solution is not correct actually, but it was accepted by the judge. This problem require the shortest distance between two sets of points. O(n^2) algorithm will get TLE, so I randomly pick 1000000 pair of points and find the shortest distance among them. The data is not strong enough and this get accepted.

11103 - WFF 'N PROOF

This is a string processing problem. There are three kinds of characters: the literal, operator with one argument, and operator with two arguments. First, since "if w is a WFF, Nw is a WFF", we can add all 'N' before one literal. Then, try to make full use of 'K','A','C','E', if any, to form longer WFF. If the number of literals is 0, it is impossible to form any WFF. So output "no WFF possible".

11105 - Semi-prime H-numbers

This is a math problem. First, use the idea of sieve to find all the H-primes. Then, find all H-sem-prime by enumerating all pair of H-primes less than or equal to 1,000,001. Since all H-numbers are in the form of 4*n+1, so we can simply use integer n to represent a H-number. The answer is the number of H-semi-primes less than or equal to n.

11107 - Life Forms

This is a string processing problem. First build suffix array for all substrings of each string. Then find all minimum intervals in the suffix array which contains at least substring of more than half of the original strings, and find the longest prefix of two end of each intervals. The longest prefix of all intervals is the result. stable_sort (merge sort) runs faster when comparison is expensive (string comparison).

11108 - Tautology

This is a math problem. There are at most 5 Boolean variables. So just use brute force to enumerate all possible truth table and evaluate the expression. If we get a false as the result of the expression for some truth table, then it is not a Tautology.

11110 - Equidivisions

This is a flood fill problem. The only tricky part is the input may not necessarily be n pair each line.

11115 - Uncle Jack

This is a math problem. The result is obviously n^d. 10^25 is larger than the maximun value of long long, so use big integer to calculate and store the result.

11121 - Base -2

This is a math problem. If the number is an odd number, then b0 must be 1, else b0 is 0. If we know the value of b0, reduce the original number by b0, and devide by -2, then the base -2 representation of the new number will be b1+(-2)*b2+...
To find b1,b2.. is a subproblem of the original problem.
The base case is when the number is 1, the result is 1; when the number is 0, the result is 0..

11122 - Tri Tri

This is a computational geometric problem. Two triangles have common internal point if and only if there exist one edge in on triangle which can separate this triangle from the other one.

11129 - An antiarithmetic permutation

This is an ad hoc problem. Notice that if the first half of an array are even numbers, the second half of an array are odd numbers, then no arithmetic progression containing both odd and even elements will be found because (even even odd) and (even odd odd) are impossible to be arithmetic progression. Then the problem becomes to find a permutation of all odd(even) elements smaller than n which contains no subsequence which is arithmetic progression. If we devide all elements of the odd(even) permutation by 2, we will get an antiarithmetic permutation, which is a subproblem. So this problem can be solved using divide and conquer. The total complexity should be O(n log n).

11130 - Billiard bounces

This is a math (physics?) problem. First, find the distance the ball can go if there is no boundary. Then, according to the symmetric property of the moving path, we can consider that the ball is moving in a segment in a plain with a*b grids. The result is the number of times the segment intersect with vertical lines and horizontal lines.

11133 - Eigensequence

This is a math and DP problem.
If an array is eigensequence, then a[n]%(a[n]-a[n-1])==0,
so a[n]=k*(a[n]-a[n-1]) for some integer k.
so a[n]-(a[n]-a[n-1])=a[n-1]=(k-1)*(a[n]-a[n-1])
so a[n-1]%(a[n]-a[n-1])==0.
In fact, for any integer b, if a[n-1]%b == 0, a[n-1]+b is a valid choice for a[n].(because a[n]%b==0).
For any interval [x,y], use f[x][y] to denote the number of eigensequence start with x and end with y.
f[x][y]=sum(f[x+i][y]) for all i which a%i==0 and a+i<b.
boundery cases: if x == y, f[x][y]=1;
if x > y, f[x][y]=0;

11137 - Ingenuous Cubrency

This is coin change problem. Use long long to store answer, and memoization to perform DP.

11138 - Nuts and Bolts

This is a max matching problem. First read Jimmy's code. Jimmy is trying to use back tracking to solve a max matching problem. Just use code of Hungary algorithm to replace his match_bolt function will do.

11149 - Power of Matrix

This is a matrix multiplication problem.
To calculate
A + A^2 + A^3 + .. + A^k
If k is even,
then the result equals
A + A^2 + A^3 + .. + A^(k/2)
+
A^(k/2)*(A + A^2 + A^3 + .. + A^(k/2))
If k is odd
then the result equals
A + A*(
A + A^2 + A^3 + .. + A^(k/2)
+
A^(k/2)*(A + A^2 + A^3 + .. + A^(k/2))
)

The complexity is O(n^3 * log k).

11150 - Cola

In problem 11150, note that bottles borrowing can be done at any time without changing the result of the problem. Thus, to solve the problem, just simulate the normal method given in the problem statement. If there are two empty bottles left at the end of the simulation, then one more bottle can be borrowed to maximize the number of bottles enjoyed.

11151 - Longest Palindrome

Problem 11151 can be solved by using dynamic programming. Let longest[i][j] be the longest palindrome extracted from the substring s[i..j] of s. The answer for the problem will be longest[0][strlen(s)-1]. The values of longest[i][j] can be calculated as follows:
If i > j then longest[i][j] = 0
If i = j then longest[i][j] = 1
If i < j and s[i] = s[j] then longest[i][j] = 2 + longest[i+1][j-1]
If i < j and s[i] != s[j] then longest[i][j] = max(longest[i+1][j], longest[i][j-1])

11152 - Colourful Flowers

Problem 11152 is a simple geometry problem. In this problem, use the following formulas:
p = (a+b+c)/2;
S = sqrt(p*(p-a)*(p-b)*(p-c));
R = (a*b*c)/(4*S);
r = S/p;
S_red = (PI*r*r);
S_blue = S-S_red;
S_yellow = (PI*R*R)-S;

11155 - Be Efficient

For this problem, note that the same answer can be obtained if the sequence is changed to:
X0 = A%M
Xi = ((((Xi-1)*B+C)%M)+1)%M
With the new sequence, process the elements in order X0, X1, ..., Xn-1. At iteration for Xi, maintain a number "base" and an array "numRemainder[0..M-1]" such that numRemainder[(base+i)%M] is the number of consecutive subsequences whose last element is Xi and whose sum divided by M give the remainder i. The value of "base" and "numRemainder" can be updated efficiently at each iteration.

11157 - Dynamic Frog

The problem can be solved by a simple greedy algorithm. If the current rock is i, then check the rock i+1. It rock i+1 is big, then land on it. If rock i+1 is small, then land on rock i+2. Start at the left bank and repeat the process until reaching the right bank. Then return back to the left bank using the remaining rocks.

11158 - Elegant Permuted Sum

This problem can be solved by using a greedy algorithm. First, sort the array and make a new list of two elements: the smallest and the largest integers from the sorted array. Then, in each step, greedily choose the best among the following 4 cases: (1) put the smallest element of the remaining sorted array to the beginning of the new list, (2) put the smallest element of the remaining sorted array to the end of the new list, (3) put the largest element of the remaining sorted array to the beginning of the new list, and (4) put the largest element of the remaining sorted array to the end of the new list.

11159 - Factors and Multiples

For this problem, build a bipartite graph between set A and set B where there is an edge between i (in A) and j (in B) if i|j. Then, the question will be equivalent to finding the maximum matching in this bipartite graph. Use Ford Fulkerson/Edmonds Karp algorithm to solve this problem.

11160 - Going Together

This problem can be solved by using BFS algorithm. Let a state be a triple of the positions of A, B, and C in the maze. Use BFS to search whether there is a path from the initial state to a final state. A final state is a state where A, B, and C are on three target cells.

11161 - Help My Brother (II)

Problem 11161 is about Fibonacci sequence and big integer arithmetic. Let f(n) be the n-th Fibonacci number and m(k) be the median of the k-th line. The problem can be solved by using the formula m(k) = (f(k+3)-3)/2.

11164 - Kingdom Division

Let d1 be the area of triangle XEF and d2 be the area of triangle AEF. Then d1 and d2 can be calculated from the following equations: d1/a = c/b and (a+d1)/d2 = (a+b)/(c+d1+d2). The result will be d = d1+d2.

11166 - Power Signs

Note that 0++ = +0-, 0+++ = +00-, 0++++ = +000-, 0+++++ = +0000-, ...
So, the problem can be solved by the following greedy algorithm: process the input from right to left, replace all the 011...110 subsequences with +00..0-0, except for the left most 11.

11170 - Cos(NA)

Problem 11170 just asks to calculate cos(nA) as a polynomial of cos(A) (note that the coefficients of the polynomial may be larger than 32 bits). To calculate cos(nA), use the polynomial arithmetic and the following recursive formula: cos(nA) = 2*cosA*cos((n-1)A) - cos((n-2)A) for n >= 2.

11172 - Relational Operator

Problem 11172 is a simple problem about relational operators. Given two numbers a and b, print out:
"<" if a < b
"=" if a = b
">" if a > b

11173 - Grey Codes

For problem 11173, let f(n,k) be the integer that appears in position k of the n-bit Reflected Gray Code (0 <= k < 2^n). The value of f(n,k) can be computed by using the following recursive formulas:
For n = 1: f(1,k) = k
For n > 1:
If k < 2^(n-1) then f(n,k) = f(n-1,k)
If k >= 2^(n-1) then f(n,k) = 2^(n-1) + f(n-1, 2^n-k-1)

11176 - Winning Streak

This is a dynamic programming problem. Let P[i][j] be the probability of having at most j consecutive wins in i consecutive games. The probability of having a winning streak of length k is P[N][k] - P[N][k-1]. To calculate P[i][j], consider the following cases:
P[i][j] = 1 for all 0 <= i, j <= N and j >= i
P[i][i-1] = 1-p^i for all 1 <= i <= N
P[i][j] = P[i-1][j]-p^{j+1}*(1-p)*P[i-2-j][j] if 2 <= i <= N, 0 <= j <= i-2

11180 - Base i-1

In this question, note that 2 = (i-1)^2 + (i-1)^3. First, rewrite a+bi = (a+b) + b(i-1).
If a+b > 1 or a+b < 0, then using the above formula to propagate the coefficient to (i-1)^2 and (i-1)^3. Then, continue with the coefficient of (i-1) and propagate to (i-1)^3 and (i-1)^4. Just be careful with the termination condition for this process.

11181 - Probability|Given

Note that P(X|Y) = P(XY)/P(Y). So, for each person i, calculate the probability Pi of the event that person i buys and there are other r-1 buyers. Also, calculate the probability P that there are exactly r buyers among the N persons. The result for each person i will be Pi/P. To calculate the probabilities, use a complete search to find all the subsets that have exactly r elements.

11184 - Joyful Ride

In this problem, if N%4=1 or N%4=2, then there is no solution. If N%4=0 or N%4=3, use the following greedy algorithm: let A[0] = 1 and A[1] = N+1, the difference height between them is N. Now put the heights into A[2], A[3], ... such that the difference heights are N-1, N-2, ..., N/2+1, N/2-1, ..., 2, 1, N/2 respectively. Note that the array A must satisfy the property (A[i]-A[i-1])(A[i]-A[i+1]) > 0.

11185 - Ternary

Problem 11185 is a simple problem about ternary. To solve the problem, use the standard algorithm to convert a decimal number into ternary and print out the result.

11192 - Group Reverse

Problem 11192 is a simple problem about strings. For each group in the given string, reverse the group by swapping the first and the last characters, the second and the second to last characters, etc. Then, print out the final string.