Last updated on: 04 May 2009 12:03:23 PM

Comment on this volume: The hints for this volume are contributed by my CS3233 students:
10600-11649: Lam Woon Cherk (WC)
11650-11699: Li Jiashu (LJ)

Total hints in this volume: 53

10600 - ACM Contest and Blackout (by: Sohel Hafiz, notes by: Reinaldo Astudillo)

10602 - Editor Nottobad

I thought of using exhaustive search. But it is far too slow (Time Limit Exceeded). Until I found out in message board that this problem can be solved using Greedy. Just sort the words based on how many similar prefix (compared to the first fixed word). See example below:

abcdef
aasda   1
aafgh   1
abcjkl  3
ghy     0
aafyy   1
abcghj  3
uiop    0

abcdef
abcjkl  3
abcghj  3
aafgh   1
aafyy   1
aasda   1
ghy     0
uiop    0

10603 - Fill (by: Eduard Piliposyan)

This is backtracking problem with pruning.

10604 - Chemical Reaction

This problem can be solved using DP.

10606 - Opening Doors

This is classic maths problem. The problem can be solved by square rooting the test case and square the answer back. The trick is to work with square root of BigInt. A simple BigInt class that do square root can be found here. http://www.box.net/shared/ej14u01cqu

10608 - Friends

Use Union-Find data structure to organize the people into groups of friends. Then search for the group with the largest elements.

10610 - Gopher and Hawks

Single source shortest path. First find the points that the gopher can reach. Then do SSSP to find the answer.

10611 - The Playboy Chimp

You can't do exhaustive search because N can be as big as 50.000.
Use binary search algorithm to solve this problem.

10616 - Divisible Group Sums (by: Eduard Piliposyan)

This is a Knapsack problem, can be solved using DP.

10617 - Again Palindrome

DP.

10620 - A Flea on a Chessboard

Basically you need to simulate the Flea jumps up to a value slightly larger than 1000, say 1100, why? because dx and dy is positive integer and since max S is 1000, testing up to values slightly larger than 1000 will ensure that we know decisively whether the Flea can finally arrive at white square or not.

Now, how to check whether a flea already touching white square?
Let say the flea is at coordinate (x,y) now. (x,y) is inside white square if:

x%S != 0 && y%S != 0 -> because if either x or y is divisible by S, this means the flea is still touching border, still not acceptable

(x/S)%2 != (y/S)%2 -> because x/S => x's column, y/S => y's row
for (x,y) to be a white square:
if x's column is even then y's row must be odd, and
if x's column is odd then y's row must be even...

10622 - Perfect P-th Powers

This problem is not difficult. Find the GCD of all the prime powers. Special case occurs if x is negative. If this is the case, then convert x to positive then do the same thing the result ois power until this power is not even.

Examples:

25 = 5^2, output 2
100 = 2^2 * 5^2 = (2*5)^2, output GCD(2,2): 2
3600 = 2^4 * 3^2 * 5^2 = (2*2*3*5)^2, output GCD(4,2,2): 2
-64 = (-2)^3, output 3
-2147483648 = (-2)^31, output 31. <<== note that + 2147483648 is OVERFLOW!!!, special case!

10623 - Thinking Backward (by: MD Erfan Hoque)

One of the critical derivational mathamatics problem.
Firstly think reversly when you know N(circle),M(Ellipse),
and P(triangle).What is the total region?

step1: When N circle intersect each other then total number
of region is n^2-n+2.Now when M ellipse intersect with N circle
then region will increase as 4N+(4N+4)+(4n+8)+(4N+12)+.....+M times=CE.
[i,e:Draw a small figure of intersection 2 circle and 2 ellipse then observe above description.]
Now total region after intersection N circle and M ellipse is: n^2-n+2+CE
Now solve CE.
Final result may be like: n^2-n+2+4MN+2M^2-2M;-----------(i)

step2:Now when P triangle will intersect with intersection of N circle
and M ellipse then what's result? Draw a figure, ovserve for
P trinagle with N circle and P trinagle with M ellipse.
When 1 triangle intersect with 1 circle then 6 new region create and
same way when 1 triangle intersect with 1 ellipse then again 6 new region create.
So when N circle and M ellipse then it will 6N and 6M.
It means, with 1 triangle when intersect N circle and M ellipse then
number of new region is 6N+6M.When triangle is 2 then it is
6N+6M+6.
So the equation is like (6N+6M)+(6N+6M+6)+(6N+6M+12)+......P times
Now solve it and make it --------------(ii)

now (i)+(ii) is final equation from where if you know N,M and P
then you can found Total number of region.
Again now think reverse as if you know Number of total region and any
two from N,M,P then you can found third one.

