Volume IX
Problematic problems: 930, 932, 933, 934, 935, 936, 937, 938, 942, 943, 963, 965, 966, 968, 971, 994, 998 (still discovering)
- 900 - Brick Wall Patterns
- 902 - Password Search
這一題可以 reduce 成在 unsorted array 裡找眾數的問題，Lower bound 是 Ω(n log n)，我主要是用 quick sort 解題，排名第 32。
這題不會出現兩種以上的答案，每個 test case 不一定會寫在同一行，test case 的長度在800000內
- 903 - Spiral of Numbers
Find which outskirt the input number locates, and then find the rank of the input in that outskirt. Finally, there are 11 cases to be considered when producing output.
Remark: input numbers [1..9] are special cases.
This problem seems labor-intensive.....
- 906 - Rational Neighbor
The point is how to avoid floating pointing rounding. First, inverse n to get inv_n so that the following computation does not involve floating point. Then use the formula in the problem to find feasible c and d that satisfies the requirement. Next, for each d* = 1, 2,..., d-1, find the corresponding c* such that c*/d* is another answer better than c/d.
- 907 - Winterim Backpacking Trip
Let m* be the answer. I use binary search to find m*. At first, m* must be in [0..total_length]. Then I maintain a function called ifPossible(int daily_walk_length) returning YES/NO. With this function, the search field size [0..total_length] can be halved in each iteration of binary search.
- 908 - Re-connecting Computer Sites
The simplest solution seems to construct the minimum spanning tree from scratch. Here I use another approach. I update the given MST by checking if adding some of K edges can lead to a better MST.
For a new edge e, add e to MST. A cycle is formed as a result. Identify the cycle, find the edge e' in the cycle that has the maximum cost and remove e' from the cycle. The cost of MST is reduced if cost(e') ＞ cost(e). Repeat this procedure for all the K edges.
- 910 - TV game
This problem is not hard. Just create an adjacency matrix M and calculate M^m in O(n^3 log m) time, where n is the number of places in the problem. Two tricky things needed to be taken into consideration: (1) There may be multiple special places. (2) The initial adjacency matrix may have 2 (such as the place E in the sample).
- 911 - Multinomial Coefficients
- 912 - Live From Mars
Whenever a mutant DNA corresponds to a normal DNA, mutate!
- 913 - Joana and the Odd Numbers
- 914 - Jumping Champion
This problem is essentially to find the mode in a sequence of numbers. I first find the prime numbers in the range [2 .. 1000000]. For each pair of query input, use binary search to find the index of the two corresponding primes, calculate the gap between the primes involved and stores the gaps in an array, sorted the array, find the frequency for each gap, sort the gap, and then determine the answer.
Note: inputs &le 2 are special cases. - 918 - ASCII Mandelbrot
This is in fact an easy problem, although the problem descirption is lengthy and the output seems scary. Just follow the instruction given in the problem and use two-fold loop to calculate the output. Choose double as the data type, and append a very small number when comparing two floating points (that is, when comparing two floating points number x and y, the statement is x &le y + 1e-12 rather than x &le y ).
Like Problem 920, if your programming language is ANSI C, select C++ when you submit the program.
- 920 - Sunny Mountains
Sort the data points based on their x-axis values. Then, plane-sweep the landscape from right to left. If a data point is higher than the current maximum, calculate the length of the hill and update the maximum.
This problem involves floating point arithmetics, and I kept receiving WA without knowing why (My program output was consistent with that from uva toolkit website). It seems that UVa judge has a bug for ANSI C floating point arithmetics. After choosing language as C++, my wrong-answer ANSI-C code was accepted.
- 921 - A Word Puzzle in the Sunny Mountains
Not difficult. A simple recursive function is enough to solve the puzzle.
- 923 - One Against Many
My DP solution uses a table[round][#opponents], in each round there is at least a loser. The value of table[round][0] is a potential answer. Because subjects are tested in a cyclic way, round can be set to c*nSubject when Oinit is large, where c is a constant. That is, we don't need to find all the potential answers.
- 924 - Spreading The News
implement a BFS traversal.
- 925 - No more prerequisites, please!
Find a complete set of prerequisites for each course. Then use it to find immediate prerequisites by a filtering method. Time: 0.008s
- 927 - Integer Sequences from Addition of Terms
Another problem about simple math and binary search
- 928 - Eternal Truths
Think of the map as a 3-dimensional maze, build up possible routes, and use the shortest path algorithm to solve it. Be careful: if the move is 2-step or 3-step long, you have to check whether there is a '#' along the way. Also, the problem states that 2 &le R, C &le 300, but I kept getting WA until I set R and C to 2000.
Test data:
1 7 11 .S#E....#.. .#.##...#.. .#...#..... .#.##.###.. .####..##.. ...........
The output is 15.
- 926 - Walking Around Wisely
Remember to use unsigned long int to maintain the number of paths.
- 929 - Number Maze
Use priority queue.
- 939 - Genes
I use ANSI-C tsearch() and qsort() to solve this problem. No special tricks, just build the family tree and greedily decide the genes.
- 940 - Autobiographical Numbers
Autobiographical numbers with length &ge 7 have regular format. Just generate the numbers with length &le 10, observe their property and use it to generate the numbers with length &le 100.
If the input string has length &le 3, just skip it and read the next input string.
- 941 - Permutations
Decide the first char, the second char,...., one by one.
- 944 - Happy Numbers
construct a directed acyclic graph and apply a topological sort to find the answer.
- 946 - A Pile of Boxes
Define a recursive data structure and define two functions ableContain() and insertBox(). Then you know how to solve the problem. PS: I also deal with the case of 0 box, but I don't know whether it matters.
- 947 - Master Mind Helper
My method has no trick. Just generate all possible secrets and check if they satisfy the number of right places/wrong places. If yes, increment a count by one.
- 948 - Fibonaccimal Base
- 949 - Getaway
The is a variation of the shortest path problem. A little modification of the distance function suffices to solve this problem.
- 950 - Tweedle Numbers
This is a tricky problem. My method considers each tweedle number is a K-digit, M-ary number, where each digit represents the number of bits in a run. By definition, the sum of all the digits is N, and each digit has value &ge 1. To find out the rank of a tweedle number, I maintain a table[1..K-1][1..N]. Each table cell table[R][C] is the number of ways to fill R digits with summation C. After filling out the table, the rank of a given tweedle number can be found.
Consider the sample given in the problem description. The table is
For a given tweedle number 111011, first convert it into 312 (K-digit, M-ary). It outranks the tweedle numbers beginning with 1 and 2 (in the M-ary form), so its rank is at least table[2][6-1] + table[2][6-2] = 2 + 3 = 5. It also outranks the tweedle numbers beginning with 32 (because the second run is filled with bit 0), so its rank is at least 5 + table[1][6-3-2] = 6. Since we have traced down to the last digit, it is sure that 312 outranks 6 tweedle numbers and the rank is 6 + 1 = 7.1 2 3 4 5 6 1 1 1 1 0 0 0 2 0 1 2 3 2 1 The remaining question is how to use dynamic programming to fill out the table. It is not hard to come up with.
- 956 - The Minimum Slot Machine
This is the same as finite state machine optimization. You can find such an optimization algorithm in some textbooks regarding computation theory or formal language. Here I use a trivial solution. I maintain a table diff[A..Z][A..Z] to indicate whether two states are distinguishable. Initially, every diff[i][j] is set to 0. Then, for two states i and j, if one is an accepting state while the other one is not, then set diff[i][j] = 1 (meaning that states i and j are distinguishable). Next, keep a list of i's and j's such that diff[i][j] = 0. If i and j transmit to two states that are distinguishable for some input (1 euro or 2 euro), then diff[i][j] is set to 1. Repeat this operation until no such i, j exist. Finally, output the answer based on diff[i][j]. When implementing this trival algorithm, you can consider only the case j ＞ i (only upper half of the table is used).
- 957 - Popes
Use binary search smartly.
- 960 - Gaussian Primes
http://mathworld.wolfram.com/GaussianPrime.html
- 962 - Taxicab Numbers
- 967 - Circular
- 970 - Particles
After receiving 24 times of TLE, I finally managed to get my problem accepted. The test data set is so huge that I was forced to use as many bit operations as possible. I also used a dirty trick of hard-coding a hash function in my program. Without the dirty trick, I got TLE. With it, the running time becomes 0.6 seconds.
In essence, this is a DP problem; I use a table [seqLen][startPos] to maintain the possible quarks generated in the reaction, where seqLen is [1..strlen(input)] and startPos is [0..strlen(input) - 1]. Row 1 (seqLen = 1) is the base case. Each element in the table is char type. When an element is found to be 7, just move on to calculate the value of next element. The running time is O(n3).
- 972 - Horizon Line
- 973 - The Guessing Game
The general idea is the same as Problem 989, sudoku. Perform greedy steps and try-and-error steps alternatively. When performing a greedy step for a row/column/diagonal, calculate the number of cells that is not decided yet, say #undecide, and the number of cookies, say #cookie. Let #spec denote the number of cookies appearing in that row/column/diagnonal. Set undecided cells to NONE if #spec = #cookie and set to COOKIE if #undecide = #spec - #cookie.
- 974 - Kaprekar Numbers
- 976 - Bridge Building
This is, I think, the most interesting problem in Volum IX.
First, I use BFS traversal to identify the north terrain, marking them as 'N'.
Then I build an array A[i] representing the distance between the river bands for each vertical strip i.
The problem thus reduces to finding B elements in array A[1..C] such that their sum is minimum and
the distance between those elements is &ge S + 1.
I use DP to find the minimum sum. The table is t[1..B][1..C]; each t[x][y] is the minimum sum for x elements selected in the array A[1..y]. The value of t[x][y] can be decided based on A[y] and {t[x - 1][1 .. y - S - 1]} (The formula is left for readers to work out).
For Sample Input 1, the table looks like
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1 6 6 4 4 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 2 X X X X X 9 10 8 10 9 9 9 9 9 9 9 7 6 9 9 3 X X X X X X X X X X 15 15 14 14 14 14 12 11 14 14 where X represents impossible. The final answer is the minimum value in the last row.
- 978 - Lemmings Battle!
Use two priority queues to simulate the battle.
- 979 - The Abominable Triangleman
Just check the possible triangles to see if they match the length of the sides of the gold triangle. I use tsearch() function in ANSI C to carry out this method efficiently.
- 980 - X-Express
Use a greedy algorithm to approach. First, for each of the two sections(Paris to Brussel and Brussel to Amsterdam), find the number of wagons for politicians, businessmen, artists, and young people respectively, and add second-class wagons for tourists if necessary. Next, calculate the number of empty seats for the train and assign the empty seats to regular passengers. If there are regular passengers having no seat, then add second-class wagons for those passengers.
This problem has multiple test cases and there should be a blank line between separating each set of output.
- 983 - Localized Summing for Blurring
Use 2-dimensional prefix sum. Notice that the matrices are presented in a way that we are used to.
- 986 - How Many?
A not-so-simple DP problem. As suggested by the UVa forum, the DP is done by a table[x][y][p][move] for a given k, where p is the number of peaks at height k, and move is either DOWN or UP indicating (x, y) is reached by a downhill move or a uphill move. The answer is table[2n][0][r][DOWN]. One of the DP rule is table[x][y][p][DOWN] = table[x-1][y+1][p][DOWN] + table[x-1][y+1][p-1][UP] if x ＞ 0, y + 1 = k and p ＞ 0. Other rules can be developed in a similar way.
987 - Maternity
I use branch-and-bound approach to solving this problem. I maintain a pointer for each city that points to the nearest city that has maternity service. When city i's maternity service is stopped, only the cities pointing to i renew their pointers so that the new cost function can be computed efficient.
Note 1: trivial branch-and-bound gets TLE.
Note 2: the distance between two cities is the summation of vertical displacement and horizontal displacement. This is mentioned in the problem, but I overlooked it and got many wrong answers.
- 988 - Many Paths, One Destination
- 989 - Su Doku
Sudoku is like maze-walking. When there is only one possible number for a sudoku cell, fill the cell with that number (greedy step). When every unfilled cell has many possible numbers, fill that cell with one of the numbers (try-and-error step). If a try-and-error step leads to a dead end, we simply go back to that cell and fill it with another possible number. Repeat this step until a solution is found or report "Impossible".
I use recursion to realize this idea. Given a sudoku grid, I fill the grid with greedy steps &rarr a try-and-error step &rarr greedy steps &rarr ... Before performing a try-and-error step, I make a copy of the current state, fill a cell with a value to generate a new state, and recursively find the solution for the new state. If the try-and-error step fails, the previous state can be quick recovered.
Note that Problem 989 considers not only 9x9 sudoku but also 1x1 and 4x4.
- 990 - Diving for Gold
Branch and bound
- 991 - Safe Salutations
The output are actually Catalan numbers, see The Art of Computer Programming, Volume 4, Section 7.2.1.6.
- 993 - Product of digits
- 995 - Super Divisible Numbers
Not a difficult problem; a simple recursive function can solve it. The annoying thing is to use a char array to simulate a big number.
- 996 - Find the Sequence
It is better to try Prob. 997 first. My method is to maintain a table for back-tracing the sequence. The row 0 is the input numbers. The table is filled out in top-to-down and then bottom-to-up manner.
- 997 - Show the Sequence
A simple recursion suffices to solve this problem.
- 999 - Book signatures
For each signature, maintain two variables indicating the starting page and the ending page.
