Last updated on: 04 May 2009 12:10:27 PM

Comment on this volume: Some of the hints for this volume are contributed by my CS3233 student:
10700-10749: Huang Wenjun (HW)

Total hints in this volume: 30

10700 - Camel Trading

Easy problem, the difficulty is in the coding... If you want to maximize the overall value, do all additions first, and then multiplication. In the other hand, if you want to minimize the overall value, do all multiplications first, and then additions.

Alternative: 10700 requires us to find the min and max of a math expression with only + and * operator and number from 1 to 20. Use greedy
algo. For max, sum first then plus. For minus, time first then sum.

10701 - Pre, in and post

It is in Graph theory that if you are given preorder and inorder tree traversal, you will be able to reconstruct the tree (thus solve the problem of outputting the postorder traversal).

The key idea is that the first node in preorder traversal is the root.
Then, find this root in the inorder traversal. Left subtree and right subtree from this root will be the next subproblem that you need to solve.

Preorder: ABCDEF, 'A' is the root
Inorder: CBAEDF, find 'A' in the inorder traversal, 'CB' and 'EDF' is the left & right subtree

Figure out the pattern and then decode the postorder traversal.

Alternative: this problem requires us to print the post order tranversal of a binary tree given the preorder and inorder traversal. Requires ingenuity to come out with short code. Recursive in nature.

10702 - Travelling Salesman

Use DP. Create a 2D array overallProfit[V][D], where V is the current city and D is total days left. Initially, all cells is filled with -1 (null). Then, fill overallProfit[cities listed in E][0] with 0, this will indicate our base case that last cities will have 0 values. Then, from all cities i with day D and non null profit, update the profit for the neighbouring cities j with D+1 days left:

overallProfit[j][D] = overallProft[i][D-1] + profit[i][j]

This problem is similar to 10681 - Teobaldo's Trip

Alternative: 10702 requires us to find the maximum profit a businessman can earn by going through a set of city. It suffices to use a
array of size 110 to represent the city since we know the starting city. We build a array which get updated every cycle.
Cycle one represents the profit by going from point A to point B directly. Cycle 2 represents the maximum profit by going
from point A to some point that is not B and from that point to B.

10703 - Free spots

Brute force will do. Set up a Boolean matrix "isFree" of size 500x500, all initialized to true. Then fill in the covered spots as given in the input (set the cell value to false). Finally count how many 'true' cells in the matrix. Output the result accordingly (when the case is 0, 1, or more than 1).

Alternative: 10703 requires us to find the number of uncovered block in a board of certain width and height when certain rectangular
blocks are used to cover the board. Tricky part is the x1 and x2 ( and y1 and y2). x1 may not be smaller than x2.

10705 - The Fun Number System (by: Vahe Musoyan, Bugz Podder)

By: Vahe Musoyan

n is our number.
i = k

for i = k downto 1
{
  if (n is odd) then it contains i-th bit in it's FNS representation
  {
    used[i] = true;
    if (i-th bit is with a + sign)
      n--;
   else
    n++;
  }
  n = n / 2
}

in the end if n == 0 then
  print the array used
else
  print that it is not possible

In this algorithm we simulate the operation backwards.
At first we consider that it is possible and try to guess how it is represented in FNS.
And in each step we can surely no wheter a bit is used or not.
If our consideration was correct we get n == 0; else n != 0;

By: Bugz Podder