According to problem description you are given Total region.Again
0<=M<100, 0<=N<20000 and 0<=P<100 is describe in problem description.
So with two nested for loop for any two variable (N,M,P) and input
value(Total region) you can get third variable for several times.Mind it that
if you choose M and P for first two variable then may be it will
time consumable.Try to solve without floating point calculation.
Finally read output format from problem desciption and if need then sort
all output.

10624 - Super Number

Backtracking. If the backtracking cannot beat the time limit, precalculate the result, and store it to a text file. Then, assign the result to a variable, and store the result into array. Then, it takes constant time to get the answer.

10625 - GNU = GNU'sNotUNIX

Simple simulation problem. But don't simulate the actual string replacement, you'll just crash your program. What you need is just counting the character's frequency. The initial string will give you the initial frequency of each character (ASCII 33 to 126), then simulate the frequency addition n times. Output the desired character's frequency.

10633 - Rare Easy Problem

One of the obvious value for N is (N-M)*10/9, btw this operation will overflow if you don't use unsigned long long data type. Let's call this value N_obvious. Now the question is, is there other possible values for N in this case? The answer, yes, they may be one other possible value, which lies between N_obvious - 10 to N_obvious + 10, try it one by one.

10637 - Coprimes (By: Stephanus)

This problem is a backtracking problem. Consideration of backtracking problem:

1. Solution Representation

Vector P = (p1,p2,…,pt) where t is number of partition. Roughly, the backtracking procedure try all possible values from 1…S for each pi (1 <= i <= t). Hence, total combination is St, i.e 10030 which is very big. Unfortunately, I don’t find any other better representation.

2. Pruning

Fortunately, the pruning is very good that can reduce the search space significantly. Pruning tips: 

- Notice that we don’t consider the solution order. I mean 1 2 3 is the same as 1 3 2, 3 2 1, and so on. So we only need to pick the smallest in lexicographical order which is 1 2 3.

- Assume the solution is the set P = { p1,p2,…,pt } where p1 < p2 < … < pt and we are given sum S and we have to partition it to T. For each si what is the biggest values for si? Is it S? No, by PHP (Pigeon Hole Principle) we know that the largest value is ceil(S/T)

10642 - Can You Solve It?

Transform the grid coordinates into its index... Remember that x and y axis is reversed (see problem description), not like the ordinary Cartesian coordinate.

(0,0) index 1
(0,1) index 2
(1,0) index 3
...
and so on

For each coordinate (x,y), the corresponding index is (1+(y+x))*(y+x)/2 + x;
(y+x) indicate the layer this coordinate lies...
(1 + (y+x)) * (y+x) / 2 is the arithmetic progression formula (see your math book)
finally add the value with x to complete the mapping.

Remember that since x,y <= 200.000, 200.000 * 200.000 can be bigger than 32-bit int, use long long instead.

10643 - Facing Problem With Trees

Math that involves BigInt.

10646 - What is the Card?

Just a straightforward simulation problem...
Maybe the problem description is not clear enough..., I'll rephrase it here...

Given a list of 52 cards from bottom to top, written from left to right, starting index: 1
Then take top 25 cards, i.e. take cards from index 28,29...,52
Then set Y = 0
Then starting from card index 27, determine the value of card => X, add X to Y
Decrease index by 1 and by (10-X)
Repeat these process THREE TIMES !!!, after that stop...
If (Y < index), directly output card with index Y
else, output card with index 27 + (Y-index), skipping the cards that already removed...

10649 - Danger Point

Math and computational geometry. The answer is s = sqrt(2 * (r * r + a * sqrt(2 * r * r - a * a))) - a. r is haf the distance of Jamal and Kamal. a is the distance between Rahim of Karim and the danger point.

10650 - Determinate Prime (by: MD Erfan Hoque)

One of the easy prime problem. Firstly read problem carefully.
Generate all prime from 0-32000.
Now pre generate all consecutive prime with same distance.
Mind that 31 37 43 is not consecutive for missing 41, though ditance
between them is 6.
You should get 162 different sequence.
A prime number can appear in more than one sequence - as the start of one and the end of the other.
As for example:251 257 263 269 is a sequence.
If input is 250 265 output is 251 257 263
If input is 252 270 output is 257 263 269
Input may be x<=y or x>y.if x>y then range is y to x.

Alternative: Ad hoc problem. Pre-calculate all the primes in that range. Print them according to the problem description. One thing to note is that the 2nd integer may be larger than the first one.

10651 - Pebble Solitaire

