Freaks City

In an N×M (N<100, M<10) grid, we need to place cannons on plains (P) while avoiding mountains (H). Cannons attack in a cross pattern: 2 cells left and right horizontally, and 2 cells up and down vertically. Cannons cannot attack each other. The goal is to maximize the number of cannons placed. Example input: 5 4 PHPP PPHH PPPP PHPP PHHP ...

Define ∩ as bitwise AND, ∪ as bitwise OR, and ⊕ as bitwise XOR. The notation i ⊆ x means the set of bits in binary representation i is a subset of x, i.e., i ∩ x = i. SOS DP (Sum Over Subsets) Given an array a, define F(x) = Σ a_i for all i ⊆ x. The goal is to compute F(x) for all x. Define dp[x][k] as the sum of a_i for all i that differ from ...

Guess Number Higher or Lower II We need to solve a game where we guess a number between 1 and n. Each wrong guess costs the amount equal to the guessed number. The goal is to find the minimum amount of money needed to guarantee a win regardless of which number is selected. Brute-Force Recursion class Solution { public: int calculateMinCost( ...

Interval Game Theory via Dynamic Programming Two participants alternately extract characters from either end of a string. Assuming optimal play from both sides, the objective is to predict the final match outcome. The input guarantees an even-length string, with cumulative lengths capped at 2000 across all test cases. The problem resolves effic ...

Counting Palindromic Substrings This section addresses the problem of counting all palindromic substrings within a given string, similar to LeetCode problem 647. Problem Description Given a string s, determine and return the total count of palindromic substrings. A substring is a contiguous sequence of charcaters. A palindromic string reads the ...

A Problem: You need to stay for (n) consecutive days. The pricing is (x) yuan per night for the first (k) days, and (y) yuan per night thereafter. What is the total cost? Solution: (min(k, n) \cdot x + max(n - k, 0) \cdot y) B Problem: Given a string (s), determine if it is "beautiful". A string is beautiful if every lowercase charac ...

Notation Let \(dp_i\) denote the expected number of attempts to correctly play the prefix \(1 \to i\), with \(dp_1 = n\). The target melody is given by the array \(target_i\). Analysis When playing a melody, the current partially correct sequence falls into one of two cases: The current suffix matches some prefix of the melody. No suffix of ...

DAY0 (2024.11.15) Finally arriving at the camp. T2 GYM104787M First, we define a replica connected component as a connected component formed by traversing only nodes with index greater than n. It's not hard to observe that a replica connected component (green nodes) connects to several leaves with index less than n, and together with the origin ...

It is clear that S represents the initial magic value, k is the number of selected items, and x is given in the problem. Noting that x is large but k and n are small, we can define a state that tracks the i-th item, the number of selected items j, and the sum modulo k as l. The goal is to maximize the initial magic value, as higher values reduc ...

RC-u1 Heat Wave Problem Summary: Given daily maximum temperatures and the day of the week for the first day, count how many days have temperatures ≥ 35°C. Days falling on weekends (Saturday and Sunday) should be counted separately. Solution: Iterate through the temperature data while tracking the current weekday. For each temperature ≥ 35, incr ...