Last updated on: 05 May 2009 03:42:04 PM

Comment on this volume: People are starting their own contests, new contest volume is needed. Again... many mathematical questions, try problem 10168 to 10181 for example...

Total hints in this volume: 43

10100 - Longest Match

This is another LCS-DP problem. But this time, instead of characters, the matching is based on words. Refer to my Dynamic Programming page.

10101 - Bangla Numbers

Even though I didn't understand Bangla number system, it seems that the key idea is to read 2 digits by 2 digits from rightmost (minus two digits) except for 1 digit for shata.

Start from the rightmost digit minus two digits, just cycle from shata read 1 digit, hajar, read 2 digits, lakh, read 2 digits, kuti, read another 2 digits, and go back to shata again. So, 45897458973958 will be transformed into something like this 45 89 7 45 89 73 9 58.

10102 - The path in the colored field

In this problem, we will be playing with minimum and maximum...

First, calculate the cost of reaching from any 1 to any 3,
Quick formula: Abs(1.x - 3.x) + Abs (1.y - 3.y).
Then find the minimum for every 1 in the table.
At last, find the maximum of all this numbers.

10104 - Euclid Problem

Search the Net (via google) for this information. "Extended Euclid", use then simply use the formula given. =)

10105 - Polynomial coefficients (By: Maciej Ligenja)

The only component in which xk is in n(k) power is:
, because (x1+..+xk-1)n-n(k) does not contain xk.

And again the only component which contains xk in n(k) power and xk-1 in n(k-1) power is:

, and so on…

The last stage is:

We have a coefficient but in a very ugly form.
We know: n=n(1)+n(2)+..+n(k).
So:

Our coefficient becomes:

10106 - Product

A good problem to test your elementary school mathematic =). Just simulate your elementary school mathematic (use String as your data structure)

10107 - What is the Median?

Another elementary school mathematic =). Just simulate your elementary school mathematic.

10110 - Light, more light

Points to ponder:

1. You only have to care about the last bulb, default state of last bulb is OFF
2. Every i'th walk, only bulbs which serial divisible by i will be toggled
3. Let's examine the last bulb (bulb "n"), all "i" which can divide "n" are factors of "n".
4. See this example: n=36, factors: 1,2,3,4,6,6,9,12,18,36
5. Walk no 1 will toggle last bulb ON, walk no 2 will toggle it OFF, 3->ON, 4->OFF,
    6->ON, 9->OFF, 12->ON, 18->OFF,36->ON
6. See this pattern like this: walk 1 paired with walk "n", walk 2 paired with walk "n-1",
    walk 3 paired with walk "n-3", and so on until walk sqrt(n)
7. In each pairs, if one element toggle last bulb ON, then the other will turn it OFF.
8. Since the default state of last bulb is OFF, then to determine the final state of this bulb,
    you only have to check whether sqrt(n) is an INTEGER or not.
9. If sqrt(n) is integer, then we can find integer x such that x*x=n.
    Walk no "x" will turn the last bulb ON (see example with n=36).

10111 - Find the Winning Move

This problem is just a simulation using backtracking.

You are given an incomplete 4x4 tic-tac-toe board. Currently it is x's turn and asked whether player 'x' can make a forced win. There is no direct formula here... just try from top left (0,0) to bottom right (4,4), try inserting 'x' in this coordinate and recursively check whether 'o' can't do anything to stop x from winning (simulate using backtrack).

Btw this hint may help: if you only have 2'x's and 2'o's (start of the game), there is no winning move... (first sample input)

10112 - Myacm Triangles

Have you solved 478? You can use the formula of knowing whether a point is inside a triangle here. However, this problem is quite complex and floating point related... so be careful.

10113 - Exchange Rates

Dynamic shortest path problem. You know the 'edges' (exchange rate) dynamically. My brother's solution use Djikstra algorithm to find the lowest exchange rate dynamically as new data are materialized.

10115 - Automatic Editing

Simply do what they want.

10116 - Robot Motion

