You are my friends and the greatest love a person can have for his friends is to give his life for them.
- The Passion of the Christ -

Last updated on: 07 August 2008 12:02:47 PM

Comment on this volume: This is the first volume containing problems not from ACM ICPC contests. The problems here are set by some professionals out there. And most of them are mathematical questions rather than algorithmic question, which is a bit funny I think... This volume is still "normal", wait until you see the subsequent Volume Contest problems, you'll start asking whether this is a mathematical OJ or algorithmic OJ :p

Total submit-able problems in this volume: 100
Solved problems: 36
Problems in Wrong Answer list from this volume: 11
Unattempted problems: 53
Total hints in this volume: 44

10000 - Longest Paths

You have to determine the longest path from a given Graph. There is no other way other than exhaustive search.

Build an adjacency matrix (or any other graph representation that you like) and start traversing. The simplest one is using Depth First Search (DFS) to traverse all possible paths, and remember the longest paths (and if there are two or more paths with similar longest path, record the SMALLEST END ROUTE !!!). After there is no more paths left, output the longest paths.

Take note that you must prune the search tree as soon as possible. I.e. if you have visited a particular node with path length = 5, then if you somehow re-visit this node using another path, but with length = 4... quickly prune and backtrack, since it will be useless. This way, you can avoid Time Limit Exceeded.

10003 - Cutting Sticks

Exactly similar to matrix-chain multiplication problem (Refer to: Introduction to Algorithms book). Do a complete search through all possible combinations, and apply dynamic programming to it. This problem exploits many repeating sub problems and using DP is compulsory.

10004 - Bicoloring

Simply traverse the graph using Breadth First Search, and flip flop the color along the way, i.e. If current node color is "black", then all neighbors of this node (can be reached by one-step BFS) must be colored with "white" and vice versa.

10005 - Packing Polygons (by: Hadi Moshayedi)

I consider every pair of points, then I suppose that these two points are on the border of circle. using this, I find the center of the circle. then I calculate the distance of other points from the center. if all points are in distance less than R, a solution has been found, and the polygon can be packed in the circle.

10006 - Carmichael Number (corrected by: Tommy Lofstedt)

Carmichael numbers are odd numbers which have at least three prime factors, but also, a number is a Carmichael number if and only if it is square-free (that is, it has no repeated prime factors) and for all prime factors p of the number n, p-1 must divide n-1 (that is, p-1|n-1 for all prime factors p of n).

The last two rules are the only ones necessary, but filtering with the first two will make finding the numbers a lot faster.

See these links for more information:
http://mathworld.wolfram.com/CarmichaelNumber.html
http://en.wikipedia.org/wiki/Carmichael_number

You can do brute force calculation and then just pre-calculate the output. There are only 15 Carmichael numbers below 65000 and those 15 numbers are: 561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, and 63973.

10007 - Count the Trees

The number of binary tree can be counted using Catalan Number. Here is the efficient way to compute Catalan numbers bottom up using DP.

Catalan Number: (2n C n) / (n+1)

Catalan(n) =

2n!
---------------
n! * n! * (n+1)

Catalan(n+1) =

2*(n+1)
--------------------------- =
(n+1)! * (n+1)! * ((n+1)+1)

(2n+2) * (2n+1) * 2n!
------------------------------- =
(n+1) * n! * (n+1) * n! * (n+2)

(2n+2) * (2n+1) * 2n!
----------------------------------- =
(n+1) * (n+2) * n! * n! * (n+1)

(2n+2) * (2n+1)
--------------- * Catalan(n)
(n+1) * (n+2)

From the pattern above, you can calculate Catalan number bottom up. However in this problem, you must time the result by N! because the trees can be flipped...

You may be interested to solve problem 10303 now :), very very similar

10008 - What's Cryptanalysis?

A simple alphabet frequency counting and then output the frequency in descending order... Very easy =)

10009 - All Roads Lead Where?

Read the input and convert them into graph representation according to your style. For each pair of cities given, output the shortest distance between them. You can use BFS to solve this problem.

10010 - Where's Waldorf?

Read the input into 2 dimensional array. Then check all coordinate (from uppermost+leftmost) and all 8 directions (N,NE,E,SE,S,SW,W,NW) for the desired word.

10012 - How Big Is It?

Greedy won't work. You must do exhaustive search. Maximum number of circles is 8. Exhaustive permutation is 8! = 40.320. With pruning it is acceptable. For each ordering, calculate the smallest width by using phytagoras rule.

