⚡ Samsung PPO · Java Algorithm Mastery

❓Problem

Given an undirected graph as an adjacency matrix, decide whether it is bipartite — i.e. whether the vertices can be split into two groups so that every edge joins the two groups (never two vertices inside the same group). If it is bipartite, print one of the two colour groups; otherwise print -1. The graph may be disconnected.

💡Key Idea

A graph is bipartite iff it has no odd-length cycle. Try to 2-colour it: start a component with colour 0, and every neighbour must get the opposite colour (1 - color[u]). If you ever reach a neighbour that is already coloured the same as the current vertex, an odd cycle exists → not bipartite. Loop over all vertices to also colour disconnected components.

📈Visualization

❓Problem

Given a directed graph, determine whether it contains a cycle, and if so print the vertices that form one such cycle in order.

💡Key Idea

Use the classic three-colour DFS:

• WHITE (0) — not visited yet.
• GRAY (1) — on the current recursion stack (being explored).
• BLACK (2) — fully finished.

If DFS reaches a GRAY vertex, that edge points back into the active path — a back edge — which means a cycle. Record the back-edge endpoints (cycleStart, cycleEnd) and rebuild the path with a parent[] array.

📈Visualization

❓Problem

Given an undirected graph (n vertices, m edges), detect a cycle and print its vertices.

💡Key Idea

DFS while remembering the vertex you came from (the parent). A neighbour that is already visited and is not the parent means you reached it by a second route → cycle. The one extra rule vs. the directed case is the v == parent skip, because in an undirected graph the edge you just used appears in both directions.

📈Visualization

❓Problem

A doctor moves around divisions connected as a directed weighted graph; an edge weight is the probability of moving along it. He spends 10 minutes in each division. Given a total time T, find the division he is most likely to be in at that moment (and the probability), by summing the probability of every walk of the right length ending in each division.

💡Key Idea

Enumerate all walks from the start that last exactly T/10 hops. Carry the running product of edge probabilities p. When time runs out, add p to answer[currentDivision] (many different walks can land on the same division — their probabilities accumulate). Finally pick the division with the largest accumulated probability.

📈Visualization

❓Problem

On an N×M board a moving piece jumps like a knight. Find the minimum number of moves to land exactly on a stationary target. Print -1 if unreachable.

💡Key Idea

Unweighted shortest path on a grid ⇒ BFS. Each cell has up to 8 knight moves. BFS explores in expanding rings, so the first time we touch the target, its distance is the minimum. Mark cells as visited the moment they enter the queue to avoid re-processing.

📈Visualization — BFS rings (press Play)

❓Problem

Gas is released at one cell of a grid and spreads to the 4-adjacent open cells (value 1) each second; walls are 0. Output how many seconds until the gas stops spreading — i.e. the maximum distance from the source to any reachable cell.

💡Key Idea

Plain multi-ring BFS flood fill. The source is distance 0; each ring of newly-reached open cells is +1 second. The answer is simply the largest distance label assigned during the flood.

📈Visualization

❓Problem

A frog sits on a grid where 1 = lily pad (standable), 0 = water. Moving horizontally along pads is free (cost 0). A vertical hop costs 1. Find the minimum cost to travel from a source pad to a destination pad.

💡Key Idea

Edges weigh only 0 or 1 ⇒ use 0-1 BFS with a double-ended queue. A 0-cost (horizontal) move pushes to the front; a 1-cost (vertical) move pushes to the back. This keeps the deque sorted by distance, giving Dijkstra-quality answers in O(V+E) without a heap.

📈Visualization

❓Problem

A grid of pipe pieces (types 1–7); each type opens toward some of {left, right, up, down}. Starting from a given pipe and an endoscope of length L, count how many pipes are reachable. You may move between adjacent pipes only when both sides have a matching opening, and only within L steps.

💡Key Idea

Encode each pipe as four booleans (its openings). A step from A to its neighbour B on the right is legal only if A opens right AND B opens left. Then it is ordinary BFS with a distance cap: only enqueue a neighbour when dist + 1 ≤ L. Count every cell that gets a distance label.

📈Visualization — opening shapes

❓Problem

A grid has roads (1) and blocked cells (0). Up to 5 rare-element locations sit on roads. Build a research centre on a road so that the longest distance from the centre to any element is as small as possible. Output that minimised longest distance.

💡Key Idea

Naïvely you'd BFS from every road cell — O((N²)²). Instead, BFS once from each element (only ≤5 of them) to get its distance to every road cell. Then for each candidate cell take the max over the elements (worst element), and the answer is the min of those maxes — a classic min-of-max (1-centre) pattern.

📈Visualization

❓Problem

