Just writing on a SPOJ problem I worked on recently. It’s called *Absurd Prices*, code name **ABSURD**.

In this problem, when given an integer representing an item’s price in cents, our program has to determine whether the price is *absurd *or not.

There is an algorithm to calculate the *absurdity *of an integer: the higher the absurdity, the more absurd it is. An integer is considered absurd when within the range there is an integer with a lower absurdity.

To find the absurdity of a price:

- Remove all the trailing 0’s from it
- Count the
*length*of the remaining number - The absurdity is twice the length
- If the number (with trailing zeroes removed) ends with 5, subtract 1 from the absurdity

As a result of these rules, prices with a lot of trailing zeroes, like 3500000, would have a very low absurdity, while those without trailing zeroes, like 7999999, would have a much higher absurdity.

A brute force approach seemed at first to be the way to go. This is because the range, isn’t too big and it isn’t a big deal to simply calculate the absurdity of all of them, and mark it as absurd when any of the integers in the range has a lower absurdity.

However, the time limit is very strict for this problem. Even when my program only checked 50 random numbers in the range, the system returned with TLE (Time Limit Exceeded)!

Fortunately there is a better way of solving the problem.

Given a range, it is easy to** find the least absurd number in the range**. For example, if our minimum and maximum bounds are 6655 and 7799 respectively, it’s easy to see that the least absurd number in that range is 7000, simply because it has the most trailing zeroes.

The algorithm that we can use to find the least absurd number in a range (defined by two integers) is follows:

- In their decimal expansions, compare the first characters, then the second characters, etc, until the character is different.
- The minimum absurdity is .
- If the character of the smaller number is less than 5, and the character of the larger number is five or greater, subtract 1 from the minimum absurdity.

Here’s my implementation in Haskell:

-- Integer with trailing zeroes removed removeZeroes x = head . filter (\n -> n `mod` 10 > 0) $ iterate (\n -> n `div` 10) x -- Calculuate the absurdity of a price absurdity x = let r = removeZeroes x d = fromIntegral . length $ show r l = r `mod` 10 in if l == 5 then 2*d-1 else 2*d -- The minimum possible absurdity in a given range minabsd a b | a == b = absurdity a minabsd a b = let c = show a; d = show b sm = fromIntegral . length . takeWhile (uncurry (==)) $ zip c d lst = (c!!sm,d!!sm) offset = if fst lst < '5' && snd lst >= '5' then 1 else 0 in minimum [absurdity a, (2 * (sm + 1) - offset), absurdity b] absurd x = let r1 = ceiling $ 0.95*(realToFrac x) r2 = floor $ 1.05*(realToFrac x) absx = absurdity x in absx > minabsd r1 r2 main = interact run where as s = let k = read s in if absurd k then "absurd" else "not absurd" run = unlines . map as . tail . lines

as you said that we compare characters in their decimal representation, so what if the lengths are not equal?

LikeLike

Oh I think that’s pretty trivial. If you have xxxxx and xxxxxx then the lowest in the bound is 100000.

LikeLike

sorry, but didn’t get you,is the value always 100000 for any difference in length? E.g, [950000,1050000]

LikeLike

Oh no. In that case your minimum value should be 1000000 (absurdity value of 2).

Edit- Strictly speaking, my implementation of minabsd isn’t correct (it crashes for 9 and 99 for instance). This turns out to be inconsequential as these inputs never actually occur. Now when they don’t start with the same leading number, sm evaluates to 0 which gives the correct answer.

LikeLike