The objective is to partition an m by n rectangular cake into 1x1 unit squares with the least total cost. Each horizontal cut between rows i and i+1 incurs a cost of horizontalCut[i]. Each vertical cut between columns j and j+1 incurs a cost of verticalCut[j]. The total cost is the sum of all cut co...
Problem A Given three integers (x), (y), and (n), construct a sequence (a) of length (n) satisfying: (a_1 = x), (a_n = y). Sequence (a) is strictly increasing. The differences (b_i = a_{i+1} - a_i) form a strictly decreasing sequence. Start by defining the array with (a_1 = x) and (a_n = y). The key...
Canvas Painting The problem involves finding the maximum number of effective operations to reduce distinct colors. With n initial colors, each operation can reduce one color by making two positions share the same color. The answer is n minus the maximum effective operations. Algorithm: Group paintin...
Problem Overview Given T time units and n tasks, each task i has a value a_i and a deadline b_i. In each time unit t, you may select one unselected task i where b_i ≥ t to gain a_i. The goal is to maximize the total reward. Algorithm Strategy Sort tasks in descending order of value a_i. Use a set to...
Problem A: The Man who became a God For a sequence (a) of length (n), define the cost of a segment ([l, r]) as (f(l, r) = \sum_{i=l}^{r-1} |a_i - a_{i+1}|). We need to partition the entire sequence into (k) contiguous segments to maximize the sum of segment costs. The total cost of the whole sequenc...
Given an integer array prices where prices[i] represents the stock price on day i, determine the maximum profit achievable. You may engage in multiple transactions (buy one and/or sell one share of the stock each day) but can hold at most one share at any time. Buying and selling on the same day is...
The classic problem of arranging two sequences to maximize pairwise advantages can be modeled as an optimizaton task. Given two arrays of equal length, the goal is to permute the first array so that the count of positions where its element exceeds the corresponding element in the second array is max...
Jump Game: Greedy Reachability public boolean canJump(int[] nums) { int farthest = 0; for (int idx = 0; idx < nums.length; idx++) { if (idx > farthest) return false; farthest = Math.max(farthest, idx + nums[idx]); if (farthest >= nums.length - 1) return true; } return true; } The core idea...
A. The Good Array Tags: greedy, math Problem: For any (i \in {1,2,\dots,n}), the array (a) must have at least (\lceil \frac{i}{k} \rceil) ones among its first (i) elements and also atleast (\lceil \frac{i}{k} \rceil) ones among its last (i) elements. Solution: Special case (k=1): The positions where...
A river contains a starting rock at position 0 and an ending rock at position L. Between them there are N intermediate rocks, each at a distinct coordinate Di (0 < Di < L). A cow must jump from rock to rock, never skipping ahead by less than some distance. To challenge the cows, we can remove...