VOL.

01 · CODING HANDS-ON ISSUE: EXAM RECALL

LAKSHMI · BUILDS

A FIELD REPORT —

Three
Problems,
One Sitting.
Notes recalled from the exam hall by a
senior who sat the paper — reconstructed,
reasoned, and solved.

SOURCE FORMAT

Senior's exam recall Coding Hands-On · 3 questions

STACK COMPILED BY

Python 3 Lakshmi Builds

How to read this. Each question is laid out the way it appeared on screen — problem, input
format, constraints, sample cases — followed by an approach, a working Python 3 solution, and
 a verification trace. Use it the way you'd use a senior's handwritten notes: as a head-start, not a
substitute for sitting the chair yourself.

— INSIDE THIS ISSUE —

Q.01 Minimum Vote Flips for Candidate 1 G REEDY

Q.02 Tiling a Strip with Penalties D P · 1D

Q.03 Phase Scheduling under Duration Cap B RUTE FORCE

LAKSHMI BUILDS — COVER — PAGE 01
LAKSHMI · BUILDS QUESTION ONE PAGE 02

Q.01 — GREEDY · SORTING

The Vote
that turned the count.
N voters, each casting a 0 or a 1, each carrying a weight. Flip at most
K votes. Make Candidate 1 win — with the fewest flips you can
manage.

— THE PROBLEM —

You have N voters , each with a vote (0 or 1) and a weight w[i] . You may flip up to K votes (change 0 → 1 or
1 → 0).

After flipping, candidate 1 wins if the total weight of votes for 1 is strictly greater than the total weight of
votes for 0.

Determine whether candidate 1 can win, and if so, return the minimum number of flips . Return -1 if candidate
1 cannot win even with K flips.

— INPUT FORMAT —

› First line: integer n — number of votes.

› Second line: integer k — maximum flips allowed.

› Next n lines: integer v[i] — the vote (0 or 1).

› Next n lines: integer w[i] — the weight.

— CONSTRAINTS —

1 ≤ n ≤ 10^5

1 ≤ k ≤ 10^5

-10^9 ≤ v[i] ≤ 10^9

-10^9 ≤ w[i] ≤ 10^9

— SAMPLE CASES —
 CASE 01 OUTPUT → 0

INPUT READ

3 n = 3
1 k = 1
1 v = [1, 0, 1]
0 w = [10, 5, 10]
1
10
5
10

S₁ = 10 + 10 = 20, S₀ = 5. Since 20 > 5, Candidate 1 is already winning. Zero flips needed.

CASE 02 OUTPUT → 1

INPUT READ

4 n = 4
2 k = 2
0 v = [0, 0, 0, 1]
0 w = [10, 20, 5, 5]
0
1
10
20
5
5

S₁ = 5, S₀ = 35. Flip the heaviest 0-voter (w = 20). Now S₁ = 25, S₀ = 15. Candidate 1 wins in one flip.

CASE 03 OUTPUT → -1

INPUT READ

3 n = 3
1 k = 1
0 v = [0, 0, 0]
0 w = [100, 100, 100]
0
100
100
100

S₁ = 0, S₀ = 300. Even after the one allowed flip, S₁ = 100 vs S₀ = 200. Impossible.

— THE APPROACH —

GREEDY · O(N LOG N)

1. Compute S₁ (weight already for 1) and S₀ (weight for 0).

 2. If S₁ > S₀, answer is 0 — already winning.

3. Sort the 0-voters by weight in descending order.

4. Flip the heaviest 0 first — each flip swings the gap by 2 × w.

5. After each flip (up to k), check if S₁ > S₀. Return that count.

6. If k flips don't suffice, return -1.

— PYTHON 3 SOLUTION —

import sys
input = [Link]

def solve(n, k, v, w):

s1 = 0 # weight for candidate 1
s0 = 0 # weight for candidate 0
zero_w = []

for i in range(n):
if v[i] == 1:
s1 += w[i]
else:
s0 += w[i]
zero_w.append(w[i])

if s1 > s0:
return 0

zero_w.sort(reverse=True)