Read the input into 2 dimensional array, start from corner, and simulate the movement. Mark your path and count your path length along the way. If you get outside the grid, then output "<total path length> to exit.". If you encounter marked cell, this means you encounter a cycle. Use your path counter to output the desired values.

10120 - Gift?!

A DP problem. Frank start from left bank and at iteration i, Frank can only jump 2*i-1 meters

Base case: Initially at iteration 1, Frank can jump 1 meter.

Recursive case: From all stone j that Frank can reach at iteration i, then stone[j-2*i-1] and stone[j+2*i+1] also reachable provided that they doesn't fall outside the range [1..N].

Just check whether stone[M] (where the gift is located) is ever reached... Stop the algorithm if no more stones can be reached... (algorithm will definitely terminate because jump length is always increases, it will at one time jump outside range [1..N]).

Now, since N can be very big (up to 10^6), we need to speed up the algorithm by using a special case that when N >= 49, no matter where frog Funny put the gift, Frank will be able to reach it. Proof by induction:

if at N = i, all stones will be reachable then at N = i+1, all stones will always be reachable too because at that time, whatever your jump length is, we can always arrive from any of stone [1..i] to reach stone i+1. This special index happens to be 49 in this case...

10124 - Subway (by: Niaz Morshed Chowdhury)

Let's have some critical calculation.

D - the distance between stations, in metres
M - the maximum allowable speed of the train, in metres/sec
A - the maximum absolute acceleration of the train, in metres/sec2
J - the maximum absolute jerk, in metres/sec3

jtimeaccellimit = A/J
jtimespeedlimit = sqrt(M/J)
jtimedistlimit = exp(log(D/2/J)/3)
jtime = jtimeaccellimit

Now...

if jtimespeedlimit < jtime
  then jtime = jtimespeedlimit
if jtimedistlimit < jtime
  then jtime = jtimedistlimit

atime = (M - J*pow(jtime,2))/A

a = 0.5*A
b = A*jtime + 0.5*J*pow(jtime,2)
c = J * pow(jtime,3) - D/2
r = (-b + sqrt(b*b - 4*a*c))/2/a

if r < atime
  then atime = r

dist = J * pow(jtime,3) + 0.5*J*pow(jtime,2)*atime + 0.5*A * pow(atime,2) + A * atime*jtime
out_put = [4*jtime+2*atime+2*(D/2-dist)/M]

10125 - Sumsets

Simply use O(n^4) algorithm, a 4-nested for loops. Note: my program is currently slow in problem 10125 rank list :-(, to improve the running time, you might want to apply Dynamic Programming.

10126 - Zipf's Law

You only have to be very careful in tokenizing the input. Get the input line by line, tokenize them into words, put them to a very big array of words, then sort them, and finally count their frequencies. If the frequency equal to "n", print them.

10127 - Ones (by: Niaz Morshed Chowdhury)

This is a very easy but tricky problem. If you want to calculate the sequence of one by increasing ONE, then two thing can be happened.

1) If your data type is even long double (in C it is the highest data type), it can not hold the sequence and because of overflow you will get WA.
2) If your data type is string then you will get "time limit exceeded". To avoid these problems we need to follow a trick here.

The Algorithm

input (it will be the input of the problem) 
N=1
one=1 (in this variable finally we get how many one will be in the sequence)

loop until we find the desired answer {
  if N < input
    append a '1'.  (this the way -> N=N*10+1)
    one = one + 1
  k = N mod input  ( k is a variable )
  do this until k = 0, otherwise N = k and repeat everything
}

Example

Let the input is 3
At first N = 1 and one  = 1

Now,
3 | 1 | but here N < input so, append a '1'
one = one + 1 = 2
3 | 11| 3
     9
   -----
     2
Now, k = 2, so, N=k;
again,

3 | 2 | but here N < input so append a '1'
one = one + 1 = 3

3 | 21| 7
    21
  -----
     x

So the output is variable 'one' which contains the value 3

