How ever much I like paper, rock and scissor we only use paper and scissor in the problem of cutting paper squares. Continue reading →

## HackerRank: Connecting Towns

Welcome to the Shire… Well at least welcome to Middle Earth, we don’t actually need to travel through the shire in the next HackerRank problem with Connecting Towns. The problem reads

Gandalf is travelling from

RohantoRivendellto meet Frodo but there is no direct route fromRohan(T_{1}) toRivendell(T_{n}).But there are towns T

_{2},T_{3},T_{4}…T_{n-1}such that there are N_{1}routes from Town T_{1}to T_{2}, and in general, N_{i}routes from T_{i}to T_{i+1}for i=1 to n-1 and 0 routes for any other T_{i}to T_{j}for j ≠ i+1Find the total number of routes Gandalf can take to reach Rivendell from Rohan.

Note

Gandalf has to pass all the towns T_{i}for i=1 to n-1 in numerical order to reach T_{n}.

For each T_{i}, T_{i+1}there are only N_{i}distinct routes Gandalf can take.

Input Format

The first line contains an integer T, T test-cases follow.

Each test-case has 2 lines. The first line contains an integer N (the number of towns).

The second line contains N – 1 space separated integers where the i^{th}integer denotes the number of routes, N_{i}, from the town T_{i}to T_{i+1}

Output Format

Total number of routes from T_{1}to T_{n}modulo 1234567

http://en.wikipedia.org/wiki/Modular_arithmetic

## Solving the math of Connecting Towns

There are two things we need to get our heads around. There is the first part which is how many paths there are, and then there is the second part of the modulo.

The former problem of the paths is rather simple as it is a simple combinatorics problem and the total number of paths are just the product of the paths of each leg of the journey

The problem of the modulo operator can be treated in different ways. Since we are using Python as implementation language we can completely ignore it, as it can handle arbitrarily large integers. However, we can also solve it as we have done for Project Euler problem 48.

In general we have the formula

Which means that for every time we multiply with the next set of paths we can also take the modulo, which means we will keep the total size of the integer down significantly. If it actually matters in Python I don’t know.

## Implementing Connecting towns in Python

Let us implement the one with modulo arithmetic. However since we know that both a and b in the previous formula will be smaller than the modulo. Therefore a%c = a and b%c= b, so we only need to take modulo of the result during the iterations. Therefore the function we need to implement is

def connectingTowns(n, routes): paths = 1 for i in routes: paths = (paths * i) % 1234567 return paths

and that should solve the problem.

## HackerRank: Minimum Height Triangle

It is always fun to work with triangles in any kind of setting not least problem solving in HackerRank. The problem Minimum Height Triangle is no exception. The problem reads

Given integers b and a, find the smallest integer h, such that there exists a triangle of height h, base b, having an area of at least a.

In case we should have forgotten the primary school mathematics. The area of a triangle is given by

This can be isolated such that we get the height of the triangle instead as

Since we want the minimum integer size we then need to ceil that such that we get

This can be implemented in Python as

def lowestTriangle(base, area): return math.ceil(2 * area / base)

I usually write somewhat longer posts. But to be honest, I don’t know what to add to this problem.

## HackerRank: Handshake

Time to shake hands with a lot of people in the next HackerRank challenge called Handshake. The problem reads

At the annual meeting of Board of Directors of Acme Inc, every one starts shaking hands with everyone else in the room. Given the fact that any two persons shake hand exactly once, Can you tell the total count of handshakes?

Input Format

The first line contains the number of test cases T, T lines follow.

Each line then contains an integer N, the total number of Board of Directors of Acme.

Output FormatPrint the number of handshakes for each test-case in a new line.

## HackerRank: Maximum Draws

Second round of the fundamental mathematics problems on HackerRank is called Maximum draws. It asks the following

Jim is off to a party and is searching for a matching pair of socks. His drawer is filled with socks, each pair of a different color. In its worst case scenario, how many socks (x) should Jim remove from his drawer until he finds a matching pair?

Input Format

The first line contains the number of test cases T.

Next T lines contains an integer N which indicates the total pairs of socks present in the drawer.

Output Format

Print the number of Draws (x) Jim makes in the worst case scenario.

## HackerRank: Find the Point

I finally found the math problems on HackerRank which makes me so happy. So let’s getting cracking on the first one called Find the Point. It asks us to

Consider two points, and . We consider the inversion or point reflection, , of point across point to be a rotation of point around .

Given sets of points and , find for each pair of points and print two space-separated integers denoting the respective values of and on a new line.

## HackerRank: Utopian Trees

I found another fun little problem at HackerRank called Utopian trees. It is not an easy due to the input constraints. Given how small they are I am pretty sure it could be solved by bruteforce. The problem description is

The Utopian Tree goes through

2cycles of growth every year. Each spring, itdoublesin height. Each summer, its height increases by1meter.Laura plants a Utopian Tree sapling with a height of

1meter at the onset of spring. How tall will her tree be after n growth cycles?

Given that the number of test cases is smaller than 10 and the number of cycles are less than 60, it should be pretty obvious that it can be bruteforced. However, there is also a nice analytical solution to this. Continue reading →

## Shenzhen I/O: Carbine Target Illuminator

Once again we are going to make equipment for military use. Someone in the company is not going to be happy about it. This time it is a Carbine Target illuminator, so we can see the bad guys before we shoot them. With the use of radar we are going to measure the distance to the bad guy by counting the number of cycles between output and input to the radar. Based on that we will turn on the laser sight and or the flood light in the following configuration.

## Hackerrank: Forming a magic Square

I must admit that this problem actually took me a good while to solve. Once you have the right insight on forming a magic Square it is really straight forward. But until that point I was just stuck. Anyway, before rambling on lets get to the actual problem.

We define a magic square to be an matrix of distinct positive integers from 1 to n^{2 }where the sum of any row, column, or diagonal (of length n) is always equal to the same number (i.e., the *magic constant*).

Consider a matrix, s, of integers in the inclusive range [1, 9]. We can convert any digit, a, to any other digit, b, in the range [1, 9] at cost .

Given , convert it into a magic square at

minimalcost by changing zero or more of its digits. Then print this cost on a new line.

Note:The resulting magic square must contain distinct integers in the inclusive range [1, 9].

## Shenzhen I/O: Personal Sandwich Maker

Yeah, this time we are going to make a personal sandwich maker. What could possibly go wrong when making food? Nothing right! This one took me a while to crack, or rather it was fairly easy to make *a *solution. But it took me quite a few tries to make a good one.

The sandwich maker print board have an xbus input where it gets a number from 1 to 3 which is three different modes

- Normal sandwich
- Hold the cheese
- Extra mustard