Everyone knows you as a man of honor; I am glad to know you simply as a friend. You have always taken time to be my brother, and I will be standing by you in the end. But I would never put you on a pedestal. I thank the Lord for everything you do. I will be there to pray for you and for the ones you love. I believe that He will finish all He started in you.

I am one of many whose path has been made clearer by the light you have carried faithfully as a warrior and a child. God has used you greatly to encourage and inspire, and you have remained a true friend all the while. But I would never put you on a pedestal, cause we both know all the glory is the Lord's. I will be there to pray that he will keep you by His grace and I always will remind you to be seeking His face.

Should it ever come you time to mourn, I will weep with you. And every single time you win, I am celebrating too. I will celebrate with you. I will be faithful. I will be an open door that you can count on, anywhere you are, anywhere you have been. I will be an honest heart you can depend on. I will be a faithful friend.  --- Faithful Friend by Twila Paris and Steven Curtis Chapman.

Last updated on: 07 August 2008 12:04:10 PM

Comment on this volume: N/A.

Total submit-able problems in this volume: 100
Solved problems: 15
Problems in Wrong Answer list from this volume: 4
Unattempted problems: 81
Total hints in this volume: 22

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.

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.

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

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).

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.

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).

10719 - Quotient Polynomial

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

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.

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.

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.

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...

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'.