Our Quest to Solve the UVa ICPC Online Problem Set :: UVa Solutions
#10602 - Editor Nottoobad
| Solved By: | wesley |
| Theory Difficulty: | easy |
| Coding Difficulty: | easy |
| Algorithms Used: | ad hoc greedy strings |
| Solution Description: | This problem can be solved greedily. Start with the first word. Then, while there are words remaining, find the word the matches the greatest amount of characters from the beginning, and use that one next. So for example, the second input case: popcorn (7 characters used) Now, "plum" shares 1 character with the beginning of "popcorn", and the other two words share 0. So, we choose "plum": plum (10 characters used) Now, it doesn't matter which word is next. apple (15 characters used) And finally, apricote (21 characters used) |
#10603 - Fill
| Solved By: | wesley |
| Theory Difficulty: | easy |
| Coding Difficulty: | medium |
| Algorithms Used: | dijkstra other graph |
| Solution Description: | You can represent this problem as a graph with 200x200x200 nodes. Each node has three values, a, b, c, representing the amount of water in each of the three jugs. The edge weight between two nodes is how much water must be poured. You can use Dijkstra, or you can use BFS where you redo a node if you come back to it with a better value (This only works because the bounds are small). See Also: Problem 571 (Jugs) |
#10608 - Friends
| Solved By: | peter |
| Theory Difficulty: | easy |
| Coding Difficulty: | easy |
| Algorithms Used: | other graph |
| Solution Description: | Setup the friends as nodes, and join two if they are friends. Start at an arbitrary friend (f), and Breadth-First-Search from there, counting the nodes who are connected to f, and marking each as being visited. max = Math.max(max, number of connected nodes) Repeat if a node has not yet been visited. NOTE: you cannot use an adjacency matrix, since it could be as big as [30000][30000] - and even booleans will throw a runtime error. I used an array of arraylists, but found this out the hard... long way 'sigh; |
| Solved By: | wesley |
| Theory Difficulty: | medium |
| Coding Difficulty: | easy |
| Algorithms Used: | other graph |
| Solution Description: | This is one of the simpler union find problems. Just use union find to form all the groups of friends. Afterwards, search through the groups to find the largest one. This can be done easily with an array where a[i] is the number of nodes that have i as a set leader. Just iterate through all nodes i, incrementing a[leader(i)], then print the largest value. |
#10610 - Gopher and Hawks
| Solved By: | wesley |
| Theory Difficulty: | easy |
| Coding Difficulty: | easy |
| Algorithms Used: | 2D geometry other graph |
| Solution Description: | This is just a BFS problem with a bit of math. Run BFS on the gopher holes, and consider two holes connected if the distance between them is less than or equal to m*v*60. |
#10611 - The Playboy Chimp
| Solved By: | wesley |
| Theory Difficulty: | easy |
| Coding Difficulty: | easy |
| Algorithms Used: | searching |
| Solution Description: | Just binary search the list to see where the chimp would fit, and search linearly from that point to find the two answers. Obviously, handle the cases of when the input is < a[0] or > a[n-1]. |
#10618 - Tango Tango Insurrection
| Solved By: | wesley |
| Theory Difficulty: | hard |
| Coding Difficulty: | medium |
| Algorithms Used: | dynamic programming |
| Solution Description: | Our DP will be a series of arrays of size [4][4][3][70]. f(l, r, m, k) is the amount of energy it takes to complete the rest of dance given that you've completed k steps so far, your left foot is on square l, your right foot is on square r, and m is a value (0, 1, or 2) that represents which foot (if any) moved in the last step. The convention I use for l and r is 0 = Up, 1 = Left, 2 = Right, 3 = Down. For m I use 0 = no foot moved, 1 = Left, 2 = Right. So, we want to determine f(1, 2, 0, 0), and return the appropriate sequence of actions. At each step, there are two cases: Case 1: The next step is '.' In this case, try moving your left foot to all four squares, and then try moving your right foot to all four squares. Nothing is going to be tapped, but you can use this pause in the music to reposition yourself. If you move a foot, make sure to output the foot that moved, even though it didn't tap. Case 2: The next step is 'U', 'L', 'R' or 'D': In this case, try moving your left foot to the appropriate square, and try moving your right foot to that square as well. In both cases, make sure not to allow any illegal moves. I recommend having three parallel arrays. Each is indexed as mentioned above, by (l, r, m, k). The first array, COST, is the standard DP array that keeps track of how much energy it takes to complete the dance from the given state. The second array, NEXT, keeps track of some integer or object that points to the next state in the path, and the third array, MOVE, keeps track of what move was taken. For example, consider the input "LUR". We go through the following transitions to get the output "LRL": l r m k 1 2 0 0 (move is "L") 1 2 1 1 (move is "R") 1 0 2 2 (move is "L") 2 0 1 3 (sequence is finished) And the arrays look like this: NEXT[1][2][0][0] = (1, 2, 1, 1) MOVE[1][2][0][0] = 'L' COST[1][2][0][0] = 3 NEXT[1][2][1][1] = (1, 0, 2, 2) MOVE[1][2][1][1] = 'R' COST[1][2][1][1] = 2 NEXT[1][0][2][2] = (2, 0, 1, 3) MOVE[1][0][2][2] = 'L' COST[1][0][2][2] = 1 At the end of the DP, use the information in NEXT to traverse through the optimal states, and use the information in MOVE to print out the move sequence. |
#10622 - Perfect P-th Powers
| Solved By: | wesley |
| Theory Difficulty: | easy |
| Coding Difficulty: | easy |
| Algorithms Used: | math |
| Solution Description: | Given that the square root of 2^31 is less than 47,000, there must not be more than 47,000 (positive) inputs that return "2" as their answer. In the same way, the cubic root of 2^31 is less than 1300, there are no more than 1300 (positive) inputs that return "3". Given that the vast majority of inputs will return "1", you can just pregenerate all of the answers that won't return "1", store them in a hash map, and output them when necessary. Don't forget: input numbers can be negative too. |
#10633 - Rare Easy Problem
| Solved By: | wesley |
| Theory Difficulty: | easy |
| Coding Difficulty: | trivial |
| Algorithms Used: | math |
| Solution Description: | First, note that M is (N div 10) ("div" being integer division). N-M is then approximately 9N/10. Given that (N div 10) <= (N / 10), we know that (N-M) <= 9N/10. Also, the difference between (N div 10) and (N / 10) is at most 10. Let X = N-M. We can a range of numbers [10X/9 + 20, 10X/9 - 20] and test each one to see if it is a possible solution. A range this wide is just for safety. You definitely don't need to have a range that wide, and you can actually prove that if there are multiple solutions, there are at most two solutions and the difference between them is 1. Unsigned 64-bit integers make this problem easier, but you can manage with signed 64-bit integers if you do (X + X/9) rather than (10*X) / 9. |
#10642 - Can You Solve It?
| Solved By: | wesley |
| Theory Difficulty: | easy |
| Coding Difficulty: | easy |
| Algorithms Used: | ad hoc math |
| Solution Description: | Consider the lines with equation x+y = C to be different "levels". So, co-ordinates with the same C are on the same level. Note that you first go through level 0 [(0,0)], then level 1, [(0,1) (1,0)], etc. Let the input co-ordinates be x1, y1, x2, y2. Let l1 = x1+y1 be the level of the source, and let l2 = x2+y2 be the level of the finish. There are two cases: Case 1: Source and finish on same level In this case, just output y1 - y2. Case 2: Source and finish on different levels In this case, output y1 + x2 + (l2-l1) + cumsum(l1+1, l2-1), where cumsum(x,y) returns the sum of all numbers between x and y inclusive, or 0 if x > y. For more intuition behind this formula, read on: - y1 is the number of steps it takes to get to the end of level l1 - x2 is the number of steps taken past the beginning of level l2 - (l2-l1) is the number of transitions between levels that we have to do - cumsum(l1+1, l2-1) is the number of nodes on all levels between l1+1 and l2-1 inclusive Note that you must use longs to hold some of the higher values. |
#10651 - Pebble Solitaire
| Solved By: | wesley |
| Theory Difficulty: | easy |
| Coding Difficulty: | easy |
| Algorithms Used: | dynamic programming recursion |
| Solution Description: | It's fairly easy to do this as a top-down DP. Keep an array of length 2^12 where a[i] is the minimum number of pebbles left over starting from state i. i is a binary representation of the current state of the game. So for instance, -------oo-o-- = 110100 (base 2) = 52 (base 10) and a[52] would be 1, because you can reduce this state to 1 pebble by moving right twice. The recurrence is pretty simple. Just try all possible moves and recurse on them. If there are no possible moves, then count the number of pebbles remaining and return that as your answer. |
#10673 - Play with Floor and Ceil
| Solved By: | wesley |
| Theory Difficulty: | trivial |
| Coding Difficulty: | trivial |
| Algorithms Used: | math |
| Solution Description: | It actually *is* pretty easy to prove this theorem. If you take p = floor(x/k), you'll be missing an extra x % k. So add 1 to x % k numbers to get: q = x % k p = k - q. |
#10678 - The Grazing Cow
| Solved By: | wesley |
| Theory Difficulty: | easy |
| Coding Difficulty: | trivial |
| Algorithms Used: | 2D geometry math |
| Solution Description: | An ellipse is the set of points, {P}, such that the distance from P to a fixed point F1, plus the distance from P to a fixed point F2 is a constant for all points in the set. The rope and the two posts define such a set, so the area the cow can move in is an ellipse. The area of an ellipse is a*b*pi where a and b are half the distance of the minor and major axes respectively. It shouldn't be too hard to see that: a = sqrt((L/2)^2 - (D/2)^2) b = L / 2 |
#10680 - LCM
| Solved By: | wesley |
| Theory Difficulty: | medium |
| Coding Difficulty: | easy |
| Algorithms Used: | dynamic programming math |
| Solution Description: | Let P(n) be the multiset of prime factors of n. So, P(60) = {2, 2, 3, 5}. The LCM of a set of numbers {a1, a2, a3, ..., an} is the product of the intersection of P(a1), P(a2), ..., P(an). Intuitively, this means that you need "enough" of each prime factor in the LCM to "satisfy" each of the numbers. Let a[i] be the LCM of the numbers from 1 to i. To determine a[i+1], factorize i+1, then see if you need any of its factors. Keep an array c[] where c[j] is the number of times you've used j as a factor in your LCM so far. When you factorize i+1, check if the count of each factor, j, is greater than c[j]. If it is, multiply your current LCM by j until the count is satisfied. Now, the LCM grows very quickly, so we don't want to actually store the entire LCM in a[]. Instead, we store the last 7 or so digits before the final string of zeros. So, if our LCM was 182158203800000000, we would store "1582038" in a[]. This can be accomplished by the following code: while(a[i] % 10 == 0) --- a[i] /= 10 a[i] %= 10000000 We keep 7 digits because the largest number we might multiply a[i] by is 6 digits long. |
#10684 - The jackpot
| Solved By: | wesley |
| Theory Difficulty: | easy |
| Coding Difficulty: | easy |
| Algorithms Used: | dynamic programming |
| Solution Description: | This is a straightforward Maximum Interval Sum DP. You can solve it in O(n) as follows: Let a[i] be the ith bet. Then, dp[0] = a[0] dp[i] = max(dp[i-1] + a[i], a[i]) So, either choose to continue the sequence, or start a new one if the previous one wasn't profitable. Output the maximum value in dp[], if it's greater than 0. |
#10696 - f91
| Solved By: | peter |
| Theory Difficulty: | trivial |
| Coding Difficulty: | trivial |
| Algorithms Used: | |
| Solution Description: | if(n > 100) output n-10 else output 91 Use stringbuffers to avoid TLE. |
| Solved By: | wesley |
| Theory Difficulty: | easy |
| Coding Difficulty: | trivial |
| Algorithms Used: | math |
| Solution Description: | Simulating the function is too slow (for Java at least), but if you test it out on a few small numbers, you'll notice a pattern: f91() returns 91 for all numbers <= 100, so just output 91, or n-10 as necessary. In Java you'll need BufferedReader AND StringBuffer. |
#10699 - Count the factors
| Solved By: | wesley |
| Theory Difficulty: | easy |
| Coding Difficulty: | easy |
| Algorithms Used: | math |
| Solution Description: | Use the Sieve of Eratosthenes to generate all the primes up to 1,000,000. For each input, check whether each prime divides it. You don't need to do an O(sqrt(n)) check. O(n) will do fine. |
Read full article from Our Quest to Solve the UVa ICPC Online Problem Set :: UVa Solutions
No comments:
Post a Comment