Starting at the office, Mr Kim must visit all N customers (5–10) and finish at his home. Distance between points is Manhattan |x₁−x₂|+|y₁−y₂|. Find the length of the shortest such route.

💡Key Idea

With N ≤ 10, just try every order of customers (backtracking permutations). Keep a running cost; when all customers are visited add the hop to home and update the best. Crucial speed-up: prune the branch as soon as cost ≥ best — this turns a hopeless 10! search into something instant.

📈Visualization

❓Problem

Given an N×N airfare matrix (entry 0 = no flight), start at city 0, visit every city exactly once, and return to city 0 at minimum total fare. Print -1 if impossible.

💡Key Idea

Same permutation backtracking as Mr Kim, but it's a cycle: after placing the last city you must add the edge back to 0. Skip any move where the fare is 0 (no flight). Base case fires at count == N-1 because city 0 is fixed as start.

📈Visualization

❓Problem

A spaceship travels from source to destination. There are N bidirectional wormholes; wormhole i connects point A=(x₁,y₁) and B=(x₂,y₂) and costs w to traverse. Moving on the plane costs Manhattan distance. Find the minimum total cost; you may use any number of wormholes (or none).

💡Key Idea

At each state (current position, target, accumulated cost) you may either go straight to the destination, or enter any unused wormhole from either end (pay the walk to that mouth + the wormhole fee, then continue from the other mouth). DFS over the order of wormholes used, marking each used so it isn't re-entered. Track the global minimum.

📈Visualization

❓Problem

m oil mines sit in a circle. Split them among n companies so each company gets a contiguous arc (no interleaving). Minimise the difference between the richest and poorest company's total.

💡Key Idea

Because the layout is a ring, fix where the first cut goes by trying every mine as a starting point. Walk the circle; at each mine choose to either extend the current company or close it and open a new one. When you arrive back at the start having opened exactly n companies, update the answer with max − min of the company totals.

📈Visualization

❓Problem

From an array of block heights, build two pillars of equal height (each pillar is a subset of blocks; not every block must be used) to place a banner as high as possible. Print the maximum equal height, or 0 if no non-trivial pair exists.

💡Key Idea

Each block has three choices: go on pillar 1, go on pillar 2, or be left out. Recurse index by index carrying the two running sums p1, p2. Whenever p1 == p2, that's a valid equal height → update the max. This 3-way recursion is cleaner (and avoids duplicate work) compared with picking blocks in arbitrary order.

📈Visualization

❓Problem

An N×N maze: 0 = passage, 1 = wall, 2 = jewel. Enter at top-left, exit at bottom-right, never stepping on the same cell twice. Collect the maximum number of jewels and print the winning path (marked with 3).

💡Key Idea

Brute-force DFS with backtracking: from each cell try all 4 directions onto unvisited non-wall cells, adding 1 whenever you step on a jewel. When you reach the exit, if the jewel count beats the best so far, snapshot the current visited grid as the best path. Restore visited on the way back so other routes can use those cells.

📈Visualization

❓Problem

Given a binary matrix, you may toggle any column (flip all its bits), exactly k toggles in total (a column may be toggled more than once). Maximise the number of rows that become all 1s.

💡Key Idea

Only the parity of each column's toggle count matters — flipping a column twice is a no-op. So the real decision is: which set S of columns ends up flipped an odd number of times. A set of size f is reachable iff f ≤ k and k − f is even (dump the leftover toggles in cancelling pairs). Enumerate all 2^cols subsets, keep the feasible ones, and count all-1 rows.

📈Visualization

❓Problem

An old phone's dial pad has some broken digits; a calculator offers some working digits and operations (+ − × ÷ =). Every key press is one "touch". Find the minimum touches to display a target number — either by typing it directly (if its digits work) or by computing it, e.g. 1 + 4 = (4 touches) to get 5.

💡Key Idea

Search the space of partial calculator expressions with a hard cap of O touches (so the recursion always terminates). State = (previousValue, currentNumber, pendingOp, touches). From any state you may press a working digit (append/start a number) or, once a number is shown, press an operation (which evaluates the pending op into previousValue). Whenever the value equals the target within the budget, record the touch count.

❓Problem

A river bank has N numbered fishing spots (1…N). Several gates each release a number of fishermen; the gate at position g sends a fisherman to a spot at cost |spot − g|. Every fisherman must take a distinct spot. Minimise the total walking distance of all fishermen.

💡Key Idea

Flatten every fisherman into a list tagged with its gate position. This is a minimum-cost assignment: place fishermen one by one onto free spots, accumulate |spot − gate|, and keep the global minimum. Prune any branch whose partial cost already reaches the best found — that keeps the search tiny for the small N of a real test.

📈Visualization

❓Problem

