What Jesus Christ did around 2000 years ago, is simply an act of substitution. We all, like what I said in the past volumes, have gone astray, each of us has sinned. But God, who should punished us because of our sins, has laid on him, Jesus, the iniquity of us all. God substitutes the one who did wrong, us, with Jesus Christ, the one who was recorded as living a sinless life when He was on earth 2000 years ago. Because of this kind of sacrifice by Jesus, we, sinful human, can be declared righteous in front of God since Jesus has paid the cost of our sins... This opens up the access to heaven... The final question is whether we want to take that access or not?... To be continued in volume 8. See previous story in volume 6.

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

Comment on this volume: This volume consists of some regional problems, many of them are still can't be judged. I said that the difficulty rating for this volume is medium...

Total submit-able problems in this volume: 100
Solved problems: 19
Problems in Wrong Answer list from this volume: 12
Unattempted problems: 69
Total hints in this volume: 25

700 - Date Bugs

This problem is 'similar' to 105-The Skyline Problem and 467-Synching Signals. You can use an array of 10000 Boolean flags to mark the years. Try it

703 - Triple Ties: The Organizer's Nightmare

Similar spirit to problem 626, with additional constraint. Just create three nested loops i,j,k from 1 to N. Check for condition:

1. (i<j<k or i>j>k) and (win[i][j] && win[j][k] && win[k][i])
2. (i<j<k) and (!win[i][j] && !win[j][i] && !win[i][k] && !win[k][i] && !win[j][k] && !win[k][j])

But since this problem requires you to output the total triples first, you need to do this loop twice. First, to count the total, print it, and then do this O(n^3) loop again to actually print the triples.

Or you can do one loop only, insert all feasible triplets into array, then directly print this array later (faster... but sacrifice more memory storage).

706 - LC-Display

This is a pure output-related problem. Just do what they want, precisely. There are various tricks to solve this problem and it is up to your imagination :)

I can say that solving this problem need patience since you must be very precise...

713 - Adding Reversed Numbers

This problem is easy. Just ignore all 'reverse' stuffs... this problem can be solved without reversing anything...

Read in the input as string!!!, no default data type can store up to 200 digits...

Then do basic carry addition to the right (the normal addition is to align two numbers rightmost and then shift the carry to the left).

Example:

 4- 3- 5- 8
 7- 5- 4-
-----------+
11- 8- 9- 8
shift carry to the right
 1- 9- 9- 8

 3- 0- 5-
 7- 9- 4-
-----------+
10- 9- 9-
shift carry to the right
 0- 0- 0- 1
here... ignore leading zeroes

 4- 5-
 5- 5-
-----------+
 9-10-
shift carry to the right
 9- 0- 1
here... don't print "9" only (terminate because there is '0' in the middle
but you should print "901"

714 - Copying Books

This is a classic partitioning problem. You can either use DP to solve this, or use Divide & Conquer method. More details will be placed here later...

725 - Division

Just systematically enumerate all possibilities... Clever brute force approach will be able to pass the time limit.

727 - Equation

Given an infix expression, convert it to postfix.

There are a lot of Infix to Postfix conversion algorithm available in the web. Go and learn the algorithm to solve this problem. You only need one stack to do this conversion.

729 - The Hamming Distance Problem (by: Wei Tu)

You know the length and how many 1's should be in the bit string. Therefore, you can solve the problem by dual recursion first bit is a 0 or 1, with an extra argument of all the preceding bits.

732 - Anagram by Stack

Permute ii..iioo..oo (total 'i'=total 'o'=length of the original word), and then try simulating this ii..iioo..oo using a stack. If our simulation yields the desired output, then print this permutation.

737 - Gleaming the Cubes (by: Wei Tu)

If there is only one cube, then the total volume is the cube. If there's two, it is the intersection of the two. If there's three, the answer is the intersection of the first one intersects with the third. By keeping the vertices of current intersection cube, you'll be able to solve the problem.

739 - Soundex Indexing

Straightforward conversion will do. Just follow their rules :)

740 - Baudot Data Communication Code

What you have to do is simple, decrypt the input using the given table.

Store the decryption table into an 2 array with size 32. One for Up-Shift table, the other for Down-Shift table. These information are given in the first 2 lines of the input.

Read input per 5-characters, then use your binary->decimal technique to convert them to binary. This is the index for your decryption table.

After that just print out the contents of your array with that index. Print Up-Shift characters if you are in Up-Shift mode, or Down-Shift characters if you are in Down-Shift mode. Use Flag to distinguish these 2 state. Remember: The initial state of each message should be assumed to be in the down-shift state.

741 - Burrows Wheeler Decoder

Solving this problem will be much easier if you understand how Burrows Wheeler compression algorithm works. I suggest that you do Google search on the term: 'Burrows Wheeler'. You'll find the decompression algorithm there. The algorithm is in linear time.

743 - The MTM Machine

You need a recursive checker. Formulate your recursive checker based on the rule given. Once it violates the rule, output "NOT ACCEPTABLE", otherwise, output the new number produced by this MTM machine.

748 - Exponentiation (By: Darkman)

First, found out where the decimal point is. If after the decimal point there are x digits and the power is n, then the final result will have n*x digits after the decimal point (Of course you have to eliminate the trailing zeros explicitly). Then convert the original number into an integer by withdrawing the '.' , example, if it 98.876 then the integer is 98876, then use your BigNumber exponentiation. The remaining part is all about printing the output in the right format, which is replacing the '.' back.

750 - 8 Queens Chess Problem

This problem is quite popular, refer to your algorithm books regarding 'backtracking', they usually use 8 Queens problem as a sample.

753 - A Plug for UNIX

A maximum bipartite matching problem. Formulated this problem as a graph and then pass it to a specialized maximum bipartite matching algorithm or a network flow algorithm.

755 - 487-3279

Simulate... and simulate...

756 - Biorhythms

Similar to problem 105,467,and 700... use an array to flags these days... Please browse the internet to find out more about biorhythms.

762 - We Ship Cheap

Solve this problem using Breath-First Search. Formulate the input as a graph, then since the edge weight is uniform, the shortest one found by BFS will be the minimal route. Simply start traversing from starting city to destination city.

776 - Monkeys in a Regular Forest

To solve this problem (+ problem 784 and 785), you need a recursive flood-fill algorithm, which I believe should be a standard algorithm taught in algorithm class.

Flood-fill the area which have the same monkey ID (represent the same family), starting with number 1 from top-left to bottom-right. The output must be formatted as requested, otherwise you'll get Presentation Error.

782 - Contour Painting

Similar as problem 776, we use flood-fill algorithm to paint the maze. But this time we only paint if and only if it is near the border. (the initial '*' can be inside or outside the border, treat them appropriately).

I think this problem is the hardest among 776-782-784-785 flood fill problems...

784 - Maze Exploration

Similar as problem 776 and 782, we use flood-fill algorithm to paint the maze.

785 - Grid Coloring

Similar as 784, just use flood-fill algorithm appropriately. The difference between 784 and 785 is very minimal. You can solve two problems using roughly similar source code.

793 - Network Connections

The best way to solve this problem is using disjoint forest set data structure (implementation of Union Find data structure).

When you know 2 computers are connected, union them by calling union_set(comp1,comp2), then for checking connectivity, you can just determine if find_set(comp1) == find_set(comp2). Everything will be very simple if you do this. However, don't forget if this is a multiple input problems.