Basically, this problem is a reverse version of dividing a series of '1's with N. In the example above. The step by step of dividing "111" with "3" is like this:

3 |111| 37
    9   => the same '9' that we see above
  -----
    21
    21  => the same '21' that we see above
   ----
     x

So, basically we just simulate this division but without spanning out the actual string of '1's.

This problem is a 0-1 Knapsack problem solvable using Dynamic Programming. Note: Top-down DP may be faster for 0-1 Knapsack problem since most likely not all possible states are visited.

This problem can be categorized as 2-constraints Longest Increasing Subsequence (LIS). First, sort the elephants based on their decreasing IQ, then apply LIS based on their increasing weight to these elephants. You got the answer. This problem is VERY SIMILAR to problem 10154.

This problem is actually just a tedious... error prone... simulation problem. Please read the constraints in the problem description properly... That's all that I can tell you...

The problem with this problem may be related to precision error. Here is solution by Neilor:

double highx = (int)((total/n+0.0099)*100);
double lowx = (int)((total/n)*100);
highx /= 100;
lowx /= 100;
Where total is the total sum of the money and n is the number of students.

Then, test each student money if is > than highx or < than lowx, accumulate (student[i]-highx) or (lowx-students[i]), respectively.
Then, output the variable that have the bigger value.

Find the nearest and most distant adjacent prime numbers within a range L<=N<=U.

Use Sieve of Eratosthenes method.
from L,U (inclusively) we have d=U-L+1 numbers.

bool flag[d];
use flag[i] to mark whether (L+i) is a prime number or not.

1)  mark all to be true
    for (i=0;i<d;i++) { flag[i]=true;}

2) mark even numbers to be false
    if (L is even) i=L else i=L+1;
    for (;i<d;i+=2) { flag[i]=false; }    

3) sieve by prime factors staring from 3 till sqrt(U)
    for (i=3;i<=sqrt(U);i+=2) {
    if (i>L && !flag[i-L]) continue;

    // choose the first number to be sieved -- >=L,
    // divisible by i, and not i itself!
    j=l/i*i;
    if (j<L) j+=i;
    if (j==i) j+=i; // if j is a prime number, have to start form next one

    // now start sieving
    j-=L; // change j to the index representing j
    for (;j<d;j+=i) flag[j]=false;
  }

  // mark 1 to be false, 2 true
  if (L<=1) flag[1-L]=false;
  if (L<=2) flag[2-L]=false;

4) use one iteration to find nearest and most distant adjacent prime numbers.

10141 - Request for Proposal

You don't need to store anything... I'll explain using sample input...

6 4           // read 6 (number of requirements) and 4 (number of proposals)
engine        // IGNORE
brakes        // IGNORE
tires         // IGNORE
ashtray       // IGNORE
vinyl roof    // IGNORE
trip computer // IGNORE
Chevrolet     // for each proposal, read their name
20000.00 3    // remember their price and requirements (higher the better)
engine        // IGNORE
tires         // IGNORE
brakes        // IGNORE
Cadillac      // read the name
70000.00 4    // since 4 > 3, overwrite Chevrolet with Cadillac
ashtray       // IGNORE
vinyl roof    // IGNORE
trip computer // IGNORE
engine        // IGNORE
Hyundai       // read the name
10000.00 3    // since 3 < 4, don't overwrite Cadillac
engine        // IGNORE
tires         // IGNORE
ashtray       // IGNORE
Lada          // read the name
6000.00 1     // since 1 < 4, don't overwrite Cadillac
tires         // IGNORE

// Output "Cadillac"

See... You don't need to store ANYTHING except best proposal name, highest number of requirements, and lowest price (when number of requirements tied).

10142 - Australian Voting

Basically you are given a voting rule and list of votes. What you need to do is determine who is the winner under the voting system. There is no way to solve this other than simulate the process.

10147 - Highways

