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
2. (i
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.