Just do a complete search/backtracking... For each 'o' encountered, you can jump to the left or jump to the right... (provided that the constraint is satisfied). The problem size is not large (12), so, brute force all the way...

10653 - Bombs! NO they are Mines !! (by: Zac Friggstad)

This is the e-mail that I received from Zac, I still have not try the following method, but you can try:

I noticed you said that you needed to optimize your BFS on problem 10653. Are you, per chance, using some sort of priority queue? Well, I tried the same thing and it wasn't working for me. I eventually optimized its brains out and had it accepted in 9.something seconds. However, I made this observation afterward.

Say, at any point of the BFS, the distance from the start square to the square in the front of the priority queue is C. Now notice that all squares in the PQ are of distance C or C+1. Finally, observe that we only add distance C+1 squares to the PQ. Once all distance C squares have been used, we then start looking at the C+1 distance squares and adding distance C+2 squares.

This is where the major optimization can come into play... don't use a PQ. Instead, have two arrays, one to store the distance C squares and one to store the distance C+1 squares. Just iterate through the distance C squares and store the appropriate squares in the C+1 array. Once you have looked at all distance C squares, simply switch arrays. That is, treat the C+1 array like the new C array. Once you try to add the end square to the current C+1 array, then quit because you have the shortest path.

In fact, with this, we don't even need to mark the length of the path from the start to the current square. We just simply need to mark a square as having been 'visited". When we finally "visit" the end square, the value C+1 should be the distance to this square.

Alternative: BFS. Use STL queue is enough for time limit. When reach the destination, output the steps form the original to the destination.

10654 - The Uxuhul Voting System

Dynamic Programming. Consider the best situation for every one from the end to the beginning. And decide what the first will do and output the final result.

10656 - Maximum Sum (II)

A trivial question. What you need to do is to read in number by number, then output those non-zero numbers... why? because the input will not have negative number. Any positive number (not zero) will definitely increase the value of the subsequence sum.

Alternative: Ad hoc? I think the problem may be wrong. Just output all the numbers that is not equal to zero. I got AC using this "algorithm".

10658 - ReArrange

It seems to be a problem like Tower of Hanoi. I made this problem AC by looking into the result in binary system. Maybe it is a "cheat" way. :-<

10659 - Fitting Text into Slides

Ad hoc problem. Calculate the maximum characters per line for each size. Pre-scan the characters per line. And go through all the lines to try every size.

10660 - Citizen attention offices

Complete search. Try every combinations of putting the officers.

10662 - The Wedding

Long problem description, but actually very simple. Read all the constraint (note: 0 is true, 1 is false), and then just do a o(n^3), 3 nested loops to try all possibilities and find the desired answer.

Alternative: Complete search again. Use adjacency list to record the graph. And search all the possible combinations of travel agencies, restaurants and hotels.

10663 - Non-Powerful Subsets

Ad hoc. Add number to the set one by one. When the number is a power or it can combine with any number(s) already in the set to be a power, do not let the number in.

10664 - Luggage

Sum all the weight, say the sum is S. If S is odd, obviously there is no way to properly divide this into two, print "NO". If S is even, sort the weight in descending order, then do backtracking from the biggest item to the smallest item, checking whether the partialsum = S/2, prune as soon as a solution become infeasible. Even though maximum possibility is 2^20 (2 choices, 20 items), you will be in the safe side if you prune effectively.

10666 - The Eurocup is Here!

I'm sad England didn't win the Euro cup, but anyway let's congratulate the Greek's for eventually winning the cup...

Let's move on to the problem itself, for optimistic ranking, count the number of ones in binary representation of X then add 1. Why? try it yourself first.

for pessimistic ranking, count the number of zeros at the least significant digit before encounter one (which is total nodes - number of children in topological tree).

It is hard to explain the logic why binary representation helps... I just unintentionally figure out this pattern...

10667 - Largest Block

Have you solved problem 108? The easiest way to solve this problem is to transform this problem into problem 108, then use your p108 solution to solve the transformed problem.

Initially, all cell has value 1. Then, for each covered block, write a very high negative value, such as -32767 per each covered cell..., in this way, your p108 solution will be able to get the biggest rectangle formed by all free cells with value 1, giving you the correct area :).

Don't forget when your p108 solution return -32767, you should actually print 0, since there is no free area...

10668 - Expanding Rods (by: Meng-Hsuan Wu)

First, we calculate the value of L', the rod's length after heated. Then, use binary search to find out the angle of the arc. Initially we assume the arc is 90 degrees and calculate arc's length when the chord's length is fixed at L and the angle is fixed at 90 degrees. If the result is smaller than L', then we have to decrease the estimated value of the angle, so we try 45 degrees the next time. Oppositely, if the result is greater than L', then we try 135 degrees the next time.

