คำอธิบายปัญหา ให้ต้นไม้ N โหนด (0..N-1) และ N-1 edges หา ans[i] = ผลรวมระยะทางจากโหนด i ไปทุกโหนดอื่น ตัวอย่าง N=6, edges=[[0,1],[0,2],[2,3],[2,4],[2,5]] → Output: [8,12,6,10,10,10] แนวทางแก้ปัญหา: Tree DP (Two-pass DFS) Pass 1 (Post-order): คำนวณจากใบขึ้นราก cnt[u] = จำนวนโหนดใน subtree u (รวม u

คำอธิบายปัญหา สตริง X, Y คล้าย ถ้าสลับตัวอักษร 2 ตัวใน X ได้ Y (หรือ X==Y) ความคล้ายเป็น equivalence relation หาจำนวนกลุ่ม (connected components) ในลิสต์สตริง A (ทุกคู่เป็น anagram) ตัวอย่าง A = [tars,rats,arts,star] → Output: 2 Group 1: {tars, rats, arts}, Group 2: {star} แนวทางแก้ปัญหา: Union-Fi

คำอธิบายปัญหา กราฟไม่มีทิศทาง เชื่อมต่อ N โหนด หาความยาวเส้นทางสั้นที่สุดที่เยี่ยมชมทุกโหนด (เริ่ม/จบที่ไหนก็ได้, เยี่ยมซ้ำ/ใช้ edge ซ้ำได้) ตัวอย่าง graph = [[1],[0,2,4],[1,3,4],[2],[1,2]] → Output: 4 Path: [0,1,4,2,3] แนวทางแก้ปัญหา: BFS + Bitmask State State: (mask, node) โดย mask = bitmask ของ

คำอธิบายปัญหา สตริง A, B เป็น K-similar ถ้าสลับตัวอักษรใน A ทั้งหมด K ครั้ง ได้ B (A, B เป็น anagram) หา K น้อยที่สุด ตัวอย่าง A=abc, B=bac → Output: 1 (swap a,b) แนวทางแก้ปัญหา: BFS + Pruning BFS จาก A ระดับต่อระดับ (แต่ละระดับ = 1 swap) i ก็ต่อเมื่อ: A[j] == B[i] (สลับแล้ว i จะถูกต้อง)

คำอธิบายปัญหา มีคน N คน คนที่ i มี quality[i] และค่าจ้างขั้นต่ำ wage[i] จ้าง K คน จ่ายค่าจ้างสัดส่วน quality และต้อง ≥ wage[i] หาต้นทุนรวมน้อยที่สุด ตัวอย่าง quality=[10,22,5], wage=[70,52,30], K=2 → Output: 105 จ้างคน 0 และ 2: อัตรา = max(70/10, 30/5) = 7 → จ่าย 70+35=105 ข้อสังเกตสำคัญ อัตราค่าจ

คำอธิบายปัญหา ให้อาร์เรย์ A หาความยาวซับอาร์เรย์ติดต่อกันสั้นที่สุดที่ผลรวม ≥ K หากไม่มีคืน -1 ตัวอย่าง A = [5,3,-2,2,1], K = 6 → Output: 2 (ซับอาร์เรย์ [5,3]) แนวทางแก้ปัญหา: Monotonic Deque + Prefix Sum คำนวณ prefix sum: P[i] = A[0]+...+A[i] ต้องการหา i

คำอธิบายปัญหา รถเดินทาง target ไมล์ เริ่มต้นน้ำมัน startFuel ใช้น้ำมัน 1 ลิตร/ไมล์ มีสถานีน้ำมัน st[i] = [position, fuel] หาจุดหยุดเติมน้อยที่สุดเพื่อถึงจุดหมาย หากไม่ได้คืน -1 ตัวอย่าง target=100, startFuel=10, stations=[[10,40],[20,30],[30,20],[60,40]] → Output: 3 แนวทางแก้ปัญหา: Greedy + Max He

คำอธิบายปัญหา มีคน G คน และอาชญากรรมหลายอย่าง อาชญากรรม i ให้กำไร profit[i] ต้องการคน group[i] คน คนหนึ่งทำอาชญากรรมได้อย่างมาก 1 อย่าง หาจำนวน subset ของอาชญากรรมที่กำไรรวม ≥ P และคนรวม ≤ G modulo 10⁹+7 ตัวอย่าง G=5, P=3, group=[2,2], profit=[2,3] → Output: 2 แนวทางแก้ปัญหา: 0/1 Knapsack DP State

คำอธิบายปัญหา F และไม่แตกถ้าทิ้งจากชั้น ≤F หาจำนวนการทิ้งน้อยที่สุดที่รับประกันหา F ได้ ตัวอย่าง K=2, N=6 → Output: 3 แนวทางแก้ปัญหา: DP + Binary Search State: dp[k][n] = จำนวนการทิ้งน้อยที่สุดสำหรับ k ฟอง n ชั้น Recurrence: dp[k][n] = 1 + min_{1≤x≤n} max(dp[k-1][x-1], dp[k][n-x]) ทิ้งที่ชั้น x:

คำอธิบายปัญหา ให้อาร์เรย์ A พิจารณา subsequence ทุกตัว (ไม่ว่าง) ความกว้าง = max - min หาผลรวมความกว้างของทุก subsequence modulo 10⁹+7 ตัวอย่าง A = [3,1,2] → Output: 6 Subsequences: [1],[2],[3],[2,1],[2,3],[1,3],[2,1,3] Widths: 0,0,0,1,1,2,2 → Sum = 6 แนวทางแก้ปัญหา: คณิตศาสตร์ + Sorting เรียง A เ

คำอธิบายปัญหา ออกแบบ FreqStack รองรับ: push(x): ใส่ x เข้า stack pop(): ลบและคืนค่าที่มีความถี่มากที่สุด ถ้ามีหลายค่า ให้คืนตัวที่ใกล้ top มากที่สุด ตัวอย่าง push: 7,9,7,9,6,7 → pop×4: 7, 9, 7, 6 แนวทางแก้ปัญหา: HashMap + Stack of Stacks cnt[x]: ความถี่ของ x sts[f]: stack ของค่าที่มีความถี่ f (

คำอธิบายปัญหา ให้สตริง S ตัวพิมพ์เล็ก ในแต่ละการเคลื่อนย้าย เลือก 1 ใน K ตัวแรก ย้ายไปท้าย สตริง หาสตริง lexicographically smallest ที่เป็นไปได้ ตัวอย่าง S = cabaa, K = 3 → Output: aaabc ข้อสังเกตสำคัญ K = 1: สามารถ rotate ได้อย่างเดียว → หา rotation ที่เล็กที่สุด 1: สามารถสลับตัวอักษรได้ทุกคู่

คำอธิบายปัญหา ให้ชุดตัวเลข D (subset ของ {1..9} เรียงแล้ว) เขียนเลขได้โดยใช้ตัวเลขใน D ซ้ำได้ หาจำนวนเลขบวก ≤ N ตัวอย่าง D = [2,3,4,7], N = 100 → Output: 20 แนวทางแก้ปัญหา: Digit DP แบบ Greedy นับเลขที่มีหลักน้อยกว่า N: Σ |D|ⁱ สำหรับ i=1..len(N)-1 นับเลขที่มีหลักเท่ากัน N (most significant digit

คำอธิบายปัญหา P[i+1], S[i]==I ⇒ P[i]

คำอธิบายปัญหา จำนวนเต็มบวก N เรียกว่า superpalindrome ถ้า N เป็น palindrome และ N เป็นกำลังสองของ palindrome อีกตัว หาจำนวน superpalindrome ในช่วง [L, R] ตัวอย่าง L=5, R=500 → Output: 3 (คือ 9, 121, 484) ข้อสังเกต ถ้า x² เป็น palindrome และ x เป็น palindrome → x² เป็น superpalindrome x ≤ √R ≤ 10⁹

คำอธิบายปัญหา มีเพลง N เพลง ต้องการฟัง L เพลง เงื่อนไข: ทุกเพลงเล่นอย่างน้อย 1 ครั้ง เพลงเดิมจะเล่นซ้ำได้ก็ต่อเมื่อมีเพลงอื่น K เพลงถูกเล่นระหว่างนั้น หาจำนวนเพลย์ลิสต์ที่เป็นไปได้ modulo 10⁹+7 ตัวอย่าง N=2, L=3, K=0 → Output: 6 [1,1,2], [1,2,1], [2,1,1], [2,2,1], [2,1,2], [1,2,2] แนวทางแก้ปัญหา

คำอธิบายปัญหา ให้อาร์เรย์ A ของ 0 และ 1 แบ่งเป็น 3 ส่วนไม่ว่าง ที่แทนค่า binary เท่ากัน คืน [i,j] ที่ i+1

คำอธิบายปัญหา ให้สตริง S นับจำนวน subsequence ที่ต่างกัน (distinct) ของ S ผลลัพธ์ modulo 10⁹+7 ตัวอย่าง S = bab → Output: 6 Subsequences: a, b, ba, ab, bb, abb แนวทางแก้ปัญหา: DP บนตัวอักษรล่าสุด dp[c] = จำนวน subsequence ที่จบด้วยตัวอักษร c (รวม empty subsequence ที่นำมาต่อ) เมื่ออ่านตัวอักษร x

คำอธิบายปัญหา ให้อาร์เรย์ A ของสตริง หาสตริงสั้นที่สุดที่มีทุกสตริงใน A เป็น substring สมมติว่าไม่มีสตริงใน A ที่เป็น substring ของอีกตัวหนึ่ง ตัวอย่าง A = [dbsh,dsbbhs,hdsb,ssdb,bshdbsd] → hdsbbhssdbshdbsd แนวทางแก้ปัญหา: TSP บนกราฟ Overlap + DP Bitmask คำนวณ overlap graph: graph[i][j] = จำนวนตั

คำอธิบายปัญหา 1 หาขนาด connected component ใหญ่สุด ตัวอย่าง A = [4,6,15,35] → Output: 4 4-6 (gcd=2), 6-15 (gcd=3), 15-35 (gcd=5) → เชื่อมต่อทั้งหมด แนวทางแก้ปัญหา: Union-Find (DSU) บนตัวหารเฉพาะ สำหรับแต่ละจำนวน x ใน A แยกตัวประกอบเฉพาะ ใช้ map m: prime_factor → index ของจำนวนแรกที่มีตัวประกอบนี