Freaks City

Six problems drawn from a competitive programming rating competition are analysed below. Every solution is accompanied by both C++ and Python implementations. Keep in mind that Python code may run slower and care should be taken with complexity constants. Problem 1 – Output a Digit Different from the Product Given two integers a and b, print an ...

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

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

Problem A Given a snacks to distribute equally among b people. Snacks cannot be divided. Find the minimum number of additional snacks that need to be purchased. Solution Each person requires ceil(a/b) snacks. Therefore, the total snacks needed is ceil(a/b) * b. The additional snacks required is ceil(a/b) * b - a. int snacks, people; std::cin &g ...

The basic bubble sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process continues until the array is sorted. import java.util.Arrays; public class BubbleSort { public static void main(String[] args) { int[] data = {5, 8, 6, 3, 9, 2, 1, 7}; basicSort(da ...

This article delves into advanced backtracking techniques for solving common algorithmic problems, specifically focusing on generating increasing subsequences and permutations, including handling duplicates. Generating Increasing Subsequences (Problem 491) Given an integer array, the task is to find all increasing subsequences with a length of ...

To implement a counter supporting both increment and reset operations in O(n) amortized time, we utilize a bit array along with a pointer tracking the position of the most significant set bit. The data structure maintains: A binary array bits representing the counter value An index top_bit pointing to the highest-order 1-bit For the increment ...

Big Integer Addition Given two positive integers (without leading zeros), calculate their sum. Input Format Two lines, each containing one integer. Output Format One line containing the resulting sum. Constraints $1 \leq \text{integer length} \leq 100000$ Example Input: 12 23 Output: 35 Algorithm Represent numbers as digit arrays in reverse o ...

Two Sum Use a hash map to store each number’s index. For every element, check if the complement (target - current) exists in the map. class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: seen = {} for idx, val in enumerate(nums): complement = target - val if complement in se ...

The Pragmatic Guide to Maximizing Scores in Informatics Contests In competitive programming, the prevailing wisdom often emphasizes rigorous training and mastering advanced algorithms. However, for those who are still developing their technical foundation, "cheating"—or more accurately, strategic scoring—is an essential survival skill ...