Last updated on: 29 April 2009 09:04:02 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...

Some hints for this volume are contributed by my CS3233 student:
750-799: Lim Boon Hwee, Matthew (ML)

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.
Alternative: Brute Force. Use 1D array (only one queen per column) to find combinations. Finally, check if diagonals violate rule.

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.

Alternative: Bipartite Matching. Create a graph that has a source node connected to all plugs with each capacity 1, all devices connects to plugs with capacity 1, all adapters connect from plug A to plug B with infinite capacity, and all devices connects the sink with capacity 1. After that, use a maxflow algorithm to determine that maximum number of connected devices. The answer will then be total-connected devices. Note that adapters should only connect one way. A to B does not mean B to A.

755 - 487-3279

Ad hoc, simulation. Convert all to numbers. Use STL map for 'hashing'. All telephone numbers are 7-digits, with '-' between 3rd and 4th number. Trailing zeroes (if int is used) should be added when necessary.

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.
Complete search, ad-hoc. If they are already in the triple peak, calculate the next one.

758 - The Same Game

Ad-hoc. Fun! Takes time to code, but just follow instructions.

759 - The Return of the Roman Empire

Backtracking / Coin change. Notice that valid numeric sequences are just these rules:

1. Pick 0 or 1 from each row. Top to bottom only.
M MM MMM
C CC CCC CD D DC DCC DCCC CM
X XX XXX XL L LX LXX LXXX XC
I II III IV V VI VII VIII IX

2. The string should terminate, i.e. no trailing characters.

Store the sequence used to get the converted number.

760 - DNA Sequencing

Complete search. Use strncmp for each and every possible combination. Note that null zero should not be checked (do not go out of bounds!).

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. Note that input is quite large.

775 - Hamiltonian Cycle

Backtracking / complete search. Note that all nodes can only be traversed once except the first node. Possible not to mark the first node when it first start. Order does not seem to be important.

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.

778 - Recording a tape

Ad-hoc, complete search. Surprising that so few attempted the question. Perhaps it's because there is no limits set. So here it is: Max number of songs = 32. Try to place all the songs into Side A, then place the songs starting at the back into side B(in a binary way).

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.

787 - Maximum Sub-sequence Product

Big Int. Use java (or write your own) BigInt class. Credits to chrismoh in UVA forum for the algorithm. Starting from the first element, update the largest positive and negative product. Upon reading 0 or end, reset the values. Print the highest number calculated. Note that the result may be negative or zero.

789 - Indexing

Ad-hoc. Use STL map for storing the words that needed to be indexed. Unfortunately, it does not have a test case yet. Any blank answer will do for now (hint hint).

790 - Head Judge Headache

Ad-hoc. Use STL sort and comparator for easier coding. The setter did not specify the requirements well, which is well discussed in the UVA forums. When events occur at the same time, all rejected answers, ie. "N", are considered first before the accepted "Y". Also, show all the teams up to the highest number that have submitted something, ie if 1,2,4 submitted something, show 1,2,3,4. Finally, do not print trailing spaces, and keep the numbers aligned to the right.

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.

795 - Sandorf's Cipher

Ad-hoc. Find out the one to one mapping between the message and the cipher. Use paper with holes (at the correct places of course). Read the question carefully - it says that the paper with holes turn, but I initially understood it as the bottom paper turns... Also note that the trailing # should be removed.

796 - Critical Links

Modified DFS. This problem can be solved by modifying DFS to check for articulation points. During DFS, store dfsnum(u) the order that the element u is checked, and low(u) the lowest order number that element u can be accessed from. Whenever dfsnum(u) < low(v), edge u-v is a bridge. Remember to sort the answer in ascending order.

799 - Safari Holiday

Math. For people who read the forums (too much), the answer of this problem is posted in the forums. It deals with block designs but the implementation is just 2 mod checks.