Fighting Armies – HackerRank Solution

In this post, we will solve Fighting Armies HackerRank Solution. This problem (Fighting Armies) is a part of HackerRank Functional Programming series.

Task

Your country is at war!

As a General, you initially have N armies numbered from 1 to N under your command. Each army consists of some number of soldiers, and each soldier is assigned an integer, c, representative of his or her combat ability. Since, you are responsible for all of them, you want to give orders to your armies and query them about their current state. You must handle Q events, where each event is one of the 4 following types:

1. findStrongest(i) – Print the maximum combat ability of any soldier in army i.
2. strongestDied(i) – A soldier with the maximum combat ability among all soldiers in army i has died, so the soldier is removed from the army.
3. recruit(i, c) – A soldier with combat ability c has joined army i.
4. merge(i, j) – Armies i and j are merged into a single army i, and army j is removed (ceases to exist).

Note: The input can be quite large, so we suggest you use fast I/O methods.

Input Format

The first line contains 2 space-separated integers, N (the number of armies you command) and Q (the number of events taking place), respectively. Each of the Q subsequent lines describes a single event.

Each event first contains an integer, , describing the event type.
If t = 1 or t = 2, the line contains 1 more integer denoting the parameter of the event.
If t = 3 or t = 4, the line contains 2 more integers denoting the respective parameters of the event.

Constraints

• 1 <= N <= 1100000
• 1 <= Q <= 2200000
• 1 <= c <= 10⁷
• 1 <= i, j <= N, where i != j
• Indices of armies in the input represent valid armies at the time they are given.

Output Format

For each event of type 1, print a single line containing 1 integer denoting the answer for the event.

Sample Input

2 6
3 1 10
3 2 20
4 1 2
1 1
2 1
1 1

Sample Output

20
10

Explanation

Here is a breakdown of each event:

1. A soldier having combat ability c = 10 is added to army 1.
2. A soldier having combat ability c = 20 is added to army 2.
3. Armies 1 and 2 are merged into army 1 (and army 2 no longer exists).
4. The maximum combat ability of a soldier in army 1 is 20.
5. The soldier having combat ability 20 is removed from army 1.
6. The maximum combat ability of a soldier in army 1 is 10.

Solution – Fighting Armies – HackerRank Solution

Scala

import java.io.{BufferedReader, IOException, InputStreamReader}
import java.util.StringTokenizer

import scala.collection.immutable.TreeMap

class FastReader() {
  val br: BufferedReader = new BufferedReader(new InputStreamReader(System.in))
  var st: StringTokenizer = _

  def nextInt: Int = next.toInt

  def next: String = {
    while (st == null || !st.hasMoreElements) try
      st = new StringTokenizer(br.readLine)
    catch {
      case e: IOException =>
        e.printStackTrace()
    }
    st.nextToken
  }

  def nextLong: Long = next.toLong

  def nextDouble: Double = next.toDouble

  def nextLine: String = {
    var str = ""
    try
      str = br.readLine
    catch {
      case e: IOException =>
        e.printStackTrace()
    }
    str
  }
}

trait Army {
  def strongest: Int

  def values: TreeMap[Int, Int]

  def add(c: Int): Army = new AddedArmy(this, c)

  def remove(): Army = new RemovedArmy(this)

  def merge(that: Army): Army =
    if (this.isEmpty) that
    else if (that.isEmpty) this
    else new MergedArmy(this, that)

  def isEmpty: Boolean = false
}

case object Empty extends Army {
  override def isEmpty: Boolean = true

  override def strongest: Int = throw new Exception("Strongest of empty army")

  override def add(c: Int): Army = new SingleArmy(c)

  override def remove(): Army = throw new Exception("Remove from empty army")

  override def merge(that: Army): Army = that

  override def values: TreeMap[Int, Int] = throw new Exception("Values of empty army")
}

class SingleArmy(val strongest: Int) extends Army {
  override lazy val values: TreeMap[Int, Int] = TreeMap(strongest -> 1)

  override def remove(): Army = Empty
}

class AddedArmy(army: Army, c: Int) extends Army {
  override lazy val strongest: Int = math.max(army.strongest, c)

  override lazy val values: TreeMap[Int, Int] = army.values + (c -> (army.values.getOrElse(c, 0) + 1))
}

class RemovedArmy(army: Army) extends Army {
  override lazy val strongest: Int = values.lastKey

  override lazy val values: TreeMap[Int, Int] = {
    val (key, value) = army.values.last
    if (value == 1) {
      army.values - key
    } else {
      army.values + (key -> (value - 1))
    }
  }
}

class MergedArmy(left: Army, right: Army) extends Army {
  override lazy val strongest: Int = math.max(left.strongest, right.strongest)

  override lazy val values: TreeMap[Int, Int] = {
    left.values.foldLeft(right.values)((acc, v) => {
      val nextValue = acc.getOrElse(v._1, 0) + v._2
      acc + (v._1 -> nextValue)
    })
  }
}

object Solution {
  def main(args: Array[String]): Unit = {
    val sc = new FastReader

    val n = sc.nextInt
    val q = sc.nextInt

    val armies = Array.fill[Army](n)(Empty)

    var index = 0
    val answers = Array.ofDim[Int](q)

    (0 until q).foreach(_ => {
      val tokens = sc.nextLine.split(" ").map(_.toInt)

      val event = tokens.head
      val first = tokens(1) - 1
      lazy val second = tokens(2)

      event match {
        case 1 => //Find
          answers(index) = armies(first).strongest
          index += 1
        case 2 => //Kill
          armies(first) = armies(first).remove()
        case 3 => //Recruit
          armies(first) = armies(first).add(second)
        case 4 => //Merge
          armies(first) = armies(first).merge(armies(second - 1))
          armies(second - 1) = Empty
      }
    })

    println(answers.take(index).mkString("\n"))
  }
}

Note: This problem (Fighting Armies) is generated by HackerRank but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.