djnzx · djnzx · Oct 28, 2024 · Nov 2, 2024 · Jan 10, 2025 · Sep 19, 2025
diff --git a/.github/workflows/maven.yml b/.github/workflows/maven.yml
@@ -28,4 +28,5 @@ jobs:
         distribution: 'temurin'
         cache: maven
     - name: Build with Maven
+      working-directory: play
       run: mvn -B package --file pom.xml
diff --git a/.github/workflows/scala.yml b/.github/workflows/scala.yml
@@ -11,16 +11,18 @@ permissions:
 
 jobs:
   build:
-
     runs-on: ubuntu-latest
 
     steps:
-    - uses: actions/checkout@v4
-    - name: Set up JDK 17
-      uses: actions/setup-java@v4
-      with:
-        java-version: '17'
-        distribution: 'temurin'
-        cache: 'sbt'
-    - name: Run tests
-      run: sbt algo/test
+      - uses: actions/checkout@v4
+      - name: Set up JDK 17
+        uses: actions/setup-java@v4
+        with:
+          java-version: '17'
+          distribution: 'temurin'
+          cache: 'sbt'
+      - uses: sbt/setup-sbt@v1
+        with:
+          sbt-runner-version: 1.11.5
+      - name: Run tests
+        run: sbt algo/test
diff --git a/algo/src/main/scala/djnz/hackerrank/fp/a3structures/P10StockPrediction.scala b/algo/src/main/scala/djnz/hackerrank/fp/a3structures/P10StockPrediction.scala
@@ -0,0 +1,92 @@
+package djnz.hackerrank.fp.a3structures
+
+/** https://www.hackerrank.com/challenges/stocks-prediction/problem */
+object P10StockPrediction {
+
+  def next() = scala.io.StdIn.readLine()
+
+  /** index from 0 */
+  case class Query(index: Int, d: Int, up: Int)
+
+  def solve(stocks: Seq[Int], queries: Seq[Query], n: Int) = {
+
+    // queries per price
+    val qpp: Map[Int, List[Int]] = stocks.zipWithIndex
+      .foldLeft(Map.empty[Int, List[Int]]) {
+        case (map, (price, idx)) =>
+          val x = price -> (idx :: map.getOrElse(price, Nil))
+          map + x
+      }
+
+    case class Item(price: Int, indexes: IndexedSeq[Int])
+
+    // queries per price sorted by price
+    val qppSorted: Seq[Item] = qpp
+      .map { case (price, indexes) => Item(price, indexes.toIndexedSeq) }
+      .toIndexedSeq
+      .sorted(Ordering.by((x: Item) => x.price))
+
+    import scala.collection.mutable
+    def update(map: mutable.TreeMap[Int, Int], idx: Int): Unit = {
+
+      def doUpdate(l: Int, r: Int): Unit =
+        if (l <= r) map += (l -> r)
+        else map -= l
+
+      val (left, right) = map.rangeTo(idx).last
+      doUpdate(left, idx - 1)
+      doUpdate(idx + 1, right)
+    }
+
+    case class Bound(l: Int, r: Int)
+    val minBounds = Array.ofDim[Bound](n)
+    val minBoundMap = mutable.TreeMap[Int, Int](0 -> (n - 1))
+
+    // TODO: make it more functional
+    /** update minBoundMap, minBounds */
+    qppSorted
+      .flatMap { x =>
+        val idxBound = x.indexes.map { i =>
+          val (l, r) = minBoundMap.rangeTo(i).last
+          i -> Bound(l, r)
+        }
+        idxBound.indices.foreach(i => update(minBoundMap, x.indexes(i)))
+        idxBound
+      }
+      .foreach { case (index, bound) => minBounds(index) = bound }
+
+    val maxBounds = Array.ofDim[Int](queries.length)
+    val maxBoundMap = mutable.TreeMap[Int, Int](0 -> (n - 1))
+
+    // TODO: make it more functional
+    /** update minBoundMap, minBounds */
+    var idx = qppSorted.length - 1
+    queries
+      .sortBy(_.up)(Ordering.Int.reverse)
+      .map { q =>
+        while (idx >= 0 && qppSorted(idx).price > q.up) {
+          qppSorted(idx).indexes.foreach(update(maxBoundMap, _))
+          idx -= 1
+        }
+        val (l, r) = maxBoundMap.rangeTo(q.d).last
+        val minBound = minBounds(q.d)
+        q.index -> (math.min(minBound.r, r) - math.max(minBound.l, l) + 1)
+
+      }
+      .foreach { case (index, answer) => maxBounds(index) = answer }
+
+    maxBounds
+  }
+
+  def main(args: Array[String]): Unit = {
+    val n = next().toInt
+    val stocks = next().split(" ").map(_.toInt).take(n)
+    val m = next().toInt
+    val queries = (1 to m).map { i =>
+      next().split(" ").map(_.toInt) match { case Array(d, m) => Query(i - 1, d, stocks(d) + m) }
+    }
+
+    solve(stocks, queries, n)
+      .foreach(println)
+  }
+}
diff --git a/algo/src/main/scala/djnz/hackerrank/fp/a3structures/P10StockPredictionNaive.scala b/algo/src/main/scala/djnz/hackerrank/fp/a3structures/P10StockPredictionNaive.scala
@@ -0,0 +1,57 @@
+package djnz.hackerrank.fp.a3structures
+
+/** https://www.hackerrank.com/challenges/stocks-prediction/problem */
+object P10StockPredictionNaive {
+  // 0 < l < d < r < n
+
+  def next() = scala.io.StdIn.readLine()
+  case class Query(index: Int, d: Int, m: Int, min: Int, max: Int)
+
+  // as - prices per day
+  // d  - index
+  // we need the longest subarray: all i: ad <= ai <= ad + m
+  def query(as: Array[Int], d: Int, m: Int): Int = {
+    val min = as(d)
+    val max = min + m
+    def fits(x: Int) = x >= min && x <= max
+
+    def findL(it: Iterator[Int], acc: Int): Int = it.hasNext match {
+      case false => acc
+      case _     =>
+        val i = it.next()
+        fits(as(i)) match {
+          case true  => findL(it, i)
+          case false => acc
+        }
+    }
+
+    def findR(it: Iterator[Int], acc: Int): Int = it.hasNext match {
+      case false => acc
+      case _     =>
+        val i = it.next()
+        fits(as(i)) match {
+          case true  => findR(it, i)
+          case false => acc
+        }
+    }
+
+    val l = findL((0 to d).reverseIterator, d)
+    val r = findR((d until as.length).iterator, d)
+    r - l + 1
+  }
+
+  def solve(as: Array[Int], qs: Seq[Query]): Seq[Int] =
+    qs.map(q => query(as, q.d, q.m))
+
+  def main(args: Array[String]): Unit = {
+    val n = next().toInt
+    val as = next().split(" ").map(_.toInt).take(n)
+    val nq = next().toInt
+    val qs = (1 to nq)
+      .map(i => next().split(" ").map(_.toInt) match { case Array(d, m) => Query(i, d, m, as(d), as(d) + m) })
+
+    solve(as, qs)
+      .foreach(println)
+  }
+
+}
diff --git a/algo/src/main/scala/djnz/hackerrank/fp/a3structures/P11ConstructionSiteDP.scala b/algo/src/main/scala/djnz/hackerrank/fp/a3structures/P11ConstructionSiteDP.scala
@@ -0,0 +1,77 @@
+package djnz.hackerrank.fp.a3structures
+
+/** https://www.hackerrank.com/challenges/mirko-at-construction-site/problem */
+object P11ConstructionSiteDP {
+
+  def next() = scala.io.StdIn.readLine()
+
+  def main(args: Array[String]): Unit = {
+    val (_, q) = next().split(" ").map(_.toInt) match { case Array(x, y) => x -> y }
+
+    val base = next().split(" ").map(_.toInt)
+    val increments = next().split(" ").map(_.toInt)
+
+    case class Query(idx: Int, time: Int)
+    val queries = (0 until q).map(i => Query(i, next().toInt)).sortBy(_.time)
+
+    case class Building(idx: Int, base: Long, inc: Long) extends Ordered[Building] {
+      override def compare(that: Building): Int =
+        if (this.inc < that.inc) -1
+        else if (this.inc > that.inc) 1
+        else if (this.base < that.base) -1
+        else if (this.base > that.base) 1
+        else this.idx.compareTo(that.idx)
+    }
+
+    val buildings: List[Building] = base.indices
+      .map(i => Building(i + 1, base(i), increments(i)))
+      .groupBy(_.inc)
+      .map { case (_, list) => list.maxBy(_.base) }
+      .toList
+      .sorted
+
+    def cross(b0: Building, b1: Building) = (b1.base.toDouble - b0.base) / (b0.inc.toDouble - b1.inc)
+
+    @scala.annotation.tailrec
+    def sort(buildings: List[Building], acc: List[Building]): List[Building] = (buildings, acc) match {
+      case (Nil, _)            => acc              // done
+      case (v :: Nil, _)       => v :: acc         // last one, done
+      case (h :: t, Nil)       => sort(t, List(h)) // start
+      case (b1 :: b2 :: bs, h :: _) if {
+            val is1 = cross(h, b1)
+            val is2 = cross(h, b2)
+            is1 < is2 || is1 == is2 && b1.idx > b2.idx
+          } => sort(b2 :: bs, b1 :: acc)
+      case (_ :: bs, _ :: Nil) => sort(bs, acc)
+      case (_ :: bs, h :: hs)  => sort(h :: bs, hs)
+    }
+
+    val buildingsReordered = sort(buildings, Nil).reverse
+
+    case class Pair(qIdx: Int, highestIdx: Int)
+    case class State(buildings: List[Building], highest: List[Pair])
+    val s0 = State(buildingsReordered, Nil)
+
+    queries
+      .foldLeft(s0) { (s, q) =>
+
+        @scala.annotation.tailrec
+        def highest(buildings: List[Building]): State = buildings match {
+          case b :: Nil => State(s.buildings, Pair(q.idx, b.idx) :: s.highest)
+          case b1 :: b2 :: _ if {
+                val is = cross(b1, b2)
+                is > q.time || is == q.time && b1.idx > b2.idx
+              } => State(buildings, Pair(q.idx, b1.idx) :: s.highest)
+          case _ :: bs  => highest(bs)
+          case Nil      => sys.error("impossible, but req for exhaustiveness")
+        }
+
+        highest(s.buildings)
+      }
+      .highest
+      .sortBy(_.qIdx)
+      .map(_.highestIdx)
+      .foreach(println)
+  }
+
+}