instead of the greedy algorithm, the brute force algorithm with a little backtracking does the trick. just try all 2^N possibilities... but and the backtracking is based on the idea that
2^0+2^1+2^2+...+2^(k-1)=2^k - 1<2^k... so terminate the recursion when you have something like that (i.e. don't try to make a value of 2^k or greater when you can only use the ones from 2^0 to 2^(k-1)). The runtime for this algorithm gave me 0.00.002

10706 - Number Sequence

1 12 123 1234
Find the pattern, and solve it...
You may want to refer to problem 10427 - Naughty Sleepy Boys, an easier version of this problem.

10707 - 2D-Nim

Compare the similarity between two boards. I solve this by converting each cluster into a specific index.

x = vertex
- = edge

Then, for the following vertex and edges, I will give a value as follows:

--x   => 1

--x-- => 2

--x-- => 3
  |

  |
--x-- => 4
  |

  |
--x   => 5

Thus for the following cluster, I will give a value: 19 (5+5+5+3+1)

x--x
|  |
x--x--x

I will do this for all cluster in board 1 and board 2, sort the values, and finally compare the two set of values. Only if all of them equal, then I will declare two boards as compatible (Yes), otherwise output No.

Alternative: 10707 requires us to check if two board are equivalent in the sense that the two board has the same number of same-shape section. To check for same shape, define six basic shapes and for board1, count the number of the six basic shape. Do likewise for board2, Check if number of each shape on board1 equals that of board2 and output accordingly. Question is not clear that the order of stating the pieces does not represent the piece name in each board.

10709 - Intersection is Not that Easy

This problem requires us to find the distance of a line segment or line from another line segment. Find equation of line even for line segment. Check cases of parallel for line or line segments (determinant=0). Otherwise, check for intersection between the line (for a line segment, assume they are lines and then see if intersection point is between the range of x and y ).

10713 - Map

This problem requires us to find the path to reach the treasure from a landing point. Only 8 cardinal direction are allowed. Trick of this question is that most people will think that since circle is convex, a person can reach the treasure from the landing point without going beyond the circular island. However, given the 8 cardinal directions, it is possible to go out if for example you go north first before going northeast or sometime you go northeast first before going north. Need to check all the test. Expert coders may be able to code this by considering a few cases whereas cumbersome one may need to exhaust all the case. Should not use sqrt(2.0f), use calculator to calculate and define macro. Do not use 2.0f else double not accurate to 10dp.

10714 - Ants

After some observation:

the shortest time for all ant to fall down will be determined by the shortest length among all ants in position x to left side of the pole (length: x-0 = x) or to right side of the pole (length: l-x).

the longest time for all ant to fall down will be determined by the farthest length among all ants in position x to left side of the pole (length: x-0 = x) or to right side of the pole (length: l-x).

Alternative: 10714 requires us to find the minimum time and maximum time taken by ants on a rod to fall off the rod with carefully chosen
initial direction of all the ants. It is easy to see that the minimum time is when there is no collision (i.e all ants on left side of the middle of rod move left and all ants on right side of middle of rod move right. For the maximum time, it is intuitive that more collision will lead to more distance travelled by all the ants implying a longer time taken. However, it will lead to TLE if we try to stimulate it. Observe the input carefully to observe that the longest time is the max(time for leftmost ant to reach RHS, time for rightmost ant to reach LHS). This is quite similar with the minimum time formula max(time for leftmost ant on RHS of middle to reach RHS, time for rightmost ant on LHS of middle to reach LHS). The proof is hard to establish though.

10716 - Evil Straw Warts Live

This problem requires us to find the number of swaps needed to turn a string into a palindrome or ouput impossible if string cannot be turned into a palindrome. Use greedy algo. First check if the string can be turned into a palindrome by checking the frequency of letters. If only one or zero letter have odd frequency, then string can be turned into palindrome. To check the number of swaps needed, keep a table of leftmost idx(to count the number of position to the right of the leftmost letter of the first-occuring letter) and rightmost idx(to count the number of position to the left of the rightmost letter of the first-occuring letter) for each alphabet that appears in the string. Find the sum of the two array for each alphabets. The least of the sum array will be the letter to shift to the leftmost and to the rightmost and the least sum will be the number of shifts needed. This will result in a truncated string. Continue until 1 or 2 letter are left. The greedy algo is hard to see and hard to prove also.

10717 - Mint

This problem requires us to find the min and max height of a table formed with a set of coin with distinct coin type for its four legs. This is an ad hoc question. Implement the following algo. if coin={50,100,200,400} and desired table height is 1000, find the closest multiple (that is smaller) of coin thickness for each coin type. coin becomes {1000,1000,1000,800}. Check if there are at least 4 of maximum=1000. If yes, output 1000, else look for 2nd maximum which is 800. Repeat the above step with desired table height=800. Implement the same algo for max height of table.

10718 - Bit Mask

This problem requires us to find the minimum M that will give the maximum M or N where M lies within a range (L,U). Use greedy algo. Start finding the MSB of the answer. Set bit to 1. Check if it is greater than U. If it is, set bit to 0. If not, check if bit of N at that bit position=1. If =1, check if you set bit to 0 will lead to ans less than L. If it will lead to ans less than L, dont set it to 0, else set it to zero. Hard to come up with greedy algo.

10719 - Quotient Polynomial

Pretty straightforward. And if I am not mistaken, this problem already appear previously in other volume...

Alternative: 10719 requires us to print the coefficient of the quotient and remainder when a polynomial is divided by x-k. The input needs
to be retrieved using istringstream and its eof() function. The input given by the UVA judge is problematic as it prints -5 as ^u5. Need to edit the - accordingly. The input could be 0 0 0 0 5 which means the polynomial is 5. The ans to print is also 0 0 0 0 for the quotient. No need to remove the leading zero. When the input is just 5. The quotient should not have anything after the : ("q(x) :"). Need to print new line at the end of every test case, even the last. This is a Math problem. Need to do some algebraic Math before translating it to code.

10721 - Bar Codes

10721 requires us to find the number of ways to produce a barcode of given length (len), number of segment(seg) and the maximum(max) length that the longest length can take. Use 3D DP. 4 base case: a) max>len => 0. b)seg=1, i)len==max => 1 ii) len!=max => 0 c)len<max+seg-1 =>0. This dparr will store the number of ways toproduce a barcode of given length, number of segment and the maximum length(compulsory) that the longest length can take. Output must then be summing out the possible maximum length from 1 to max. Use long long = 64 bits.

