Mirko at the Construction Site – HackerRank Solution

In this post, we will solve Mirko at the Construction Site HackerRank Solution. This problem (Mirko at the Construction Site) is a part of HackerRank Functional Programming series.

Task

Mirko is monitoring a construction site. He monitors N buildings enumerated from 1 to N, starting from the left. For each building, he knows the current number of floors and the number of floors built on each day. He needs to know the answer to Q queries. The answer to each query is the index of the tallest building after T days, as defined by the query. Your task is to help Mirko find the answers to these queries.

Input Format

The first line consists of the numbers N and Q. The second line consists of N integers, where the i^th integer represents the initial height of the i^th building. The third line consists of N integers, where the i^th integer represents the number of floors erected in one day for the i^th building. The following Q lines consist of the integer, T, representing the day in the query.

Output Format

For each query, output one number which represents the index of the tallest building after T days. If there is more than one building, output the building with the greatest index in the input array (with indexes starting at 1).

Constraints

• 1 <= N <= 10⁵
• 1 <= Q <= 10⁵
• Every other integer in the input will fit in a 32-bit signed integer. And they will be non-negative integers.

Sample Input

3 6
7 5 1
1 2 3
0
1
2
3
4
5

Sample Output

1
1
2
2
3
3  

Explanation

Query #1: The height at the end of the 0^th day will be {7, 5, 1}. Here, the 1^st building is the tallest.
Query #2: The height at the end of the 1^st day will be {8, 7, 4}. Here, the 1^st building is the tallest.
Query #3: The height at the end of 2^nd day will be {9, 9, 7}. Here, the 1^st and 2^nd buildings are the tallest, while the 2^nd is the larger index.
Query #4: The height at the end of 3^rd day will be {10, 11, 10}. Here, the 2^nd building is the tallest.
Query #5: The height at the end of 4^th day will be {11, 13, 13}. Here, the 2^nd and 3^rd buildings are the tallest, while the 3^rd is the larger index.
Query #6: The height at the end of 5^th day will be {12, 15, 16}. Here, the 3^rd building is the tallest.

Solution – Mirko at the Construction Site – HackerRank Solution

Scala

import java.util.Scanner

object Solution {
  def main(args: Array[String]): Unit = {
    val sc = new Scanner(System.in)

    sc.nextInt
    val q = sc.nextInt
    sc.nextLine
    val initials = sc.nextLine.split(" ").map(_.toInt)
    val steps = sc.nextLine.split(" ").map(_.toInt)

    case class Query(index: Int, time: Int)
    val queries = (0 until q).map(Query(_, sc.nextInt)).sortBy(_.time)

    sc.close()

    case class Building(index: Int, initial: Long, step: Long) extends Ordered[Building] {
      override def compare(that: Building): Int = {
        if (this.step < that.step) -1
        else if (this.step > that.step) 1
        else if (this.initial < that.initial) -1
        else if (this.initial > that.initial) 1
        else this.index.compareTo(that.index)
      }

      def height(time: Long): Long = initial + step * time
    }

    val buildings: List[Building] = initials.indices.map(i => Building(i + 1, initials(i), steps(i)))
      .groupBy(_.step)
      .map { case (_, list) => list.maxBy(_.initial) }
      .toList
      .sorted

    def intersection(b0: Building, b1: Building) = (b1.initial.toDouble - b0.initial) / (b0.step.toDouble - b1.step)

    @scala.annotation.tailrec
    def prepare(buildings: List[Building], acc: List[Building]): List[Building] = buildings match {
      case Nil => acc
      case v :: Nil => v :: acc
      case v0 :: v1 :: vs =>
        val highest = acc.head
        val inter0 = intersection(highest, v0)
        val inter1 = intersection(highest, v1)

        if (inter0 < inter1 || inter0 == inter1 && v0.index > v1.index)
          prepare(v1 :: vs, v0 :: acc)
        else if (acc.tail.isEmpty)
          prepare(v1 :: vs, acc)
        else
          prepare(acc.head :: v1 :: vs, acc.tail)
    }

    val highBuildings = prepare(buildings.tail, List(buildings.head)).reverse

    case class Pair(queryIndex: Int, highestIndex: Int)
    case class Acc(buildings: List[Building], highestIndices: List[Pair])
    val answer = queries.foldLeft(Acc(highBuildings, Nil))((acc, q) => {
      @scala.annotation.tailrec
      def findHighest(buildings: List[Building]): Acc = buildings match {
        case b :: Nil => Acc(acc.buildings, Pair(q.index, b.index) :: acc.highestIndices)
        case b0 :: b1 :: bs =>
          val inter = intersection(b0, b1)
          if (inter > q.time || inter == q.time && b0.index > b1.index)
            Acc(buildings, Pair(q.index, b0.index) :: acc.highestIndices)
          else
            findHighest(b1 :: bs)
        case Nil => throw new Exception("Impossible")
      }

      findHighest(acc.buildings)
    })

    println(answer.highestIndices
      .sortBy(_.queryIndex)
      .map(_.highestIndex)
      .mkString("\n")
    )
  }
}

Note: This problem (Mirko at the Construction Site) is generated by HackerRank but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.