After trying for about 30 times, the estimated value is accurate enough. Now we can use the formula d = L * (1 - acos (theta / 2)) to determine the displacement of the rod, in which theta is the angle we estimated.

Note: Because the input is "non-negative", we should be careful about the cases in which
L = 0. Just output "0.000" in such conditions.

10669 - Three Powers (by: Meng-Hsuan Wu)

Each time we get an input, subtract one from it and transform it into binary representation (with at most 64 digits). Now we view this number from the lowest bit to the highest bit. If the N'th bit is one, then output the element 3^(n-1). Note that the largest element used (3^63) has 31 digits.

10670 - Work Reduction (by: Meng-Hsuan Wu)

To reduce the cost of reducing one unit, never perform the "reduce one unit" instruction before any of the "reduce half" instructions. So the key point is how many "reduce half" instructions is needed.

First we calculate the cost of all companies if no "reduce half" instruction is performed, i.e. use the "reduce one unit" instruction N - M times. Next we try to perform one "reduce half" instruction before using the "reduce one unit" instructions, and so on, until we cannot increase the times of "reduce half" anymore. In this process, we keep track of the lowest price of each company.

After sorting the companies by the costs and the names, we can output the answer.

10671 - Grid Speed (by: Meng-Hsuan Wu)

Because there are so many ways and possible speeds to drive between the two intersections, it is not a good idea to try all the possible ways once. Instead, we can use dynamic programming to keep track of all the possible arriving time of each intersection.
According to the problem, the possible speeds are 5, 10, 15, ..., 50 mph. Since the least common multiple of 1, 2, 3, ..., 9 and 10 is 2520, we can say that it takes 2520 "units" of time to across a block when the speed is 5 mph; and it takes 1260 units of time when the speed is 10 mph; and so forth.

Now we find out all the possible arriving time of each intersection and the minimum amount of fuel needed when arriving at each possible time. For example, if the max speed is 50 mph and the block size is m miles, it could take 252, 280, 315, 360, 420, 504, 630, 840, 1260 or 2520 units of time to drive from the starting point to the adjoining intersection, and it takes m/5, m/19.25, m/32, m/43.25, m/53, m/61.25, m/68, m/73.25, m/77, m/79.25 gallons of fuel, respectively. Similarly, we can calculate the possible arriving time of all the intersections. If there are more than one way to go to the same intersection at the same time, we choose the one with the smallest amount of fuel.

After the calculation is done, we can determine whether it is possible to arrive at the appropriate time. If it is possible then output it, otherwise output "IMPOSSIBLE".

10672 - Marbles on a tree

This problem is solvable using greedy method. Starting from total_move = 0, always check the tree's leaves until there is only one node left...

      if this leaf has < 1 marbles, parent's total marbles -= abs(n-1), total_move += abs(n-1)
else if this leaf has only 1 marbles, do nothing (just remove this leaf)
else if that vertex has n marbles, parent's total marbles += n-1, total_move += n-1

total_move will be the answer.

Alternative solution by Meng-Hsuan Wu:

In order to perform the smallest number of moves, we need to make as less marbles move pass the first level (the root) as possible. After the number of marbles move pass the first level is determined, we need as less marbles move pass the second level as possible, and so on, until the all the moves are determined.

At first we calculate the numbers of nodes and marbles of every subtree and record these numbers on the root of each subtree. Then we use BFS to adjust the marbles to make each node has exactly one marble and find out how many moves are needed.

For instance, if there are 2 marbles on the root and 3 branches adjoin the root. And there are 1, 3, 4 nodes and 2, 2, 3 marbles on each branches, respectively. Then the first branch should give 1 marble to the root, and the root should give 1 marble to the second branch and 1 to the third branch. Totally 3 marbles are moved passed the root.

After the BFS is done, we can output the answer. Note that some nodes could have a negative number of marbles at some time, but they will become positive again later.

10673 - Play with Floor and Ceil (By: Sohel Hafiz)

The equation given is x = p * floor(x/k) + q * ceil(x/k)

If x % k == 0:
We can consider p = 0 and q = k, since 0 + k*ceil(x/k) = x

But if x % k != 0:
The equation can be converted to x = p * a + q * (a + 1), where a = floor(x/k).
If Ax + By = d, where d = gcd(A,B) then Extended Euclid (see CLRS, number theoretic algorithms) finds the value of x and y.
 
For the former equation if we write P*a + Q*(a+1) = 1,
then we can find the value of P and Q using Extended Euclid, since gcd(a,a+1) is always 1.
 