A spaceship starts at the bottom-centre of a 5-column grid and climbs upward, each step moving to the cell above-left, above, or above-right. 1 = coin, 2 = enemy (blocks the move), 0 = empty. You may detonate a bomb once to clear all enemies in the 5×5 block ahead. Collect the maximum coins before getting stuck or running off the top.

💡Key Idea

Recurse upward exploring the three diagonal moves, adding coins, never stepping onto an enemy. If all three moves are blocked and the bomb is still available, detonate the 5×5 region ahead (clearing enemies) and retry from the same cell with one fewer bomb. The recursion returns the best coin total over all choices.

📈Visualization

❓Problem

You hold D CPUs, E memory chips, F boards. A leftover CPU sells for d, a leftover chip for e. Each of N PC configurations consumes (Dᵢ,Eᵢ,Fᵢ) parts and sells for SPᵢ. Using at most 3 distinct configurations (each any number of times), maximise total revenue (assembled PCs + leftover parts sold raw).

💡Key Idea

DFS over configurations with two moves at each: skip this config, or use it 1, 2, 3… times while parts remain (incrementing the "distinct configs used" counter, capped at 3). When you stop, add the value of leftover CPUs and chips (D·d + E·e) and update the best.

❓Problem

From the top-left to the bottom-right of an N×N grid of digits, moving only right, down, or diagonally down-right, find the maximum digit sum and how many distinct paths achieve it. Cells marked x are blocked. Output 0 0 if no path exists.

💡Key Idea

Fill a DP table from the bottom-right backward. Each cell stores two things: the best sum reachable to the goal, and the count of ways achieving it. A cell's best = its digit + max of its three forward neighbours; its count = sum of the counts of every neighbour that ties for that max. Blocked cells are −∞. If the start ends up −∞, there is no path.

📈Visualization

❓Problem

Balloons hold numbers. Bursting balloon i earns nums[left]·nums[i]·nums[right] coins, where left/right are its current neighbours (treat out-of-range as 1). After it pops, its neighbours become adjacent. Burst all balloons to collect the maximum coins.

💡Key Idea

The trick is to think about which balloon is the last to burst in a range (left, right). If balloon k is last, its neighbours are exactly the fixed walls left−1 and right+1 (everything between is already gone). So:

dp[l][r] = max over k of ( nums[l-1]·nums[k]·nums[r+1] + dp[l][k-1] + dp[k+1][r] )

Pad both ends with 1, then fill by increasing interval length. Answer is dp[1][n].

📈Visualization — DP table fills by interval length (press Play)

❓Problem

The Samsung/CareerCup wording: bursting a balloon scores the product of its left and right neighbours (left only / right only / itself at the boundaries), and balloons with value 0 are best removed first using their surrounding values. Maximise total points.

💡Key Idea

First, sweep out the zero balloons, crediting each one the product of its previous kept value and its next value. Then run an interval DP over the surviving balloons (padded with 1s): for a sub-range a burst scores nums[left]·nums[right], except for the very outer range where it scores the full triple product. Add the pre-counted zero points to the DP result.

❓Problem

Run a marathon of D km with energy budget H. You may pick one of 5 paces for each km; a pace has a (time, energy) cost per km. Find the minimum total time to finish all D km without exceeding energy H. Output minutes and seconds.

💡Key Idea

Two quantities accumulate independently — kilometres done and energy spent — so DP over both. dp[k][e] = minimum time to have run k km using exactly e energy. From each state, try all 5 paces for the next km. Answer = min over e ≤ H of dp[D][e]. Convert seconds → min sec at the end.

📈Visualization

❓Problem

A robot starts at position 0 on a line 0…n and must cut every tree (positions 1…n−1, up to one on each side) and deliver them all to position n. Cutting any tree costs 1; moving distance d costs d. The carried stack must stay non-increasing in height bottom→top (you may only pick up a tree no taller than the one currently on top). Minimise total cost.

💡Key Idea

The stack rule forces you to collect trees in decreasing height order (tallest at the bottom). So process heights from high to low. For a given height, all its trees sit between positions L (leftmost) and R (rightmost); the robot must sweep that whole span and end at one of the two ends before dropping to the next-lower height. Memoise on (currentHeight, robotPosition). Cutting cost (= total trees) is added naturally as you pass each level.

📈Visualization

❓Problem

Given stall positions on a line and c cows, place the cows so that the minimum distance between any two cows is as large as possible. Output that largest possible minimum distance.

💡Key Idea

"Maximise the minimum" ⇒ binary search on the answer. Sort the positions. For a candidate gap x, greedily place cows left-to-right, dropping a cow whenever it's ≥ x away from the last placed one. If you can seat all c cows, x is feasible — try larger; otherwise try smaller. The feasibility is monotonic (works for x ⇒ works for all smaller x), which is exactly what binary search needs.