This is a partial MST problem. You already given fixed edges (highways that already built), and then you are asked to continue spanning the partial-MST (no longer guaranteed the minimum though, that's why I called it partial). See problem 10397 for exactly similar problem.

10152 - ShellSort

In this problem, we are given 2 stacks, original stack and desired stack from top to bottom (remember this). Let's use sample input to understand my greedy algorithm.

Original:     |  Desired:
Yertle        |  Duke of Earl (top)
Duke of Earl  |  Yertle
Sir Lancelot  |  Sir Lancelot (bottom)

Since the only move allowed is to pick a turtle (in original stack) and then ask the turtle climb up to the top of the stack. For example in the first input, if Duke of Earl go outside the original stack and then climb on top of Yertle, you will get the desired stack...

   Duke now here <---|
Yertle               |
     Duke of Earl ---|
Sir Lancelot

Observe the pattern that those in bottom stack didn't need to be altered since it already in the required order (in this case: Sir Lancelot). Now let's see the second sample input, you should be able to get the be very clear after this.

Original:           |  Desired:
Yertle              |  Yertle
Duke of Earl        |  Richard M. Nixon
Sir Lancelot        |  Sir Lancelot
Elizabeth Windsor   |  Duke of Earl
Michael Eisner      |  Elizabeth Windsor
Richard M. Nixon    |  Michael Eisner
Mr. Rogers          |  Mr. Rogers
Ford Perfect        |  Ford Perfect
Mack                |  Mack

Find maximal subsequence of turtles in desired stack (continuously from bottom to top) inside the original stack, stop when you can't expand this subsequence anymore. I will indicate this using numbers, see below.

Original:              |  Desired:
-. Yertle ***          |  9. Yertle ***
6. Duke of Earl        |  8. Richard M. Nixon **
-. Sir Lancelot *      |  7. Sir Lancelot *
5. Elizabeth Windsor   |  6. Duke of Earl
4. Michael Eisner      |  5. Elizabeth Windsor
-. Richard M. Nixon ** |  4. Michael Eisner
3. Mr. Rogers          |  3. Mr. Rogers
2. Ford Perfect        |  2. Ford Perfect
1. Mack                |  1. Mack

This greedy method is minimal and find the unique solution... Now what you need to do is to print out 7,8,9 (Sir Lancelot, Richard M. Nixon, and Yertle), in that order..., why?

Because if you want Sir Lancelot to be 3-rd topmost, you must ask him to go to the top first, and then ask 2 other turtles (in this case, Nixon & Yertle) to go on top of him later.

Greedy works, my solution for this problem is very short :)

10154 - Weights and Measures

* This problem is not really a Longest Increasing Subsequence-DP problem according to message board. I'll re-write my code later.

10161 - Ants on a Chessboard (by: Md. Arifuzzaman)

10162 - Last Digit (by: Zhang Kaicheng)

Use only last 2 digit of N

proof:

last digit of:
n->n^2->n^3->n^4->n^5
1->1->1->1->1
2->4->8->6->2
3->9->7->1->3
4->6->4->6->4
5->5->5->5->5
6->6->6->6->6
7->9->3->1->7
8->4->2->6->8
9->1->9->1->9

You can see that for any digit a:
lastDigit(a^1) = lastDigit(a^5) = ... = lastDigit(a^(4k+1)) for all k>=0
lastDigit(a^2) = lastDigit(a^6) = ... = lastDigit(a^(4k+2)) for all k>=0
lastDigit(a^z) = lastDigit(a^(4+z)) = ... = lastDigit(a^(4k+z)) for all k>=0

Now consider two digit number (ab):
lastDigit((ab+100)^(ab+100)) =
lastDigit((ab+100)^(ab+4*25)) =
lastDigit((ab+100)^ab)) = /* see above -> lastDigit(a^(4*25+ab)=lastDigit(a^ab) lastDigit(ab^ab) /* now apply to the left side */

By the derivation, we only have to keep the last 2 digit, since
lastDigit(xab) = lastDigit(ab)

10164 - Number Game (by: William Anggakusuma)

