| 0882 |[Reachable Nodes In Subdivided Graph](src/main/kotlin/g0801_0900/s0882_reachable_nodes_in_subdivided_graph/Solution.kt)| Hard | Heap_Priority_Queue, Graph, Shortest_Path | 434 | 100.00

| 0881 |[Boats to Save People](src/main/kotlin/g0801_0900/s0881_boats_to_save_people/Solution.kt)| Medium | Array, Sorting, Greedy, Two_Pointers | 370 | 96.07

| 0880 |[Decoded String at Index](src/main/kotlin/g0801_0900/s0880_decoded_string_at_index/Solution.kt)| Medium | String, Stack | 134 | 100.00

| 0879 |[Profitable Schemes](src/main/kotlin/g0801_0900/s0879_profitable_schemes/Solution.kt)| Hard | Array, Dynamic_Programming | 198 | 75.00

package g0801_0900.s0879_profitable_schemes

class Solution {

fun profitableSchemes(n: Int, minProfit: Int, group: IntArray, profit: IntArray): Int {

val dp = Array(n + 1) { LongArray(minProfit + 1) }

val modulus = 1000000007L

for (i in dp.indices) {

dp[i][0] = 1

}

for (i in group.indices) {

val currWorker = group[i]

val currProfit = profit[i]

for (j in dp.size - 1 downTo currWorker) {

for (k in dp[j].indices.reversed()) {

dp[j][k] = (

(dp[j][k] + dp[j - currWorker][(k - currProfit).coerceAtLeast(0)]) %

modulus

)

}

}

}

return dp[n][minProfit].toInt()

}

}

879\. Profitable Schemes

Hard

There is a group of `n` members, and a list of various crimes they could commit. The <code>i^th</code> crime generates a `profit[i]` and requires `group[i]` members to participate in it. If a member participates in one crime, that member can't participate in another crime.

Let's call a **profitable scheme** any subset of these crimes that generates at least `minProfit` profit, and the total number of members participating in that subset of crimes is at most `n`.

Return the number of schemes that can be chosen. Since the answer may be very large, **return it modulo** <code>10⁹ + 7</code>.

**Example 1:**

**Input:** n = 5, minProfit = 3, group = [2,2], profit = [2,3]

**Output:** 2

**Explanation:** To make a profit of at least 3, the group could either commit crimes 0 and 1, or just crime 1. In total, there are 2 schemes.

**Example 2:**

**Input:** n = 10, minProfit = 5, group = [2,3,5], profit = [6,7,8]

**Output:** 7

**Explanation:** To make a profit of at least 5, the group could commit any crimes, as long as they commit one. There are 7 possible schemes: (0), (1), (2), (0,1), (0,2), (1,2), and (0,1,2).

**Constraints:**

* `1 <= n <= 100`

* `0 <= minProfit <= 100`

* `1 <= group.length <= 100`

* `1 <= group[i] <= 100`

* `profit.length == group.length`

* `0 <= profit[i] <= 100`

package g0801_0900.s0880_decoded_string_at_index

@Suppress("NAME_SHADOWING")

class Solution {

fun decodeAtIndex(s: String, k: Int): String {

var k = k

var i = 0

var count: Long = 0

while (i < s.length && count <= k) {

val c = s[i]

count = if (Character.isDigit(c)) count * (c.code - '0'.code) else count + 1

i++

}

i--

while (i < s.length) {

val c = s[i]

if (Character.isDigit(c)) {

count /= (c.code - '0'.code).toLong()

k %= count.toInt()

} else {

if (k % count == 0L) {

break

}

--count

}

i--

}

return s[i].toString()

}

}

880\. Decoded String at Index

Medium

You are given an encoded string `s`. To decode the string to a tape, the encoded string is read one character at a time and the following steps are taken:

* If the character read is a letter, that letter is written onto the tape.

* If the character read is a digit `d`, the entire current tape is repeatedly written `d - 1` more times in total.

Given an integer `k`, return _the_ <code>k^th</code> _letter (**1-indexed)** in the decoded string_.

**Example 1:**

**Input:** s = "leet2code3", k = 10

**Output:** "o"

**Explanation:** The decoded string is "leetleetcodeleetleetcodeleetleetcode". The 10^th letter in the string is "o".