flips = 0
for weight in zero_w:
if flips >= k:
break
s0 -= weight
s1 += weight
flips += 1
if s1 > s0:
return flips

return -1

if __name__ == "__main__":
try:
n = int(input())
k = int(input())
v = [int(input()) for _ in range(n)]
w = [int(input()) for _ in range(n)]
print(solve(n, k, v, w))
except (EOFError, ValueError):
pass
T I M E O (n log n) S P A C E O (n) S T Y L E G reedy

· · · · ·
LAKSHMI · BUILDS QUESTION TWO PAGE 03

Q.02 — DYNAMIC PROGRAMMING

Tile
the strip, dodge the toll.
A strip of length N. Tiles of width 1, 2, or 3. Each placement carries a
fixed tile cost plus a per-position surcharge. Cover the strip for as
little as possible.

— THE PROBLEM —

A strip of length N must be fully tiled using tiles of width 1, 2, or 3 . Placing a tile of width w starting at
position i costs c[w] + penalty[i] , where c[1], c[2], c[3] are fixed tile costs and penalty[i] is a per-position
surcharge applied at the tile's starting position.

Positions are 0-indexed (spanning 0 to N-1). Find the minimum total cost to tile the entire strip.

— INPUT FORMAT —

› Line 1: integer N — length of the strip.

› Line 2: integer C1 — cost of a width-1 tile.

› Line 3: integer C2 — cost of a width-2 tile.

› Line 4: integer C3 — cost of a width-3 tile.

› Line 5: N space-separated integers — penalties[i] .

— CONSTRAINTS —

1 ≤ N ≤ 10^5

1 ≤ C1, C2, C3 ≤ 10^5

-10^9 ≤ penalties[i] ≤ 10^9

— SAMPLE CASES —
 CASE 01 OUTPUT → 11

INPUT READ

3 N = 3
10 C1 = 10
10 C2 = 10
10 C3 = 10
1 1 1 penalties = [1, 1, 1]

One width-3 tile at position 0. Cost = C3 + penalty[0] = 10 + 1 = 11.

CASE 02 OUTPUT → 8

INPUT READ

4 N = 4
1 C1 = 1
100 C2 = 100
100 C3 = 100
1 1 1 1 penalties = [1, 1, 1, 1]

Width-1 tiles are 100× cheaper. Four of them at cost (1 + 1) each = 8.

CASE 03 OUTPUT → 103

INPUT READ

5 N = 5
100 C1 = 100
1 C2 = 1
100 C3 = 100
1 100 1 100 1 penalties = [1,100,1,100,1]

Width-2 tile at position 0 (cost 1 + 1 = 2) + width-3 tile at position 2 (cost 100 + 1 = 101). Total = 103. The high-
penalty positions (1 and 3) are skipped as starting points.

— THE APPROACH —

DP · SUFFIX · O(N)

1. Let dp[i] = minimum cost to tile from position i to N-1.

2. Base case: dp[N] = 0.

3. For each i from N-1 down to 0, try width 1, 2, 3 (if they fit).

4. dp[i] = min(c[w] + penalty[i] + dp[i+w]) for valid w.

5. Answer is dp[0].

— PYTHON 3 SOLUTION —
import sys
input = [Link]

def solve(N, C1, C2, C3, penalties):

dp = [0] * (N + 1)

for i in range(N - 1, -1, -1):

best = C1 + penalties[i] + dp[i + 1]
if i + 2 <= N:
best = min(best, C2 + penalties[i] + dp[i + 2])
if i + 3 <= N:
best = min(best, C3 + penalties[i] + dp[i + 3])
dp[i] = best

return dp[0]

if __name__ == "__main__":
try:
N = int(input())
C1 = int(input())
C2 = int(input())
C3 = int(input())
penalties = list(map(int, input().split()))
print(solve(N, C1, C2, C3, penalties))
except (EOFError, ValueError):
pass

T I M E O (N) S P A C E O (N) → O(1) S T Y L E DP

· · · · ·
LAKSHMI · BUILDS QUESTION THREE PAGE 04

