11500 - Vampires
Reading http://en.wikipedia.org/wiki/Gambler's_ruin there are 2 cases to consider. The first case is "fair coin flipping" (AT = 3) and the second case is "unfair coin flipping" (AT != 3). The formula are given in the link to the wiki.
11501 - Laurel Creek
This problem is not solved yet.
11502 - Rocket Stages
This problem is not solved yet.
11503 - Virtual Friends
This is a simple disjoint sets question. Watch the part about updating the number of people in the "social network", i.e. the set after each union_set. It would be necessary to use STL map (or some hash table) to speed up the searching.
Note: There is one thing to be careful with: the number of people who just become friends. I suppose this part is quite tricky because I output 0 if two people has been included in a single network, however, what is required turns out to be that you must output the number of people in the network, namely, if A, B, C know each other and the input is "A B", you have to output 3 instead of 0 or 2 (the reason why I got WA a couple of times. )
11504 - Dominos
The question has to be modeled as an directed graph. We cannot search for nodes that have no in-degree edges and DFS from there, because the graph is not acyclic. So we have to decompose the graph to a DAG (directed acyclic graph) first before we can search for the number of nodes with no in-degree edges. So to be able to do it, we have to decompose the graph to strongly connected components. Once the directed graph is transformed into another graph that composes only of the strongly connected component, the graph becomes a DAG. However, is there really a need to do DFS after all the strongly connected component is found? The answer is no. All we are seeking for are the number of strongly connected component that does not have any in-degree edge from a node that is outside the component.
To count the number of such strongly connected components, use Tarjan's algorithm(http://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm).
11505 - Logo
This is just a simple simulation. Just follow the instructions.
Be careful with precision error, pi = 2*acos(0.0);
11506 - Angry Programmer
For this question, it could be seen clearly that it is a min-cut question. First to make the graph directed, split each edge into 2 arcs. Also split the nodes into two nodes each, innode and outnode. Then link all the inarcs to the innode and all the outarcs to the outnode. Finally link the innode and outnode with the cost it takes to blow up each computer.
11507 - Bender B. Rodriquez Problem
This is a simulation problem. We can use 1-6 to represent the +x,-x,+y,-y,+z,-z, and write a function to enumerate all possible bending cases.
11508 - Life on Mars?
This problem is a problem to re-arrange the order of the array. Observe that if and only if there is some element in the sequence is greater than n, the message is hacked by Martian. (very easy to prove) Then, re-arrange the sequence of the sequence. Just make sure that S(i)=i, if i is in the sequence. The others, just fill in by ascending order.
This is an ad hoc problem and my solution is exactly the same as GY's.
Basically, if s(i)<>i, let s(i)=p then s'(s(i))=s'(p)=s(i)=p , hence s'(p)=p. Then we can just fill all i into i th place as many as possible and the value of other place doesn't matter.
Only" hacked version" appear when there is a number greater than the number of elements.
11509 – Touring Robot
To solve this problem, we need to calculate exactly the ccw angle between 2 given vectors. To accomplish the purpose, dot product and cross product can be combined to get the sin and cos of the respective angle. By knowing the sign of cos and sign (-ve or +ve), we can decide on which quadrant that the angle between the 2 vector lies. Thus, the exact angle can be determined. Though it is not stated explicitly in the question, one turn is 360 degrees or 2*pi. A useful function (C - math.h) for this question is atan2. Just simulate accordingly.
Tricky problem dealing with floating points. Starting from the first point, keep moving to successive points, finding the angles between lines made- taking care that the measurement is anticlockwise. The question is quite ambiguous, and what is asked for is the number of 360 * rotation the robot makes. Useful to use the function atan2(y,x) defined in cmath that returns the radian angle that (x,y) ---(0,0) makes with the + direction of x axis.
11510 – Erdos Unit Fractions
It is a Math problem. It seems quite difficult at the first sight. But I realized that we can just search for the result. For this problem, if n is even, the answer is obvious (let x=n/2 y=n z=n). If n is odd, we assume that x<=y<=z, so 1/x>=1/y>=1/z. As 1/x+1/y+1/z=4/n so 4/n >=1/x>= 4/3n. so n/4+1<=x<=3n/4+1. Similarly, work out the range of y: nx/(4x-n)+1<= y<=2nx/(4x-n)+1....so search the x and y, computer z, if z is integer, print out the result. One more thing to consider: if 4/n-1/x=1/k, just let y=z=2k. Take note to use long long int. Do not worry about the time limit. It is 5 sec, and my program only takes 0.02sec. 11511 - Frieze Patterns If we use simulation, we need a table of 10^8 columns, and 1000 rows, which is impossible. Also, if we fill in the table column by column, we only need the previous one column. So we can use a array of 1000 elements, and repeat filling in the array as a column. But if there are 10^8 columns, we still get TLE. So, we need to find some pattern of the output. I noticed that the data in each column will repeat after certain columns. So we just need to find the period, and then a lot redundant calculation are avoided. 11512 - GATTACA To find repeated substring in a long string S, we cannot use naive solution! We need to use a good data structure: I use "Suffix Array" (see http://sary.sourceforge.net/docs/suffix-array.html) The original suffix array has indices, however, we do not use these indices for this problem. I left the indices below for clarity. I use the second sample input, S = "GAGAGAG" for illustration. This string S has 7 possible suffixes (a simple loop can be used to produce these suffixes), they are: G, starting from index 6 AG, index 5 GAG, index 4 AGAG, index 3 GAGAG, index 2 AGAGAG, index 1 GAGAGAG, index 0 We can sort these suffixes into (e.g. by storing these suffixes in STL):
AG, index 5
AGAG, index 3
AGAGAG, index 1
G, index 6
GAG, index 4
GAGAG, index 2
GAGAGAG, index 0
Now that we have these sorted suffixes, we can easily find the common substrings by comparing adjacent suffixes...
(these substrings are indicated with bold, italic, or underline)
Here, we can see that "GAGAG" is the longest substring.
Now, iterate through the set of suffixes one more time to see how many times "GAGAG" occurs as the prefix of these suffixes!
Note that you need to output "No repetitions found!" when necessary.
11513 - 9 Puzzle
This is a graph&BFS problem, pecalculation and implementation are equally important.
Basically, I do BFS from the original point (1 2 3 4 5 6 7 8 9) to generate all possible state and use stl map as a hash table(simple hash: ((1 2 3) (4 5 6) (7 8 9))-->987654321 .) when doing the BFS.
3 array I use ( the size of array <20000, by checking the final size of map container) link[] : record the father node for each state(for printing) depth[]: record how many steps needed to get this state from original state method[]: record which method is used to generate the current state For each case x, check if x is a valid state by map.find( hash value of x) . If yes, call the print method which is implemented by recursion, if not, output error message. 11514 - Batman This is a classic Dp problem and some skill of string operation is needed to process the input data. Let's say, assp[i][j] represents the minimum energy consumed when you use first i weapons to destroy first j villains. Dp formula is assp[i][j]=min{ assp[i-1][j], assp[i-1][j-1]+cost[i][j] (if i th weapon can defeat j th villian) } , then check if assp[p][v]<=upper limit of energy STL map provide easy access when checking the name list. 11515 - Cranes Given that there are at most 15 cranes, it is possible to brute force it as we only need to check 2^15 states (all the possible combination of cranes) to find the maximum area that is covered by the crane and yet the arm of the crane will not hit another crane. 11516 - WiFi This is a problem about binary search. First, we read in the input and sort them. Do the binary search for all the possibilities of the maximum distance. For convenience, the maximum range the server can cover is twice the max distance.(the distance now all become integers). If the distance is possible, the range of length k can cover all the houses. All possible ranges are from 0 to the difference between the start and the end. Do binary search for that until you find the point that distance k can cover all the houses while the distance k-1 cannot. More specifically, in the process of judging whether distance k can cover all houses, we just see whether t(the number of servers) ranges of length k can cover all houses. that is, we start from the first and go length k, the next range, go from the smallest one which is not covered by previous one........until the last range, see the last range exceed the last house or not. if so, it can. if not, it cannot cover. The complexity is O(nlgn) as the sorting. It will not exceed the time limit if you always use the binary search. This is a search problem. All access points can cover some intervals in the axis, and all the houses are to be covered by at least one interval, and the max size of intervals should be minimized. Since all houses coordinates are integers, the size of max interval must be a integer. I assume all intervals are of the same size, and use binary search to minimize the valid (can cover all houses) intervals. 11517 - Exact Change A slight variation to the 0-1 knapsack problem. A simple DP is outlined. Define f[i][k] as the minimum number of coins required to get sum exactly i using the first k coins. Since, this implementation uses excess memory, storing 2 copies of the above array, for k and k+1 at any point of time will suffice. The Memory limit for this problem even though not mentioned, I guess to be 4 MB. This is a DP problem, and instead of using a two dimensional array as mentioned in the solution, I only used a one dimensional array a[20010], a[i] record how many coins are needed at least to form i cents. First fill all elements in a[] with a big number MAX, and perform the 0-1 knapsack dp. Finally, look for the number k closest to the price, and a[k] is not MAX. 11518 - Dominos 2 This is a search problem. First, we construct a directed graph, if domino number x falls, it will cause domino number y to fall, then there is an edge from x to y. Then, use depth first search (or flood fill) and count how many dominos will fall over. 11519 - Logo 2 Let O(0,0) be the starting point, O’(x,y) be the ending point, A(xA,yA) be the point where we meet the missing number. If (the missing number is in the move “bk” or “fd”) result = distance between O and O’ else (if the missing number is in the move “lt”) result = angle O’AO else //(the missing number is in the move “lt”) result = - angle O’AO The complexity: O(number of moves) 11520 - Fill the Square This is a greedy problem. Lexicographically smallest output is required, so just choose the smallest valid (different from adjacent letter) letter in each empty grid row by row from left to right. 11521 - Compressor This problem is not solved yet. 11522 – Pyramid Number Instead of formulate the question as how many numbers are strictly pyramid numbers between a & b, it could be formulated as how many numbers are not strictly pyramid numbers. This is because there is only a limited number of numbers that are not strictly pyramid numbers. This set of numbers could be easily brute forced. This is Ad hoc problem + DFS. There is no rule to judge if a number is pyramid number except brute force, however, by a simple DFS, it is obvious that any number greater than 77 must be a pyramid number. Therefore, we can just brute force all number less than 77 and print out the answer according to the test data. Question does not tell us a 0
- paper -> 1
- glass -> 2
min[0][0] = we have processed until position 0 (the 1st paper) with the right most that 'still have not been processed' material is non-recyclable material (value: 0)
min[2][1] = we have processed until position 2 (the 2nd paper) with the right most that 'still have not been processed' material is paper. (value: 1 - Remove glass and leave 2 papers unprocessed)
min[4][1] = we have processed until position 4 (the 3rd paper) with the right most that 'still have not been processed' material is paper. (value: 2)
min[4][0] = we have processed until position 4 (the 3rd paper) with the right most that 'still have not been processed' material is non-recyclable material. (value: 3)
11524 - InCircle
We first assume n1 and m1 is the length of respective segment, then we can know the length of each edge. Then we use s=sqrt(p*(p-a)*(p-b)*(p-c)), where a,b,c are the length of three edges, and p=(a+b+c)/2, to get the area of the triangle. But it is not the final answer because our assumption at the beginning may not be correct. So we use S=p*r' to get r', and the real area of the triangle is S*(r*r)/(r'*r').
11525 - Permutation
We can use Cantor's theory (not sure whether the name is correct) to calculate ith permutation of n numbers in Lexicographically order. Each time, we need to pick kth smallest number in an array for some number k, and there are at most 5000 numbers. Naive algorithm to pick the kth number costs O(n), which will end in TLE. So we need to implement an interval tree which each pick costs O(log(n)) time.
11526 - H(n)
The problem is not difficult but we need to consider the problem of time limit exceeded, e.g. we are computing n/n, n/n-1, .....there are so many ones and twos, these can be computed in one step. We can observe the number of 1, 2, 3.....the number of j is n/j - n/(j+1). so when the number is small and many, we use the previous method. for numbers big and few, just use the original method. We can set the break point at sqrt(n). Do not repeat the values around sqrt(n). Try to avoid division by 0 and sqrt of negative numbers.
11527 - Morning Walk
Given a positive integer S, find all the triangles that has perimeter S, integer side lengths and integer coordinates
Solution:
By Pick's Theorem, a triangle has integer coordinates iff 2*Area is an integer
Using Heron's formula we can deduce that a triple a, b, c, in which a+b+c=s is a solution iff
s(a+b-c)(a+c-b)(b+c-a) = 4k^2, where k is an integer
A program doing exhaustive search on a and b will not pass the time limit.
Here we do an exhaustive search for a and based on a, reduce the search space for b:
1. For each a, factorize b+c-a=s-2a, combining with the factorization of s to determine the largest prime factor p of s*(b+c-a) that wasn't squared
2. It implies that either (a+b-c) | p or (a+c-b) | p. i.e., either 2b=s-2a (mod p) or 2b=s(mod p)
It means we can reduce the search space for b by a factor of p, which turns out to be a very good optimization.
This optimization idea is from Derek Kisman.
11528 - Switch Grid
Construct a bipartite graph that has N+M vertices
N vertices on the left represents the rows and M vertices on the right represents the columns
There is an edge (i, j) iff cell (i,j) contains a switch
For each vertex i, let b[i]=the difference between final and initial state of bulb i (modulo 2).
The problem now is to select some edges of the graph s.t. the number of selected edges incident to any vertex i is b[i] (modulo 2)
I use the following algorithm:
Repeatedly try to find a path between i and j where b[i]=b[j]=1.
If at any time, we cannot find such a path, then there is no solution (haven't proved rigorously)
11529 - Strange Tax Calculation
This problem is not solved yet.
11530 - SMS Typing
This problem is basically a mapping problem. You need to map each character available on the SMS keypad to the number of keypresses needed. Since the characters involved are only the space character and all the lowercase alphabets, I can simply create two arrays, one containing all the characters involved in ascending order (by ASCII code) and the other containing the number of keypresses needed for each character. Thus from there, I can binary search each character in the characters array and use that index to get the number of keypresses. I then add all the keypresses up to retrieve the total.
For C\C++ programmers, make sure not to append a \n when reading in the number T as this will lead to consumption of spaces if the 1st test case starts with spaces.
Faster, you do not need to do binary search, a direct addressing table of character à num of key presses required is sufficient as there are only 26 (27 characters including space).
11531 - Solve the Broken Maze
This problem is not solved yet.
11532 - Simple Adjacency Maximization
This is a greedy problem.
If there are enough 0s (P/2<=Q), the answer should look like 00..00 101 101..101 If there are not enough 0s, the answer should look like 101 101..101 11..11 Use long long! To test your program, use this test case: 1 50 0 Answer: 1125899906842623 11533 - Special Number The problem seem to be easy at first. The algorithm is just follow the instruction, multiply y (the y times of the original number), and take care of the carry digit. When the digit you got is the same as the first digit, and there is no extra carry digit for the next digit, that means you got the number, just print it out. If we cannot get the kind of repeat for n^2 times, print out no solution. Something to take note: y need not to be smaller than n. So the carry digit can be very big, so you need to consider all carries but not only the previous digit. Moreover, the leading 0 is allowed: "10 6 100", the output should be 006 instead of no solution. and "2 0 0" the output should be 0 instead of no solution. 11534 - Say Goodbye to Tic-Tac-Toe This problem is not solved yet. 11535 - Set of Marbles Every state can be represented by a binary number, e.g. Marbles 1 and 3 in the first box out of 4 marbles can be represented by 1010. The idea is to transform each “n” bit binary number into its corresponding Gray Code number. The specialty of the gray code representation is that every consecutive number differs from the previous number by a Hamming distance of 1 i.e. flipping just one bit. Thus from the specified state in the gray code, you can traverse linearly to all other states. 11536 - Smallest Sub-Array This question turns out to be a search problem, however, it is a ad-hoc in fact. First of all, I use a array to store the value of each element. (Before do this step, if mn.
Caution: there is space between ":" and answer, i got a couple of presentation error for this reason
11537 - Secret Problemsetters' Union
This seems like an easy problem at first. It's a simulation problem that requires the use of correct data structure to prevent a TLE. However, this problem is full of traps. First trap is that you need to print an empty line in between test cases. That statement means EXACTLY that i.e. you have to test if the current test case is the last test case and if such, no blank line should be printed out. Second trap is if a merge operation has already occurred, all other merge operation instructions must be ignored and update and insert operations must be ignored if they do not operate on bank #1. Third trap is that the instructions will only be in capital form as mentioned. The fourth trap is that make_heap(which is O(n)) is only good for the merge operation. For the insert and update operations, you must use push_heap and pop_heap (both k lg n) as it seems that in most cases k is much smaller than n and results in a much faster operation (initially I inserted or removed everything before making heap as I assumed k was very large all the time). The fifth trap is you must clear the vectors you used after every test case. The last trap is that for the update operation, you must make sure that the vector that you are operating on is not empty. If it is empty, then you must terminate the loop. Also you must have a flag to check whether you have entered the loop or not. If you did not enter the loop then you must print "0 0". Otherwise, you can print the minimum and maximum values (which might actually refer to only one value i.e. they might be the same).
11538 – Chess Queen
This is a math related game problem....or somehow ad-hoc problem
Observe that there are two cases of attacking, so first consider the horizontal and vertical: there are m*(m-1)*n + n*(n-1)*m.
Then, consider the two kinds of diagonals: the one with length n and k (2<=kn). for the one with length n: (m-n+1)*n*(n-1). For k ones: there are k*(k-1), k are from 2 to n-1. sum those up. we have 1^2+2^2+.....+n^2-(1+2+3+....+(n-1))....using math formula: n*(n-1)*(2*n-1)/6-(n-1)*n/2. as it is double side of the square, so we have to times 2 for the length k diagonals. Besides, the diagonals are of two directions, we have to times 2 at the end [(m-n+1)*n*(n-1)+(n*(n-1)*(2*n-1)/6-(n-1)*n/2)*2]*2. So, in total the sum is m*(m-1)*n+n*(n-1)*m+(n*(n-1)*(2*n-1)/6-(n-1)*n/2)*4+2*n*(n-1)*(m-n+1) in the program just simply sub in the value and get the answer. note the problem of overflow, use unsigned long long int to make sure there is no over flow.
This is a math problem. To calculate the number of ways to make the queens in attacking position, we can divide the answer into three parts: two queens in the same row, on the same column, or the same diagonal. All data must be unsigned long long, and the output must be %llu in C (%I64u was WA, can’t understand).
Answer=m*(m-1)*n+n*(n-1)*m+(n*(n-1)*(2*n-1)/6-(n-1)*n/2)*4+2*n*(n-1)*(m-n+1);
11539 - Another Word Game
This problem is a DP problem.
Define f[i] as the maximum possible score for the first I characters of the string. Since you have only 10^4 words in the dictionary of maximum 100 characters each, check whether any of the words end at I, if so f[i]= f[i-length(specific word)]+Weight(specific word) ,else it is max( f[j-1] + (i-j+1)*p) i>=j>=i-99;
The overall complexity is 20*10000*100*log10000 which will run in 7 seconds.
11540 - Sultan's Chandelier
This problem is not solved yet.
11541 - Decoding
This is a fairly standard problem. For every line, just read the line in character by character. Be sure to read in one character followed by one number (and not just one DIGIT of a number) at a time and use a for loop to expand the string accordingly. Instead of reading the lines line by line, it's safe enough to just test for the presence of \n to know that it is the end of the line so a separate buffer is not needed.
11542 - Square
Use Gaussian Elimination over the field GF(2) to reduce to row-echelon form.
Number of solutions = 2^(number of columns - number of rows) in the row-echelon matrix.
11543 - Two Points And Curious MumboJumbo
This problem is not solved yet.
11544 - Recruiter's Problem
This problem is not solved yet.
11545 - Avoiding Jungle in the Dark
This problem is a kind of Graph problem.
Starting from 'S' (leftmost) at time 6 am, a pilgrim needs to reach destination 'D' (rightmost) by traversing plain land '.' or jungle '*'.
He has two options every step:
1. Walk to the right by 1 step in 1 hour
2. Rest in the current position for 8 hours
The objective is to find the shortest path from 'S' to destination 'D'.
There are constraints:
a. The pilgrim cannot be in '*' during night time (6pm-6am) and
b. The pilgrim cannot walk for 16 consecutive hours.
Enumerate all the branching possibilities and pick the shortest one.
There are tricky test cases, try these:
Input:
3
S**...*.*****D
S..........****.....*****.......*.......**..****.....*****.......****........****.........***D
S*..**..***......D
Output:
Case #1: -1
Case #2: 221
Case #3: 25
11546 - Olympic Swimming
Let L[i][j]- be the number of hurdles in the ith lane spanning the first j length marks.
Assume the number of lanes is 2. So, you have to find, two length marks I and J , such that, J-I is maximum and the number of hurdles in the first lane between I and J and the second lane between I and J is the same. i.e L[1][j]-L[1][i]=L[2][j]-L[2][i] which is equivalent to (L[1][j]-L[2][j])=(L[1][i]-L[2][i])
So, if you have an array L[i] that stores L[1][i]- L[2][i] , for all I, you just need to find two indices such that their values in L are same and the difference is maximum. Fix j, search in log L time, the value of i.!
For k>2 , instead of 1D L, you encounter a 2D L, and the checking for I and J is the equivalence of 2 ID arrays.
The overall complexity is O( L*Log L * K). A map implementation is useful.
11547 - Automatic Answer
This is just another coding practice. Just follow the instructions. Solve-able in less than 1 minute. No trick.
11548 – Blackboard Bonanza
This problem is a manifestation of the DP Longest Common Subword. For every pair of strings, find the length of the longest common subword, and output the global maxima. The recursive definition is, lcsw[i][j]- as the length of the longest common subword ending at I in the first string and ending at j in the 2nd string.
For each test case, for all pairs of string, try to find the maximum number of candies that Alice or Bob can get. This will give you a O(n^4) solution which will pass the time limit.
This question is a simple brute force question using an O(n^4) algorithm. Firstly, we need to obtain two strings to compare against. This is done by comparing each string that has been read in against every other string. This takes O(n^2). Once we have the two strings, we obtain the greatest number of overlap in both strings by sliding one string below the other and searching for the characters that overlap. This takes a further O(n^2). Take not that the overlapping characters need not be contiguous i.e. for two strings, we only need the number of characters that are the same given, the same position in both strings.
11549 - Calculator Conundrum
As I have coded pollard-rho factoring method (http://en.wikipedia.org/wiki/Pollard's_rho_algorithm) before, I came across the idea of floyd's method of cycle detection (http://en.wikipedia.org/wiki/Cycle_detection) which solves the question with O(1) space. Using that solves the question. However, I believe it might be possible to use map too.
This an ad hoc and using STL set can lead to an easy solution.
For each case, test the number can be properly displayed or not. If yes, just square it, if not, divide the number by ten until the number can be properly displayed.
Using STL to detect the cycle, if a cycle appears, output the maximum number in the set.
This is a math problem about set. The problem is about the number cycle. If the number in the sequence appear again there must be a cycle. so we only need to check the maximum up to the cycle. square the initial number until it is of n digit. built a set to store the numbers appear. if we find the number is already in the set. stop and output the maximum. the maximum is updated when a new number appeared. The time complexity is about nlogn. the time required is about 2 sec.( time limit is 6)
11550 - Demanding Dilemma
On first sight, this is a simple question. Just make sure for every edge, there are only 2 nodes incident to the edge. However, question wants the graph to be SIMPLE, so two adjacent nodes can only be joined together by one edge. If two adjacent nodes are linked by more than one edge, then the answer is "NO".
Alternative hint:
This is a basic graph problem and there is a trick of implementation.
Given the n*m matrix, what we need to do is the compute the sum of each column and check if the sum=2 or not. If sum<>2, it is invalid because all edge must be incident on exactly two vertices. The matrix is not big (max 8*28) , O(m*n).
In addition, maybe it is necessary to check if there exists a loop between two vertices. I add this check to my program.
11551 - Experienced Endeavour
This problem is not solved yet.
11552 - Fewest Flops
Let F[i][x] = the optimal result for S=S1,S2,..Si and x is the last character of Si’.
We can calculate F[i+1][y] by F[i][x]:
for (int i=0; i<26; ++x) if (inside(x,i)) for (int y=0; y<26; ++y) if (inside(y,i+1)) { if (x!= y) { if (inside(x,i+1)) update( f[i+1][y], f[i][x] + T(i+1)-1); else update( f[i+1][y], f[i][x] + T(i+1) ); } else { // if x==y if (T(i+1)==1) update( f[i+1][y], f[i][x] ); else update( f[i+1][y], f[i][x] + T(i+1) ); } } The complexity: O(length(S)*26*26) 11553 - Grid Game This is a search problem, although it looks like DP. We just need to enumerate permutations of 1-n (n<=8), stored in order[n], and add grid[i][order[i]] (0<=ib>a).
The main idea is to fix a and increase b one by one, get corresponding c.
For each number a=x, there is two category:
1: If x<=n/2, it is normal case and we can compute the sum for each x by : f(x）＝ （x-1)[ n-(x-1)-(x+1)]+[(x-2)+1]*[x-2]/2; 2: Otherwise, for each x>n/2, there is no x-1 c because (n-(x+2)+1)<=1000000, obviously, we cannot compute the sum directly, so I simplify the formula and get the sum for numbers of 2 categories: 1: sum1=-n*k+(-k*(k+1)*(2*k+1)+(3+2*n)*(1+k)*k)/4; where k=n/2; 2: sum2=(j*(j+1)*(2*j+1)/6-j*(1+j)/2)/2; where k=n/2+1; In this case, we have to consider an exception, namely n<=4, because k=4/2+1=3, however there is no such case that a=3; 11564 - Just A Few More Triangles! This is a very hard problem. Here is how I solve it: Consider the function f(n)=number of solutions (x,y,z) of x^2+y^2=z^2(mod n) (0<=x,y,z<=x<=y. Since f(n) is multiplicative, it is enough to determine f(p^k) for a prime k. Unfortunately, there is no easy formula for f(p^k). For a given p>2, I defined c(i,k)=number of solutions of x^2+y^2=i(mod p^k), since I observed that knowing c(0,k),c(1,k),...,c(n-1,k) we can compute f(p^k).
And to compute c(0,k),...,c(n-1,k) we can compute c(0,i),...,c(n-1,i) for i=1,...,k.
(there is some numerical relations to compute c that can be observed by trying).
There are two different relations when p=1(mod4) and p=3(mod4).
For p=2, it does not obey this relation, so I precomputed the value f(2^k) and saved it in a constant array.
11577 - Letter Frequency
Straightforward ad hoc problem, just follow the problem description.
11578 - Situp Benches
Use Dynamic Programming. Let f[i][j], i=1..n, j=1..5 be the minimum total cost when we consider student 1..i and the angle of the two benches are 10j and the angle used by student i.
11579 - Triangle Trouble
Sort the sides length in increasing order. It can be proved that to form the largest area triangle we only need to consider three consecutive sides in the sorted order.
11581 - Grid Successors
The greatest index i is the one right before the cycle: f(g), f^2(g), ..., f^i(g), (cycle)
In order to compute i easily, we map each grid to a number in [0,2^9).
11582 - Colossal Fibonacci Numbers!
The sequence f(i) mod n is always periodic, i.e. there exists k such that f(i+k)=f(i) mod n for all i.
We compute the period of the sequence f(i) mod n for all n.
Now f(a^b) mod n = f((a^b)mod period[n]) mod n.
11584 - Partitioning by Palindromes
Dynamic Programming Solution.
First, we compute boolean table pal[i][j]=true iff s[i..j] is a palindrome.
This table can be computed in O(N^2).
Then we compute f[i]=minimum number of paritions of s[1..i];
This can also be computed in O(N^2), given that we already have the table "pal".
11586 - Train Tracks
The answer is "LOOP" iff there is more than 1 piece and the number of M is equal to the number of F.
11596 - Convex Orthogonal Polygon
Let C0 be the perimeter of the bounding box B0, observe that A1=A0+C0+4,...
Eventually, we have a quadratic equation of n: An=4*n^2+C0*n+A0
By trying all the divisors of B0, we can enumerate the possible values of C0 and solve the equation for n.
Note that C0=2(w+h) is always even, so to solve the quadratic equation, we only need to compute delta'=(C0/2)^2-4(A0-An)
11597 - Spanning Subtree
Number of edges = n*(n-1)/2 and each spanning tree has n-1 edges. Therefore the number of maximum spanning trees is at most n/2. In can be proved that this upper bound can always be achieved.
Reading http://en.wikipedia.org/wiki/Gambler's_ruin there are 2 cases to consider. The first case is "fair coin flipping" (AT = 3) and the second case is "unfair coin flipping" (AT != 3). The formula are given in the link to the wiki.
11501 - Laurel Creek
This problem is not solved yet.
11502 - Rocket Stages
This problem is not solved yet.
11503 - Virtual Friends
This is a simple disjoint sets question. Watch the part about updating the number of people in the "social network", i.e. the set after each union_set. It would be necessary to use STL map (or some hash table) to speed up the searching.
Note: There is one thing to be careful with: the number of people who just become friends. I suppose this part is quite tricky because I output 0 if two people has been included in a single network, however, what is required turns out to be that you must output the number of people in the network, namely, if A, B, C know each other and the input is "A B", you have to output 3 instead of 0 or 2 (the reason why I got WA a couple of times. )
11504 - Dominos
The question has to be modeled as an directed graph. We cannot search for nodes that have no in-degree edges and DFS from there, because the graph is not acyclic. So we have to decompose the graph to a DAG (directed acyclic graph) first before we can search for the number of nodes with no in-degree edges. So to be able to do it, we have to decompose the graph to strongly connected components. Once the directed graph is transformed into another graph that composes only of the strongly connected component, the graph becomes a DAG. However, is there really a need to do DFS after all the strongly connected component is found? The answer is no. All we are seeking for are the number of strongly connected component that does not have any in-degree edge from a node that is outside the component.
To count the number of such strongly connected components, use Tarjan's algorithm(http://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm).
11505 - Logo
This is just a simple simulation. Just follow the instructions.
Be careful with precision error, pi = 2*acos(0.0);
11506 - Angry Programmer
For this question, it could be seen clearly that it is a min-cut question. First to make the graph directed, split each edge into 2 arcs. Also split the nodes into two nodes each, innode and outnode. Then link all the inarcs to the innode and all the outarcs to the outnode. Finally link the innode and outnode with the cost it takes to blow up each computer.
11507 - Bender B. Rodriquez Problem
This is a simulation problem. We can use 1-6 to represent the +x,-x,+y,-y,+z,-z, and write a function to enumerate all possible bending cases.
11508 - Life on Mars?
This problem is a problem to re-arrange the order of the array. Observe that if and only if there is some element in the sequence is greater than n, the message is hacked by Martian. (very easy to prove) Then, re-arrange the sequence of the sequence. Just make sure that S(i)=i, if i is in the sequence. The others, just fill in by ascending order.
This is an ad hoc problem and my solution is exactly the same as GY's.
Basically, if s(i)<>i, let s(i)=p then s'(s(i))=s'(p)=s(i)=p , hence s'(p)=p. Then we can just fill all i into i th place as many as possible and the value of other place doesn't matter.
Only" hacked version" appear when there is a number greater than the number of elements.
11509 – Touring Robot
To solve this problem, we need to calculate exactly the ccw angle between 2 given vectors. To accomplish the purpose, dot product and cross product can be combined to get the sin and cos of the respective angle. By knowing the sign of cos and sign (-ve or +ve), we can decide on which quadrant that the angle between the 2 vector lies. Thus, the exact angle can be determined. Though it is not stated explicitly in the question, one turn is 360 degrees or 2*pi. A useful function (C - math.h) for this question is atan2. Just simulate accordingly.
Tricky problem dealing with floating points. Starting from the first point, keep moving to successive points, finding the angles between lines made- taking care that the measurement is anticlockwise. The question is quite ambiguous, and what is asked for is the number of 360 * rotation the robot makes. Useful to use the function atan2(y,x) defined in cmath that returns the radian angle that (x,y) ---(0,0) makes with the + direction of x axis.
11510 – Erdos Unit Fractions
It is a Math problem. It seems quite difficult at the first sight. But I realized that we can just search for the result. For this problem, if n is even, the answer is obvious (let x=n/2 y=n z=n). If n is odd, we assume that x<=y<=z, so 1/x>=1/y>=1/z. As 1/x+1/y+1/z=4/n so 4/n >=1/x>= 4/3n. so n/4+1<=x<=3n/4+1. Similarly, work out the range of y: nx/(4x-n)+1<= y<=2nx/(4x-n)+1....so search the x and y, computer z, if z is integer, print out the result. One more thing to consider: if 4/n-1/x=1/k, just let y=z=2k. Take note to use long long int. Do not worry about the time limit. It is 5 sec, and my program only takes 0.02sec. 11511 - Frieze Patterns If we use simulation, we need a table of 10^8 columns, and 1000 rows, which is impossible. Also, if we fill in the table column by column, we only need the previous one column. So we can use a array of 1000 elements, and repeat filling in the array as a column. But if there are 10^8 columns, we still get TLE. So, we need to find some pattern of the output. I noticed that the data in each column will repeat after certain columns. So we just need to find the period, and then a lot redundant calculation are avoided. 11512 - GATTACA To find repeated substring in a long string S, we cannot use naive solution! We need to use a good data structure: I use "Suffix Array" (see http://sary.sourceforge.net/docs/suffix-array.html) The original suffix array has indices, however, we do not use these indices for this problem. I left the indices below for clarity. I use the second sample input, S = "GAGAGAG" for illustration. This string S has 7 possible suffixes (a simple loop can be used to produce these suffixes), they are: G, starting from index 6 AG, index 5 GAG, index 4 AGAG, index 3 GAGAG, index 2 AGAGAG, index 1 GAGAGAG, index 0 We can sort these suffixes into (e.g. by storing these suffixes in STL
AG, index 5
AGAG, index 3
AGAGAG, index 1
G, index 6
GAG, index 4
GAGAG, index 2
GAGAGAG, index 0
Now that we have these sorted suffixes, we can easily find the common substrings by comparing adjacent suffixes...
(these substrings are indicated with bold, italic, or underline)
Here, we can see that "GAGAG" is the longest substring.
Now, iterate through the set of suffixes one more time to see how many times "GAGAG" occurs as the prefix of these suffixes!
Note that you need to output "No repetitions found!" when necessary.
11513 - 9 Puzzle
This is a graph&BFS problem, pecalculation and implementation are equally important.
Basically, I do BFS from the original point (1 2 3 4 5 6 7 8 9) to generate all possible state and use stl map as a hash table(simple hash: ((1 2 3) (4 5 6) (7 8 9))-->987654321 .) when doing the BFS.
3 array I use ( the size of array <20000, by checking the final size of map container) link[] : record the father node for each state(for printing) depth[]: record how many steps needed to get this state from original state method[]: record which method is used to generate the current state For each case x, check if x is a valid state by map.find( hash value of x) . If yes, call the print method which is implemented by recursion, if not, output error message. 11514 - Batman This is a classic Dp problem and some skill of string operation is needed to process the input data. Let's say, assp[i][j] represents the minimum energy consumed when you use first i weapons to destroy first j villains. Dp formula is assp[i][j]=min{ assp[i-1][j], assp[i-1][j-1]+cost[i][j] (if i th weapon can defeat j th villian) } , then check if assp[p][v]<=upper limit of energy STL map provide easy access when checking the name list. 11515 - Cranes Given that there are at most 15 cranes, it is possible to brute force it as we only need to check 2^15 states (all the possible combination of cranes) to find the maximum area that is covered by the crane and yet the arm of the crane will not hit another crane. 11516 - WiFi This is a problem about binary search. First, we read in the input and sort them. Do the binary search for all the possibilities of the maximum distance. For convenience, the maximum range the server can cover is twice the max distance.(the distance now all become integers). If the distance is possible, the range of length k can cover all the houses. All possible ranges are from 0 to the difference between the start and the end. Do binary search for that until you find the point that distance k can cover all the houses while the distance k-1 cannot. More specifically, in the process of judging whether distance k can cover all houses, we just see whether t(the number of servers) ranges of length k can cover all houses. that is, we start from the first and go length k, the next range, go from the smallest one which is not covered by previous one........until the last range, see the last range exceed the last house or not. if so, it can. if not, it cannot cover. The complexity is O(nlgn) as the sorting. It will not exceed the time limit if you always use the binary search. This is a search problem. All access points can cover some intervals in the axis, and all the houses are to be covered by at least one interval, and the max size of intervals should be minimized. Since all houses coordinates are integers, the size of max interval must be a integer. I assume all intervals are of the same size, and use binary search to minimize the valid (can cover all houses) intervals. 11517 - Exact Change A slight variation to the 0-1 knapsack problem. A simple DP is outlined. Define f[i][k] as the minimum number of coins required to get sum exactly i using the first k coins. Since, this implementation uses excess memory, storing 2 copies of the above array, for k and k+1 at any point of time will suffice. The Memory limit for this problem even though not mentioned, I guess to be 4 MB. This is a DP problem, and instead of using a two dimensional array as mentioned in the solution, I only used a one dimensional array a[20010], a[i] record how many coins are needed at least to form i cents. First fill all elements in a[] with a big number MAX, and perform the 0-1 knapsack dp. Finally, look for the number k closest to the price, and a[k] is not MAX. 11518 - Dominos 2 This is a search problem. First, we construct a directed graph, if domino number x falls, it will cause domino number y to fall, then there is an edge from x to y. Then, use depth first search (or flood fill) and count how many dominos will fall over. 11519 - Logo 2 Let O(0,0) be the starting point, O’(x,y) be the ending point, A(xA,yA) be the point where we meet the missing number. If (the missing number is in the move “bk” or “fd”) result = distance between O and O’ else (if the missing number is in the move “lt”) result = angle O’AO else //(the missing number is in the move “lt”) result = - angle O’AO The complexity: O(number of moves) 11520 - Fill the Square This is a greedy problem. Lexicographically smallest output is required, so just choose the smallest valid (different from adjacent letter) letter in each empty grid row by row from left to right. 11521 - Compressor This problem is not solved yet. 11522 – Pyramid Number Instead of formulate the question as how many numbers are strictly pyramid numbers between a & b, it could be formulated as how many numbers are not strictly pyramid numbers. This is because there is only a limited number of numbers that are not strictly pyramid numbers. This set of numbers could be easily brute forced. This is Ad hoc problem + DFS. There is no rule to judge if a number is pyramid number except brute force, however, by a simple DFS, it is obvious that any number greater than 77 must be a pyramid number. Therefore, we can just brute force all number less than 77 and print out the answer according to the test data. Question does not tell us a
- paper -> 1
- glass -> 2
min[0][0] = we have processed until position 0 (the 1st paper) with the right most that 'still have not been processed' material is non-recyclable material (value: 0)
min[2][1] = we have processed until position 2 (the 2nd paper) with the right most that 'still have not been processed' material is paper. (value: 1 - Remove glass and leave 2 papers unprocessed)
min[4][1] = we have processed until position 4 (the 3rd paper) with the right most that 'still have not been processed' material is paper. (value: 2)
min[4][0] = we have processed until position 4 (the 3rd paper) with the right most that 'still have not been processed' material is non-recyclable material. (value: 3)
11524 - InCircle
We first assume n1 and m1 is the length of respective segment, then we can know the length of each edge. Then we use s=sqrt(p*(p-a)*(p-b)*(p-c)), where a,b,c are the length of three edges, and p=(a+b+c)/2, to get the area of the triangle. But it is not the final answer because our assumption at the beginning may not be correct. So we use S=p*r' to get r', and the real area of the triangle is S*(r*r)/(r'*r').
11525 - Permutation
We can use Cantor's theory (not sure whether the name is correct) to calculate ith permutation of n numbers in Lexicographically order. Each time, we need to pick kth smallest number in an array for some number k, and there are at most 5000 numbers. Naive algorithm to pick the kth number costs O(n), which will end in TLE. So we need to implement an interval tree which each pick costs O(log(n)) time.
11526 - H(n)
The problem is not difficult but we need to consider the problem of time limit exceeded, e.g. we are computing n/n, n/n-1, .....there are so many ones and twos, these can be computed in one step. We can observe the number of 1, 2, 3.....the number of j is n/j - n/(j+1). so when the number is small and many, we use the previous method. for numbers big and few, just use the original method. We can set the break point at sqrt(n). Do not repeat the values around sqrt(n). Try to avoid division by 0 and sqrt of negative numbers.
11527 - Morning Walk
Given a positive integer S, find all the triangles that has perimeter S, integer side lengths and integer coordinates
Solution:
By Pick's Theorem, a triangle has integer coordinates iff 2*Area is an integer
Using Heron's formula we can deduce that a triple a, b, c, in which a+b+c=s is a solution iff
s(a+b-c)(a+c-b)(b+c-a) = 4k^2, where k is an integer
A program doing exhaustive search on a and b will not pass the time limit.
Here we do an exhaustive search for a and based on a, reduce the search space for b:
1. For each a, factorize b+c-a=s-2a, combining with the factorization of s to determine the largest prime factor p of s*(b+c-a) that wasn't squared
2. It implies that either (a+b-c) | p or (a+c-b) | p. i.e., either 2b=s-2a (mod p) or 2b=s(mod p)
It means we can reduce the search space for b by a factor of p, which turns out to be a very good optimization.
This optimization idea is from Derek Kisman.
11528 - Switch Grid
Construct a bipartite graph that has N+M vertices
N vertices on the left represents the rows and M vertices on the right represents the columns
There is an edge (i, j) iff cell (i,j) contains a switch
For each vertex i, let b[i]=the difference between final and initial state of bulb i (modulo 2).
The problem now is to select some edges of the graph s.t. the number of selected edges incident to any vertex i is b[i] (modulo 2)
I use the following algorithm:
Repeatedly try to find a path between i and j where b[i]=b[j]=1.
If at any time, we cannot find such a path, then there is no solution (haven't proved rigorously)
11529 - Strange Tax Calculation
This problem is not solved yet.
11530 - SMS Typing
This problem is basically a mapping problem. You need to map each character available on the SMS keypad to the number of keypresses needed. Since the characters involved are only the space character and all the lowercase alphabets, I can simply create two arrays, one containing all the characters involved in ascending order (by ASCII code) and the other containing the number of keypresses needed for each character. Thus from there, I can binary search each character in the characters array and use that index to get the number of keypresses. I then add all the keypresses up to retrieve the total.
For C\C++ programmers, make sure not to append a \n when reading in the number T as this will lead to consumption of spaces if the 1st test case starts with spaces.
Faster, you do not need to do binary search, a direct addressing table of character à num of key presses required is sufficient as there are only 26 (27 characters including space).
11531 - Solve the Broken Maze
This problem is not solved yet.
11532 - Simple Adjacency Maximization
This is a greedy problem.
If there are enough 0s (P/2<=Q), the answer should look like 00..00 101 101..101 If there are not enough 0s, the answer should look like 101 101..101 11..11 Use long long! To test your program, use this test case: 1 50 0 Answer: 1125899906842623 11533 - Special Number The problem seem to be easy at first. The algorithm is just follow the instruction, multiply y (the y times of the original number), and take care of the carry digit. When the digit you got is the same as the first digit, and there is no extra carry digit for the next digit, that means you got the number, just print it out. If we cannot get the kind of repeat for n^2 times, print out no solution. Something to take note: y need not to be smaller than n. So the carry digit can be very big, so you need to consider all carries but not only the previous digit. Moreover, the leading 0 is allowed: "10 6 100", the output should be 006 instead of no solution. and "2 0 0" the output should be 0 instead of no solution. 11534 - Say Goodbye to Tic-Tac-Toe This problem is not solved yet. 11535 - Set of Marbles Every state can be represented by a binary number, e.g. Marbles 1 and 3 in the first box out of 4 marbles can be represented by 1010. The idea is to transform each “n” bit binary number into its corresponding Gray Code number. The specialty of the gray code representation is that every consecutive number differs from the previous number by a Hamming distance of 1 i.e. flipping just one bit. Thus from the specified state in the gray code, you can traverse linearly to all other states. 11536 - Smallest Sub-Array This question turns out to be a search problem, however, it is a ad-hoc in fact. First of all, I use a array to store the value of each element. (Before do this step, if m
Caution: there is space between ":" and answer, i got a couple of presentation error for this reason
11537 - Secret Problemsetters' Union
This seems like an easy problem at first. It's a simulation problem that requires the use of correct data structure to prevent a TLE. However, this problem is full of traps. First trap is that you need to print an empty line in between test cases. That statement means EXACTLY that i.e. you have to test if the current test case is the last test case and if such, no blank line should be printed out. Second trap is if a merge operation has already occurred, all other merge operation instructions must be ignored and update and insert operations must be ignored if they do not operate on bank #1. Third trap is that the instructions will only be in capital form as mentioned. The fourth trap is that make_heap(which is O(n)) is only good for the merge operation. For the insert and update operations, you must use push_heap and pop_heap (both k lg n) as it seems that in most cases k is much smaller than n and results in a much faster operation (initially I inserted or removed everything before making heap as I assumed k was very large all the time). The fifth trap is you must clear the vectors you used after every test case. The last trap is that for the update operation, you must make sure that the vector that you are operating on is not empty. If it is empty, then you must terminate the loop. Also you must have a flag to check whether you have entered the loop or not. If you did not enter the loop then you must print "0 0". Otherwise, you can print the minimum and maximum values (which might actually refer to only one value i.e. they might be the same).
11538 – Chess Queen
This is a math related game problem....or somehow ad-hoc problem
Observe that there are two cases of attacking, so first consider the horizontal and vertical: there are m*(m-1)*n + n*(n-1)*m.
Then, consider the two kinds of diagonals: the one with length n and k (2<=k
This is a math problem. To calculate the number of ways to make the queens in attacking position, we can divide the answer into three parts: two queens in the same row, on the same column, or the same diagonal. All data must be unsigned long long, and the output must be %llu in C (%I64u was WA, can’t understand).
Answer=m*(m-1)*n+n*(n-1)*m+(n*(n-1)*(2*n-1)/6-(n-1)*n/2)*4+2*n*(n-1)*(m-n+1);
11539 - Another Word Game
This problem is a DP problem.
Define f[i] as the maximum possible score for the first I characters of the string. Since you have only 10^4 words in the dictionary of maximum 100 characters each, check whether any of the words end at I, if so f[i]= f[i-length(specific word)]+Weight(specific word) ,else it is max( f[j-1] + (i-j+1)*p) i>=j>=i-99;
The overall complexity is 20*10000*100*log10000 which will run in 7 seconds.
11540 - Sultan's Chandelier
This problem is not solved yet.
11541 - Decoding
This is a fairly standard problem. For every line, just read the line in character by character. Be sure to read in one character followed by one number (and not just one DIGIT of a number) at a time and use a for loop to expand the string accordingly. Instead of reading the lines line by line, it's safe enough to just test for the presence of \n to know that it is the end of the line so a separate buffer is not needed.
11542 - Square
Use Gaussian Elimination over the field GF(2) to reduce to row-echelon form.
Number of solutions = 2^(number of columns - number of rows) in the row-echelon matrix.
11543 - Two Points And Curious MumboJumbo
This problem is not solved yet.
11544 - Recruiter's Problem
This problem is not solved yet.
11545 - Avoiding Jungle in the Dark
This problem is a kind of Graph problem.
Starting from 'S' (leftmost) at time 6 am, a pilgrim needs to reach destination 'D' (rightmost) by traversing plain land '.' or jungle '*'.
He has two options every step:
1. Walk to the right by 1 step in 1 hour
2. Rest in the current position for 8 hours
The objective is to find the shortest path from 'S' to destination 'D'.
There are constraints:
a. The pilgrim cannot be in '*' during night time (6pm-6am) and
b. The pilgrim cannot walk for 16 consecutive hours.
Enumerate all the branching possibilities and pick the shortest one.
There are tricky test cases, try these:
Input:
3
S**...*.*****D
S..........****.....*****.......*.......**..****.....*****.......****........****.........***D
S*..**..***......D
Output:
Case #1: -1
Case #2: 221
Case #3: 25
11546 - Olympic Swimming
Let L[i][j]- be the number of hurdles in the ith lane spanning the first j length marks.
Assume the number of lanes is 2. So, you have to find, two length marks I and J , such that, J-I is maximum and the number of hurdles in the first lane between I and J and the second lane between I and J is the same. i.e L[1][j]-L[1][i]=L[2][j]-L[2][i] which is equivalent to (L[1][j]-L[2][j])=(L[1][i]-L[2][i])
So, if you have an array L[i] that stores L[1][i]- L[2][i] , for all I, you just need to find two indices such that their values in L are same and the difference is maximum. Fix j, search in log L time, the value of i.!
For k>2 , instead of 1D L, you encounter a 2D L, and the checking for I and J is the equivalence of 2 ID arrays.
The overall complexity is O( L*Log L * K). A map implementation is useful.
11547 - Automatic Answer
This is just another coding practice. Just follow the instructions. Solve-able in less than 1 minute. No trick.
11548 – Blackboard Bonanza
This problem is a manifestation of the DP Longest Common Subword. For every pair of strings, find the length of the longest common subword, and output the global maxima. The recursive definition is, lcsw[i][j]- as the length of the longest common subword ending at I in the first string and ending at j in the 2nd string.
For each test case, for all pairs of string, try to find the maximum number of candies that Alice or Bob can get. This will give you a O(n^4) solution which will pass the time limit.
This question is a simple brute force question using an O(n^4) algorithm. Firstly, we need to obtain two strings to compare against. This is done by comparing each string that has been read in against every other string. This takes O(n^2). Once we have the two strings, we obtain the greatest number of overlap in both strings by sliding one string below the other and searching for the characters that overlap. This takes a further O(n^2). Take not that the overlapping characters need not be contiguous i.e. for two strings, we only need the number of characters that are the same given, the same position in both strings.
11549 - Calculator Conundrum
As I have coded pollard-rho factoring method (http://en.wikipedia.org/wiki/Pollard's_rho_algorithm) before, I came across the idea of floyd's method of cycle detection (http://en.wikipedia.org/wiki/Cycle_detection) which solves the question with O(1) space. Using that solves the question. However, I believe it might be possible to use map too.
This an ad hoc and using STL set can lead to an easy solution.
For each case, test the number can be properly displayed or not. If yes, just square it, if not, divide the number by ten until the number can be properly displayed.
Using STL to detect the cycle, if a cycle appears, output the maximum number in the set.
This is a math problem about set. The problem is about the number cycle. If the number in the sequence appear again there must be a cycle. so we only need to check the maximum up to the cycle. square the initial number until it is of n digit. built a set to store the numbers appear. if we find the number is already in the set. stop and output the maximum. the maximum is updated when a new number appeared. The time complexity is about nlogn. the time required is about 2 sec.( time limit is 6)
11550 - Demanding Dilemma
On first sight, this is a simple question. Just make sure for every edge, there are only 2 nodes incident to the edge. However, question wants the graph to be SIMPLE, so two adjacent nodes can only be joined together by one edge. If two adjacent nodes are linked by more than one edge, then the answer is "NO".
Alternative hint:
This is a basic graph problem and there is a trick of implementation.
Given the n*m matrix, what we need to do is the compute the sum of each column and check if the sum=2 or not. If sum<>2, it is invalid because all edge must be incident on exactly two vertices. The matrix is not big (max 8*28) , O(m*n).
In addition, maybe it is necessary to check if there exists a loop between two vertices. I add this check to my program.
11551 - Experienced Endeavour
This problem is not solved yet.
11552 - Fewest Flops
Let F[i][x] = the optimal result for S=S1,S2,..Si and x is the last character of Si’.
We can calculate F[i+1][y] by F[i][x]:
for (int i=0; i
The main idea is to fix a and increase b one by one, get corresponding c.
For each number a=x, there is two category:
1: If x<=n/2, it is normal case and we can compute the sum for each x by : f(x）＝ （x-1)[ n-(x-1)-(x+1)]+[(x-2)+1]*[x-2]/2; 2: Otherwise, for each x>n/2, there is no x-1 c because (n-(x+2)+1)
And to compute c(0,k),...,c(n-1,k) we can compute c(0,i),...,c(n-1,i) for i=1,...,k.
(there is some numerical relations to compute c that can be observed by trying).
There are two different relations when p=1(mod4) and p=3(mod4).
For p=2, it does not obey this relation, so I precomputed the value f(2^k) and saved it in a constant array.
11577 - Letter Frequency
Straightforward ad hoc problem, just follow the problem description.
11578 - Situp Benches
Use Dynamic Programming. Let f[i][j], i=1..n, j=1..5 be the minimum total cost when we consider student 1..i and the angle of the two benches are 10j and the angle used by student i.
11579 - Triangle Trouble
Sort the sides length in increasing order. It can be proved that to form the largest area triangle we only need to consider three consecutive sides in the sorted order.
11581 - Grid Successors
The greatest index i is the one right before the cycle: f(g), f^2(g), ..., f^i(g), (cycle)
In order to compute i easily, we map each grid to a number in [0,2^9).
11582 - Colossal Fibonacci Numbers!
The sequence f(i) mod n is always periodic, i.e. there exists k such that f(i+k)=f(i) mod n for all i.
We compute the period of the sequence f(i) mod n for all n.
Now f(a^b) mod n = f((a^b)mod period[n]) mod n.
11584 - Partitioning by Palindromes
Dynamic Programming Solution.
First, we compute boolean table pal[i][j]=true iff s[i..j] is a palindrome.
This table can be computed in O(N^2).
Then we compute f[i]=minimum number of paritions of s[1..i];
This can also be computed in O(N^2), given that we already have the table "pal".
11586 - Train Tracks
The answer is "LOOP" iff there is more than 1 piece and the number of M is equal to the number of F.
11596 - Convex Orthogonal Polygon
Let C0 be the perimeter of the bounding box B0, observe that A1=A0+C0+4,...
Eventually, we have a quadratic equation of n: An=4*n^2+C0*n+A0
By trying all the divisors of B0, we can enumerate the possible values of C0 and solve the equation for n.
Note that C0=2(w+h) is always even, so to solve the quadratic equation, we only need to compute delta'=(C0/2)^2-4(A0-An)
11597 - Spanning Subtree
Number of edges = n*(n-1)/2 and each spanning tree has n-1 edges. Therefore the number of maximum spanning trees is at most n/2. In can be proved that this upper bound can always be achieved.
