Last updated on: 30 April 2009 04:09:45 PM

Comment on this volume: The hints for this volume are contributed by my CS3233 students:
900-949: Sivamani Varun (SV)
950-999: Zhang Ding (ZD)

Total submit-able problems in this volume: 100
Solved problems: 3
Problems in Wrong Answer list from this volume: -
Unattempted problems: -
Total hints in this volume: 29

900 - Brick Wall Patterns

Initially seemed very complicated but after working out a few examples -> it was pretty clear the program was just asking to output Fibonacci numbers.

902 - Password Search

I started off my term assignment with this problem and but eventually become the last problem I solved. A very straightforward problem but kept on getting TLE. Its basically an optimization problem involving substring generation. I kept getting TLE because I used the substring function of <string>. After some researching upon string matching devised my own variation of the Rabin-Karp algorithm solving it in 1.5 seconds.

906 - Rational Neighbor

This is a math problem. The algorithm is given in the problem. You just need to implement such a way that you don't get floating point errors or run into an infinite loop.

907 - Winterim Backpacking Trip

This is a DP problem (finding maximin). First fill up the table with the first column containing the cumulative distances so far. Then through a bottom up DP strategy you can fill it up finding the maximin distance.

908 - Re-connecting Computer Sites

There seems to be a lot of information in this problem - do not be daunted by it and also the large size of n (<=1000000) - its basically a straightforward application of Kruskal's algorithm to find a MST. No need for priority queues or any other optimizations. Simple disjoint data structure is enough and it works very fast too.

910 - TV game

This is a DP problem. Just storing the last two rows and also storing the two possible moves from each letter is enough. Be vary that there can multiple ending locations and you need to sum them up for final answer.

911 - Multinomial Coefficients

This is a math problem. Pre-calculate the binomial table (using DP) and simplify the multinomial coefficient formula such that you work with separate products and just call from the table to prevent out of bound errors.

913 - Joana and The Odd Numbers

A straight forward problem - which I managed after working out on paper to reduce to a simple pluggable formula using the fact that addition of consecutive odd numbers always is a perfect square number. But was very surprised at my rank of 1529.

914 - Jumping Champion

A tricky problem that involved prime numbers, sorting and linear searching with a twist. The phrasing of the problem
was not very clear and was not sure whether it was asking the highest frequency of the difference or the difference with the highest frequency. I could have used a count sort method to get the final answer in O(n) but was not sure how big the upper bound between the differences of consecutive prime numbers would have been, hence went for the safer vector and sort method.

918 - ASCII Mandelbrot

Wow! What a problem. When I was browsing through the problems I thought this was the hardest problem on the entire list but then remembered that the more complicated a problem sounds the easier it probably is. It turned out to be easy coding but then suddenly became a nightmare as I had no clue why I kept getting WA. Apparently my own outputs to the two test cases were wrong, with just one character off. (lesson learnt: Always use diff/fc to compare). After painstaking debugging I came to a conclusion that it was due to floating point errors that my program kept giving the WA. Luckily I remembered reading about a floating point comparison function by the great Donald Knuth in 1102 - > which I used to get AC.

920 - Sunny Mountains

This has to be the first ever computational geometry problem that I solved and I thoroughly enjoyed myself. I basically sorted the lines according to the x axis coordinates and adopted a greedy strategy of picking only the y coordinates who are greater than the current one and finally using a formula which I derived to work out the distance.

924 - Spreading the News

My first ever problem to solve using BFS. Solved it immediately after lecture 5. You need to stored the height of each node (which represent the day) and store the neighbors of each node at another array indexed according to height.

926 - Walking Around Wisely

This is a DP/counting problem. The main issue in this problem is on how you store the edges representing the roads you cannot use. Once you solve that issue its pretty straightforward recurrence relation, with a DP table. Make sure you use unsigned long long as the value get pretty large.

927 - Integer Sequences from Additions of Terms

Another tough sounding problem that actually turned out to be easy. Just remember to use unsigned long long as the values can get really really big.

928 - Eternal Truths

This is a BFS problem. This time the number of possible moves is always changing. The issue with this problem is on how you deal with the boundaries. You also need to be careful that you don't run into a wall.

929 - Number Maze

This is a shortest path problem. But due to the input size of the problem you will need to use an optimized version of Djikstra's algorithm with priority queue or else you will get TLE or MLE (if you use a 3-d array).

930 - Polynomial Roots

An ad hoc problem but with misleading details about input. It was not stated anywhere that the number representing the total test cases would also be a floating point number -> as a result I got about 10 TLEs unnecessarily. After I made it that it can read it as floating point number did I finally get AC.

932 - Checking The N-queens Problem

Although the problem sounded easy, coding it seemed to be very challenging. And also, once again the problem phrasing was misleading. It never mentioned that there will be multiple inputs but apparently it had, hence took me couple of submissions to get it. I got rank 10 for this problem even though mine was very inefficient. It can be made very efficient by using bit manipulations.

933 - Water Flow

This is an Ad hoc problem. Reading in the input is one of the challenges in the problem. There is a very nice solution if you work backward. Although the problem does not state, its a multiple input problem. Print out the output with a blank link separating multiple test cases.

935 - Smart Strategy

This is a math problem. You need to consider all the possible cases on who starts first and who loses in the previous round to get the right answer. Although the problem does not state, its a multiple input problem. Print out the output with a blank link separating multiple test cases.

939 - Genes

This is a graph problem. I just brute forced, keeping on repeatedly processing the vertices until all the status of each node has been determined. Then just print out in alphabetic order the names of the nodes and its status.

940 - Autobiographical Numbers

This is a math problem. The key to this problem is that there there are only 3 possible numbers that can appear in the numbers in any base, 0,1, and another number. Exploit that pattern and print out all such numbers.

941 - Permutations

This is an ad hoc problem where you have to find the nth permutation of a string. Brute forcing or using stl::next_permutation will time out. First, find number of permutations left, then find which section the number will fall into and then insert the characters in there and finally print it out.

942 - Cyclic Numbers

Seemingly difficult problem at first glance but after working out some divisions on paper, you will start to see the pattern. Just need to store the remainder at each stage of division and keep checking whether that particular remainder had already been calculated. If so that's the length of the recurring decimal. If you hit a remainder of zero anywhere that's the division.

943 - Number Format Translator

This is an ad hoc problem. It is quite tricky as you have to convert words written in Portuguese into numbers. Lots of test cases are given so it kind of simplifies the problem. The only issue you need to treat numbers greater than >=1000000 separately.
Although the problem does not state, its a multiple input problem. Print out the output with a blank link separating multiple test cases.

944 - Happy Numbers

This problem is a DP problem. I used a bottom up DP strategy to pre-generate all my happy numbers and the lengths of the sequences, by first pre-storing all the happy numbers up to 100 (by observing it can be seen that all happy numbers can be generated from those from 1 to 100) and then working them up from there.

945 - Loading of a Cargo Ship

This is an ad hoc problem. I used a two dimensional matrix to keep track of all the cargos as opposed to a queue as it makes it much easier to print out output. Although the problem does not state, its a multiple input problem. Print out the output with a blank link separating multiple test cases.

948 - Fibonaccimal Base

This is a greedy problem. Although I was initially unsure about how to correctly get the Fibonanci representation but I went with my intuition with a greedy solution and it turned out to be correct. Now I finally understand what you meant when you said 'If not sure just go with greedy solution' during week2 lecture.

949 - Getaway

This is a BFS problem. Its a variant on the shortest distance in a maze. At certain nodes, you cannot be there at certain given times. So you need to push back the source node once again into the queue when such a node is encountered.