Q.03 — BRUTE FORCE · ENUMERATION

Eight tasks,
four phases, one deadline.
Each task goes to one phase. Within a phase, tasks run in parallel —
the phase lasts as long as its longest task. Phases run back-to-back.
Maximize value while staying under T.

— THE PROBLEM —

You have N tasks and P phases . Task i assigned to phase p contributes value v[i][p] and takes duration
d[i][p] .

Each phase runs sequentially ; within a phase, tasks run in parallel . The duration of a phase equals the
maximum task duration in that phase. Each task must be assigned to exactly one phase .

The total project duration is the sum of phase durations . Maximize total value subject to total project duration ≤
T. Return -1 if no valid assignment exists.

— INPUT FORMAT —

› Line 1: integer n — number of tasks.

› Line 2: integer p — number of phases.

› Line 3: integer t — max allowed total duration.

› Next n lines: p space-separated integers — row i of v .

› Next n lines: p space-separated integers — row i of d .

— CONSTRAINTS —

1 ≤ n ≤ 8

1 ≤ p ≤ 4

1 ≤ t ≤ 10^2

1 ≤ v[i][j] ≤ 20

1 ≤ d[i][j] ≤ 20
— SAMPLE CASES —

CASE 01 OUTPUT → 19

INPUT READ

3 n=3, p=2, t=10

2 v = [[5,10],[8,2],[4,6]]
10 d = [[4,6],[5,3],[2,5]]
5 10
8 2
4 6
4 6
5 3
2 5

Assign tasks 0,1 → phase 0; task 2 → phase 1. Phase durations: max(4,5)=5 and max(5)=5. Total = 10 ≤ 10. Value =
5+8+6 = 19.

CASE 02 OUTPUT → -1

INPUT READ

2 n=2, p=2, t=2

2 v = [[10,10],[10,10]]
2 d = [[5,5],[5,5]]
10 10
10 10
5 5
5 5

Every duration is 5. Any assignment puts ≥ 1 task somewhere, giving total ≥ 5 > 2. Impossible.
 CASE 03 OUTPUT → 127

INPUT READ

7 n=7, p=3, t=79

3 v = 7×3 matrix
79 d = 7×3 matrix
20 19 7
7 17 11
18 13 9
19 6 3
7 20 12
6 3 19
14 3 6
11 2 6
18 9 12
20 8 18
17 20 5
4 14 3
1 15 14
1 12 13

Optimal: phase durations 20, 14, 14 (sum 48 ≤ 79). Total value 20+17+18+19+20+19+14 = 127.

— THE APPROACH —

BRUTE FORCE · O(P^N · N)

1. Constraints are tiny: n ≤ 8, p ≤ 4. Worst case 4⁸ = 65,536 assignments.

2. Enumerate every assignment as a base-p number with n digits.

3. For each, compute per-phase max duration and total value.

4. If total duration ≤ T, track the maximum value seen.

5. If nothing fits under T, return -1.

— PYTHON 3 SOLUTION —
import sys
input = [Link]

def solve(n, p, t, v, d):

best = -1
total = p ** n

for mask in range(total):

phase_max = [0] * p
value = 0
temp = mask

for i in range(n):
ph = temp % p
temp //= p
value += v[i][ph]
if d[i][ph] > phase_max[ph]:
phase_max[ph] = d[i][ph]

if sum(phase_max) <= t and value > best:

best = value

return best

if __name__ == "__main__":
try:
n = int(input())
p = int(input())
t = int(input())
v = [list(map(int, input().split())) for _ in range(n)]
d = [list(map(int, input().split())) for _ in range(n)]
print(solve(n, p, t, v, d))
except (EOFError, ValueError):
pass

T I M E O (p^n · n) S P A C E O (n·p) S T Y L E E numerate

· · · · ·
 — fin —

Three problems. Three patterns: greedy when local choices

add up, DP when futures depend on the present, brute force
when the search space is small enough to walk through.
Read once. Code once. Then go sit your own chair.

Compiled by — Lakshmi Builds

VOL. 01 · FIELD NOTES