This is a backtracking + memoization problem. Everytime you read a number, modulo it with N. Next, use backtracking to generate all possible summation of those numbers (after you modulo it with N). Use memoization to memorize the pair {sum, numbers taken} so far. You need to use memoization because there will be many repeating sub problems.

10171 - Meeting Prof Miguel

This problem is a double all-pairs shortest path problem. After analyzing the problem description, you'll see that actually you are given 2 separate directed graph (one for young/Manzoor, one for people aged 30+/Prof Miguel). You also be given the initial starting position of Manzoor and Prof Miguel.

By executing all-pairs shortest path algorithm such as Floyd Warshall to both directed graphs, you'll get:

the shortest paths from initial position of Manzoor to all other reachable places based on Manzoor's directed graph, and

the shortest paths from initial position of Prof Miguel to all other reachable places based on Prof Miguel's directed graph.

Finally, find and output places in City of Hope for which the sum of these Manzoor's and Prof Miquel's shortest paths distance to this place is minimum. If such place exist, output "You will never meet."

10176 - Ocean Deep! Make it shallow!!

The basic thing to do is to modulo the given binary number using 131071 (base 10). See explanation for problem 10551, this problem is just a special case of 10551.

10183 - How Many Fibs?

We know that Fibonacci number can be generated sequentially using addition: i.e.,
given base case fib(1) = 1 and fib(2) = 1, we can have:
fib(3) = fib(1)+fib(2) = 1+1 = 2, then
fib(4) = fib(2)+fib(3) = 1+2 = 3, then
fib(5) = fib(3)+fib(4) = 2+3 = 5, and so on...

Therefore if I ask you how many Fibonacci between 3 & 5, the answers are 3 which can be counted easily along with the generation of those Fibonacci.

The problem is, a and b can be as big as 10^100. Therefore we can't solve this using standard data type, to handle this, use your Big Integer library to solve this problem using the above technique.

10187 - From Dusk Till Dawn

I haven't actually solve this problem. Still WA. But I'm confident it is just a small bug inside my backtracking algorithm since this problem is theoretically needs backtracking algorithm.

10188 - Automated Judge Script

In this problem, you will have to manipulate string a lot. The hardest case is in determining Presentation Error... However, I can give you some hints:

1). Combine correct solution input into one string and submitted solution input into another
     string. After that, checking for accepted condition is a simple string comparison.
     However, we must ensure that n = m!!!
2). Checking for P.E. is only for numeric characters!!!, just ignore the rest...
3). Anything else is Wrong Answer

10189 - Minesweeper

Simulate Minesweeper game, easy.

10191 - Longest Nap

This problem is quite simple but parsing the input may be troublesome. You can simplify the problem by converting the hh:mm format into minutes (09:00 => 9*60 = 360 ; 10:30 => 10*60+30 = 630, etc), then the rest is simply integer comparison, just find the longest gap...

10192 - Vacation

Another LCS problem. Refer to my Dynamic Programming page.

10193 - All You Need Is Love (by: Md. Arifuzzaman)

Convert both integer number into decimal number n1 and n2.
if GCD(n1,n2)>1 print->All you need is love!
else print->Love is not all you need!

10194 - Football (aka Soccer)

This problem is a "simple" multi-field sorting (sorting with many field to consider, in which one field has stronger priority than others). This can be done using a modified comparison function to cater this sorting rule, and simply pass this comparison function to your quick sort method.

However, since the rules are very complex, you must be very careful not to miss a single characters... (oh yeah, sort the team names lexicographically if all others criteria are tied)

10195 - The Knights Of The Round Table

This problem is just a simple mathematic problem, finding the largest circle that can be fitted inside a triangle, given the side lengths of the triangle.

The standard formula can be found in Math books/websites..., here it is:

s = (a+b+c)/2
r = sqrt((s-a)*(s-b)*(s-c)/s)

10197 - Learning Portuguese

There is no specific algorithm to solve this problem. Just do what the problem wants...