Last updated on: 27 April 2009 04:08:54 PM

Comment on this volume: None

Total submit-able problems in this volume: 100
Solved problems: 27
Problems in Wrong Answer list from this volume: 6
Unattempted problems: 67
Total hints in this volume: 30

10300 - Ecological Premium

Compute the premium, just ignore total_animal. Very very easy. =)

10301 - Rings and Glue

You can solve this problem using backtracking. The main consideration is how you compute that 2 rings intersect...

First, compute the distance between 2 center of rings.

If this distance greater than total radius of ring 1 and ring 2, then these 2 rings are separated too far, no intersection... ignored

If this distance equal with total radius of ring 1 and ring 2, then these 2 rings are touching each other, but only in one intersection... ignored

If this distance + minimum of (radius ring 1,radius ring 2) smaller than maximum of (radius ring 1, radius ring 2), then one of this ring is inside of the bigger ring, again there is no intersection... ignored

Otherwise, they are intersect, count this.

10302 - Summation of Polynomials

I'm not a Math expert... I cannot derive the formula using my brain... However I found this formula from my high school textbook, just use this to get Accepted: (x/2)^2 * (x+1)^2

10303 - How Many Trees?

See my explanation for problem 10007, very similar... But this time you don't need to time the result with N!

10304 - Optimal Binary Search Tree (by: Limon) - I haven't solve this

This problem is just like matrix chain multiplication

Keep a track of the root of all tree
in the third loop instead of k= i to j
write k=root[i][j-1] to root[i][j+1]
update root as well as the cost
because the root of tree [i to j] must not be to the left of root of the tree [i,j-1] and must not be right to the root of the tree[i+1,j]

This will reduce complexity of the three loop to O(n^2).

10305 - Ordering Tasks

Read the input, and do Hill Climbing algorithm (Artificial Intelligence term), which means: keep repeating the rules until there is no more violation to any single rule. If there is a violation, swap the elements, and keep checking.

10309 - Turn the Lights Off (By: Yandry)

Use Gauss method to solve systems of linear equations.

You can obtain 100 equations from the grid that is given in the input, for example:

simple
#O########
OOO#######
#O########
####OO####
###O##O###
####OO####
##########
########O#
#######OOO
########O#

As the light that is in the upper left corner changes its state when we press it, or we press the one at its left, or we press the one at its bottom, we can obtain the equation:

numberofpresseslight1 + numberofpresseslight2 + numberofpresseslight11 = evennumber

Because we must change its state an even number of times since we want it turned off in the final state.

So, you can obtain the 100 equations in the same way and then apply Gauss elimination, using the following rules:

a(plus)b=(a+b)%2
a(minus)b=(a-b)%2

or you may want to use XOR.

10310 - Dog and Gopher

You need to find a hole where dist(dog,hole) >= 2.0*dist(gopher,hole). The only main problem here is the precision error.

However, you can remove the square root in dist() function and transform the above equation to:

distWithoutSqrt(dog,hole) >= (2.0^2)*distWithoutSqrt(gopher,hole)
distWithoutSqrt(dog,hole) >= 4.0*distWithoutSqrt(gopher,hole)

10311 - Golbach and Euler

Prime Numbers again...
some interesting properties:

if n < 3, obviously not a sum of two primes (smallest prime 2+2 = 4)
if n is odd, only 2 + (n-2) is the feasible summation
if n is even, you must check it all

Use a good and fast prime number generator (such as Sieve) to solve this problem.

10323 - Factorial! You Must be Kidding!!!

The only tool that you need is a "long long" data structure... Surprised? me too... simply declare a 'long long' variable, and just do the factorial calculation. Check whether this value is within 10.000 and 6.227.020.800.

HOWEVER!!!, I don't know how come there is a negative input for this problem (I know this from message board). if -even number => output Underflow!, if -odd number => output Overflow!...

Don't ask me whether there exist a negative factorial... I also unsure...

10324 - Zeros and Ones

Declare an integer array "change_counter" with size 1000001, all elements initialized to 0. Now scan the 0-1 input once, every time you encounter a change, increase the counter value. Now anytime you want to know elements within two indices consists of all '0' or all '1', you can simply check whether the change_counter[index1] equal to change_counter[index2]

Example: 101001
Change counter: 0,1,2,2,2,3
If you ask 0-2, then return false (0 != 2)
If you ask 2-4, then return true (2 == 2)
and so on

10327 - Flip Sort

Exactly similar to 299 - Train Swapping. Count the number of bubble sort swaps O(N^2) or you can do better using inversion index counting (Merge Sort) ~ O(N*log N).

10334 - Ray Through Glasses

It is a fibonacci pattern, but use Big Integer since the values are very big.

10336 - Rank the Languages

Read the input data into 2 dimensional array. Then do floodfill for each region + counting this region. Output the result in decreasing order of frequency.

10337 - Flight Planner

This is similar to problem 116. A left to right scanning (using DP). Formulate this problem as DP. You know that for each step, you can only have 3 possibilities: either climb, hold, sink, with their respective wind properties.

10338 - Mischievous Children

Standard formula: N! / (any similar letter)!

Example:
HAPPY, similar letter: 'A' occurs twice, Output: 5!/2! = 60
WEDDING, similar letter: 'D' occurs twice, Output: 7!/2! = 2520
ADAM, similar letter: 'A' occurs twice, Output: 4!/2! = 12
AAAA, similar letter: 'A' occurs 4 times, Output: 4!/4! = 1
AABB, similar letter: 'A' occurs twice, 'B' occurs twice, Output: 4!/(2!*2!) = 6