10013 - Super long sums

Given two m digits integer, output the sum of them.

Sacrifice memory for this. Declare an array with size 1.000.000.
When you read the input, add them directly and then store the value to the array.
After that, normalize the value and output them.

 9   8   7   6
 5   3   7   5
---------------+
14  11  14  11

Step by step normalization
14  11  15   1
14  12   5   1
15   2   5   1

Result = 15251

10014 - Simple calculations

At first, I totally confused until I found solution in the Internet.

This is how to derive the formula:

a1=(a0+a2)/2-c1
2a1=a0+a2-2c1
4a1=2a0+2a2-4c1 ... (1)

a2=(a1+a3)/2-c2
2a2=a1+a3-2c2 ... (2)

Combine (1) & (2)

4a1=2a0+(a1+a3-2c2)-4c1
3a1=2a0+a3-2(c2+2c1)

... and so on until n-th term ...
(n+1)a1=n*a0 + (an+1) - 2(n*c1 + (n-1)*c2 + (n-2)*c3 + ... + 1*cn)

You can calculate a1 from formula above, and don't forget that this problem is in multiple input format.

10015 - Joseph's Cousin

This problem is variant of problem 305-Joseph. Now we use prime numbers to count which person to kill... So, pick up your 305 solution, and again simulate the 'killing' process (the circular array stuffs..., you can use linked list but simple array with appropriate shifts after one person killed is enough to pass the time limit), but this time use prime numbers.

I advise you to pre-generate the first 3501 prime numbers and save this in an array, it will save you a lot of time.

10016 - Flip-flop the Squarelotron

A very very tedious array manipulation problem. Basically what you need to do is to create 2D integer array, and shifting it contents according to the problem description. You need a lot of debugging to solve this problem. Indeed, this is a very good problem to test your array manipulation skill... I'll give you some trick:

Let outermost ring as ring 0 and innermost ring as ring ceil(N/2)
You can simplify your coding by "forgetting the inner rings" by doing this:

Original:

aaaa
bbbb
cccc
dddd

After UpsideDownFlip(ring 0) => (actually I flip all from ring 0 and ring 1 ...)

dddd
cccc
bbbb
aaaa

I'll fix the mistake by calling UpsideDownFlip(ring 0 + 1 ~ ring 1)

dddd
cbbc
bccb
aaaa

This will save you a lot of coding time...

10017 - The Never Ending Towers of Hanoi

Simulate the process of solving Towers of Hanoi problem. A well known problem and there are a lot of websites discussing this Tower of Hanoi problem, please refer to these websites. However, I still find that Towers of Hanoi is a bit complex...

10018 - Reverse and Add

Just do what they want. They guarantee that the input case will have answer, doesn't need more than 1000 iterations to solve, and will not overflow. These 3 condition simplifies the problem a lot. =)

10019 - Funny Encryption Method

You don't have to do Xor at all, what they want is from a given input number M, how many '1' this M in binary format (we call this total->'b1') and how many '1' this M in hexadecimal format (we call this total->'b2'). Simply convert M to binary and hexa, and then count how many '1' in these two representations of M.

10020 - Minimal coverage

Greedy solution works, sort the input line segments by Left side first, and if Left side equal, sort by Right side, and then greedily choose the one which Left side <= current left, and Right side is the rightmost (with current left initially set to 0 => because we want to cover 0..M). After we choose one line segment, we update current left with Right side of this line segment, and repeat the procedure until the Right side of chosen line segment exceeds M (which means we successfully covered 0..M). Print "0" if we cannot find any possible combination to cover O..M.

10023 - Square root

Y can be as big as 10^1000... very big number... I thought of using BigNumber and calculate manually, but the a function 'sqrtl' in math.h is enough to solve this problem... -_-. It's okay anyway :)

long double Y;
scanf("%Lf",&Y);
printf("%.0Lf\n",sqrtl(Y));

10025 - The ? 1 ? 2 ? ... ? n = k problem

To simplify the problem:

1. The smallest n that satisfy the formula can only occur if and only if the "?" is not alternating positive/negative => it's not like this 1+2-3+4-5..., this will make calculation longer.

2. The value for n will be the same for both k and -k, so don't bother about negative k, just get the absolute value of k to find n.

3. For the arithmetic series above, the total Sum formula is Sn=n(n+1)/2, we will use this.

