# SPOJ: 1728. Common Permutation

Given two strings of lowercase letters, a and b, print the longest string x of lowercase letters such that there is a permutation of x that is a subsequence of a and there is a permutation of x that is a subsequence of b.

Solution: That’s short and nice problem. You have to find all letters which are in both strings. I’d actually like to see some other implementations of this. I bet there are some languages which handle this in a smart way.

# SPOJ: 3374. Scavenger Hunt

He does a poor job, though, and wants to learn from Bill’s routes. Unfortunately Bill has left only a few notes for his successor. Bill never wrote his routes completely, he only left lots of little sheets on which he had written two consecutive steps of the routes. […]
This made much sense, since one step always required something from the previous step. George however would like to have a route written down as one long sequence of all the steps in the correct order.

Solution:

# SPOJ: 1268. CN Tower (Easy)

On the way, she stops in Toronto to do some sightseeing. The unfortunate thing about travelling is that everyone back home expects her to bring back pictures of everything. […] 351 m up the tower is the “360” rotating restaurant, which rotates a full 360 degrees every 72 minutes. From there, Christy can see the whole city, and take close-up pictures of all the landmarks using her fancy new 100x optical zoom camera. Since the restaurant itself rotates, she only needs to stand in one place to take pictures in all directions. […] Since the restaurant staff only realize she is a tourist once she starts taking pictures, we begin measuring the time required once she takes her first picture.

Solution: Afterwards this problem is really easy, however I first made it too hard. The trick is pretty easy we are looking for the biggest distance between each consecutive degree. To check the difference between the highest and the lowest I appended (lowest + 360) to the list of degrees. The + 360 helps to calculate the distance more easily. Afterwards just select the biggest difference and calculate the minimum time.

# SPOJ: 1030. Triple Fat Ladies

Pattern Matchers have been designed for various sorts of patterns. Mr. HKP likes to observe patterns in numbers. After completing his extensive research on the squares of numbers, he has moved on to cubes. Now he wants to know all numbers whose cube ends in 888.

Given a number k, help Mr. HKP find the kth number (indexed from 1) whose cube ends in 888.

Solution: Yeah, an other number problem! And again I just looked for patterns.

Which gets us:

EDIT: Thanks to the anonymous person who found a simple connection between the numbers but can’t properly communicate. You can find the k-th number with this simple formula: $192 + 250(k-1)$

You should see that each number ends in 2. If you look closer you see that the last two digits are 42 if i is even, and 92 if i is odd. Let’s look at the other digits. We get:

If you do some basic arithmetics you see that:

You can calculate your first digits either recursively or search for a function. This takes probably some time, so I looked this sequence up. OEIS gives us the formular: a(n) = floor((5n-2)/2) for n > 2