📈Visualization — binary search the gap (press Play)

❓Problem

On an N×M plot with K marked sinkholes, find the largest square sub-region containing at most one sinkhole, and report its corner coordinates.

💡Key Idea

Build a 2-D prefix sum so the number of sinkholes inside any rectangle is an O(1) query. The side length is monotonic: if no square of side k has ≤1 hole, none of side k+1 does either (a bigger square can only contain more). So binary search the side length, and for each candidate scan all squares using the prefix sum.

count(i,j,k) = pre[i+k][j+k] − pre[i+k][j] − pre[i][j+k] + pre[i][j]

📈Visualization — inclusion–exclusion

❓Problem

There are N pots; pot i overflows after Oᵢ stones. The crow wants K pots to overflow but doesn't know which pots are which. Compute the minimum number of stones needed to guarantee K overflows in the worst case.

💡Key Idea

Worst case = adversary reveals the hardest pots first, so the crow must fill all pots level by level. Sort overflow numbers ascending. Raising the water from one level to the next costs that height increment times the number of pots still in play. After K pots overflow, the rest can be ignored:

total = Σ (Oᵢ − Oᵢ₋₁) · (N − i), for i = 0 … K−1

📈Visualization

❓Problem

In a range [a, b], count the "valid" numbers — those in which the given forbidden digits appear, in total, fewer than k times. (A product number is discarded if it contains the forbidden digits k or more times.)

💡Key Idea

Ranges in these problems are small enough to iterate. For each number, peel off digits with % 10 and / 10, count how many are forbidden, and accept it if that total is below k. A boolean lookup table for the forbidden digits keeps the inner check O(1).

📈Visualization

❓Problem

A compressed string is a run of letter,count pairs, e.g. a10b5a3. Merge repeated letters by summing their counts and print each present letter (a→z) with its total.

💡Key Idea

Single linear scan. Read a letter, then read all the digits that follow it into a number, and add that to a size-26 bucket for that letter. Finally print the buckets in order. The only subtlety is correctly consuming a multi-digit count before the next letter.

📈Visualization

❓Problem

A necklace has 2n beads (R/B) with a knot exactly in the middle (between bead n and n+1); beads can't cross the knot. By removing beads from both ends, find the minimum removals so the remaining middle segment has equal R and B counts.

💡Key Idea

Map B→+1, R→−1 and take a running prefix balance. A segment has equal R and B exactly when its two endpoints share the same prefix balance. Store the first index of each balance in a hashmap; when the same balance reappears with the left end before the knot and the right end after it (so the kept segment straddles the knot), it's a valid balanced middle. Keep the longest; answer = 2n − longest.

📈Visualization

❓Problem

A binary tree is encoded as nested parentheses, each node written as (value (leftSubtree)(rightSubtree)), values may be negative. Given a level K (root = level 0), output the sum of all node values at that level.

💡Key Idea

No tree object needed — track the parenthesis depth while scanning. A value always appears right after its own opening bracket, so a value read at paren-depth d sits at tree level d − 1. Parse signed integers as you go and add the ones whose level equals K.

📈Visualization

❓Problem

An N×N sheet (N = 2ᵏ) is coloured with 0 (white) / 1 (blue). Cutting rule: if a square isn't a single colour, cut it into four equal quadrants and repeat on each; stop when a square is uniform. Count how many white and how many blue pieces result.

💡Key Idea

Textbook quadtree divide & conquer. For a square, check if it's uniform; if yes it's one piece (tally its colour); if not, recurse into the 4 sub-squares of half the side. The recursion depth is log₂N.

📈Visualization

❓Problem

Same task as problem 12 — get from source to destination using bidirectional wormholes — but solved by modelling it as a weighted graph instead of backtracking. Far cleaner when the number of wormholes grows.

💡Key Idea

Create 2N + 2 nodes: the source, the destination, and the two mouths of every wormhole. Between any two nodes the base cost is the Manhattan distance (you can always just walk); additionally the two mouths of each wormhole are joined by an edge of weight w (cheaper teleport). Run Floyd–Warshall for all-pairs shortest paths and read off cost[source][dest].

📈Visualization

❓Problem

Given points in the plane, output the vertices of the smallest convex polygon enclosing them all (the convex hull). Print -1 if a polygon can't be formed (fewer than 3 hull vertices).

💡Key Idea

Jarvis March (gift wrapping): start at the leftmost point (definitely on the hull) and repeatedly pick the next point that is the most counter-clockwise relative to the current one — that's the point for which every other point lies to its left. Wrap around until you return to the start. The orientation of an ordered triple is found from the sign of a cross product (no floating point needed).

cross = (q.y−p.y)(r.x−q.x) − (q.x−p.x)(r.y−q.y)

📈Visualization