10724 - Road Construction

This problem requires us to find the road to built to maximise the efficency of the road network. The increase in efficiency of the road network is measured by the summation of the difference of old distance from node i to node j before a particular road was built and the new distance after the road is built. If the increase in efficency is less than 1, then no road should be built. Use Floyd Warshall algorithm. Later, for each edge built, find the cost fn of it by summing all the efficiency of different node-to-node distance when that edge is built. At the same time, save the maximum cost function and its associated weight and the 2 nodes involved. As this question involves double use epilson 1e-10 to check >,<.

10733 - The Colored Cubes

This problem requires us to find the number of unique cubes given different number of color to color the sides of the cube. This question requires the knowledge of Polya-Burnside theory to count equivalence class. Once you understand the Math behind, you can write a polynomial answer for output. The answer for this question is (n^6+3n^4+12n^3+8n^2)/24.

10734 - Triangle Partitioning (by: Eduard Piliposyan)

This problem is easy and can be solved recursively. You must remember all triangles and stop, if during recursion you get such triangle that you already get before. Because N is small this algorithm will finish very fast.

Alternative: 10734 requires us to partition a triangle using the median of its longest edge and find the total number of type of triangle formed. We are assured that the number of triangle is less than 100 so we could just use recursion to perform the dividing and insert into library if a certain type of triangle cannot be found in the list. Use array instead of map to store the triangle dimension as using double as key in map is dangerous. Use "fabs(trianglelist[0][i]-side[0])<0.000001" to compare if a particular dimension can be found in the triangle list. Normalize the triangle length to its longest edge. Do the Math on paper to reduce the cosine rule to algebraic Math.

10738 - Riemann vs Mertens

The problem is easy. It depends on how you optimize your algorithm. My algorithm use the idea of modified Sieve.

Here is my algorithm:
Prepare a Boolean array squareFree[1..1000000], initialize them all to true
Prepare an integer array totalPrimeFactors[1..1000000], initialize them all to 0

Then do modified sieve:
loop from 2 to 1000000, but this time,
instead of deleting multiples of 2, I increment the totalPrimeFactors of multiple of 2 by one,
and then go on to 3, increment totalPrimeFactors of multiple of 3 by one,
and then go on to 5, increment totalPrimeFactors of multiple of 5 by one,
and so on.
At the end, for each number i, I will know how many "distinct" prime factors make up this number :).

loop again from 2 to 1000000, this time update the squareFree flags,
instead of deleting multiples of 2, mark squareFree of multiples of 4 (2*2) as false
and then go on to 3, mark squareFree of multiples of 9 (3*3) as false
and then go on to 5, mark squareFree of multiples of 25 (5*5) as false
until 1000 (1000*1000 = 1000000).
At the end, for each number i, I will know whether this number is squareFree or not.

The rest is easy.

Alternative: this problem requires us to find the mu and mobius of a number from 1 to 1,000,000. Precalculate. Modify Sieve so that sieve[number] will contain the number of unique prime. Later, turn odd number into mu=-1 and even number into mu=1. For not square-free number, they are 2*2=4, and all multiples of 4 and 3*3=9 and all multiple of 9, etc. Use a boolean array to keep track of that. If boolean is false, change mu to 0. Also compute mobius by summing up the mu from bottom up.

10739 - String to Palindrome

This is a DP problem. For string[1..n], the problem can be solved by the following recurrence:

