Problem: generate a list of passwords by a set of words and rules.
Solution: in a rule, a digit is presented by a '0' and a word is '#', and then all digits can be iterated like incresing a bigint if '#' is neglected. Then loop through all rules and words and replace '#' with the given word.
Problem: convert a date to a new format called Doors.
Solution: count the number of days from 0001-01-01, subtract to 1998-06-24, and then divide by 365 and count the number of leap years. The period, month, week and day can be determined then.
Note: the 4th year is leap, but the 1bd year is not in the example output. Therefore, assuming 4bd is leap and so on. I also found a typo in the string literal, which takes quite a while.
Problem: anagram of a given word is the counts of each alphabets. The problem gives a list of words, and a query word asks the program to print all words with the same anagram.
Solution: just count, compare and print.
Problem: for a given graph, print the shortest path from one vertex to another. In 626, a cycle with 3 vertices is requested.
Size: 300 nodes at most.
Solution: either BFS or all-pair shortest path do the job. With a graph with N nodes and edges stored in list, BFS takes O(N) for each query. All-pair shortest path takes O(N^3) preprocess, thus much more inefficient.
Note: it is not specified, but all nodes are labeled with id from 1 to N. Furthermore, there exists no query from a vertex to itself. This makes codes compact.
Consider the following code, which matches a vector u to another vector v and then executes some functions if u == v
bool equal = true;
for(int i=0; i<n; i++)
if(u[i] != v[i]){
equal = false;
break;
}
if(equal){
/* do something with u and v */
}
Compared to the equivalent one using goto
for(int i=0; i<n; i++)
if(u[i] != v[i])
goto _inequal;
/* do something with u and v */
_inequal: ;
In such situation, using goto makes the code shorter and more intuitive.
Problem: given a set of 16 reserved words, transcript a program text to the compressed form that replacing reserved words and other identifier words to number labels.
Size: all identifier words is less than 40 characters and there is 2000 different words at most.
Solution: keep a table of identifiers, and replace strings line-by-line.
Note: an input line does not exceed 200 characters. Furthermore, all encoded identifier (including reserved words) are 3 or more characters.
Problem: binary knapsack problem with integer size. In the description, the knapsack is a CD with length N and the items are songs with length l1, l2, ..., lk. All numbers are integer.
Size: the number of songs k is less than or equal to 20, but N is not limited.
Solution: let s[w] be boolean, true if there exists a solution with length w exactly, and let c[w, j] true if item j is chosen in the corresponding solution. Then mark the table from s[0] to s[N]:
1) s[0] = true, c[0, j] = false
2) for w from 1 to N
for all j
mark s[w+lj] true if s[w] true and c[w][j] false
mark the corresponding c[w+lj][j] if s[w+lj] true
Then find the max w that s[w] true in the table. The general dynamic programming solution in Wikipedia also works.
Problem: print the factorial of a given number N, which is less than 1000.
Size: 1000! has no more than 3000 digits.
Solution: write a big integer with multiplication operation.
Note: computing and storing all 1000 factorials is efficient for multiple query. In practice, 2700 digits are sufficient for 1000!.
Problem: evaluate an integer expression with +, *, and (). The grammar of evaluting parentheses first, then multiplication and finally addition is given. Strings which are not in the grammar must report an error.
Solution: recursively parse the string according to the grammar. In fact, there are 3 recursive function to parse expressions, components and factors separately in my code.
Note: the grammar states positive integers, which includes 0.
Problem: given a set of regular grammar, answer the state of the input string in the corresponding FSA (Finite-State Automata). In problem 620, reporting the input is not in the grammar is also required.
Solution: because the spec gives only a couple of simple rules, we can solve it by checking the head and the tail of the given string iteratedly.
Problem: lexicographically number all words. Translation from both side is required.
Size: Not specified, but output is limited to words with 22 alphabets.
Solution: use big integers. Note that there is no zero in alphabets, each char must add 1 while changing base. For example, word zz = 26*26 + 26 = (25+1)*26^1 + (25+1)*26^0.
Problem: given a screen of dimensions W x H and the dimensions of 4 windows all in pixels, determine if there is a layout to resize 4 windows to cover the whole screen without overlapping or out of screen but still keeps the width-height ratio of each window.
Solution: there are 2 cases while spliting the screen with a straight line: 1) 2 windows in both sides, and 2) 1 window in one side and all 3 in the other. In case 1, we can examine all 3 positions. In case 2, the problem is then recursive since it is always this case when the number of windows is less than 3.
Note: we need to splite the screen vertically and horizontally, but switching width and height just convert the splitting to the other.
Problem: given the positions and cycle-lengths of a set of traffic signals, find integer speeds between 30 and 60 that pass through all signals without stopping.
Solution: iterately checking that if a given speed s make the car pass through all signals.
Problem: given n coconuts, find the maximum number of people p such that perform a process, which give 1 coconut to the monkey and hide exactly 1/p coconuts, repeatedly p times and the remaining coconuts can be divided into p equal shares. Size: it is believed that input number is less than signed 32-bit integer (2^31), but it is not specified.
Solution: for a given number of people p, the minimun number of coconuts n can be calculated by
1) find x, y such that x * p^(p+1) = y * (p-1)^p - sum{1 <= i <= p}{(p-1)^i * p^(p-i)}, and
2) the minimun n is y mod p^(p+1)
The above equation in step 1 is expaned from the whole sharing process, and the algorithm to finish step 1 is exactly extended euclidean algorithm. In step 2, it is observed that all solutions n are equivalent onder modular operation of given p. Building a table of min n(p) for small p can find the max p for given n effectively.
In this problem with n limited to 2^32 or 2^64, the maximum p is less than 30, and thus simulating the process with all possible p is efficient.
Note: the spec does not limit the last p shares from 0, and then n = 3 has a solution of p = 2.
Speeding up: iterately simulating 2 <= p <= 9 can cover all n n for 2 <= p <= 9 and computing modular is also fast. Efficient I/O operation is required since the computation time is little.
Problem: given a set of directed edges where both nodes of an edge are denoted by integers. Determine is such graph is a tree. Size: the number of edges and the size of the integer label of any node are not specified.
Assume the label of any node is less then 2^16. Use a set of integer pairs to store edges, and then collect the set of nodes from edges. To determine a tree, check that: number of edges + 1 = number of nodes. Secondly, find the unique root. Then perform tree search and check all nodes are reachable from the root. Finally, do remember that a empty tree has no node nor edge.
Notice: I guess the test data is small because of the running time is short, therefore, array and linear search are fast enough to perform set operations.
Problem: find the route from a given start to a given goal in a rectangular maze. The search goes west, north, east and south sequentially. The output is the maze with the route and all touched grids marked. Size: the maze is 12x12 at most.
The algorithm given is exactly DFS, and we need to mark the trace. The output maze includes a '+' on each grid, no matter there is a wall or not. Note that there is two blank line after "each" output maze, instead of "between" two consecutive mazes. I just wasted TWO HOURS on the last two blank line.
Problem: count the number of each decimal digits of given number, and then concatenate the counts and the digits to get a new number called "inventory'. Iterately get the inventory of the inventory, and find self-inventorying numbers or inventory loops. Size: each number have 80 digits at most, and 15 iterations to see at most.
It is easy since we don't need to find the loop after 15 iterations. Just do string manupulations and comparisons. Using char array speeds up.
Problem: sort DNA sequences by non-sorted-order, where "non-sorted-order" is the number of pairs of element that is not in sorted order. Size: 100 sequences and 50 elements at most.
The solution is straightforward: calculate the non-sorted-order and then sort sequences according to that order. Pointers speeds up program, and library-built sorting functions speed up programming.
Problem: given a set of processes. Each process has a list of instructions that sends/receives message to/from other processes. A instruction can be blocking or non-blocking. Output the finish time of each process, and the list of processes prevent a process to finish if it will never finish. Size: 26 processes and 100 instructions for each process at most.
Just do simulation run. Instructions and messages can be stored in arrays. Simulates until no instructions is executed and no messages passed. Finally, print the message queue is the answer.
Problem: convert a all bi-directional street map to a map that contains the same streets but maximum number of one-directional streets. Problem size: 1000 intersections at most, each intersection connects 4 streets at most.
Easy problem. The graph can be stored in an 1000x1000 array. Perform DFS and mark all back edges as a directed edge. In the DFS tree, each edge to a subtree is on a cycle if the subtree has a back edge goes up, and mark such edges directed also. Notice the directions of back edges and tree edges that on a cycle.