December 3, 2018 Single Round Match 742 Editorials

I participated on SRM 742 Div II and, inspired by my brother’s editorial of SRM 739, decided to present my solutions here!
During SRM I was solving tasks in C++ but, since I am currently learning Haskell, I will also present my solutions in Haskell.

BirthdayCandy (250)

To figure out how many candies will Elisa get if she picks specific candy bag, we do the whole number division with (K + 1) to learn how many rounds of giving candies Elisa will do. Then, we take the rest of the candies (which is remainder from the whole division with (K + 1) and sum it up with the number of rounds and that is the total number of candies Elisa would get from that bag of candies. We do this for every bag of candies and return the biggest number.

C++

#include <vector>
using namespace std;
class BirthdayCandy {
public:
    int mostCandy(int K, vector <int> candy) {
        int maxCandy = -1;
        for (int i = 0; i < (int) candy.size(); i++) {
            const int numCandy = candy[i] / (K + 1) + candy[i] % (K + 1);
            if (numCandy > maxCandy) maxCandy = numCandy;
        }
        return maxCandy;
    }
};

Haskell

It is really easy to describe this solution in Haskell, resulting in just one line of logic!

module BirthdayCandy (mostCandy) where
mostCandy :: Int -> [Int] -> Int
mostCandy k = maximum . map (\c -> c `div` (k + 1) + c `mod` (k + 1))

SixteenQueens (500)

At first, this one seems hard, if we want to make sure that we arrange queens in an optimal way so that the biggest amount of them can fit on the board.
However, if we look at the constraints (board size and the maximal number of queens), we can figure out that the board is so big that we can just put queens one by one in a greedy manner on it and there will always be enough space for all of them.
Therefore, we go with the greedy solution where we, for each queen that we want to add, go through all the fields on the board until we find the first field that is available (not under attack by queens that are already on the board).
Then we put the new queen on the board and continue with the next queen.
To figure out if the field is under attack we check that it is not on the same diagonal, row or column as any other queen.
Nice way to check if two fields are on the same diagonal is by checking if the absolute difference of their row indexes is equal to the absolute difference of their column indexes. If it is, they are on the same diagonal, otherwise, they are not.

C++

#include <vector>
#include <cstdlib>
using namespace std;
class SixteenQueens {
public:
    vector <int> addQueens(vector <int> row, vector <int> col, int add) {
        vector<int> result;
        for (int i = 0; i < add; i++) { // For each queen that we want to add.
            bool done = false;
            for (int r = 0; r < 50 && !done; r++) { // Let's try every field on the board. Every row.
                for (int c = 0; c < 50 && !done; c++) { // And every column.
                    bool fieldOk = true; // Is field ok to put queen on it?
                    // Check if any of previous queens is compromising the field.
                    for (int j = 0; j < (int) row.size() && fieldOk; j++) {
                        if (r == row[j] || c == col[j] || (abs(r - row[j]) == abs(c - col[j]))) {
                            fieldOk = false; break;
                        }
                    }
                    if (fieldOk) { // If field is ok to go, put queen on it.
                        row.push_back(r); col.push_back(c); // Add to queens on board.
                        result.push_back(r); result.push_back(c); // Add to results.
                        done = true;
                    }
                }
            }
        }
        return result;
    }
};

Haskell

This problem can naturally be described recursively, which results in a very elegant solution in Haskell.

module SixteenQueens (addQueens) where
addQueens :: [Int] -> [Int] -> Int -> [Int]
addQueens row col 0 = []
addQueens row col add = rAdd:cAdd:(addQueens (rAdd:row) (cAdd:col) (add - 1))
  where (rAdd, cAdd):_ = [(r, c) | r <- [0..49], c <- [0..49], not (isUnderAttack (r, c))]
        isUnderAttack (r, c) = any (\(r', c') -> r == r' || c == c' || abs (r - r') == abs (c - c')) (zip row col)

ResistorFactory (1000)

This task I was not able to finish during the SRM – I did come up with the solution and started implementing it, but “thinking part” took me a long time and I did not have enough time left to finish it. I finished it later and confirmed in the practice room that it works correctly.
While the problem is in itself simple – combine resistors to achieve wanted value – the solution is not so obvious.
The way problem is stated made me consider if there is a dynamic programming solution, however, I concluded that search space is just too big and I could not see any smart way to narrow down that search. There are just too many choices – resistor values can be real numbers, we can do series or parallel, we can combine any two resistors that we have built so far.
Therefore, I decided to somehow simplify the situation.

Series doubles, parallel halves

First, we can observe that if we put a resistor in series with itself, we get a resistor with double the resistance, and if we put it in parallel, we get a resistor with half the resistance. This means that if we start with a resistor of resistance R, we know how to easily create resistors of resistance 2^x * R where x is an integer.
Since we start with a resistor of 10^9 nano ohm (all the values from now on I will express in nano-ohms), we can create 2 * 10^9 resistor by putting it in series with itself, or we can create 0.5 * 10^9 resistor by putting it in parallel with itself. We can then repeat this process with newly created resistors to create smaller and bigger resistors.

Creating an inventory

Next, we can observe that if we have an inventory of resistors with various values, we can just put some of them in series and probably get pretty close to the target value. But, what kind of values should those be, so that we can actually do that?

1. We need a resistor of small enough value that we can achieve any possible target value with high enough precision. Precision defined in the problem is 1 nano ohm.
2. We need resistors to have big enough values so that we don’t need to combine too many resistors in series since limit stated by the problem is 1000 commands, which means that we can’t combine more than 1000 resistors.

We start our inventory with the only resistor we have at the beginning, resistor #0 with a resistance of 10^9 nano-ohms.
Combining the observations so far, we can see that if we repeatedly create smaller and bigger resistors as described before (by doubling and halving), we will cover the space of possible target resistor values (from 0 to 10^18 nano-ohms) with values that are logarithmically (base 2) spaced.
To cover that space densely enough and to also be sure that we have small enough resistor to always be able to obtain the needed precision, we can keep halving the smallest resistor in the inventory and doubling the biggest resistor in the inventory until the smallest resistor is 2^-30 * 10^9 (~ 0.001) nano-ohms and the biggest resistor is 2^29 * 10^9 (~0.54 * 10^18) nano-ohms.
Now, let’s observe the commands needed to build such inventory.
First, let’s build resistors from 2 * 10^9 to 2^29 * 10^9, that is 29 resistors. We can do this by repeatedly putting the last resistor in inventory in series with itself, 29 times.
This results in following commands:

[(0, 0, 0), (1, 1, 0), ..., (27, 27, 0), (28, 28, 0)]

Next, let’s build resistors from 2^(-1) * 10^9 to 2^(-30) * 10^9, that is 30 resistors. The first resistor we build by putting the resistor #0 in parallel with itself and then we repeatedly put the last resistor in inventory in parallel with itself, 29 times.
This expands our list of commands to a total of 59 commands:

[(0, 0, 0), (1, 1, 0), ..., (27, 27, 0), (28, 28, 0), (0, 0, 1), (30, 30, 1), (31, 31, 1), ..., (59, 59, 1)]

Values of created resistors (in ohms, not in nano-ohms!):

[2^1, 2^2, ..., 2^28, 2^29, 2^-1, 2^-2, 2^-3, ..., 2^-30]

Does this inventory satisfy our needs from before?
The smallest resistor is smaller than required precision, so that is ok. The only question that remains is, are we sure that we can always build target resistor with less than 1000 – 59 = 941 commands by using this inventory of resistors that we created?

Building target resistor from the inventory

First, let’s see how we can use our resistor inventory to build the target resistor.
The problem states that the last command in our list of commands has to be the one constructing target resistor.
With inventory just freshly built, the last command is currently the one that constructs resistor of 2^-30 ohms (~0.93 nano-ohms).
If that is not close enough to target resistor, we are going to add to it, in series, another resistor from inventory that will bring us as close as possible to target resistor (which is the biggest resistor that is smaller than the difference between target resistor value and the last resistor in inventory). We are going to repeat this process until we construct the resistor that is close enough to target resistor, and that is it!
Now, to answer the question from before, if we can guarantee that we are not going to need more than 1000 commands in total.
Since distance between our inventory resistors is logarithmic with base 2 it means that with each resistor we add to series while building target resistor as described above we are halving the mistake between our current best resistor and target resistor, which means that a few dozen steps (<= 60) will be always enough to build it!
This means we are in total never going to have more than 59 + 60 = 119 commands, which is way below the limit of 1000.
That is all! Although slightly complex, this solution performs very well in terms of speed and is reliable. I do wonder if there is a simpler solution or solution that returns the smallest number of commands but have not thought of one yet.

C++

#include <vector>
using namespace std;
class ResistorFactory {
public:
    vector <int> construct(long long nanoOhms) {
        vector<int> commands;
        vector<double> values;
        values.push_back(1000000000.0); // Product 0 is 10^9 ohm.
        for (int i = 0; i <= 28; i++) { // Products 1 to 29, each next is 2 times bigger.
            commands.push_back(i); commands.push_back(i); commands.push_back(0);
            values.push_back(((double) values[values.size() - 1]) * 2);
        }
        // Product 30, which is 10^9 / 2 (product #0 / 2).
        commands.push_back(0); commands.push_back(0); commands.push_back(1);
        values.push_back(values[0] / 2);
        for (int i = 30; i <= 58; i++) { // Products 31 to 59. each is 2 times smaller.
            commands.push_back(i); commands.push_back(i); commands.push_back(1);
            values.push_back(((double) values[values.size() - 1]) / 2);
        }
        // Inventory is built! Now we use our inventory to build the final resistor.
        double remaining = nanoOhms - values[values.size() - 1]; // Difference between what we have and target.
        while (remaining >= 1) {
            int bestIdx = -1; // Biggest resistor that is smaller than remaining amount.
            for (int i = 0; i < (int) values.size(); i++) {
                if (values[i] <= remaining && (bestIdx == -1 || remaining - values[i] < remaining - values[bestIdx])) {
                    bestIdx = i;
                }
            }
            commands.push_back(values.size() - 1); commands.push_back(bestIdx); commands.push_back(0);
            values.push_back(values[values.size() - 1] + values[bestIdx]);
            remaining -= values[bestIdx];
        }
        return commands;
    }
};

Haskell (v1, more expressive)

First Haskell version I came up with ended up pretty big, due to me writing very expressive code. This comes natural when writing Haskell because it is so easy to define functions and data types.

module ResistorFactory (construct) where
import Data.List (foldl', maximumBy)
precisionInNanoOhm = 1 :: Double
data ResistorBuild = Parallel Resistor Resistor | Series Resistor Resistor | OnePiece
data Resistor = Resistor { getResistorId :: Int, getValueInNanoOhm :: Double, getBuild :: ResistorBuild }
resistorToCommand :: Resistor -> (Int, Int, Int) -- Transforms resistor into format expected by Topcoder as result.
resistorToCommand (Resistor _ _ (Series r1 r2)) = (getResistorId r1, getResistorId r2, 0)
resistorToCommand (Resistor _ _ (Parallel r1 r2)) = (getResistorId r1, getResistorId r2, 1)
resistorToCommand _ = error "Can't be transformed to command!"
createFromSeries :: Int -> Resistor -> Resistor -> Resistor
createFromSeries id r1 r2 = Resistor id (getValueInNanoOhm r1 + getValueInNanoOhm r2) (Series r1 r2)
createFromParallel :: Int -> Resistor -> Resistor -> Resistor
createFromParallel id r1 r2 = Resistor id (v1 * v2 / (v1 + v2)) (Parallel r1 r2)
  where (v1, v2) = (getValueInNanoOhm r1, getValueInNanoOhm r2)
type Inventory = [Resistor]
resistor0 = Resistor 0 (10^9) OnePiece -- This is the resistor we start with, 1 ohm.
initialInventory :: Inventory
initialInventory = [resistor0] -- Initial resistor.
                   -: (extendInventory createFromSeries [1..29]) -- Big resistors (> 10^9 nano ohm).
                   -: ((createFromParallel 30 resistor0 resistor0):) -- First small resistor.
                   -: (extendInventory createFromParallel [31..59]) -- Other small resistors (< 10^9 nano ohm).
  where
    -- For each of given ids, it takes last resistor from inventory, creates new one with that id from it and
    -- adds it to the end of that same inventory, repeating the process.
    extendInventory create ids inv = foldl' (\i@(r:_) id -> (create id r r):i) inv ids
    a -: f = f a
construct :: Integer -> [(Int, Int, Int)]
construct target = transformResult $ construct' initialInventory (fromIntegral target)
  where transformResult = map resistorToCommand . tail . reverse
-- Given initial inventory and value of target resistor, it will return inventory in which
-- last resistor has that value (within defined precision).
construct' :: Inventory -> Double -> Inventory
construct' inv@(lastResistor:_) target = if diff < precisionInNanoOhm
                                         then inv -- We are done.
                                         else construct' (newResistor:inv) target
  where
    diff = target - (getValueInNanoOhm lastResistor)
    closestResistor = maximumBy (\r1 r2 -> compare (getValueInNanoOhm r1) (getValueInNanoOhm r2))
      $ filter (\r -> getValueInNanoOhm r <= diff) inv
    newResistor = createFromSeries (getResistorId lastResistor + 1) lastResistor closestResistor

Haskell (v2, less expressive)

I also refactored it to make it shorter but less expressive and therefore much more similar to C++ version. I prefer the first, more expressive version.

module ResistorFactory (construct) where
import Data.List (foldl', maximumBy)
initialInventory :: [(Int, Int, Int, Double)]
initialInventory = [(undefined, undefined, undefined, 10^9)] -- Initial resistor.
                   -: (extendInventory (\id v -> (id, id, 0, v * 2)) [0..28]) -- Big resistors (> 10^9 nano ohm).
                   -: ((0, 0, 1, 10^9 / 2):) -: (extendInventory (\id v -> (id, id, 1, v / 2)) [30..58]) -- Small resistors.
  where extendInventory create ids inv = foldl' (\i@((_,_,_,v):_) id -> (create id v):i) inv ids
        a -: f = f a
construct :: Integer -> [(Int, Int, Int)]
construct target = transformResult $ construct' initialInventory (fromIntegral target)
  where transformResult = map (\(id1, id2, c, v) -> (id1, id2, c)) . tail . reverse
construct' :: [(Int, Int, Int, Double)] -> Double -> [(Int, Int, Int, Double)]
construct' inv@(lastRes:_) target = if diff < 1 then inv else construct' (newRes:inv) target
  where lenInv = length inv
        diff = target - (value lastRes)
        (bestResId, bestRes) = maximumBy (\(_, r1) (_, r2) -> compare (value r1) (value r2))
          $ filter (\(_, r) -> value r <= diff) $ zip [lenInv - 1, lenInv - 2 .. 0] inv
        newRes = (lenInv - 1, bestResId, 0, value lastRes + value bestRes)
        value (_,_,_,v) = v