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 ...

In a binary matrix of size m x n, a subset of rows is considered "good" if, for every column, the sum of the elements in that column does not exceed half the size of the subset. Formally, if the subset conntains k rows, the sum of each column must be less than or equal to floor(k / 2). The goal is to return the indices of such a subse ...

A player collects trading cards with n distinct types. Each draw yields card type i with probability pi. Duplicate cards convert to coins, where k coins can be exchanged for one missing card. The process continues until all card types are collected. Compute the expected number of draws required. Input Format First line: n (card types) and k (co ...

Solving Cache Penetration Consider a typical product lookup service: public Product getProductById(Long id) { Product product = cache.get(id); if (product != null) { return product; } product = database.query(id); if (product != null) { cache.put(id, product); } return product; } If a product ID ...

Bitmask Dynamic Programming (Bitmask DP) is a technique used to solve problems where the state of a system can be represented by a small set of binary flags. By using an integer's bits to store boolean information—where each bit corresponds to a specific element's status—we can compactly represent and manipulate complex configurations. Core Con ...