Assume 1+2+...+i=k, then by arithmetic series formula
i(i+1)/2=k
i^2+i-2k=0
i=(-1 + sqrt(1-8k)) / 2  /* get the root */

This i will be used as starting value to get the final answer "n"

if (i*(i+1)/2 == k) then okay,
but if (i*(i+1)/2 < k) then we have to increase this i (we still need more)
  when to stop increasing i?
  if and only if (i*(i+1)/2 - k) can be divisible by two...
    why?
    k+2z=i(i+1)/2
    for example:
        1+2+3+4+5+6+7==28     (i=7)
        28-12=16 is divisible by 2... and 16/2 is 8
        this 8 is actually combination of -1-7=-8 (the negative part)
        the smallest n to satisfy the formula above is 7 => -1+2+3+4+5+6-7==12

10033 - Interpreter

Just simulate what they want..., straightforward.

10034 - Freckles

A basic Minimum Spanning Tree problem, refer to your algorithm book regarding how to compute MST, and now they change this problem to Multiple Input format. For those who got WA after re-judge, don't worry, just change your code into Multiple Input format and send again =)

10035 - Primary Arithmetic

Simply calculate total carry.
(note, if total carry>1 you must output ''operations" instead of "operation").

10036 - Divisibility (By: Gawry)

Looks simple but if you use brute force (count all possible values of +/- for N numbers) then determine whether it is divisible by K or not, then your solutions possibly get Time Limit Exceeded.

Use mathematical properties + Dynamic Programming

Let d[1],...,d[N] be sequence of N integers and t[I,J] (2 dimensional array, but after some considerations, we'll find out that we only need 2 linear array of size J) be true iff we can place +/- operators in the sequence of first I integers so that result = J (mod K).

We can use DP to calculate t[I,J] for all [I,J]:

for i=1
t[1,j] = true for t[1,j] where j=abs(d[1]) mod K

This means: You divide one integer (the first integer from N integers) with K, get the remainder, t[1,remainder] is set to be true.

for i>1
if t[i-1,j] true then
  t[i,(j+abs(d[i]) mod K] = true /* add */
  t[i,(j+K-abs(d[i]) mod K] = true /* substract */

This means: For the 2nd integer up to Nth integer, you either add it with previous remainder modulo K or substract it with previous remainder modulo K, to get another remainders in the range [0..K] that can be reached using combination of i integers.

Answer should be Divisible iff t[N,0], which means, you can arrange +/- operators in the sequence of N integers, with remainder 0 / divisible.

10038 - Jolly Jumpers

Simply do what they want.

10041 - Vito's Family

Brute force calculation, simply try all possible location of Vito's House, choose one that minimizes sum of distance with his relatives.
Hint: Sorting can simplify this problem, think about it...

10042 - Smith Numbers

This problem is similar to 583-Prime Factors, you only have to sum up the digits, easy.

10048 - Audiophobia

Can be solved easily using O(N^3) Floyd Warshall All Pairs Shortest Path. Read my programming section for explanation of Floyd Warshall.

10050 - Hartals

The easiest way is to store a big array of boolean, hartal_days[3651], initially all false. Then for each party, flag the days which they have hartal. Take note about Friday & Saturday. Finally, count how many working days flagged..., simple.

10051 - Tower of Cubes

The underlying algorithm for this problem is Dynamic Programming solution for Longest Increasing Subsequence. However, you have to handle specific case with the cubes first. Good luck.

10055 - Hashmat The Brave Warrior

Use long long data type (that means use C++ compiler) + absolute function (create this function yourself, standard abs is not enough).

10060 - A Hole to Catch a Man

Pure math problem. Just be careful with precision error. Use epsilon rather than direct equality for floating point numbers, i.e. instead of doing this: X == Y, you do this X - Y < 0.0001, where X and Y are floating point numbers.

10062 - Tell me the frequencies!

Simply count the ASCII frequency and output them in ascending order of their frequencies.

10066 - The Twin Towers

Simple Longest Common Subsequence (LCS) problem. Refer to my Dynamic Programming page regarding LCS.

10067 - Playing with Wheels

You can model this problem as a graph. You always have 8 ways to do branching (there are 4 numbers, for each number you can either turn the wheel to the left or turn to the right) minus the forbidden states if encountered.

So, what you need to do is to start from initial configuration, and then do a graph traversal algorithm to reach the target configuration.

10071 - Back to High School Physics

Simplest problem ever... just output 2*v*t

10074 - Take The Land (by: Maeenul)

This is a problem similar to the 108 (Maximum Sum) and 10667 (Largest Block).
 
First fill the input matrix with 1 where the input is 0 and fill the 1s with some very big negative number. The negative number must ensure that it is bigger (in magnitude) than the total number of matrix entry (such as -n*n). Then simply find the maximum sum from the matrix. That's it.

10075 - Airlines

Another all pairs shortest path problem. The most difficult part is in determining the shortest distance on a sphere (earth). It is hard to solve this problem without knowing the formula, please refer to my computational geometry section to find out the formula. With this formula, the rest is solvable using Floyd Warshall.

10077 - The Stern-Brocot Number System

Just do a simple binary search, starting from m1,n1,m2,n2 = (0,1,1,0), keep finding total m = m1+m2 and total n = n1+n2, go to left, right or stop according whether current
total m/total n is greater, lesser or equal to desired m/n, respectively.

10079 - Pizza Cutting (Proof by: Waldek Jarosik)

If you can derive the formula, this problem will be very simple. Just count (n+n*n)/2 + 1.

1+n*(n+1)/2 Proof by Yaro (Waldek Jarosik):

We start with 0 cuts - in this case we have one piece of pizza.
Consider we have n cuts done, whose gave us the maximal number of pieces.
Now let's think about what is the 'best' (n+1)-th cut
(a cut which gives us the maximal number of pieces).
If we draw a circle with some cuts done, it's easy to notice that the number of pieces is:
previous number of pieces + 1 + number of previous cuts intersected by our new cut.
There is always a way to make the cut that intersects ALL previous cuts.

This gives us a simple recursive formula:
  t[0] = 1 (whole pizza)
  t[n] = t[n-1] + n, n>0 (previous number of cuts + 1 + n-1)

But we can't save so big array in memory (210*10^6) that's why we are looking for generalized formula.

Let's look at this:
  t[n] = t[n-1]+n = (t[n-2]+n-1)+n = ((t[n-3]+n-2)+n-1)+n and so on..

In the end we reach the formula:
  t[n] = t[0] + n-(n-1) + n-(n-2) + n-(n-3) + ... + n =
    = 1    + 1       + 2       + 3       + ... + n =
    = 1 + (1+n) + (2+n-1) + (3+n-2) + ... + (floor(n/2) + ceil(n/2)) =
    = 1 + (n+1) + (n+1)   + (n+1)   + ... + (n+1) [(n+1) occurs n/2 times]
    = 1 + n*(n+1)/2

10080 - Gopher II

This problem is a maximum bipartite matching. Find the best assignment of gopher and holes. First, construct the bipartite graph. Left side: Gophers, Right side: Holes. Draw an edge from Gopher i to Hole j iff distance between Gopher i and Hole j is within v*s time (remember your physics: v*s = distance covered).

After you build this graph, just pass this to your Max Bipartite Matching or Network Flow algorithm to get the result. Done.

10082 - WERTYU

Simply simulate what they want.

10092 - The Problem with the Problem Setter

The underlying algorithm for this "complex" problem is Maximum Flow.

       ->(capacity c1) -> Category1       Problem1 (capacity 1)-->
Source ->(capacity c2) -> Category2 -**-> Problem2 (capacity 1)--> Sink
       ->(capacity cNk)-> CategoryNk      Problem3 (capacity 1)-->
                                          ProblemNp(capacity 1)-->

** Draw edge from category i to problem j if problem j can be classified to category i (set capacity of these middle edges as 1)

Pass this Flow Graph to your Network Flow algorithm (Ford Fulkerson, Edmund Karp, or anything else that you know) to get the maximum flow. Output "1" and the selection of problems/category if all categories has max flow. Output "0" otherwise...

The conclusion is: to solve this problem, you must study Network Flow algorithm first...
You can notice that this problem is VERY SIMILAR to 10249 (but 10249 is a special version of this problem -> 10249 can be solved using Greedy algorithm)

10093 - An Easy Problem

Convert the 0..9, A..Z (10..35), a..z (36..61) representation to standard number first, I called it 'num' and then starting from the highest index, find the smallest N (2<=N<=62) such that num modulo n == 0, then output num+1. (0..1 => base 2, 0..9 => base 10, always +1).

10098 - Generating Fast, Sorted Permutation

Similar to p195, this one is called anagram, not permutation... I think.

10099 - The Tourist Guide

Use Floyd Warshall O(N^3) All Pairs Shortest Path algorithm. =)