And finally multiplying the new equation by x,
P*x*a + Q*x*(a+1) = x; ---- similar to original equation.
 
So p = Px and q = Qx.

10676 - Grid Points (By: Observer Mak)

All you need to solve this task is patience and carefulness. If you read through the long problem description, you should see that there are only ~50 possible ways of spacing. Thus, you can simply do brute force! :) Just remember to follow the instructions meticulously.

10677 - Base Equality

The sample input case 4 is NOT wrong. What you need to do is to brute force from r2 to r1 (exclusive, from bigger to smaller, we want the biggest one...), find an integer i in that range (base 10), which when converted to base b1, then directly converted again to base b2, can properly divide i again (the value % i == 0). So in the sample input case 4:

11 14 10 9999 have the solution 9240.
9240 (base 10) = 6A40 (base 11) = 6*14^3+A*14^2+4*14^1+0*14^0 = 18480 (base 14).
18480 is 9240 * 2, or 18480 % 9240 == 0.

10678 - The Grazing Cows

After careful observation, the cow's reachable area is an ellipse, formed by stretching a unit circle by factor a to x-axis and stretching by factor b to y-axis.

factor a can be calculated by L/2 (the rope+two pillars form a line)
factor b can be calculated by sqrt((L/2)^2 - (D/2)^2) (the rope+two pillars form a triangle)

Since unit circle has area pi, this ellipse has area pi * a * b.

10681 - Teobaldo's Trip

Use DP. Refer to my explanation for similar problem 10702 - Travelling Salesman, to get the gist of how to solve this problem using DP.

10683 - The decadary watch (by: Sohel Hafiz, MD Erfan Hoque)

By MD Erfan Hoque:

Very easy problem. Take input as HH,MM,SS,CC and convert it to second by this equation:
sum = (HH*3600 + MM * 60 + SS) * 100 + CC;

Now convert sum to decimal time by multiplying 125/108. But be careful about precision error
if calculate in floating point and also for input: "0000000" which output is 0000000.

10684 - The jackpot

Simple Maximum Interval Sum problem (I'm not sure if the name is correct). Refer to my DP page.

10685 - Nature

Use Union-Find to union two animals if they are in relationship (one is eating the other). At the end, just return the biggest set. However, since C can be as big as 5000, you must sort them first, and then use binary search to quickly retrieve the name<->index mapping!!! (or you may want to use BST to store the name<->index mapping).

10689 - Yet another Number Sequence (by: Shamsul Alam, Sohel Hafiz)

Some hint from Shamsul Alam:

The problem can be solved very easily if you know about the Pisano period.

The last digit of Fibonacci number repeats with a period of 60. The last two digits repeat with a period of 300, the last three with a period of 1500 and the last four digits have a period of 15000.

See the following link:
http://mathworld.wolfram.com/PisanoPeriod.html

And also the problem can be solved by getting the help from the following link:
http://home.ozonline.com.au/davmac/davpage/algrthm/fibonacci.html

Some hint from Sohel Hafiz:

The input is in the order of a b n m.
 
set m = 10^m
 
if n = 0 output a % m
if n = 1 output b % m
if n = 2 output (a+b) % m
 
otherwise
let the matrix [w; x; y; z] = [a+b; b; b; a] * [1; 1; 1; 0]^(n-2);
 
Then w % m should give the correct result.
 
Another question that arises is to find the value of [1; 1; 1; 0]^(n-2);
Well you can use divide and conquer for that.

10690 - Expression Again (by: Eduard Piliposyan)

This is a Knapsack problem, can be solved using DP.

10693 - Traffic Volume (by: MD Erfan Hoque)

Simple physics equation problem.
Try:
V=sqrt(L*f*2.0);
volume=(v*3600)/2*L;

10694 - Combinatorial Summation (by: MD Erfan Hoque)

The sum looks like this:
C(3,1) - first iteration
C(2,1) + C(2, 2) - second
C(1,1) - third
Since then, C = 0, and the final value is 3 + 2 + 1 + 1 = 7.
Actually this is distance fibonacci sequence.
Like output (sequently) 0,1,3,7,14,26,46.
SO the distance is 1,2,4,7,12,20.Now find the relation?
that is (1+2)+1=4.(2+4)+1=7.(4+7)+1=12.(7+12)+1=20.
But you should solve it using big integer.

10696 - f91

Ad hoc problems which can be solved in less than 5 minutes. Output 91 for N <= 100, otherwise, output N-10.

10699 - Count the factors

A popular prime factoring problem. Can be solved in less than 10 minutes if you remember how to do quick prime factoring (start with 2, keep dividing n with prime factors).