However, since 12! already outside the limit of unsigned long, how to calculate 20! ??
I was once tried solving this problem using p369 tricks, but got TLE...
The answer is: use "long long" and just directly calculate 20!, "long long" can handle 20! :)

10340 - All in All

The greedy solution works, i.e. use a pointer into the supposed sub-sequence that is advanced if a character matches while you iterate through the super-sequence.

10344 - 23 Out of 5

"bijective function" for "pi" means that the order of operands "a" can be reordered within range 1-5. i.e. a1 can be swapped with a3, a2 with a4, and so on. There are roughly 5! = 120 possible combinations of rearranging the operands.

Operators can be either +,-,or *, and there exist 4 slots, therefore there are only 3^4 = 81 possible combinations for rearranging the operators.

Backtracking will be able to perform those shuffles easily. For each combination, evaluate the expression (remember the brackets!!!), is the result 23? If any of the combinations can reach 23, output "Possible", otherwise output "Impossible".

Example:
1 2 3 4 5 => (((1*2)+4)*3)+5 = ((2+4)*3)+5 = (6*3)+5 = 18+5 = 23, Possible

10346 - Peter's Smoke

Find the pattern and derive the following formula (total_cigar and butt initally set to 0) and simply simulate the process...

while (n > 0) {
  total_cigar += n; /* accumulate all new cigars so far */
  butt += n; /* after Peter smokes these n cigar, we have n butts */
  n = butt / k; /* so these n butts become new cigars */
  butt %= k; /* butts left are reserved for future cigars */
}

10347 - Medians (by: Sohel Hafiz)

Area = 4/3 * sqrt( s * ( s - m1 ) * (s - m2) * ( s - m3 ) );
 
where m1, m2 and m3 are the three medians and
s = 0.5 * ( m1 + m2 + m3 );
 
So output the area if: s * ( s - m1 ) * (s - m2) * ( s - m3 ) > 0.
 
Critical part is that you have to output -1.000 for invalid combinations.

10354 - Avoiding Your Boss

I haven't try this, but quick look at the problem description give me a glimpse of this algorithm:

1. Find the shortest path of Boss (OF, office to BH, Boss's home)
2. Remove all nodes (and all edges adjacent to it) used in the previous shortest path
3. If (YH, your home or M, market) removed in step 2, output MISSION IMPOSSIBLE
4. If in any means you can't reach M from YH, output MISSION IMPOSSIBLE
5. else output the shortest path

10356 - Rough Roads

I haven't try this. However this problem is about finding shortest path with even length using the rule given in the problem.

10360 - Rat Attack

Tackle this problem the other way round... Declare 1025*1025 sized array, initialized to all 0. Each array element represent the coordinate of grid world. For each rat position, add + population to every cells within radius d. After that, scan this 1025*1025 from top,left coordinate to find the biggest value... place your bomb here.

10361 - Automatic Poetry

Read the input pairs, tokenize first line into 5 strings s1,s2,s3,s4,s5, then print this first line as usual, but without '<' or '>'. For the second line, print the original up to '...', then print s4,s3,s2,s5. Very easy...

10363 - Tic Tac Toe

This problem is easy but tricky... Firstly, you have to count how many 'X' and 'O', then you must decide who win and not win (neither win is possible), and then use the following rule:

1. X starts first, so at least X==O or X==O+1
2. Either X win and O not win and X==O+1,
    or O win and X not win and X==O,
    or neither win
3. nothing else

10365 - Blocks

To wrap the gifts, Donald need to stack the boxes into rectangular solid. He need to arrange the items in such a way. The key is that the volume are still the same!!!

So find all possible combination of height h, length l and width w such that h * l * w == n (because there are n boxes with size 1*1*1 = 1 inch^3)

Among all these possible h,l,w combinations, choose the one that has the smallest area.

10370 - Above Average

Simply count the average (can be done on the fly while reading the input), and then print out the percentage of students which are above this average.

10371 - Time Zones

Straightforward problem. Just follow the problem description.

10377 - Maze Traversal

Read the input carefully (a bit tricky), then simply simulate the movement of the robot.

10382 - Watering Grass

Let's analyze.

       r /|
       /  | 0.5*w
|-c--*--c-|-----------
       \  |
         \| 

See the ASCII art above. Sprinkler with origin * and radius r, actually can only fully covers up to length c...  which can be calculated via c = r^2-(1/2w)^2.

Thus maximum coverage of a sprinkler is actually [left = position-c, right=position+c].
Sort the sprinklers based on the left value. Then greedily choose sprinklers that covers the longest, this will be the minimum.

10393 - The One-Handed Typist

Straightforward problem. Just follow the problem description.

10394 - Twin Primes

Pre-generate primes up to 2.000.000 using Sieve algorithm, and then record prime p which p+2 also a prime number. The implementation detail is up to you, however the most important thing is to effectively generate the primes.

10397 - Connect the Campus

This problem is very very similar to 10147-Highways. You are given a list of buildings in campus and a set of pre-defined edges. Now you need to expand the partial-Minimum Spanning Tree. That's it..., Kruskal's MST algorithm is very suitable for this problem. :)