**Example 2:**

**Input:** s = "ha22", k = 5

**Output:** "h"

**Explanation:** The decoded string is "hahahaha". The 5^th letter is "h".

**Example 3:**

**Input:** s = "a2345678999999999999999", k = 1

**Output:** "a"

**Explanation:** The decoded string is "a" repeated 8301530446056247680 times. The 1^st letter is "a".

**Constraints:**

* `2 <= s.length <= 100`

* `s` consists of lowercase English letters and digits `2` through `9`.

* `s` starts with a letter.

* <code>1 <= k <= 10⁹</code>

* It is guaranteed that `k` is less than or equal to the length of the decoded string.

* The decoded string is guaranteed to have less than <code>2⁶³</code> letters.

package g0801_0900.s0881_boats_to_save_people

class Solution {

fun numRescueBoats(people: IntArray, limit: Int): Int {

people.sort()

var i = 0

var j = people.size - 1

var boats = 0

while (i < j) {

if (people[i] + people[j] <= limit) {

boats++

i++

j--

} else if (people[i] + people[j] > limit) {

boats++

j--

}

}

return if (i == j) {

boats + 1

} else boats

}

}

881\. Boats to Save People

Medium

You are given an array `people` where `people[i]` is the weight of the <code>i^th</code> person, and an **infinite number of boats** where each boat can carry a maximum weight of `limit`. Each boat carries at most two people at the same time, provided the sum of the weight of those people is at most `limit`.

Return _the minimum number of boats to carry every given person_.

**Example 1:**

**Input:** people = [1,2], limit = 3

**Output:** 1

**Explanation:** 1 boat (1, 2)

**Example 2:**

**Input:** people = [3,2,2,1], limit = 3

**Output:** 3

**Explanation:** 3 boats (1, 2), (2) and (3)

**Example 3:**

**Input:** people = [3,5,3,4], limit = 5

**Output:** 4

**Explanation:** 4 boats (3), (3), (4), (5)

**Constraints:**

* <code>1 <= people.length <= 5 * 10⁴</code>

* <code>1 <= people[i] <= limit <= 3 * 10⁴</code>

package g0801_0900.s0882_reachable_nodes_in_subdivided_graph

import java.util.PriorityQueue

class Solution {

fun reachableNodes(edges: Array<IntArray>, maxMoves: Int, n: Int): Int {

val adList = getAdList(edges, n)

val pQueue = PriorityQueue { a: IntArray, b: IntArray ->

a[1] - b[1]

}

val minDis = IntArray(n)

var res = 0

pQueue.add(intArrayOf(0, 0))

while (pQueue.size > 0) {

val poll = pQueue.poll()

val node = poll[0]

val dist = poll[1]

if (minDis[node] > 0) continue

res++

minDis[node] = dist

for (child in adList[node]!!) {

val cNode = child!![0]

val weight = child[1]

if (cNode != 0 && minDis[cNode] == 0) {

res += (maxMoves - dist).coerceAtMost(weight)

val cNodeDist = dist + weight + 1

if (cNodeDist <= maxMoves) pQueue.add(intArrayOf(cNode, cNodeDist))

} else {

res += (weight - (maxMoves - minDis[cNode]).coerceAtMost(weight)).coerceAtMost(

(maxMoves - dist).coerceAtMost(weight)

)

}

}

}

return res

}

private fun getAdList(edges: Array<IntArray>, n: Int): Array<ArrayList<IntArray?>?> {

val adList: Array<ArrayList<IntArray?>?> = arrayOfNulls<ArrayList<IntArray?>?>(n)

adList[0] = ArrayList()

for (edge in edges) {

val s = edge[0]

val d = edge[1]

val w = edge[2]

if (adList[s] == null) adList[s] = ArrayList()

if (adList[d] == null) adList[d] = ArrayList()

adList[s]?.add(intArrayOf(d, w))

adList[d]?.add(intArrayOf(s, w))

}

return adList

}

}

882\. Reachable Nodes In Subdivided Graph

Hard

You are given an undirected graph (the **"original graph"**) with `n` nodes labeled from `0` to `n - 1`. You decide to **subdivide** each edge in the graph into a chain of nodes, with the number of new nodes varying between each edge.