cost(string[l..r]) = 0 if l >= r, which denotes 1 element string or empty string or,
cost(string[l..r]) = cost(string[l-1..r-1]) if string[l] = string[r], this is obvious.
cost(string[l..r]) = 1 + min(cost(string[l-1..r-1]), cost(string[l-1..r]), cost(string[l..r-1])),
if string[l] != string[r], which models the possible operations given in the problem description.

Use memoization to optimize overlapping sub-problems.

Alternative: this problem requires us to find the number of edit operations to change a string to palindrome. Use DP. Look at leftmost and rightmost character at a time. If they are the same, look at the inner string (no operation is needed). Need to convince yourself that insertion is not needed in this question. Use delete for left or right character to achieve the same operation as delete.

10742 - The New Rule in Euphomia

Create a list of prime numbers, there are around 80.000 prime numbers in range [2 .. 1,000,000]. We will need two distinct prime numbers a and b, where a + b <= n. Loop from 2 to prime number less than n, counting the number of way to do this addition. Hint: use binary search to speed up the searching of prime number in the array of 80.000 (sorted) prime numbers...

Alternative: 10742 requires us to find the number of way to pay a certain amount of money with two distinct coin with some or no 1 cent
coin. The coin denominator are all prime. First find all the prime less than 1 million through sieve. Then put it in a sorted array. Then binary search the number of ways to produce a sum less than or equal to the sum to pay.

10746 - Crime Wave - The Sequel

10746 requires us to find the minimum time of dispatching car to the crime scene. Use DP by keeping a state number. Number of states are 2^cars. Reuse coding from Duilian, Contest 1 adapted from Team 5. Forum says other method of solving is Min-Cost Max-Flow. Used Bellman-Ford algorithm to check for negative cycle and Ford-Fulkerson algorithm to flow. Accuracy is important for question concerning floating number. 0.015 printed in 2dp could become 0.01 instead of 0.02 (proper rounding). Use + 0.000005 for proper rounding off.

10759 - Dice Throwing (by: Eduard Piliposyan)

This problem can be solved using DP or PIE (Principe of Inclusion and Exclusion). PIE Is more general. You can find formula using PIE. The problem is very similar to 10238-Throw the dice.

10763 - Foreign Exchange

Sort the pairs (A,B) according to their A values. Then, for all pair (A,B), find the corresponding (B,A) in the list by using binary search, once found, mark the pairs as used. At the end, output "YES" if all pairs are used, output "NO", otherwise.

10771 - Barbarian Tribes (by: Eduard Piliposyan)

The answer for this problem is just one operation, the code is only 3 lines. But for finding the answer you must simulate the process than precalculate answer for small n and m, then You will find the solution.

The answer is: if (m%2==0) cout << "Gared"; else cout << "Keka";

10776 - Determine The Combination

I still got TLE... you can't enumerate them all and then print... there must be a more sophisticated way to do this...

10780 - Again Prime? No time.

I will illustrate my solution using this example: m = 24, n = 4, the answer is 1
Split m into its prime factors -> m = 2^3 * 3^1
Then loop from i = 2 to (n=4)
  there are 1 '2' in i=2, 0 '2' in i=3, 2 '2' in i=4, total: 3
  there are 0 '3' in i=2, 1 '3' in i=3, 0 '3' in i=4, total: 1
Pick the minimum from 3 and 1... => 1

Another example: m = 2, n = 10, the answer is 8
Split m into its prime factors -> m = 2^1
Then loop from i = 2 to (n=10)
  there are 1 '2' in i=2, 2 '2' in i=4, 1 '2' in i=6, 3 '2' in i=8, 1 '2' in i=10, total: 8
Output 8

10783 - Odd Sum

Very-very straightforward... Just do it in less than 2-3 minutes...

10784 - Diagonal

The number of diagonals in n-gon is n*(n-3)/2.
Therefore you need to calculate n such that:
n*(n-3)/2 >= N
n^2 - 3*n - 2*N >= 0
with a = 1, b = -3, c = -2*N, use this formula: n = ceil((-b + sqrt(b*b - 4*a*c)) / 2*a)

10785 - The Mad Numerologist (Notes from: Sabuz Hassan)

I haven't got this correct, but roughly it should be a simple string enumeration problem...

10789 - Prime Frequency

Simply count the number of occurrences of each character, and then if the number of occurrences is prime, print the character... if no such case, print 'empty'.