The graph is given as a 2D array of `edges` where <code>edges[i] = [u_i, v_i, cnt_i]</code> indicates that there is an edge between nodes <code>u_i</code> and <code>v_i</code> in the original graph, and <code>cnt_i</code> is the total number of new nodes that you will **subdivide** the edge into. Note that <code>cnt_i == 0</code> means you will not subdivide the edge.

To **subdivide** the edge <code>[u_i, v_i]</code>, replace it with <code>(cnt_i + 1)</code> new edges and <code>cnt_i</code> new nodes. The new nodes are <code>x₁</code>, <code>x₂</code>, ..., <code>x_{cnt_i}</code>, and the new edges are <code>[u_i, x₁]</code>, <code>[x₁, x₂]</code>, <code>[x₂, x₃]</code>, ..., <code>[x_{cnt_i-1}, x_{cnt_i}]</code>, <code>[x_{cnt_i}, v_i]</code>.

In this **new graph**, you want to know how many nodes are **reachable** from the node `0`, where a node is **reachable** if the distance is `maxMoves` or less.

Given the original graph and `maxMoves`, return _the number of nodes that are **reachable** from node_ `0` _in the new graph_.

**Example 1:**

**Input:** edges = [[0,1,10],[0,2,1],[1,2,2]], maxMoves = 6, n = 3

**Output:** 13

**Explanation:** The edge subdivisions are shown in the image above. The nodes that are reachable are highlighted in yellow.

**Example 2:**

**Input:** edges = [[0,1,4],[1,2,6],[0,2,8],[1,3,1]], maxMoves = 10, n = 4

**Output:** 23

**Example 3:**

**Input:** edges = [[1,2,4],[1,4,5],[1,3,1],[2,3,4],[3,4,5]], maxMoves = 17, n = 5

**Output:** 1

**Explanation:** Node 0 is disconnected from the rest of the graph, so only node 0 is reachable.

**Constraints:**

* <code>0 <= edges.length <= min(n * (n - 1) / 2, 10⁴)</code>

* `edges[i].length == 3`

* <code>0 <= u_i < v_i < n</code>

* There are **no multiple edges** in the graph.

* <code>0 <= cnt_i <= 10⁴</code>

* <code>0 <= maxMoves <= 10⁹</code>

* `1 <= n <= 3000`

package g0801_0900.s0879_profitable_schemes

import org.hamcrest.CoreMatchers.equalTo

import org.hamcrest.MatcherAssert.assertThat

import org.junit.jupiter.api.Test

internal class SolutionTest {

@Test

fun profitableSchemes() {

assertThat(

Solution().profitableSchemes(5, 3, intArrayOf(2, 2), intArrayOf(2, 3)),

equalTo(2)

)

}

@Test

fun profitableSchemes2() {

assertThat(

Solution().profitableSchemes(10, 5, intArrayOf(2, 3, 5), intArrayOf(6, 7, 8)),

equalTo(7)

)

}

}

package g0801_0900.s0880_decoded_string_at_index

import org.hamcrest.CoreMatchers.equalTo

import org.hamcrest.MatcherAssert.assertThat

import org.junit.jupiter.api.Test

internal class SolutionTest {

@Test

fun decodeAtIndex() {

assertThat(Solution().decodeAtIndex("leet2code3", 10), equalTo("o"))

}

@Test

fun decodeAtIndex2() {

assertThat(Solution().decodeAtIndex("ha22", 5), equalTo("h"))

}

@Test

fun decodeAtIndex3() {

assertThat(Solution().decodeAtIndex("a2345678999999999999999", 1), equalTo("a"))

}

}

package g0801_0900.s0881_boats_to_save_people

import org.hamcrest.CoreMatchers.equalTo

import org.hamcrest.MatcherAssert.assertThat

import org.junit.jupiter.api.Test

internal class SolutionTest {

@Test

fun numRescueBoats() {

assertThat(Solution().numRescueBoats(intArrayOf(1, 2), 3), equalTo(1))

}

@Test

fun numRescueBoats2() {

assertThat(Solution().numRescueBoats(intArrayOf(3, 2, 2, 1), 3), equalTo(3))

}

@Test

fun numRescueBoats3() {

assertThat(Solution().numRescueBoats(intArrayOf(3, 5, 3, 4), 5), equalTo(4))

}

}