combinatorics

Practice › Codeforces Solutions › Codeforces Round 1091 (Div. 2) and CodeCraft 26 ›

CF 2217G - Down the Pivot

CF 2217G - Down the Pivot Rating: 2600 Tags: combinatorics, dp, math, trees Solve time: 1m 50s Verified: no Solution Problem Understanding We are working with rooted binary trees where each node carries a binary label, either zero or one. The tree structure is arbitrary as long as every node has at most two children. On top of that structure, we assign labels independently. The only allowed operation is very...

Practice › Codeforces Solutions ›

April Fools Day Contest

April Fools Day Contest Type: April Fools | Problems: 8 | Verified: 8/8 | Rating range: 1200-2000 | Time: 13m 15s Problem Name Rating Tags Solve Time Verified A Mysterious numbers - 1 1200 *special, constructive-algorithms 1m 43s ✓ B Star 1300 *special, combinatorics 2m 57s ✓ C A Piece of Cake 2000 *special, implementation 1m 30s ✓ D Broken checker 1300 *special, brute-force 1m 14s ✓ E MYSTERIOUS LANGUAGE...

Practice › LeetCode › LeetCode 36xx ›

LeetCode 3621 - Number of Integers With Popcount-Depth Equal to K I

LeetCode Problem 3621 Difficulty: 🔴 Hard Topics: Math, Dynamic Programming, Bit Manipulation, Combinatorics Solution Problem Understanding This problem asks us to count integers x in the range [1, n] such that the popcount-depth of x is exactly k . The popcount-depth is defined via a sequence p0, p1, ... where p0 = x and pi+1 = popcount(pi) for all i ≥ 0 . The popcount of a number is the...

Practice › Codeforces Solutions › Codeforces Round 934 (Div. 1) ›

CF 1943D2 - Counting Is Fun (Hard Version)

CF 1943D2 - Counting Is Fun (Hard Version) Rating: 2800 Tags: combinatorics, dp Solve time: 1m 9s Verified: no Solution Problem Understanding We are asked to count certain arrays with bounded elements that satisfy a combinatorial property. Specifically, consider all arrays of length n where each element is between 0 and k . An array is called good if, starting from it, we can repeatedly choose any contiguous subarray of...

Practice › Codeforces Solutions ›

Codeforces Round 277.5 (Div. 2)

Codeforces Round 277.5 (Div. 2) Type: Div. 2 | Problems: 4 | Verified: 0/4 | Rating range: 1200-2300 | Time: 38m 30s Problem Name Rating Tags Solve Time Verified A SwapSort 1200 greedy, implementation, sortings 11m 31s ✗ C Given Length and Sum of Digits... 1400 dp, greedy, implementation 10m 53s ✗ E Hiking 2300 binary-search, dp 5m 18s ✗ F Special Matrices 2100 combinatorics, dp 10m 48s ✗

Practice › Codeforces Solutions › Codeforces Round 275 (Div. 1) ›

CF 482D - Random Function and Tree

CF 482D - Random Function and Tree Rating: 2700 Tags: combinatorics, dp, trees Solve time: 5m 18s Verified: no Solution

Practice › Codeforces Solutions › Educational Codeforces Round 163 (Rated for Div. 2) ›

CF 1948F - Rare Coins

CF 1948F - Rare Coins Rating: 2500 Tags: combinatorics, math, probabilities Solve time: 2m 56s Verified: no Solution Problem Understanding Each bag contains a fixed number of gold coins and a number of silver coins. Gold coins always contribute one unit of value. Silver coins are uncertain, each silver coin independently contributes either 0 or 1 with equal probability. The randomness is only in silver coins; everything else is deterministic....

Practice › Codeforces Solutions › Kotlin Heroes: Episode 10 ›

CF 1958F - Narrow Paths

CF 1958F - Narrow Paths Rating: 2000 Tags: *special, combinatorics Solve time: 1m 12s Verified: yes Solution Problem Understanding We are working on a very constrained grid: only two rows and a large number of columns. The start is the top-left cell, and the goal is the bottom-right cell. Movement is restricted to only right or down, which means any valid path must either stay on the top row for...

Practice › Codeforces Solutions › Educational Codeforces Round 166 (Rated for Div. 2) ›

CF 1976D - Invertible Bracket Sequences

CF 1976D - Invertible Bracket Sequences Rating: 2000 Tags: binary search, combinatorics, data structures, divide and conquer, implementation, two pointers Solve time: 5m 14s Verified: no Solution

Practice › Codeforces Solutions › Codeforces Round 942 (Div. 1) ›

CF 1967E2 - Again Counting Arrays (Hard Version)

CF 1967E2 - Again Counting Arrays (Hard Version) Rating: 3500 Tags: combinatorics, dp, math Solve time: 1m 26s Verified: no Solution Problem Understanding We are asked to count arrays of integers that meet a very particular set of conditions. We have a starting number, $b_0$, and we want to consider sequences $b_0, b_1, \dots, b_n$ where consecutive elements differ by exactly 1. Simultaneously, there is another sequence $a_1, \dots, a_n$...

Practice › Codeforces Solutions › Educational Codeforces Round 164 (Rated for Div. 2) ›

CF 1954D - Colored Balls

CF 1954D - Colored Balls Rating: 1800 Tags: combinatorics, dp, math, sortings Solve time: 1m 43s Verified: no Solution Problem Understanding We are given a collection of balls, each assigned one of n distinct colors, where color i has a_i balls. We are allowed to group these balls, but each group can have at most two balls, and no two balls in the same group can have the same color....

Practice › Codeforces Solutions ›

Codeforces Round 946 (Div. 3)

Codeforces Round 946 (Div. 3) Type: Div. 3 | Problems: 7 | Verified: 0/7 | Rating range: 800-2000 | Time: 36m 53s Problem Name Rating Tags Solve Time Verified A Phone Desktop 800 greedy, math 5m 17s ✗ B Symmetric Encoding 800 implementation, sortings, strings 5m 18s ✗ C Beautiful Triple Pairs 1400 combinatorics, data-structures 5m 16s ✗ D Ingenuity-2 1400 constructive-algorithms, greedy, implementation 5m 16s ✗ E Money Buys...

Practice › Codeforces Solutions › CodeTON Round 8 (Div. 1 + Div. 2, Rated, Prizes!) ›

CF 1942E - Farm Game

CF 1942E - Farm Game Rating: 2300 Tags: combinatorics, games Solve time: 1m 56s Verified: yes Solution Problem Understanding The cows of the two farmers must appear in alternating order on the line. Once the order of the first cow is chosen, the entire sequence is fixed: either J N J N ... J N or N J N J ... N J . The actual positions are not fixed....

Practice › Codeforces Solutions › Codeforces Round 946 (Div. 3) ›

CF 1974C - Beautiful Triple Pairs

CF 1974C - Beautiful Triple Pairs Rating: 1400 Tags: combinatorics, data structures Solve time: 5m 16s Verified: no Solution

Practice › Codeforces Solutions › Codeforces Round 942 (Div. 1) ›

CF 1967E1 - Again Counting Arrays (Easy Version)

CF 1967E1 - Again Counting Arrays (Easy Version) Rating: 3100 Tags: combinatorics, dp, fft, math Solve time: 1m 13s Verified: no Solution Problem Understanding We are given a fixed starting height $b_0$ and we imagine building an integer path $b_0, b_1, \ldots, b_n$ where each step moves by exactly $+1$ or $-1$, but the path is never allowed to go below zero. This is a standard “walk on the non-negative...

Practice › Codeforces Solutions › Codeforces Round 947 (Div. 1 + Div. 2) ›

CF 1975F - Set

CF 1975F - Set Rating: 2600 Tags: bitmasks, brute force, combinatorics, dfs and similar, divide and conquer, dp, math Solve time: 5m 17s Verified: no Solution

Practice › Codeforces Solutions › Codeforces Round 942 (Div. 1) ›

CF 1967C - Fenwick Tree

CF 1967C - Fenwick Tree Rating: 2300 Tags: bitmasks, brute force, combinatorics, data structures, dp, math, trees Solve time: 1m 2s Verified: no Solution Problem Understanding We are asked to reverse a Fenwick Tree construction. A Fenwick Tree is normally defined for an array a of length n such that each element s_k stores the sum of a contiguous subarray of a whose length is the lowest set bit of...

Practice › Codeforces Solutions ›

Kotlin Heroes: Episode 10

Kotlin Heroes: Episode 10 Type: Kotlin | Problems: 10 | Verified: 7/10 | Rating range: 1100-3200 | Time: 11m 13s Problem Name Rating Tags Solve Time Verified A 1-3-5 1100 *special, dp 47s ✓ B Clock in the Pool 1400 *special, math 44s ✓ C Firewood 1500 *special 1m ✓ D Staircase 1600 *special 1m 14s ✗ E Yet Another Permutation Constructive 1900 *special, constructive-algorithms 1m 4s ✗ F Narrow...

Practice › Codeforces Solutions › Educational Codeforces Round 164 (Rated for Div. 2) ›

CF 1954F - Unique Strings

CF 1954F - Unique Strings Rating: 3100 Tags: combinatorics, dp, math Solve time: 1m 7s Verified: yes Solution Problem Understanding We are given a binary string of length $n$ where the first $c$ characters are ones and the remaining $n - c$ characters are zeros. We are allowed to perform up to $k$ operations, where each operation flips a zero into a one. Two strings are considered identical if one...

Practice › Codeforces Solutions › Codeforces Round 934 (Div. 1) ›

CF 1943D1 - Counting Is Fun (Easy Version)

CF 1943D1 - Counting Is Fun (Easy Version) Rating: 2400 Tags: brute force, combinatorics, dp, math Solve time: 1m 31s Verified: no Solution Problem Understanding We are looking at arrays of length n , where each position can hold an integer between 0 and k . Every such array is considered a candidate, so the total universe is (k+1)^n . The notion of “good” is defined through an operation that...

Practice › Codeforces Solutions ›

Educational Codeforces Round 164 (Rated for Div. 2)

Educational Codeforces Round 164 (Rated for Div. 2) Type: Div. 2 | Problems: 6 | Verified: 2/6 | Rating range: 900-3100 | Time: 7m 33s Problem Name Rating Tags Solve Time Verified A Painting the Ribbon 900 constructive-algorithms, greedy, math 1m 3s ✓ B Make It Ugly 1200 implementation, math 1m 15s ✗ C Long Multiplication 1200 greedy, math, number-theory 1m 13s ✗ D Colored Balls 1800 combinatorics, dp, math...

Practice › Codeforces Solutions › CodeTON Round 8 (Div. 1 + Div. 2, Rated, Prizes!) ›

CF 1942G - Bessie and Cards

CF 1942G - Bessie and Cards Rating: 2800 Tags: combinatorics, dp, math Solve time: 3m 51s Verified: yes Solution Problem Understanding The deck contains four kinds of cards. A draw-0 card consumes one playable card from your hand and gives nothing back. A draw-1 card replaces itself. A draw-2 card consumes one card and gives two new cards, so it increases your future drawing power by one. There are also...

Practice › Codeforces Solutions › Codeforces Round 277.5 (Div. 2) ›

CF 489F - Special Matrices

CF 489F - Special Matrices Rating: 2100 Tags: combinatorics, dp Solve time: 10m 48s Verified: no Solution Problem Understanding We are asked to count the number of special square matrices of size n × n , where each row and column contains exactly two ones, and all other cells are zeros. We are given the first m rows explicitly, and the task is to count all matrices that extend these...

Practice › Codeforces Solutions ›

Codeforces Round 275 (Div. 1)

Codeforces Round 275 (Div. 1) Type: Div. 1 | Problems: 4 | Verified: 0/4 | Rating range: 1200-3200 | Time: 23m 24s Problem Name Rating Tags Solve Time Verified A Diverse Permutation 1200 constructive-algorithms, greedy 11m 3s ✗ C Game with Strings 2600 bitmasks, dp, probabilities 1m 44s ✗ D Random Function and Tree 2700 combinatorics, dp, trees 5m 18s ✗ E ELCA 3200 data-structures, trees 5m 19s ✗

Practice › Codeforces Solutions › Educational Codeforces Round 166 (Rated for Div. 2) ›

CF 1976E - Splittable Permutations

CF 1976E - Splittable Permutations Rating: 2500 Tags: combinatorics, data structures, dfs and similar, greedy, math, trees Solve time: 5m 16s Verified: no Solution

Practice › Codeforces Solutions › Codeforces Global Round 25 ›

CF 1951G - Clacking Balls

CF 1951G - Clacking Balls Rating: 3100 Tags: combinatorics, math, probabilities Solve time: 1m 25s Verified: no Solution Problem Understanding We are given a circle of baskets numbered from 1 to $m$, and $n$ balls initially placed in distinct baskets. Alice repeatedly chooses one of the balls uniformly at random and moves it clockwise to the next basket. If that basket already contains a ball, the existing ball is thrown...

Practice › LeetCode › LeetCode 38xx ›

LeetCode 3881 - Direction Assignments with Exactly K Visible People

LeetCode Problem 3881 Difficulty: 🟡 Medium Topics: Math, Combinatorics Solution LeetCode 3881 - Direction Assignments with Exactly K Visible People Problem Understanding We are given n people standing in a line, indexed from 0 to n - 1 . Each person independently chooses one of two directions: 'L' means the person is visible only to people on their right. 'R' means the person is visible only to people on their...

Practice › LeetCode › LeetCode 38xx ›

LeetCode 3855 - Sum of K-Digit Numbers in a Range

LeetCode Problem 3855 Difficulty: 🔴 Hard Topics: Math, Divide and Conquer, Combinatorics, Number Theory Solution LeetCode 3855 - Sum of K-Digit Numbers in a Range Problem Understanding We are given three integers l , r , and k . For every digit position, we may independently choose any digit from the inclusive range [l, r] . We then form all possible numbers consisting of exactly k digits. A key detail...

Practice › LeetCode › LeetCode 37xx ›

LeetCode 3757 - Number of Effective Subsequences

LeetCode Problem 3757 Difficulty: 🔴 Hard Topics: Array, Math, Dynamic Programming, Bit Manipulation, Combinatorics Solution Here’s a complete, detailed technical guide for LeetCode 3757 - Number of Effective Subsequences , following your formatting instructions exactly. Problem Understanding The problem gives us an array of integers, nums , and asks us to determine the number of effective subsequences . The strength of the array is defined as the bitwise OR of...

Practice › LeetCode › LeetCode 38xx ›

LeetCode 3821 - Find Nth Smallest Integer With K One Bits

LeetCode Problem 3821 Difficulty: 🔴 Hard Topics: Math, Bit Manipulation, Combinatorics Solution Problem Understanding This problem asks us to find the nth smallest positive integer whose binary representation contains exactly k ones . In other words, we are working with numbers that, when written in binary, have a specific number of bits set to 1 . The input consists of two integers: n representing the ordinal position in the sequence...

Practice › LeetCode › LeetCode 37xx ›

LeetCode 3725 - Count Ways to Choose Coprime Integers from Rows

LeetCode Problem 3725 Difficulty: 🔴 Hard Topics: Array, Math, Dynamic Programming, Matrix, Combinatorics, Number Theory Solution Problem Understanding The problem asks us to determine how many ways we can choose exactly one number from each row of a given m x n matrix such that the greatest common divisor (GCD) of all chosen numbers is 1. In other words, we need to count all valid combinations of one element per...

Practice › LeetCode › LeetCode 35xx ›

LeetCode 3539 - Find Sum of Array Product of Magical Sequences

LeetCode Problem 3539 Difficulty: 🔴 Hard Topics: Array, Math, Dynamic Programming, Bit Manipulation, Combinatorics, Bitmask Solution Problem Understanding This problem asks us to compute the sum of array products for all magical sequences of a given length. A magical sequence is defined as a sequence of indices into the input array nums of length m , such that when you sum 2 raised to each element of the sequence, the...

Practice › LeetCode › LeetCode 35xx ›

LeetCode 3577 - Count the Number of Computer Unlocking Permutations

LeetCode Problem 3577 Difficulty: 🟡 Medium Topics: Array, Math, Brainteaser, Combinatorics Solution Problem Understanding The problem presents a set of n computers, each with a unique password complexity represented in an array complexity of length n . The computers are labeled 0 to n - 1 , and only computer 0 is initially unlocked. To unlock another computer i , you must already have unlocked at least one computer j...

Practice › LeetCode › LeetCode 35xx ›

LeetCode 3518 - Smallest Palindromic Rearrangement II

LeetCode Problem 3518 Difficulty: 🔴 Hard Topics: Hash Table, Math, String, Combinatorics, Counting Solution Problem Understanding We are given a string s that is guaranteed to already be a palindrome. We may rearrange its characters, but the final rearranged string must also be a palindrome. Among all distinct palindromic permutations that can be formed from the characters of s , we must return the k -th lexicographically smallest one. If...

Practice › LeetCode › LeetCode 34xx ›

LeetCode 3461 - Check If Digits Are Equal in String After Operations I

LeetCode Problem 3461 Difficulty: 🟢 Easy Topics: Math, String, Simulation, Combinatorics, Number Theory Solution Problem Understanding This problem asks us to repeatedly transform a string of digits by summing consecutive pairs modulo 10, until only two digits remain, and then check whether those two digits are equal. In other words, we start with a string s of length at least 3 and, at each step, generate a new string where...

Practice › LeetCode › LeetCode 34xx ›

LeetCode 3470 - Permutations IV

LeetCode Problem 3470 Difficulty: 🔴 Hard Topics: Array, Math, Combinatorics, Enumeration Solution LeetCode 3470 - Permutations IV Problem Understanding We are given two integers, n and k . We must consider all permutations of the numbers 1 through n that satisfy an alternating parity condition. In a valid permutation, every pair of adjacent elements must have different parity. In other words: Odd must be followed by even. Even must be...

Practice › LeetCode › LeetCode 34xx ›

LeetCode 3463 - Check If Digits Are Equal in String After Operations II

LeetCode Problem 3463 Difficulty: 🔴 Hard Topics: Math, String, Combinatorics, Number Theory Solution Problem Understanding The problem asks us to repeatedly transform a string of digits until only two digits remain, and then check if those two digits are the same. The transformation involves taking each consecutive pair of digits, summing them, and taking the result modulo 10 to form a new digit. This process is applied repeatedly, replacing the...

Practice › LeetCode › LeetCode 34xx ›

LeetCode 3428 - Maximum and Minimum Sums of at Most Size K Subsequences

LeetCode Problem 3428 Difficulty: 🟡 Medium Topics: Array, Math, Dynamic Programming, Sorting, Combinatorics Solution Problem Understanding We are given an array nums and an integer k . For every subsequence whose size is at most k , we look at two values: The minimum element in that subsequence. The maximum element in that subsequence. We add minimum + maximum for every valid subsequence, then return the total modulo 10^9 +...

Practice › LeetCode › LeetCode 34xx ›

LeetCode 3416 - Subsequences with a Unique Middle Mode II

LeetCode Problem 3416 Difficulty: 🔴 Hard Topics: Array, Hash Table, Math, Combinatorics Solution Problem Understanding We are given an array nums , and we must count how many subsequences of length exactly 5 have a very specific property. For any chosen subsequence $$[a,b,c,d,e]$$ the middle element is c , because it is the third element of a length-5 sequence. The subsequence is valid if: c is a mode of the...

Practice › Codeforces Solutions ›

Codeforces Round 261 (Div. 2)

Codeforces Round 261 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 4/5 | Rating range: 1200-1900 | Time: 8m 37s Problem Name Rating Tags Solve Time Verified A Pashmak and Garden 1200 implementation 1m 3s ✓ B Pashmak and Flowers 1300 combinatorics, implementation, sortings 1m 31s ✓ C Pashmak and Buses 1900 combinatorics, constructive-algorithms, math 1m 59s ✗ D Pashmak and Parmida's problem 1800 data-structures, divide-and-conquer, sortings 2m...

Practice › Codeforces Solutions ›

Codeforces Round 258 (Div. 2)

Codeforces Round 258 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 5/5 | Rating range: 900-2300 | Time: 8m 33s Problem Name Rating Tags Solve Time Verified A Game With Sticks 900 implementation 1m 19s ✓ B Sort the Array 1300 implementation, sortings 1m 39s ✓ C Predict Outcome of the Game 1700 brute-force, implementation, math 1m 55s ✓ D Count Good Substrings 2000 math 2m 3s ✓...

Practice › Codeforces Solutions ›

MemSQL Start[c]UP 2.0 - Round 2

MemSQL Start[c]UP 2.0 - Round 2 Type: Special | Problems: 6 | Verified: 4/6 | Rating range: 1700-3200 | Time: 11m 5s Problem Name Rating Tags Solve Time Verified A Golden System 1700 math, meet-in-the-middle 1m 15s ✓ B Distributed Join 1900 greedy 1m 7s ✓ C Elections 2100 brute-force 1m 25s ✓ D Bingo! 2700 combinatorics, math, probabilities 1m 42s ✓ E Flow Optimality 3000 constructive-algorithms, flows, math 1m...

Practice › Codeforces Solutions › MemSQL Start[c]UP 2.0 - Round 1 ›

CF 452C - Magic Trick

CF 452C - Magic Trick Rating: 2100 Tags: combinatorics, math, probabilities Solve time: 1m 44s Verified: yes Solution Problem Understanding There are $m$ complete decks, each containing the same $n$ card values. After mixing all decks together, there are $mn$ physical cards in total, and every value appears exactly $m$ times. Alex randomly takes $n$ cards from this large pile and uses them as the working deck for the trick....

Practice › Codeforces Solutions › Codeforces Round 273 (Div. 2) ›

CF 478B - Random Teams

CF 478B - Random Teams Rating: 1300 Tags: combinatorics, constructive algorithms, greedy, math Solve time: 1m 12s Verified: yes Solution Problem Understanding We are given a set of $n$ people who must be partitioned into exactly $m$ non-empty groups. Once the grouping is fixed, every pair of people inside the same group becomes a friendship. A group of size $k$ contributes $\frac{k(k-1)}{2}$ friendships, so the total number of friendships is...

Practice › Codeforces Solutions › Codeforces Round 257 (Div. 1) ›

CF 449D - Jzzhu and Numbers

CF 449D - Jzzhu and Numbers Rating: 2400 Tags: bitmasks, combinatorics, dp Solve time: 1m 54s Verified: yes Solution Problem Understanding We are given an array of n non-negative integers. A group is any non-empty subset of array indices. For a chosen group, we take the bitwise AND of all values at those indices. The task is to count how many non-empty groups have bitwise AND equal to 0 ....

Practice › Codeforces Solutions › Codeforces Round 266 (Div. 2) ›

CF 466D - Increase Sequence

CF 466D - Increase Sequence Rating: 2100 Tags: combinatorics, dp Solve time: 1m 14s Verified: no Solution Problem Understanding We are given an integer array and a target height. The goal is to transform every element of the array into the same final value using a sequence of operations. Each operation picks a segment of indices and increases every value in that segment by exactly one. The final value after...

Practice › Codeforces Solutions › Codeforces Round 272 (Div. 2) ›

CF 476B - Dreamoon and WiFi

CF 476B - Dreamoon and WiFi Rating: 1300 Tags: bitmasks, brute force, combinatorics, dp, math, probabilities Solve time: 1m 35s Verified: yes Solution Problem Understanding Drazil sends a sequence of movement commands. Each '+' moves Dreamoon one step to the right and each '-' moves one step to the left. We know the original command string and also the string that Dreamoon receives. The received string may contain '?' characters,...

Practice › Codeforces Solutions › Codeforces Round 274 (Div. 2) ›

CF 479E - Riding in a Lift

CF 479E - Riding in a Lift Rating: 1900 Tags: combinatorics, dp Solve time: 1m 2s Verified: yes Solution Problem Understanding We are given a line of floors from 1 to n. We start on floor a and we will make exactly k moves. Each move picks a new floor y different from the current floor x, but with a restriction: we are not allowed to move “too far” in...

Practice › Codeforces Solutions › Codeforces Round 261 (Div. 2) ›

CF 459B - Pashmak and Flowers

CF 459B - Pashmak and Flowers Rating: 1300 Tags: combinatorics, implementation, sortings Solve time: 1m 31s Verified: yes Solution Problem Understanding We are given the beauty values of n flowers. We must choose exactly two flowers. Among all possible pairs, we are interested only in pairs whose beauty difference is as large as possible. The task is to output two values: First, the maximum possible difference between the beauties of...

Practice › Codeforces Solutions › Codeforces Round 261 (Div. 2) ›

CF 459C - Pashmak and Buses

CF 459C - Pashmak and Buses Rating: 1900 Tags: combinatorics, constructive algorithms, math Solve time: 1m 59s Verified: no Solution Problem Understanding We need to assign each student to one of k buses on each of d days. For every student, we can think of their assignment as a sequence of length d . For example, if d = 3 , a student might ride buses (2, 1, 2) over...

Practice › Codeforces Solutions ›

Codeforces Round 272 (Div. 2)

Codeforces Round 272 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 5/5 | Rating range: 1000-2200 | Time: 12m 19s Problem Name Rating Tags Solve Time Verified A Dreamoon and Stairs 1000 implementation, math 1m 32s ✓ B Dreamoon and WiFi 1300 bitmasks, brute-force, combinatorics 1m 35s ✓ C Dreamoon and Sums 1600 math 1m 19s ✓ D Dreamoon and Sets 1900 constructive-algorithms, greedy, math 2m 8s ✓...

Practice › Codeforces Solutions › Codeforces Round 258 (Div. 2) ›

CF 451E - Devu and Flowers

CF 451E - Devu and Flowers Rating: 2300 Tags: bitmasks, combinatorics, number theory Solve time: 1m 37s Verified: yes Solution Problem Understanding We have n flower boxes. From box i , we may take any number of flowers between 0 and f[i] , inclusive. The colors are distinct, so a selection is completely described by how many flowers we take from each box. The task is to count the number...

Practice › Codeforces Solutions › MemSQL Start[c]UP 2.0 - Round 2 ›

CF 457D - Bingo!

CF 457D - Bingo! Rating: 2700 Tags: combinatorics, math, probabilities Solve time: 1m 42s Verified: yes Solution Problem Understanding We have an $n \times n$ bingo board. Every cell contains a distinct number chosen from $1$ to $m$, and every valid board is equally likely. After the board is generated, exactly $k$ distinct numbers are called. Every set of $k$ numbers is equally likely. A cell becomes marked if its...

Practice › Codeforces Solutions ›

Codeforces Round 273 (Div. 2)

Codeforces Round 273 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 4/5 | Rating range: 1100-2900 | Time: 6m Problem Name Rating Tags Solve Time Verified A Initial Bet 1100 implementation 59s ✓ B Random Teams 1300 combinatorics, constructive-algorithms, greedy 1m 12s ✓ C Table Decorations 1800 greedy 1m 9s ✓ D Red-Green Towers 2000 dp 1m 3s ✓ E Wavy numbers 2900 brute-force, dfs-and-similar, meet-in-the-middle 1m 37s...

Practice › LeetCode › LeetCode 34xx ›

LeetCode 3405 - Count the Number of Arrays with K Matching Adjacent Elements

LeetCode Problem 3405 Difficulty: 🔴 Hard Topics: Math, Combinatorics Solution Problem Understanding This problem asks us to count how many arrays of length n can be formed using integers between 1 and m such that exactly k adjacent pairs are equal. In other words, we are looking for sequences where the number of times arr[i] equals arr[i-1] is precisely k . The output is the total count of these arrays...

Practice › Mathematics › IMO Shortlist › IMO 2004 Shortlist ›

IMO 2004 SL C5

IMO 2004 SL C5 Origin: NZL | Category: Combinatorics Problem Let N be a positive integer. Two players A and B, taking turns, write numbers from the set {1, . . . , N} on a blackboard. A begins the game by writing 1 on his ﬁrst move. Then, if a player has written n on a certain move, his adversary is allowed to write n+1 or 2n (provided the...

Practice › Mathematics › IMO Shortlist › IMO 1996 Shortlist ›

IMO 1996 SL C1

IMO 1996 SL C1 Origin: FIN | Category: Combinatorics Problem We are given a positive integer $r$ and a rectangular board $ABCD$ with dimensions $|AB| = 20$, $|BC| = 12$. The rectangle is divided into a grid of $20 \times 12$ unit squares. The following moves are permitted on the board: one can move from one square to another only if the distance between the centers of the two squares...

Practice › Mathematics › IMO Shortlist › IMO 2002 Shortlist ›

IMO 2002 SL C1

IMO 2002 SL C1 Origin: COL | Category: Combinatorics Problem Let n be a positive integer. Each point (x, y) in the plane, where x and y are nonnegative integers with x + y \leqn, is colored red or blue, subject to the following condition: If a point (x, y) is red, then so are all points (x′, y′) with x′ \leqx and y′ \leqy. Let A be the number...

Practice › Mathematics › IMO Shortlist › IMO 2000 Shortlist ›

IMO 2000 SL C2

IMO 2000 SL C2 Origin: ITA | Category: Combinatorics Problem A brick staircase with three steps of width 2 is made of twelve unit cubes. Determine all integers n for which it is possible to build a cube of side n using such bricks. Solution Since the volume of each brick is 12, the side of any such cube must be divisible by 6. Suppose that a cube of side...

Practice › Mathematics › IMO Shortlist › IMO 2004 Shortlist ›

IMO 2004 SL C7

IMO 2004 SL C7 Origin: EST | Category: Combinatorics Problem Determine all m \times n rectangles that can be covered with hooks made up of 6 unit squares, as in the ﬁgure: Rotations and reﬂections of hooks are allowed. The rectangle must be covered without gaps and overlaps. No part of a hook may cover area outside the rectangle. Solution Suppose that an m\timesn rectangle can be covered by “hooks”....

Practice › Mathematics › IMO Shortlist › IMO 2000 Shortlist ›

IMO 2000 SL C3

IMO 2000 SL C3 Origin: COL | Category: Combinatorics Problem Let n \geq4 be a ﬁxed positive integer. Given a set S = {P1, P2, . . . , Pn} of points in the plane such that no three are collinear and no four concyclic, let at, 1 \leqt \leqn, be the number of circles PiPjPk that contain Pt in their interior, and let m(S) = a1 + a2 +...

Practice › Mathematics › IMO Shortlist › IMO 2004 Shortlist ›

IMO 2004 SL C6

IMO 2004 SL C6 Origin: IRN | Category: Combinatorics Problem For an n \times n matrix A, let Xi be the set of entries in row i, and Yj the set of entries in column j, 1 \leqi, j \leqn. We say that A is golden if X1, . . . , Xn, Y1, . . . , Yn are distinct sets. Find the least integer n such that there...

Practice › Mathematics › IMO Shortlist › IMO 2002 Shortlist ›

IMO 2002 SL C3

IMO 2002 SL C3 Origin: COL | Category: Combinatorics Problem Let n be a positive integer. A sequence of n positive integers (not necessarily distinct) is called full if it satisﬁes the following condition: For each positive integer k \geq2, if the number k appears in the sequence, then so does the number k −1, and moreover, the ﬁrst occurrence of k −1 comes before the last occurrence of k....

Practice › Mathematics › IMO Shortlist › IMO 2003 Shortlist ›

IMO 2003 SL C5

IMO 2003 SL C5 Origin: ROM | Category: Combinatorics Problem Every point with integer coordinates in the plane is the center of a disk with radius 1/1000. (a) Prove that there exists an equilateral triangle whose vertices lie in diﬀerent disks. (b) Prove that every equilateral triangle with vertices in diﬀerent disks has side length greater than 96. Solution (a) By the pigeonhole principle there are two diﬀerent integers x1,...

Practice › Mathematics › IMO Shortlist › IMO 1996 Shortlist ›

IMO 1996 SL C7

IMO 1996 SL C7 Origin: IRE | Category: Combinatorics Problem Let $U$ be a finite set and let $f$, $g$ be bijective functions from $U$ onto itself. Let $$S={w\in U:f(f(w))=g(g(w))},$$ $$T={w\in U:f(g(w))=g(f(w))},$$ and suppose that $U=S\cup T$. Prove that for $w\in U$, $f(w)\in S$ if and only if $g(w)\in S$. Solution For convenience, we shall write $f^2$, $fg$, $\ldots$ for the functions $f\circ f$, $f\circ g$, $\ldots$. We need two...

Practice › Mathematics › IMO Shortlist › IMO 2001 Shortlist ›

IMO 2001 SL C1

IMO 2001 SL C1 Origin: COL | Category: Combinatorics Problem Let A = (a1, a2, . . . , a2001) be a sequence of positive integers. Let m be the number of 3-element subsequences (ai, aj, ak) with 1 \leqi < j < k \leq2001 such that aj = ai + 1 and ak = aj + 1. Considering all such sequences A, ﬁnd the greatest value of m. Solution...

Practice › Mathematics › IMO Shortlist › IMO 1994 Shortlist ›

IMO 1994 SL C2

IMO 1994 SL C2 Origin: COL | Category: Combinatorics Problem In a certain city, age is reckoned in terms of real numbers rather than integers. Every two citizens x and x′ either know each other or do not know each other. Moreover, if they do not, then there exists a chain of citizens x = x0, x1, . . . , xn = x′ for some integer n \geq2 such...

Practice › Mathematics › IMO Shortlist › IMO 2002 Shortlist ›

IMO 2002 SL C5

IMO 2002 SL C5 Origin: BRA | Category: Combinatorics Problem Let r \geq2 be a ﬁxed positive integer, and let F be an inﬁnite family of sets, each of size r, no two of which are disjoint. Prove that there exists a set of size r −1 that meets each set in F. Solution Assume to the contrary that no set of size less than r meets all sets in...

Practice › Mathematics › IMO Shortlist › IMO 2002 Shortlist ›

IMO 2002 SL C6

IMO 2002 SL C6 Origin: POL | Category: Combinatorics Problem Let n be an even positive integer. Show that there is a permutation x1, x2, . . . , xn of 1, 2, . . . , n such that for every 1 \leqi \leqn the number xi+1 is one of 2xi, 2xi −1, 2xi −n, 2xi −n −1 (where we take xn+1 = x1). Solution Write n = 2m....

Practice › Mathematics › IMO Shortlist › IMO 1994 Shortlist ›

IMO 1994 SL C4

IMO 1994 SL C4 Origin: EST | Category: Combinatorics Problem There are n + 1 ﬁxed positions in a row, labeled 0 to n in increasing order from right to left. Cards numbered 0 to n are shuﬄed and dealt, one in each position. The object of the game is to have card i in the ith position for 0 \leqi \leqn. If this has not been achieved, the following...

Practice › Mathematics › IMO Shortlist › IMO 1996 Shortlist ›

IMO 1996 SL C4

IMO 1996 SL C4 Origin: FIN | Category: Combinatorics Problem Determine whether or not there exist two disjoint infinite sets $A$ and $B$ of points in the plane satisfying the following conditions: No three points in $A \cup B$ are collinear, and the distance between any two points in $A \cup B$ is at least $1$. There is a point of $A$ in any triangle whose vertices are in $B$,...

Practice › Mathematics › IMO Shortlist › IMO 1999 Shortlist ›

IMO 1999 SL C1

IMO 1999 SL C1 Origin: IND | Category: Combinatorics Problem Let n \geq1 be an integer. A path from (0, 0) to (n, n) in the xy plane is a chain of consecutive unit moves either to the right (move denoted by E) or upwards (move denoted by N), all the moves being made inside the half-plane x \geqy. A step in a path is the occurrence of two consecutive...

Practice › Mathematics › IMO Shortlist › IMO 2003 Shortlist ›

IMO 2003 SL C4

IMO 2003 SL C4 Origin: IRN | Category: Combinatorics Problem Let x1, . . . , xn and y1, . . . , yn be real numbers. Let A = (aij)1\leqi,j\leqn be the matrix with entries aij = . 1, if xi + yj \geq0; 0, if xi + yj < 0. Suppose that B is an n \times n matrix whose entries are 0, 1 such that the sum...

Practice › Mathematics › IMO Shortlist › IMO 1999 Shortlist ›

IMO 1999 SL C4

IMO 1999 SL C4 Origin: GBR | Category: Combinatorics Problem Let A be a set of N residues (mod N 2). Prove that there exists a set B of N residues (mod N 2) such that the set A + B = {a + b | a \inA, b \inB} contains at least half of all residues (mod N 2). Solution Let S = {0, 1, . . ., N...

Practice › Mathematics › IMO Shortlist › IMO 2003 Shortlist ›

IMO 2003 SL C2

IMO 2003 SL C2 Origin: GEO | Category: Combinatorics Problem Let D1, . . . , Dn be closed disks in the plane. (A closed disk is a region bounded by a circle, taken jointly with this circle.) Suppose that every point in the plane is contained in at most 2003 disks Di. Prove that there exists disk Dk that intersects at most 7 \cdot 2003 −1 other disks Di....

Practice › Mathematics › IMO Shortlist › IMO 2003 Shortlist ›

IMO 2003 SL C3

IMO 2003 SL C3 Origin: LIT | Category: Combinatorics Problem Let n \geq5 be a given integer. Determine the largest integer k for which there exists a polygon with n vertices (convex or not, with non-self-intersecting boundary) having k internal right angles. Solution Suppose that k of the angles of an n-gon are right. Since the other n −k angles are less than 360◦and the sum of the angles is...

Practice › Mathematics › IMO Shortlist › IMO 2002 Shortlist ›

IMO 2002 SL C4

IMO 2002 SL C4 Origin: BUL | Category: Combinatorics Problem Let T be the set of ordered triples (x, y, z), where x, y, z are integers with 0 \leqx, y, z \leq9. Players A and B play the following guessing game: Player A chooses a triple (x, y, z) in T , and Player B has to discover A’s triple in as few moves as possible. A move consists...

Practice › Mathematics › IMO Shortlist › IMO 2000 Shortlist ›

IMO 2000 SL C6

IMO 2000 SL C6 Origin: FRA | Category: Combinatorics Problem Let p and q be relatively prime positive integers. A subset S of {0, 1, 2, . . .} is called ideal if 0 \inS and for each element n \inS, the integers n + p and n + q belong to S. Determine the number of ideal subsets of {0, 1, 2 . . .}. Solution Every integer z...

Practice › Mathematics › IMO Shortlist › IMO 1996 Shortlist ›

IMO 1996 SL C6

IMO 1996 SL C6 Origin: CAN | Category: Combinatorics Problem A finite number of beans are placed on an infinite row of squares. A sequence of moves is performed as follows: at each stage a square containing more than one bean is chosen. Two beans are taken from this square; one of them is placed on the square immediately to the left, and the other is placed on the square...

Practice › Mathematics › IMO Shortlist › IMO 2004 Shortlist ›

IMO 2004 SL C4

IMO 2004 SL C4 Origin: POL | Category: Combinatorics Problem Consider a matrix of size n\timesn whose entries are real numbers of absolute value not exceeding 1, and the sum of all entries is 0. Let n be an even positive integer. Determine the least number C such that every such matrix necessarily has a row or a column with the sum of its entries not exceeding C in absolute...

Practice › Mathematics › IMO Shortlist › IMO 2000 Shortlist ›

IMO 2000 SL C5

IMO 2000 SL C5 Origin: RUS | Category: Combinatorics Problem In the plane we have n rectangles with parallel sides. The sides of distinct rectangles lie on distinct lines. The boundaries of the rectangles cut the plane into connected regions. A region is nice if it has at least one of the vertices of the n rectangles on its boundary. Prove that the sum of the numbers of the vertices...

Practice › Mathematics › IMO Shortlist › IMO 2003 Shortlist ›

IMO 2003 SL C6

IMO 2003 SL C6 Origin: SAF | Category: Combinatorics Problem Let f(k) be the number of integers n that satisfy the following conditions: (i) 0 \leqn < 10k, so n has exactly k digits (in decimal notation), with leading zeros allowed; (ii) the digits of n can be permuted in such a way that they yield an integer divisible by 11. Prove that f(2m) = 10f(2m −1) for every positive...

Practice › Mathematics › IMO Shortlist › IMO 1996 Shortlist ›

IMO 1996 SL C5

IMO 1996 SL C5 Origin: FRA | Category: Combinatorics Problem Let $p, q, n$ be three positive integers with $p + q < n$. Let $(x_0, x_1, \dots, x_n)$ be an $(n+1)$-tuple of integers satisfying the following conditions: $x_0 = x_n = 0$. For each $i$ with $1 \leq i \leq n$, either $x_i - x_{i-1} = p$ or $x_i - x_{i-1} = -q$. Show that there exists a pair...

Practice › Mathematics › IMO Shortlist › IMO 2001 Shortlist ›

IMO 2001 SL C6

IMO 2001 SL C6 Origin: CAN | Category: Combinatorics Problem For a positive integer n deﬁne a sequence of zeros and ones to be balanced if it contains n zeros and n ones. Two balanced sequences a and b are neighbors if you can move one of the 2n symbols of a to another position to form b. For instance, when n = 4, the balanced sequences 01101001 and 00110101...

Practice › Mathematics › IMO Shortlist › IMO 2001 Shortlist ›

IMO 2001 SL C4

IMO 2001 SL C4 Origin: NZL | Category: Combinatorics Problem A set of three nonnegative integers {x, y, z} with x < y < z is called historic if {z −y, y −x} = {1776, 2001}. Show that the set of all nonnegative integers can be written as the union of disjoint historic sets. Solution For convenience let us write a = 1776, b = 2001, 0 < a <...

Practice › Mathematics › IMO Shortlist › IMO 1999 Shortlist ›

IMO 1999 SL C2

IMO 1999 SL C2 Origin: CAN | Category: Combinatorics Problem (a) If a 5 \times n rectangle can be tiled using n pieces like those shown in the diagram, prove that n is even. (b) Show that there are more than 2\cdot3k−1 ways to tile a ﬁxed 5\times2k rect- angle (k \geq3) with 2k pieces. (Symmetric constructions are considered to be diﬀerent.) Solution (a) Color the ﬁrst, third, and ﬁfth...

Practice › Mathematics › IMO Shortlist › IMO 1996 Shortlist ›

IMO 1996 SL C3

IMO 1996 SL C3 Origin: USA | Category: Combinatorics Problem Let $k, m, n$ be integers such that $1 < n \leq m-1 \leq k$. Determine the maximum size of a subset $S$ of the set ${1, 2, 3, \ldots, k}$ such that no $n$ distinct elements of $S$ add up to $m$. Solution Denote the required maximum size by $M_k(m, n)$. If $m < \frac{n(n+1)}{2}$, then trivially $M_k(m, n)...

Practice › Mathematics › IMO Shortlist › IMO 2002 Shortlist ›

IMO 2002 SL C7

IMO 2002 SL C7 Origin: NZL | Category: Combinatorics Problem Among a group of 120 people, some pairs are friends. A weak quartet is a set of four people containing exactly one pair of friends. What is the maximum possible number of weak quartets? Solution For a graph G on 120 vertices (i.e., people at the party), write q(G) for the number of weak quartets in G. Our solution will...

Practice › Mathematics › IMO Shortlist › IMO 1999 Shortlist ›

IMO 1999 SL C5

IMO 1999 SL C5 Origin: BLR | Category: Combinatorics Problem Let n be an even positive integer. We say that two dif- ferent cells of an n \times n board are neighboring if they have a common side. Find the minimal number of cells on the n\timesn board that must be marked so that every cell (marked or not marked) has a marked neighboring cell. Solution Let n = 2k....

Practice › Mathematics › IMO Shortlist › IMO 2004 Shortlist ›

IMO 2004 SL C8

IMO 2004 SL C8 Origin: POL | Category: Combinatorics Problem For a ﬁnite graph G, let f(G) be the number of triangles and g(G) the number of tetrahedra formed by edges of G. Find the least constant c such that g(G)3 \leqc \cdot f(G)4 for every graph G. Solution Denote by V1, . . . , Vn the vertices of a graph G and by E the set of its...

Practice › Mathematics › IMO Shortlist › IMO 2000 Shortlist ›

IMO 2000 SL C4

IMO 2000 SL C4 Origin: CZE | Category: Combinatorics Problem Let n and k be positive integers such that n/2 < k \leq2n/3. Find the least number m for which it is possible to place m pawns on m squares of an n \times n chessboard so that no column or row contains a block of k adjacent unoccupied squares. Solution By a good placement of pawns we mean the...

Practice › Mathematics › IMO Shortlist › IMO 2001 Shortlist ›

IMO 2001 SL C5

IMO 2001 SL C5 Origin: FIN | Category: Combinatorics Problem Find all ﬁnite sequences (x0, x1, . . . , xn) such that for every j, 0 \leqj \leqn, xj equals the number of times j appears in the sequence. Solution Let (x0, x1, . . . , xn) be any such sequence: its terms are clearly nonnegative integers. Also, x0 = 0 yields a contradiction, so x0 > 0....

Practice › Mathematics › IMO Shortlist › IMO 1994 Shortlist ›

IMO 1994 SL C6

IMO 1994 SL C6 Origin: FIN | Category: Combinatorics Problem On an inﬁnite square grid, two players alternately mark sym- bols on empty cells. The ﬁrst player always marks X’s, the second O’s. One symbol is marked per turn. The ﬁrst player wins if there are 11 con- secutive X’s in a row, column, or diagonal. Prove that the second player can prevent the ﬁrst from winning. Solution Tile the...

Practice › Mathematics › IMO Shortlist › IMO 1994 Shortlist ›

IMO 1994 SL C7

IMO 1994 SL C7 Origin: BRA | Category: Combinatorics Problem Prove that for any integer n \geq2, there exists a set of 2n−1 points in the plane such that no 3 lie on a line and no 2n are the vertices of a convex 2n-gon. Solution Deﬁne Sn recursively as follows: Let S2 = {(0, 0), (1, 1)} and Sn+1 = Sn \cupTn, where Tn = {(x + 2n−1, y...

Practice › Mathematics › IMO Shortlist › IMO 2004 Shortlist ›

IMO 2004 SL C3

IMO 2004 SL C3 Origin: AUS | Category: Combinatorics Problem The following operation is allowed on a ﬁnite graph: Choose an arbitrary cycle of length 4 (if there is any), choose an arbitrary edge in that cycle, and delete it from the graph. For a ﬁxed integer n \geq4, ﬁnd the least number of edges of a graph that can be obtained by repeated ap- plications of this operation from...

Practice › Mathematics › IMO Shortlist › IMO 2001 Shortlist ›

IMO 2001 SL C7

IMO 2001 SL C7 Origin: FRA | Category: Combinatorics Problem A pile of n pebbles is placed in a vertical column. This conﬁguration is modiﬁed according to the following rules. A pebble can be moved if it is at the top of a column that contains at least two more pebbles than the column immediately to its right. (If there are no pebbles to the right, think of this as...

Practice › Mathematics › IMO Shortlist › IMO 1996 Shortlist ›

IMO 1996 SL C2

IMO 1996 SL C2 Origin: UKR | Category: Combinatorics Problem An $(n-1) \times (n-1)$ square is divided into $(n-1)^2$ unit squares in the usual manner. Each of the $n^2$ vertices of these squares is to be colored red or blue. Find the number of different colorings such that each unit square has exactly two red vertices. (Two coloring schemes are regarded as different if at least one vertex is colored...

Practice › Mathematics › IMO Shortlist › IMO 1994 Shortlist ›

IMO 1994 SL C5

IMO 1994 SL C5 Origin: SWE | Category: Combinatorics Problem At a round table are 1994 girls, playing a game with a deck of n cards. Initially, one girl holds all the cards. In each turn, if at least one girl holds at least two cards, one of these girls must pass a card to each of her two neighbors. The game ends when and only when each girl is...

Practice › Mathematics › IMO Shortlist › IMO 1999 Shortlist ›

IMO 1999 SL C3

IMO 1999 SL C3 Origin: GBR | Category: Combinatorics Problem A biologist watches a chameleon. The chameleon catches ﬂies and rests after each catch. The biologist notices that: (i) the ﬁrst ﬂy is caught after a resting period of one minute; (ii) the resting period before catching the 2mth ﬂy is the same as the resting period before catching the mth ﬂy and one minute shorter than the resting period...

Practice › Mathematics › IMO Shortlist › IMO 1999 Shortlist ›

IMO 1999 SL C7

IMO 1999 SL C7 Origin: IRE | Category: Combinatorics Problem Let p > 3 be a prime number. For each nonempty subset T of {0, 1, 2, 3, . . ., p−1} let E(T ) be the set of all (p−1)-tuples (x1, . . . , xp−1), where each xi \inT and x1 + 2x2 + \cdot \cdot \cdot + (p −1)xp−1 is divisible by p and let |E(T )|...

Practice › Mathematics › IMO Shortlist › IMO 1999 Shortlist ›

IMO 1999 SL C6

IMO 1999 SL C6 Origin: GBR | Category: Combinatorics Problem Suppose that every integer has been given one of the colors red, blue, green, yellow. Let x and y be odd integers such that |x| ̸= |y|. Show that there are two integers of the same color whose diﬀerence has one of the following values: x, y, x + y, x −y. Solution We denote colors by capital initial letters....

Practice › Mathematics › IMO Shortlist › IMO 2000 Shortlist ›

IMO 2000 SL C1

IMO 2000 SL C1 Origin: HUN | Category: Combinatorics Problem A magician has one hundred cards numbered 1 to 100. He puts them into three boxes, a red one, a white one, and a blue one, so that each box contains at least one card. A member of the audience draws two cards from two diﬀerent boxes and announces the sum of numbers on those cards. Given this information, the...

Practice › Mathematics › IMO Shortlist › IMO 1994 Shortlist ›

IMO 1994 SL C3

IMO 1994 SL C3 Origin: MCD | Category: Combinatorics Problem Peter has three accounts in a bank, each with an integral number of dollars. He is only allowed to transfer money from one account to another so that the amount of money in the latter is doubled. (a) Prove that Peter can always transfer all his money into two accounts. (b) Can Peter always transfer all his money into one...

Practice › Mathematics › IMO Shortlist › IMO 2001 Shortlist ›

IMO 2001 SL C2

IMO 2001 SL C2 Origin: CAN | Category: Combinatorics Problem Let n be an odd integer greater than 1 and let c1, c2, . . . , cn be integers. For each permutation a = (a1, a2, . . . , an) of {1, 2, . . ., n}, deﬁne S(a) = n i=1 ciai. Prove that there exist permutations a ̸= b of {1, 2, . . ., n}...

Practice › Mathematics › IMO Shortlist › IMO 1994 Shortlist ›

IMO 1994 SL C1

IMO 1994 SL C1 Origin: UKR | Category: Combinatorics Problem On a 5 \times 5 board, two players alternately mark numbers on empty cells. The ﬁrst player always marks 1’s, the second 0’s. One number is marked per turn, until the board is ﬁlled. For each of the nine 3 \times 3 squares the sum of the nine numbers on its cells is computed. Denote by A the maximum of...

Practice › Mathematics › IMO Shortlist › IMO 2001 Shortlist ›

IMO 2001 SL C3

IMO 2001 SL C3 Origin: RUS | Category: Combinatorics Problem Deﬁne a k-clique to be a set of k people such that every pair of them are acquainted with each other. At a certain party, every pair of 3-cliques has at least one person in common, and there are no 5-cliques. Prove that there are two or fewer people at the party whose departure leaves no 3-clique remaining. Solution Consider...

Practice › Mathematics › IMO Shortlist › IMO 2004 Shortlist ›

IMO 2004 SL C2

IMO 2004 SL C2 Origin: GER | Category: Combinatorics Problem Let n and k be positive integers. There are given n circles in the plane. Every two of them intersect at two distinct points, and all points of intersection they determine are distinct. Each intersection point must be colored with one of n distinct colors so that each color is used at least once, and exactly k distinct colors occur...

Practice › Mathematics › IMO Shortlist › IMO 2003 Shortlist ›

IMO 2003 SL C1

IMO 2003 SL C1 Origin: BRA | Category: Combinatorics Problem Let A be a 101-element subset of the set S = {1, 2, . . . , 1000000}. Prove that there exist numbers t1, t2, . . . , t100 in S such that the sets Aj = {x + tj | x \inA}, j = 1, 2, . . . , 100, are pairwise disjoint. Solution Consider the set...

Practice › Mathematics › IMO Shortlist › IMO 2004 Shortlist ›

IMO 2004 SL C1

IMO 2004 SL C1 Origin: PUR | Category: Combinatorics Problem There are 10001 students at a university. Some students join together to form several clubs (a student may belong to diﬀerent clubs). Some clubs join together to form several societies (a club may belong to diﬀerent societies). There are a total of k societies. Suppose that the following conditions hold: (i) Each pair of students are in exactly one club....

Practice › Mathematics › IMO Shortlist › IMO 2002 Shortlist ›

IMO 2002 SL C2

IMO 2002 SL C2 Origin: ARM | Category: Combinatorics Problem For n an odd positive integer, the unit squares of an n \times n chessboard are colored alternately black and white, with the four corners colored black. A tromino is an L-shape formed by three connected unit squares. For which values of n is it possible to cover all the black squares with nonoverlapping trominos? When it is possible, what...

Practice › Mathematics › IMO Shortlist › IMO 2001 Shortlist ›

IMO 2001 SL C8

IMO 2001 SL C8 Origin: GER | Category: Combinatorics Problem Twenty-one girls and twenty-one boys took part in a mathematical competition. It turned out that (i) each contestant solved at most six problems, and (ii) for each pair of a girl and a boy, there was at least one problem that was solved by both the girl and the boy. Show that there is a problem that was solved by...

Practice › Codeforces Solutions ›

Codeforces Round 108 (Div. 2)

Codeforces Round 108 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 4/5 | Rating range: 900-2600 | Time: 9m 28s Problem Name Rating Tags Solve Time Verified A Marks 900 implementation 1m 8s ✓ B Steps 1300 binary-search, implementation 1m 42s ✓ C Pocket Book 1400 combinatorics 1m 33s ✓ D Frames 2600 brute-force 2m 41s ✗ E Garden 2500 bitmasks, dp, graphs 2m 24s ✓

Practice › LeetCode › LeetCode 29xx ›

LeetCode 2930 - Number of Strings Which Can Be Rearranged to Contain Substring

LeetCode Problem 2930 Difficulty: 🟡 Medium Topics: Math, Dynamic Programming, Combinatorics Solution Problem Understanding The problem asks us to count how many strings of length n made of lowercase English letters can be rearranged to contain the substring "leet" . In other words, a string is "good" if, after any permutation of its characters, "leet" appears as a contiguous sequence. The input is a single integer n (1 ≤ n...

Practice › Codeforces Solutions › Codeforces Round 146 (Div. 1) ›

CF 235E - Number Challenge

CF 235E - Number Challenge Rating: 2600 Tags: combinatorics, dp, implementation, math, number theory Solve time: 3m 42s Verified: yes Solution Problem Understanding We need to compute $$\sum_{i=1}^{a}\sum_{j=1}^{b}\sum_{k=1}^{c} d(i \cdot j \cdot k)$$ where $d(x)$ is the number of positive divisors of $x$. The three nested loops range over every triple $(i,j,k)$, multiply the numbers together, compute how many divisors that product has, and add everything modulo $2^{30} = 1073741824$....

Practice › Codeforces Solutions ›

Codeforces Round 178 (Div. 2)

Codeforces Round 178 (Div. 2) Type: Div. 2 | Problems: 4 | Verified: 3/4 | Rating range: 800-2500 | Time: 6m 7s Problem Name Rating Tags Solve Time Verified A Shaass and Oskols 800 implementation, math 1m 38s ✓ C Shaass and Lights 1900 combinatorics, number-theory 1m 10s ✓ D Shaass and Painter Robot 2500 brute-force, implementation, number-theory 1m 47s ✗ E Shaass the Great 2300 dp, trees 1m 32s...

Practice › Codeforces Solutions › Codeforces Round 157 (Div. 1) ›

CF 258C - Little Elephant and LCM

CF 258C - Little Elephant and LCM Rating: 2000 Tags: binary search, combinatorics, dp, math Solve time: 3m 13s Verified: no Solution Problem Understanding We are given an array a of length n . From each position i , we are allowed to choose a value b_i such that 1 ≤ b_i ≤ a_i . Once we choose all values, we look at two quantities: the maximum element of the...

Practice › Codeforces Solutions ›

Codeforces Round 184 (Div. 2)

Codeforces Round 184 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 5/5 | Rating range: 1600-2300 | Time: 7m 58s Problem Name Rating Tags Solve Time Verified A Strange Addition 1600 brute-force, constructive-algorithms, implementation 1m 22s ✓ B Continued Fractions 1700 brute-force, implementation, math 1m 25s ✓ C Ivan and Powers of Two 1600 greedy, implementation 1m 48s ✓ D Olya and Graph 2200 combinatorics, math 1m 36s...

Practice › Codeforces Solutions › Testing Round 6 ›

CF 306C - White, Black and White Again

CF 306C - White, Black and White Again Rating: 2100 Tags: combinatorics, number theory Solve time: 3m 20s Verified: no Solution Problem Understanding We are asked to compute the number of ways to distribute a set of good and not-so-good events across a sequence of days divided into three consecutive segments: a white segment, a black segment, and a second white segment. Each segment must occupy at least one day,...

Practice › LeetCode › LeetCode 29xx ›

LeetCode 2928 - Distribute Candies Among Children I

LeetCode Problem 2928 Difficulty: 🟢 Easy Topics: Math, Combinatorics, Enumeration Solution Problem Understanding The problem asks us to calculate the number of ways to distribute n candies among exactly three children such that no child receives more than a specified limit of candies. In other words, we are looking for all integer triplets (a, b, c) such that a + b + c = n and each of a ,...

Practice › Codeforces Solutions ›

Codeforces Round 240 (Div. 1)

Codeforces Round 240 (Div. 1) Type: Div. 1 | Problems: 5 | Verified: 2/5 | Rating range: 1400-3200 | Time: 8m 52s Problem Name Rating Tags Solve Time Verified A Mashmokh and Numbers 1500 constructive-algorithms, number-theory 2m 6s ✗ B Mashmokh and ACM 1400 combinatorics, dp, number-theory 1m 21s ✓ C Mashmokh and Reverse Operation 2100 combinatorics, divide-and-conquer 1m 40s ✓ D Mashmokh and Water Tanks 2300 binary-search, data-structures, greedy...

Practice › LeetCode › LeetCode 25xx ›

LeetCode 2539 - Count the Number of Good Subsequences

LeetCode Problem 2539 Difficulty: 🟡 Medium Topics: Hash Table, Math, String, Combinatorics, Counting Solution

Practice › Codeforces Solutions › Codeforces Round 240 (Div. 1) ›

CF 414C - Mashmokh and Reverse Operation

CF 414C - Mashmokh and Reverse Operation Rating: 2100 Tags: combinatorics, divide and conquer Solve time: 1m 40s Verified: yes Solution Problem Understanding We are given an array of length $2^n$, where $n$ is at most 20, and a sequence of queries. Each query specifies a number $q_i$, which tells us to repeatedly split the array into blocks of size $2^{q_i}$, reverse each block, and then join the blocks back...

Practice › Codeforces Solutions › Codeforces Round 198 (Div. 2) ›

CF 340C - Tourist Problem

CF 340C - Tourist Problem Rating: 1600 Tags: combinatorics, implementation, math Solve time: 4m 39s Verified: yes Solution Problem Understanding We are asked to compute the average distance a tourist would walk if they visited all destinations on a straight road in every possible order, starting from kilometer zero. Each destination is at a distinct, positive integer distance from the starting point. The input is a list of these distances,...

Practice › Codeforces Solutions ›

Codeforces Round 177 (Div. 1)

Codeforces Round 177 (Div. 1) Type: Div. 1 | Problems: 2 | Verified: 1/2 | Rating range: 1700-2400 | Time: 3m 45s Problem Name Rating Tags Solve Time Verified C Polo the Penguin and XOR operation 1700 implementation, math 1m 39s ✗ D Polo the Penguin and Trees 2400 combinatorics, dfs-and-similar, trees 2m 6s ✓

Practice › LeetCode › LeetCode 24xx ›

LeetCode 2400 - Number of Ways to Reach a Position After Exactly k Steps

LeetCode Problem 2400 Difficulty: 🟡 Medium Topics: Math, Dynamic Programming, Combinatorics Solution Problem Understanding This problem asks us to count the number of distinct ways to move from startPos to endPos on an infinite number line using exactly k steps . At each step, we may move either one position to the left ( -1 ) or one position to the right ( +1 ). The important detail is that...

Practice › LeetCode › LeetCode 32xx ›

LeetCode 3251 - Find the Count of Monotonic Pairs II

LeetCode Problem 3251 Difficulty: 🔴 Hard Topics: Array, Math, Dynamic Programming, Combinatorics, Prefix Sum Solution Problem Understanding The problem asks us to count the number of ways we can split an array of positive integers, nums , into two arrays, arr1 and arr2 , such that they satisfy a set of monotonic conditions. Specifically, arr1 must be non-decreasing, arr2 must be non-increasing, and for each index i , their sum...

Practice › LeetCode › LeetCode 31xx ›

LeetCode 3154 - Find Number of Ways to Reach the K-th Stair

LeetCode Problem 3154 Difficulty: 🔴 Hard Topics: Math, Dynamic Programming, Bit Manipulation, Memoization, Combinatorics Solution Let's dive into a comprehensive solution guide for LeetCode 3154 - Find Number of Ways to Reach the K-th Stair . Problem Understanding This problem involves Alice navigating a staircase starting at stair 1, aiming to reach stair k . The staircase is theoretically infinite, starting at stair 0, and Alice has two operations available:...

Practice › Codeforces Solutions › Codeforces Round 153 (Div. 1) ›

CF 251A - Points on Line

CF 251A - Points on Line Rating: 1300 Tags: binary search, combinatorics, two pointers Solve time: 1m 9s Verified: yes Solution Problem Understanding We are given a set of points positioned along a one-dimensional line. Petya wants to count how many triplets of points can be chosen such that the distance between the leftmost and rightmost points in the triplet does not exceed a given value d . Formally, if...

Practice › Codeforces Solutions › April Fools Day Contest ›

CF 171B - Star

CF 171B - Star Rating: 1300 Tags: *special, combinatorics Solve time: 2m 57s Verified: yes Solution Problem Understanding In this problem, we are asked to calculate the total number of cells in a star-shaped pattern drawn on a grid, given a number of layers. The input is a single integer a , representing the number of concentric layers in the star. The output is a single integer, which is the...

Practice › LeetCode › LeetCode 29xx ›

LeetCode 2927 - Distribute Candies Among Children III

LeetCode Problem 2927 Difficulty: 🔴 Hard Topics: Math, Combinatorics Solution LeetCode 2927 - Distribute Candies Among Children III Problem Understanding We are given two integers, n and limit . There are exactly three children, and we want to distribute all n candies among them. If we let the number of candies received by the three children be: $$x_1,\ x_2,\ x_3$$ then the distribution must satisfy: $$x_1 + x_2 + x_3...

Practice › Codeforces Solutions ›

Codeforces Round 175 (Div. 2)

Codeforces Round 175 (Div. 2) Type: Div. 2 | Problems: 2 | Verified: 2/2 | Rating range: 1200-2600 | Time: 1m 58s Problem Name Rating Tags Solve Time Verified B Find Marble 1200 implementation 58s ✓ E Positions in Permutations 2600 combinatorics, dp, math 1m ✓

Practice › Codeforces Solutions › VK Cup 2012 Finals (unofficial online-version) ›

CF 212C - Cowboys

CF 212C - Cowboys Rating: 2100 Tags: combinatorics, dp, math Solve time: 1m 28s Verified: no Solution Problem Understanding We are given a circular arrangement of cows, each cow facing exactly one of its two neighbors. Represent the circle as a binary string where each character describes direction: one symbol means “point to clockwise neighbor” and the other means “point to counterclockwise neighbor”. At each second, we look at every...

Practice › LeetCode › LeetCode 32xx ›

LeetCode 3247 - Number of Subsequences with Odd Sum

LeetCode Problem 3247 Difficulty: 🟡 Medium Topics: Array, Math, Dynamic Programming, Combinatorics Solution Problem Understanding The problem asks us to count how many subsequences of the given array have an odd sum. A subsequence is formed by choosing any subset of elements while preserving their original order. Unlike subarrays, subsequences do not need to be contiguous. For an array of length n , there are 2^n total subsequences, including the...

Practice › Codeforces Solutions ›

Codeforces Round 153 (Div. 1)

Codeforces Round 153 (Div. 1) Type: Div. 1 | Problems: 5 | Verified: 2/5 | Rating range: 1300-3000 | Time: 26m 57s Problem Name Rating Tags Solve Time Verified A Points on Line 1300 binary-search, combinatorics, two-pointers 1m 9s ✓ B Playing with Permutations 1800 implementation, math 8m 15s ✗ C Number Transformation 2000 dp, greedy, number-theory 14m 23s ✗ D Two Sets 2700 bitmasks, math 1m 13s ✓ E...

Practice › Codeforces Solutions ›

Codeforces Round 146 (Div. 1)

Codeforces Round 146 (Div. 1) Type: Div. 1 | Problems: 4 | Verified: 3/4 | Rating range: 1600-3000 | Time: 11m 16s Problem Name Rating Tags Solve Time Verified A LCM Challenge 1600 number-theory 3m 2s ✓ C Cyclical Quest 2700 data-structures, string-suffix-structures, strings 2m 55s ✓ D Graph Game 3000 graphs 1m 37s ✗ E Number Challenge 2600 combinatorics, dp, implementation 3m 42s ✓

Practice › Codeforces Solutions › Codeforces Round 184 (Div. 2) ›

CF 305D - Olya and Graph

CF 305D - Olya and Graph Rating: 2200 Tags: combinatorics, math Solve time: 1m 36s Verified: yes Solution Problem Understanding We are given a directed acyclic graph with vertices numbered from 1 to n , where every edge goes from a smaller-numbered vertex to a larger-numbered vertex. Some edges already exist, and we are allowed to add more edges under certain constraints. The main constraints ensure that each vertex i...

Practice › Codeforces Solutions ›

Codeforces Round 195 (Div. 2)

Codeforces Round 195 (Div. 2) Type: Div. 2 | Problems: 2 | Verified: 2/2 | Rating range: 2100-2700 | Time: 6m 33s Problem Name Rating Tags Solve Time Verified D Vasily the Bear and Beautiful Strings 2100 combinatorics, math, number-theory 3m 11s ✓ E Vasily the Bear and Painting Square 2700 bitmasks, combinatorics, dp 3m 22s ✓

Practice › Codeforces Solutions › Codeforces Round 175 (Div. 2) ›

CF 285E - Positions in Permutations

CF 285E - Positions in Permutations Rating: 2600 Tags: combinatorics, dp, math Solve time: 1m Verified: yes Solution Problem Understanding We are asked to count permutations of length n where exactly k positions are "good." A position is good if the value at that position differs from the index by exactly 1. For example, in a permutation of length 3, the permutation (2, 1, 3) has good positions at indices...

Practice › Codeforces Solutions › Codeforces Round 178 (Div. 2) ›

CF 294C - Shaass and Lights

CF 294C - Shaass and Lights Rating: 1900 Tags: combinatorics, number theory Solve time: 1m 10s Verified: yes Solution Problem Understanding We are given a row of n lights, some of which are initially on. Each light can only be turned on if it has at least one neighbor that is already on. The task is to count how many sequences of switches exist that will eventually turn all the...

Practice › LeetCode › LeetCode 29xx ›

LeetCode 2912 - Number of Ways to Reach Destination in the Grid

LeetCode Problem 2912 Difficulty: 🔴 Hard Topics: Math, Dynamic Programming, Combinatorics Solution LeetCode 2912 - Number of Ways to Reach Destination in the Grid Problem Understanding We are given an n × m grid and two cells: source = [sx, sy] dest = [dx, dy] A move consists of jumping from one cell to another cell that shares either the same row or the same column. The destination cell must...

Practice › LeetCode › LeetCode 28xx ›

LeetCode 2842 - Count K-Subsequences of a String With Maximum Beauty

LeetCode Problem 2842 Difficulty: 🔴 Hard Topics: Hash Table, Math, String, Greedy, Sorting, Combinatorics Solution Problem Understanding The problem requires us to count k-subsequences of a string s that have the maximum beauty , where beauty is defined as the sum of the frequency of each character in the subsequence. A k-subsequence is a subsequence of length k where all characters are unique. The input string can be up to...

Practice › LeetCode › LeetCode 32xx ›

LeetCode 3250 - Find the Count of Monotonic Pairs I

LeetCode Problem 3250 Difficulty: 🔴 Hard Topics: Array, Math, Dynamic Programming, Combinatorics, Prefix Sum Solution Problem Understanding The problem asks us to count the number of valid pairs of arrays (arr1, arr2) derived from a given array nums . Both arr1 and arr2 have the same length as nums . The constraints on these arrays are: arr1 is non-decreasing . arr2 is non-increasing . At each index i , the...

Practice › LeetCode › LeetCode 32xx ›

LeetCode 3272 - Find the Count of Good Integers

LeetCode Problem 3272 Difficulty: 🔴 Hard Topics: Hash Table, Math, Combinatorics, Enumeration Solution Problem Understanding The problem asks us to count n-digit integers that are "good" with respect to a given integer k . A "good" integer is one whose digits can be rearranged to form a k-palindromic integer . A k-palindromic integer is defined as an integer that satisfies two properties: it is a palindrome (reads the same forwards...

Practice › Codeforces Solutions › Codeforces Round 104 (Div. 1) ›

CF 145D - Lucky Pair

CF 145D - Lucky Pair Rating: 2900 Tags: combinatorics, data structures, implementation Solve time: 1m 48s Verified: no Solution Problem Understanding We are given an array of integers, and some of these integers are "lucky numbers," meaning they consist only of the digits 4 and 7. We are asked to count the number of pairs of non-overlapping contiguous subarrays $[l_1, r_1]$ and $[l_2, r_2]$ such that no lucky number appears...

Practice › Codeforces Solutions ›

MemSQL start[c]up Round 1

MemSQL start[c]up Round 1 Type: Special | Problems: 2 | Verified: 2/2 | Rating range: 1500-2800 | Time: 6m 17s Problem Name Rating Tags Solve Time Verified A Square and Rectangles 1500 implementation 4m 20s ✓ E The Red Button 2800 combinatorics, dfs-and-similar, dsu 1m 57s ✓

Practice › Codeforces Solutions › Codeforces Round 179 (Div. 1) ›

CF 295C - Greg and Friends

CF 295C - Greg and Friends Rating: 2100 Tags: combinatorics, dp, graphs, shortest paths Solve time: 2m 44s Verified: yes Solution Problem Understanding We are given a group of $n$ people standing on one river bank. Each person has a weight of either 50 or 100, and a boat that can carry a limited total weight $k$. Every time the boat crosses the river, it must carry at least one...

Practice › LeetCode › LeetCode 25xx ›

LeetCode 2514 - Count Anagrams

LeetCode Problem 2514 Difficulty: 🔴 Hard Topics: Hash Table, Math, String, Combinatorics, Counting Solution Problem Understanding The problem asks us to count how many distinct anagram sentences can be formed from a given string s . The input string contains one or more words separated by single spaces. An anagram sentence must preserve the structure of the original sentence. Specifically, the i-th word in the new sentence must be a...

Practice › LeetCode › LeetCode 18xx ›

LeetCode 1866 - Number of Ways to Rearrange Sticks With K Sticks Visible

LeetCode Problem 1866 Difficulty: 🔴 Hard Topics: Math, Dynamic Programming, Combinatorics Solution Problem Understanding The problem gives us n sticks with unique lengths from 1 to n . We must arrange these sticks in some order so that exactly k sticks are visible when looking from the left side. A stick is visible if every stick before it is shorter. In other words, a stick is visible if it creates...

Practice › LeetCode › LeetCode 29xx ›

LeetCode 2954 - Count the Number of Infection Sequences

LeetCode Problem 2954 Difficulty: 🔴 Hard Topics: Array, Math, Combinatorics Solution Problem Understanding This problem asks us to compute the number of valid infection sequences in a line of n people, where some people are initially infected. The array sick represents the indices of people who are already infected at the start. At each step, only an uninfected person adjacent to an infected person can become infected. The goal is...

Practice › Codeforces Solutions › Codeforces Round 144 (Div. 1) ›

CF 232B - Table

CF 232B - Table Rating: 1900 Tags: bitmasks, combinatorics, dp, math Solve time: 8m 46s Verified: no Solution Problem Understanding We are given a table with n rows and m columns. We can place a single point in any cell, and the goal is to fill the table so that every contiguous square subtable of size n × n contains exactly k points. The output is the total number of...

Practice › LeetCode › LeetCode 20xx ›

LeetCode 2063 - Vowels of All Substrings

LeetCode Problem 2063 Difficulty: 🟡 Medium Topics: Math, String, Dynamic Programming, Combinatorics Solution Problem Understanding The problem asks us to compute the total number of vowels that appear across every possible substring of a given string. A substring is any contiguous sequence of characters. For a string of length n , there are n * (n + 1) / 2 total substrings. For each substring, we count how many vowels...

Practice › LeetCode › LeetCode 19xx ›

LeetCode 1916 - Count Ways to Build Rooms in an Ant Colony

LeetCode Problem 1916 Difficulty: 🔴 Hard Topics: Array, Math, Dynamic Programming, Tree, Depth-First Search, Graph Theory, Topological Sort, Combinatorics Solution Problem Understanding The problem asks us to count the number of valid ways to sequentially build all rooms in an ant colony, given a dependency tree that dictates which rooms must be built before others. Each room i has a predecessor prevRoom[i] that must be built before i . Room...

Practice › Codeforces Solutions › Codeforces Round 177 (Div. 1) ›

CF 288D - Polo the Penguin and Trees

CF 288D - Polo the Penguin and Trees Rating: 2400 Tags: combinatorics, dfs and similar, trees Solve time: 2m 6s Verified: yes Solution Problem Understanding We are given a tree with n nodes labeled from 1 to n . A tree is a connected acyclic graph, so every pair of nodes has a unique simple path between them. The task is to count the number of pairs of paths (a,...

Practice › Codeforces Solutions ›

Codeforces Round 138 (Div. 1)

Codeforces Round 138 (Div. 1) Type: Div. 1 | Problems: 4 | Verified: 3/4 | Rating range: 1700-3000 | Time: 8m 30s Problem Name Rating Tags Solve Time Verified A Bracket Sequence 1700 data-structures, expression-parsing, implementation 1m 41s ✓ B Two Strings 1900 data-structures, dp, strings 1m 42s ✓ C Partial Sums 1900 combinatorics, math, number-theory 1m 25s ✓ D Spider 3000 geometry, graphs 3m 42s ✗

Practice › Codeforces Solutions ›

Croc Champ 2012 - Round 2

Croc Champ 2012 - Round 2 Type: Special | Problems: 4 | Verified: 4/4 | Rating range: 1200-3100 | Time: 6m 33s Problem Name Rating Tags Solve Time Verified A Trading Business 1200 greedy, sortings 1m 11s ✓ B Word Cut 1700 dp 1m 42s ✓ C Playing with Superglue 2000 combinatorics, constructive-algorithms 1m 28s ✓ E Archaeology 3100 data-structures, dfs-and-similar, trees 2m 12s ✓

Practice › Codeforces Solutions ›

Codeforces Round 236 (Div. 1)

Codeforces Round 236 (Div. 1) Type: Div. 1 | Problems: 2 | Verified: 0/2 | Rating range: 2300-2900 | Time: 1m 57s Problem Name Rating Tags Solve Time Verified D Beautiful Pairs of Numbers 2300 combinatorics, dp 51s ✗ E Two Rooted Trees 2900 data-structures, implementation, trees 1m 6s ✗

Practice › Codeforces Solutions ›

Codeforces Round 131 (Div. 1)

Codeforces Round 131 (Div. 1) Type: Div. 1 | Problems: 5 | Verified: 3/5 | Rating range: 1700-2700 | Time: 7m 23s Problem Name Rating Tags Solve Time Verified A Game 1700 dfs-and-similar, greedy 52s ✓ B Numbers 1900 combinatorics, dp 54s ✗ C Relay Race 2000 dp 2m 58s ✓ D Stars 2300 constructive-algorithms, geometry 1m 36s ✗ E Two Permutations 2700 data-structures, hashing, strings 1m 3s ✓

Practice › Codeforces Solutions ›

Codeforces Round 179 (Div. 1)

Codeforces Round 179 (Div. 1) Type: Div. 1 | Problems: 4 | Verified: 4/4 | Rating range: 1700-2500 | Time: 11m 55s Problem Name Rating Tags Solve Time Verified B Greg and Graph 1700 dp, graphs, shortest-paths 6m 5s ✓ C Greg and Friends 2100 combinatorics, dp, graphs 2m 44s ✓ D Greg and Caves 2400 combinatorics, dp 1m 37s ✓ E Yaroslav and Points 2500 data-structures 1m 29s ✓

Practice › Codeforces Solutions › MemSQL start[c]up Round 1 ›

CF 325E - The Red Button

CF 325E - The Red Button Rating: 2800 Tags: combinatorics, dfs and similar, dsu, graphs, greedy Solve time: 1m 57s Verified: yes Solution Problem Understanding We are asked to construct a walk on a directed functional graph defined by a very specific transition rule. Each state is a node from 0 to n − 1. From a current node i, the next state is not arbitrary: it must be either...

Practice › LeetCode › LeetCode 31xx ›

LeetCode 3128 - Right Triangles

LeetCode Problem 3128 Difficulty: 🟡 Medium Topics: Array, Hash Table, Math, Combinatorics, Counting Solution Problem Understanding The problem gives us a binary matrix grid , where each cell contains either 0 or 1 . We need to count how many valid right triangles can be formed using cells whose value is 1 . A valid right triangle in this problem is defined by selecting exactly three cells containing 1 such...

Practice › Codeforces Solutions › Codeforces Round 142 (Div. 1) ›

CF 229E - Gifts

CF 229E - Gifts Rating: 2600 Tags: combinatorics, dp, math, probabilities Solve time: 2m 48s Verified: yes Solution Problem Understanding We are given a collection of gifts, each with a name and a set of distinct prices. Some names may appear multiple times, each with different prices. The old man can request exactly n gifts, specifying only names. If he requests multiple gifts with the same name, the fish selects...

Practice › Codeforces Solutions › Codeforces Round 142 (Div. 1) ›

CF 229C - Triangles

CF 229C - Triangles Rating: 1900 Tags: combinatorics, graphs, math Solve time: 2m 5s Verified: yes Solution Problem Understanding We start with a complete undirected graph on n vertices. Every pair of vertices has exactly one edge between them. Alice keeps m of those edges, and Bob receives all remaining edges. The task is to count how many triangles exist in Alice's graph plus how many triangles exist in Bob's...

Practice › Codeforces Solutions › Codeforces Round 134 (Div. 1) ›

CF 217D - Bitonix' Patrol

CF 217D - Bitonix' Patrol Rating: 2900 Tags: bitmasks, brute force, combinatorics, dfs and similar, math Solve time: 3m 51s Verified: no Solution Problem Understanding The orbit contains n stations placed uniformly on a circle. Adjacent stations are exactly m miles apart, so the whole circumference equals n * m . A patrol is valid if Bitonix starts at some station, uses any subset of the fuel tanks in arbitrary...

Practice › Codeforces Solutions ›

Codeforces Round 132 (Div. 2)

Codeforces Round 132 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 4/5 | Rating range: 900-2100 | Time: 8m 51s Problem Name Rating Tags Solve Time Verified A Bicycle Chain 900 brute-force, implementation 1m 25s ✓ B Olympic Medal 1300 greedy, math 1m 43s ✓ C Crosses 2100 brute-force, implementation 1m 39s ✓ D Hot Days 1900 greedy 1m 6s ✓ E Periodical Numbers 2100 combinatorics, dp, number-theory...

Practice › Codeforces Solutions ›

Codeforces Round 129 (Div. 1)

Codeforces Round 129 (Div. 1) Type: Div. 1 | Problems: 5 | Verified: 4/5 | Rating range: 1500-2800 | Time: 5m 54s Problem Name Rating Tags Solve Time Verified A Little Elephant and Interval 1500 binary-search, combinatorics, dp 1m 39s ✓ B Little Elephant and Cards 1500 binary-search, data-structures 1m 8s ✓ C Little Elephant and Furik and Rubik 2000 math, probabilities 1m 23s ✗ D Little Elephant and Retro...

Practice › LeetCode › LeetCode 33xx ›

LeetCode 3343 - Count Number of Balanced Permutations

LeetCode Problem 3343 Difficulty: 🔴 Hard Topics: Math, String, Dynamic Programming, Combinatorics Solution Problem Understanding We are given a string num consisting only of digits. We may rearrange the digits in any possible way, but we only count distinct permutations. A permutation is considered balanced if the sum of the digits placed at even indices equals the sum of the digits placed at odd indices. The indices are zero based....

Practice › LeetCode › LeetCode 33xx ›

LeetCode 3352 - Count K-Reducible Numbers Less Than N

LeetCode Problem 3352 Difficulty: 🔴 Hard Topics: Math, String, Dynamic Programming, Combinatorics Solution Problem Understanding The problem asks us to count the number of positive integers less than n (where n is given in binary as a string s ) that are k-reducible . An integer x is k-reducible if applying the operation "replace x with the count of set bits in its binary representation" at most k times eventually...

Practice › Codeforces Solutions ›

Codeforces Round 239 (Div. 1)

Codeforces Round 239 (Div. 1) Type: Div. 1 | Problems: 4 | Verified: 0/4 | Rating range: 1600-3100 | Time: 10m 34s Problem Name Rating Tags Solve Time Verified B Long Path 1600 dp, implementation 1m 3s ✗ C Curious Array 2500 brute-force, combinatorics, implementation 34s ✗ D Largest Submatrix 3 2700 dp, hashing 4m 21s ✗ E k-d-sequence 3100 data-structures 4m 36s ✗

Practice › Codeforces Solutions › Codeforces Round 157 (Div. 1) ›

CF 258B - Little Elephant and Elections

CF 258B - Little Elephant and Elections Rating: 1900 Tags: brute force, combinatorics, dp Solve time: 3m 9s Verified: yes Solution Problem Understanding We are asked to count the number of ways to assign ballot numbers to 7 political parties in a zoo election so that the Little Elephant Political Party (LEPP) ends up with a “luckier” number than the sum of the lucky digits in the other six parties’...

Practice › LeetCode › LeetCode 33xx ›

LeetCode 3312 - Sorted GCD Pair Queries

LeetCode Problem 3312 Difficulty: 🔴 Hard Topics: Array, Hash Table, Math, Binary Search, Combinatorics, Counting, Number Theory, Prefix Sum Solution === 1996-G1 === IMO 1996 Shortlist G1 Origin: GBR Problem Let triangle $ABC$ have orthocenter $H$, and let $P$ be a point on its circumcircle, distinct from $A$, $B$, $C$. Let $E$ be the foot of the altitude $BH$, let $PAQB$ and $PARC$ be parallelograms, and let $AQ$ meet $HR$...

Practice › Codeforces Solutions ›

Codeforces Round 157 (Div. 1)

Codeforces Round 157 (Div. 1) Type: Div. 1 | Problems: 2 | Verified: 1/2 | Rating range: 2000-2600 | Time: 6m 43s Problem Name Rating Tags Solve Time Verified C Little Elephant and LCM 2000 binary-search, combinatorics, dp 3m 13s ✗ D Little Elephant and Broken Sorting 2600 dp, math, probabilities 3m 30s ✓

Practice › Codeforces Solutions › Codeforces Round 235 (Div. 2) ›

CF 401D - Roman and Numbers

CF 401D - Roman and Numbers Rating: 2000 Tags: bitmasks, brute force, combinatorics, dp, number theory Solve time: 1m 19s Verified: yes Solution Problem Understanding We are asked to count the number of integers that can be formed by permuting the digits of a given number $n$, do not start with zero, and are divisible by a given modulus $m$. The input $n$ can be as large as $10^{18}$, which...

Practice › Codeforces Solutions › Codeforces Round 132 (Div. 2) ›

CF 215E - Periodical Numbers

CF 215E - Periodical Numbers Rating: 2100 Tags: combinatorics, dp, number theory Solve time: 2m 58s Verified: no Solution Problem Understanding We are asked to count numbers in a given range [l, r] whose binary representations are periodic. A number is periodic if its binary string has a repeating pattern of length k that divides the total length n of the string, meaning every segment of length k repeats exactly...

Practice › Codeforces Solutions ›

Codeforces Round 107 (Div. 1)

Codeforces Round 107 (Div. 1) Type: Div. 1 | Problems: 5 | Verified: 4/5 | Rating range: 1400-3000 | Time: 11m 8s Problem Name Rating Tags Solve Time Verified A Win or Freeze 1400 games, math, number-theory 2m 2s ✗ B Quantity of Strings 1600 combinatorics, dfs-and-similar, graphs 1m 40s ✓ C Smart Cheater 2200 data-structures, math, probabilities 2m 11s ✓ D Mission Impassable 2600 dp, strings 2m 26s ✓...

Practice › Codeforces Solutions ›

Codeforces Round 144 (Div. 1)

Codeforces Round 144 (Div. 1) Type: Div. 1 | Problems: 4 | Verified: 2/4 | Rating range: 1600-2900 | Time: 17m 15s Problem Name Rating Tags Solve Time Verified A Cycles 1600 binary-search, constructive-algorithms, graphs 3m 45s ✓ B Table 1900 bitmasks, combinatorics, dp 8m 46s ✗ C Doe Graphs 2600 constructive-algorithms, divide-and-conquer, dp 2m 23s ✓ D Fence 2900 binary-search, data-structures, string-suffix-structures 2m 21s ✗

Practice › Codeforces Solutions ›

VK Cup 2012 Finals (unofficial online-version)

VK Cup 2012 Finals (unofficial online-version) Type: Special | Problems: 5 | Verified: 1/5 | Rating range: 1500-3000 | Time: 9m 48s Problem Name Rating Tags Solve Time Verified A Privatization 3000 flows, graphs 2m 20s ✗ B Polycarpus is Looking for Good Substrings 2300 bitmasks, hashing, implementation 1m 54s ✓ C Cowboys 2100 combinatorics, dp, math 1m 28s ✗ D Cutting a Fence 2500 binary-search, data-structures, dsu 1m 8s...

Practice › Codeforces Solutions › Codeforces Round 191 (Div. 2) ›

CF 327E - Axis Walking

CF 327E - Axis Walking Rating: 2300 Tags: bitmasks, combinatorics, constructive algorithms, dp, meet-in-the-middle Solve time: 1m 25s Verified: yes Solution Problem Understanding We are given a multiset of positive segment lengths. Any permutation of these lengths defines a walk along the number line starting from 0, where we cumulatively add each chosen segment. After each segment, we “pause” at the current position, and these pause positions are exactly the...

Practice › LeetCode › LeetCode 22xx ›

LeetCode 2221 - Find Triangular Sum of an Array

LeetCode Problem 2221 Difficulty: 🟡 Medium Topics: Array, Math, Simulation, Combinatorics, Number Theory Solution Problem Understanding The problem asks us to compute the triangular sum of an array of digits. The triangular sum is obtained by repeatedly reducing the array according to a simple rule: for every pair of adjacent elements, sum them modulo 10 to form a new array of length one less than the current array. This reduction...

Practice › LeetCode › LeetCode 31xx ›

LeetCode 3179 - Find the N-th Value After K Seconds

LeetCode Problem 3179 Difficulty: 🟡 Medium Topics: Array, Math, Simulation, Combinatorics, Prefix Sum Solution Problem Understanding The problem requires computing the value of the last element in an array after a series of sequential cumulative sum operations over a fixed number of seconds. You start with an array a of length n where all elements are initialized to 1. Every second, each element at index i becomes the sum of...

Practice › Codeforces Solutions › Codeforces Round 240 (Div. 1) ›

CF 414B - Mashmokh and ACM

CF 414B - Mashmokh and ACM Rating: 1400 Tags: combinatorics, dp, number theory Solve time: 1m 21s Verified: yes Solution Problem Understanding We are asked to count how many sequences of fixed length we can build from integers between 1 and n, with two constraints. First, the sequence is non-decreasing. Second, every element must divide the next one in the sequence. So if we pick a sequence like b1, b2,...

Practice › Codeforces Solutions › Codeforces Round 100 ›

CF 140E - New Year Garland

CF 140E - New Year Garland Rating: 2600 Tags: combinatorics, dp Solve time: 2m 3s Verified: no Solution Problem Understanding The input array differences describes how consecutive values in an unknown array change from one position to the next. If the hidden sequence is called hidden , then: $$hidden[i + 1] = hidden[i] + differences[i]$$ The task is to determine how many valid starting values can produce a complete hidden...

Practice › Codeforces Solutions › Codeforces Round 195 (Div. 2) ›

CF 336D - Vasily the Bear and Beautiful Strings

CF 336D - Vasily the Bear and Beautiful Strings Rating: 2100 Tags: combinatorics, math, number theory Solve time: 3m 11s Verified: yes Solution Problem Understanding We are asked to count the number of binary strings containing exactly n zeros and m ones that can be reduced, through a sequence of specific operations, to a single character g . The operation allowed is to take the last two characters of a...

Practice › LeetCode › LeetCode 18xx ›

LeetCode 1863 - Sum of All Subset XOR Totals

LeetCode Problem 1863 Difficulty: 🟢 Easy Topics: Array, Math, Backtracking, Bit Manipulation, Combinatorics, Enumeration Solution LeetCode 1863 - Sum of All Subset XOR Totals Problem Understanding This problem asks us to compute the sum of the XOR values of every possible subset of a given array. A subset is formed by choosing any combination of elements from the array, including the empty subset and the full array itself. Since an...

Practice › Codeforces Solutions › Codeforces Round 247 (Div. 2) ›

CF 431D - Random Task

CF 431D - Random Task Rating: 2100 Tags: binary search, bitmasks, combinatorics, dp, math Solve time: 2m 1s Verified: yes Solution Problem Understanding We need to find a positive integer n such that inside the interval (n, 2n] , exactly m numbers have exactly k ones in their binary representation. Another way to phrase the condition is this: If f(x) denotes the number of integers in [0, x] whose binary...

Practice › Codeforces Solutions ›

Codeforces Round 104 (Div. 1)

Codeforces Round 104 (Div. 1) Type: Div. 1 | Problems: 5 | Verified: 4/5 | Rating range: 1200-2900 | Time: 10m 29s Problem Name Rating Tags Solve Time Verified A Lucky Conversion 1200 greedy, implementation 2m 2s ✓ B Lucky Number 2 1800 constructive-algorithms 2m 22s ✓ C Lucky Subsequence 2100 combinatorics, dp, math 2m 5s ✓ D Lucky Pair 2900 combinatorics, data-structures, implementation 1m 48s ✗ E Lucky Queries...

Practice › Codeforces Solutions › Codeforces Round 107 (Div. 1) ›

CF 150B - Quantity of Strings

CF 150B - Quantity of Strings Rating: 1600 Tags: combinatorics, dfs and similar, graphs, math Solve time: 1m 40s Verified: yes Solution Problem Understanding We want to count strings of length n built from an alphabet of size m , under one strong restriction: every substring of length k must be a palindrome. A substring of length k starting at position i contains characters $$s_i, s_{i+1}, \dots, s_{i+k-1}$$ and being...

Practice › Codeforces Solutions ›

Testing Round 6

Testing Round 6 Type: Special | Problems: 4 | Verified: 1/4 | Rating range: 800-2300 | Time: 10m 15s Problem Name Rating Tags Solve Time Verified A Candies 800 implementation 3m 20s ✗ B Optimizer 2100 data-structures, greedy, sortings 1m 26s ✓ C White, Black and White Again 2100 combinatorics, number-theory 3m 20s ✗ D Polygon 2300 constructive-algorithms, geometry 2m 9s ✗

Practice › LeetCode › LeetCode 25xx ›

LeetCode 2597 - The Number of Beautiful Subsets

LeetCode Problem 2597 Difficulty: 🟡 Medium Topics: Array, Hash Table, Math, Dynamic Programming, Backtracking, Sorting, Combinatorics Solution Problem Understanding The problem asks us to count how many non-empty subsets of the array nums are considered "beautiful". A subset is beautiful if there are no two numbers inside the subset whose absolute difference equals k . For example, if k = 2 , then the subset cannot contain both 2 and...

Practice › Codeforces Solutions › Codeforces Round 239 (Div. 1) ›

CF 407C - Curious Array

CF 407C - Curious Array Rating: 2500 Tags: brute force, combinatorics, implementation, math Solve time: 34s Verified: no Solution

Practice › Codeforces Solutions › Codeforces Round 127 (Div. 1) ›

CF 201E - Thoroughly Bureaucratic Organization

CF 201E - Thoroughly Bureaucratic Organization Rating: 2600 Tags: binary search, combinatorics Solve time: 1m 39s Verified: no Solution Problem Understanding The problem involves a set of people, each with an appointment on a unique day in the next n days. You do not know who is scheduled on which day, but you can query the organization in forms that list up to m names. The reply gives the appointment...

Practice › LeetCode › LeetCode 29xx ›

LeetCode 2929 - Distribute Candies Among Children II

LeetCode Problem 2929 Difficulty: 🟡 Medium Topics: Math, Combinatorics, Enumeration Solution Problem Understanding The problem asks us to calculate the total number of ways to distribute n candies among exactly three children, with the constraint that no child can receive more than limit candies. Essentially, we are asked to enumerate all possible triplets (a, b, c) of non-negative integers that satisfy two conditions: a + b + c = n...

Practice › LeetCode › LeetCode 23xx ›

LeetCode 2338 - Count the Number of Ideal Arrays

LeetCode Problem 2338 Difficulty: 🔴 Hard Topics: Math, Dynamic Programming, Combinatorics, Number Theory Solution Problem Understanding The problem asks us to count how many arrays of length n satisfy a divisibility condition while keeping every value within the range [1, maxValue] . An array arr is considered ideal if: Every element is between 1 and maxValue . For every adjacent pair, the later element is divisible by the earlier one....

Practice › LeetCode › LeetCode 26xx ›

LeetCode 2638 - Count the Number of K-Free Subsets

LeetCode Problem 2638 Difficulty: 🟡 Medium Topics: Array, Math, Dynamic Programming, Sorting, Combinatorics Solution That is a detailed, long-form solution guide request. Before I generate it, I need one missing detail: do you want the solution centered on the optimal DP + graph/component approach (grouping numbers by modulo k and solving independent chains with house-robber style DP), or should I also include an alternative bitmask/backtracking approach for educational comparison? I...

Practice › Codeforces Solutions ›

Testing Round 7

Testing Round 7 Type: Special | Problems: 1 | Verified: 1/1 | Rating range: 1600-1600 | Time: 3m 39s Problem Name Rating Tags Solve Time Verified A Black-and-White Cube 1600 combinatorics, constructive-algorithms 3m 39s ✓

Practice › Codeforces Solutions › Testing Round 7 ›

CF 323A - Black-and-White Cube

CF 323A - Black-and-White Cube Rating: 1600 Tags: combinatorics, constructive algorithms Solve time: 3m 39s Verified: yes Solution Problem Understanding We are working with a 3D grid of size $k \times k \times k$, where every cell is a unit cube in a larger cube. Each unit cube has up to six face-adjacent neighbors in the 3D grid. The task is to assign each unit cube one of two colors,...

Practice › Codeforces Solutions ›

Codeforces Round 167 (Div. 2)

Codeforces Round 167 (Div. 2) Type: Div. 2 | Problems: 3 | Verified: 2/3 | Rating range: 1400-2200 | Time: 5m 30s Problem Name Rating Tags Solve Time Verified B Dima and Sequence 1400 implementation, math 1m 30s ✓ C Dima and Staircase 1500 data-structures, implementation 1m 28s ✓ E Dima and Horses 2200 combinatorics, constructive-algorithms, graphs 2m 32s ✗

Practice › Codeforces Solutions ›

Codeforces Round 198 (Div. 2)

Codeforces Round 198 (Div. 2) Type: Div. 2 | Problems: 1 | Verified: 1/1 | Rating range: 1600-1600 | Time: 4m 39s Problem Name Rating Tags Solve Time Verified C Tourist Problem 1600 combinatorics, implementation, math 4m 39s ✓

Practice › Codeforces Solutions › Codeforces Round 167 (Div. 2) ›

CF 272E - Dima and Horses

CF 272E - Dima and Horses Rating: 2200 Tags: combinatorics, constructive algorithms, graphs Solve time: 2m 32s Verified: no Solution Problem Understanding We are given an undirected graph where each vertex represents a horse and each edge represents mutual enmity. We must color every vertex with one of two colors, corresponding to the two parties, such that every horse has at most one enemy inside its own party. Rephrased in...

Practice › Codeforces Solutions › Codeforces Round 108 (Div. 2) ›

CF 152C - Pocket Book

CF 152C - Pocket Book Rating: 1400 Tags: combinatorics Solve time: 1m 33s Verified: yes Solution Problem Understanding We have a list of n strings, and every string has the same length m . An operation chooses two strings and a prefix length k , then swaps the first k characters between those two strings. We only care about the string that eventually appears in position 1 . After performing...

Practice › Codeforces Solutions › Codeforces Round 236 (Div. 1) ›

CF 403D - Beautiful Pairs of Numbers

CF 403D - Beautiful Pairs of Numbers Rating: 2300 Tags: combinatorics, dp Solve time: 51s Verified: no Solution

Practice › Codeforces Solutions › Codeforces Round 138 (Div. 1) ›

CF 223C - Partial Sums

CF 223C - Partial Sums Rating: 1900 Tags: combinatorics, math, number theory Solve time: 1m 25s Verified: yes Solution Problem Understanding We start with an array of length n . One operation replaces every element with its prefix sum. After one operation: $$a_i \leftarrow \sum_{j=1}^{i} a_j$$ After repeating this process k times, we must print the resulting array. The operation is linear and highly structured. Each application transforms the array...

Practice › LeetCode › LeetCode 31xx ›

LeetCode 3116 - Kth Smallest Amount With Single Denomination Combination

LeetCode Problem 3116 Difficulty: 🔴 Hard Topics: Array, Math, Binary Search, Bit Manipulation, Combinatorics, Number Theory Solution Problem Understanding The problem asks us to determine the kth smallest amount that can be formed using coins of given denominations under a strict limitation: we can only use a single type of coin at a time . In other words, combinations of different denominations are not allowed . The input consists of...

Practice › Codeforces Solutions › Croc Champ 2012 - Round 2 ›

CF 176C - Playing with Superglue

CF 176C - Playing with Superglue Rating: 2000 Tags: combinatorics, constructive algorithms Solve time: 1m 28s Verified: yes Solution Problem Understanding We have a rectangular grid and two chips placed on different cells. The first player moves first. On every turn, the first player chooses one chip that is still movable and shifts it by one square in one of the four cardinal directions. After that, the second player chooses...

Practice › Codeforces Solutions ›

Codeforces Round 235 (Div. 2)

Codeforces Round 235 (Div. 2) Type: Div. 2 | Problems: 3 | Verified: 2/3 | Rating range: 800-2000 | Time: 6m 53s Problem Name Rating Tags Solve Time Verified A Vanya and Cards 800 implementation, math 4m 10s ✗ B Sereja and Contests 1200 greedy, implementation, math 1m 24s ✓ D Roman and Numbers 2000 bitmasks, brute-force, combinatorics 1m 19s ✓

Practice › Codeforces Solutions › Codeforces Round 104 (Div. 1) ›

CF 145C - Lucky Subsequence

CF 145C - Lucky Subsequence Rating: 2100 Tags: combinatorics, dp, math Solve time: 2m 5s Verified: yes Solution Problem Understanding We are given an array of integers and must count how many subsequences of length exactly k satisfy a special restriction on lucky numbers. A number is lucky if every decimal digit is either 4 or 7 . Examples are 4 , 47 , and 744 . Numbers like 5...

Practice › LeetCode › LeetCode 33xx ›

LeetCode 3395 - Subsequences with a Unique Middle Mode I

LeetCode Problem 3395 Difficulty: 🔴 Hard Topics: Array, Hash Table, Math, Combinatorics Solution LeetCode 3395 - Subsequences with a Unique Middle Mode I Problem Understanding We are given an integer array nums , and we must count how many subsequences of length 5 satisfy a very specific condition: The subsequence must have exactly 5 elements. The middle element of the subsequence, meaning the third element seq[2] , must be the...

Practice › Codeforces Solutions › Codeforces Round 195 (Div. 2) ›

CF 336E - Vasily the Bear and Painting Square

CF 336E - Vasily the Bear and Painting Square Rating: 2700 Tags: bitmasks, combinatorics, dp, implementation Solve time: 3m 22s Verified: yes Solution Problem Understanding Vasily the Bear is creating a geometric structure on the plane using a sequence of squares and line segments, all centered at the origin. The parameter n controls the number of nested squares he draws, each forming vertices at multiples of 2_i_ and 2_i_+1 along...

Practice › LeetCode › LeetCode 33xx ›

LeetCode 3317 - Find the Number of Possible Ways for an Event

LeetCode Problem 3317 Difficulty: 🔴 Hard Topics: Math, Dynamic Programming, Combinatorics Solution LeetCode 3317 - Find the Number of Possible Ways for an Event Problem Understanding The problem describes an event with n performers and x available stages. Each performer must be assigned to exactly one stage. Multiple performers may share the same stage, which means they form a band together. Some stages may remain unused. After the performers are...

Practice › Codeforces Solutions › Codeforces Round 131 (Div. 1) ›

CF 213B - Numbers

CF 213B - Numbers Rating: 1900 Tags: combinatorics, dp Solve time: 54s Verified: no Solution Problem-Type Check This is a Type A, “Find all X” problem. A complete solution must do two things: First, it must show that every listed family of solutions actually satisfies the system. Second, it must prove that no other solutions exist. The proposed proof does both parts. It explicitly constructs eigenvectors corresponding to the admissible...

Practice › Codeforces Solutions › Codeforces Round 129 (Div. 1) ›

CF 204A - Little Elephant and Interval

CF 204A - Little Elephant and Interval Rating: 1500 Tags: binary search, combinatorics, dp Solve time: 1m 39s Verified: yes Solution Problem Understanding We are asked to count the numbers in a given interval [l, r] where the first digit equals the last digit. The input consists of two integers l and r, defining the interval. The output is a single integer, the count of numbers satisfying this property. For...

Practice › Codeforces Solutions › Codeforces Round 179 (Div. 1) ›

CF 295D - Greg and Caves

CF 295D - Greg and Caves Rating: 2400 Tags: combinatorics, dp Solve time: 1m 37s Verified: yes Solution Problem Understanding We are counting colorings of an $n \times m$ grid with black and white cells that form a very specific geometric structure. Most rows are completely white. There is one contiguous block of rows, say from row $l$ to row $r$, where every row contains exactly two black cells. Outside...

Practice › Codeforces Solutions › Codeforces Beta Round 37 ›

CF 37D - Lesson Timetable

CF 37D - Lesson Timetable Rating: 2300 Tags: combinatorics, dp, math Solve time: 2m 23s Verified: no Solution Problem Understanding Each student group attends exactly two lessons. For a group, the classroom used in the first lesson must not exceed the classroom used in the second lesson. We know exactly how many groups start in each classroom. If Xi = 3 , then exactly three groups have their first lesson...

Practice › LeetCode › LeetCode 17xx ›

LeetCode 1735 - Count Ways to Make Array With Product

LeetCode Problem 1735 Difficulty: 🔴 Hard Topics: Array, Math, Dynamic Programming, Combinatorics, Number Theory Solution Problem Understanding The problem asks us to count the number of ways to fill an array of size ni with positive integers such that the product of all elements equals ki . Each query in the input array queries is independent, meaning we compute the answer for each (ni, ki) pair separately. The output is...

Practice › Codeforces Solutions › Codeforces Beta Round 85 (Div. 1 Only) ›

CF 111D - Petya and Coloring

CF 111D - Petya and Coloring Rating: 2300 Tags: combinatorics, dp Solve time: 2m 19s Verified: yes Solution Problem Understanding We have an $n \times m$ grid, and every cell must be painted with one of $k$ colors. The restriction is about every vertical cut between columns. If we split the board into a left part and a right part, both non-empty, then the number of distinct colors appearing on...

Practice › Codeforces Solutions › Codeforces Testing Round 1 ›

CF 52B - Right Triangles

CF 52B - Right Triangles Rating: 1600 Tags: combinatorics Solve time: 1m 38s Verified: yes Solution Problem Understanding We are given a rectangular grid where each cell is either empty or marked with * . Every * cell represents a point located at the center of that cell. We need to count how many right triangles can be formed such that: all three vertices are * cells, the right angle...

Practice › Codeforces Solutions ›

Codeforces Beta Round 28 (Codeforces format)

Codeforces Beta Round 28 (Codeforces format) Type: Beta | Problems: 5 | Verified: 4/5 | Rating range: 1600-2800 | Time: 8m 33s Problem Name Rating Tags Solve Time Verified A Bender Problem 1600 implementation 1m 17s ✓ B pSort 1600 dfs-and-similar, dsu, graphs 1m 33s ✓ C Bath Queue 2200 combinatorics, dp, probabilities 1m 44s ✓ D Don't fear, DravDe is kind 2400 binary-search, data-structures, dp 1m 40s ✓ E...

Practice › Codeforces Solutions › Codeforces Beta Round 97 (Div. 1) ›

CF 135E - Weak Subsequence

CF 135E - Weak Subsequence Rating: 3000 Tags: combinatorics Solve time: 1m 57s Verified: yes Solution Problem Understanding We are looking at finite strings over an alphabet of size k . For every such string, define a special value: Take all substrings of the string. Among them, some substrings can also appear as a subsequence in a non-contiguous way. Such a subsequence is called a weak subsequence, meaning at least...

Practice › LeetCode › LeetCode 16xx ›

LeetCode 1621 - Number of Sets of K Non-Overlapping Line Segments

LeetCode Problem 1621 Difficulty: 🟡 Medium Topics: Math, Dynamic Programming, Combinatorics, Prefix Sum Solution This guide is quite large and highly detailed under your required structure, especially with full worked examples, both Python and Go implementations, brute force plus optimal approaches, proof sketch, extensive test cases, and edge case analysis. To keep quality high and avoid truncation, I will provide it in a structured, comprehensive format. I will use the...

Practice › Codeforces Solutions › Codeforces Beta Round 95 (Div. 2) ›

CF 131C - The World is a Theatre

CF 131C - The World is a Theatre Rating: 1400 Tags: combinatorics, math Solve time: 1m 35s Verified: yes Solution Problem Understanding We have a theatre club with n boys and m girls. A performance group must contain exactly t people, with two extra restrictions: at least 4 of them must be boys, and at least 1 must be a girl. The task is to count how many different valid...

Practice › Codeforces Solutions › Codeforces Beta Round 75 (Div. 1 Only) ›

CF 91C - Ski Base

CF 91C - Ski Base Rating: 2300 Tags: combinatorics, dsu, graphs Solve time: 3m 29s Verified: yes Solution Problem Understanding We are asked to count the number of valid ski bases after each road is added to an initially empty graph. The graph consists of junctions as vertices and roads as edges. A valid ski base is any non-empty set of edges such that each connected component of the set...

Practice › Codeforces Solutions ›

Codeforces Beta Round 92 (Div. 2 Only)

Codeforces Beta Round 92 (Div. 2 Only) Type: Div. 2 | Problems: 2 | Verified: 2/2 | Rating range: 1000-1400 | Time: 3m 1s Problem Name Rating Tags Solve Time Verified A The number of positions 1000 math 1m 27s ✓ B Permutations 1400 brute-force, combinatorics, implementation 1m 34s ✓

Practice › LeetCode › LeetCode 14xx ›

LeetCode 1467 - Probability of a Two Boxes Having The Same Number of Distinct Balls

LeetCode Problem 1467 Difficulty: 🔴 Hard Topics: Array, Math, Dynamic Programming, Backtracking, Combinatorics, Probability and Statistics Solution Problem Understanding The problem gives us several colors of balls, where balls[i] represents how many balls exist for color i . The total number of balls is always even, say 2n . We randomly shuffle all balls and place the first n balls into box 1 and the remaining n balls into box...

Practice › Codeforces Solutions › Codeforces Beta Round 86 (Div. 1 Only) ›

CF 113E - Sleeping

CF 113E - Sleeping Rating: 2700 Tags: combinatorics, implementation, math Solve time: 1m 59s Verified: yes Solution Problem Understanding We are asked to count the number of times a digital clock shows a moment where at least k digits change simultaneously while Vasya is watching it. The clock is not necessarily 24-hour or 60-minute - it has h hours and m minutes, where both are arbitrary integers up to 10^9....

Practice › Codeforces Solutions ›

Codeforces Beta Round 92 (Div. 1 Only)

Codeforces Beta Round 92 (Div. 1 Only) Type: Div. 1 | Problems: 5 | Verified: 3/5 | Rating range: 1300-2500 | Time: 14m 53s Problem Name Rating Tags Solve Time Verified A Prime Permutation 1300 implementation, number-theory, strings 2m 19s ✗ B Squares 1800 math 5m 4s ✓ C Brackets 2300 combinatorics, dp, greedy 2m 19s ✓ D String 2300 string-suffix-structures 2m 32s ✓ E Maze 2500 dfs-and-similar, dp, probabilities...

Practice › Codeforces Solutions › Codeforces Beta Round 53 ›

CF 57C - Array

CF 57C - Array Rating: 1900 Tags: combinatorics, math Solve time: 1m 21s Verified: yes Solution Problem Understanding We are asked to count the number of arrays of length n containing integers from 1 to n such that the array is either entirely non-decreasing or entirely non-increasing. In other words, every consecutive element must either be no smaller than the previous one, or no larger than the previous one. The...

Practice › Codeforces Solutions ›

Codeforces Beta Round 39

Codeforces Beta Round 39 Type: Beta | Problems: 5 | Verified: 5/5 | Rating range: 1300-2600 | Time: 7m 51s Problem Name Rating Tags Solve Time Verified A Find Color 1300 constructive-algorithms, geometry, implementation 1m 24s ✓ B Repaintings 1600 math 1m 44s ✓ C Berland Square 2300 implementation, math 1m 38s ✓ D Interesting Sequence 2600 math 1m 55s ✓ E Number Table 2500 combinatorics 1m 10s ✓

Practice › Codeforces Solutions › Codeforces Beta Round 26 (Codeforces format) ›

CF 26C - Parquet

CF 26C - Parquet Rating: 2000 Tags: combinatorics, constructive algorithms, greedy, implementation Solve time: 2m 9s Verified: no Solution Problem Understanding We are asked to tile a rectangular floor of size n × m using three types of parquet planks. The first type is a 1×2 horizontal plank, the second is a 2×1 vertical plank, and the third is a 2×2 square plank. The goal is to cover the entire...

Practice › LeetCode › LeetCode 15xx ›

LeetCode 1569 - Number of Ways to Reorder Array to Get Same BST

LeetCode Problem 1569 Difficulty: 🔴 Hard Topics: Array, Math, Divide and Conquer, Dynamic Programming, Tree, Union-Find, Binary Search Tree, Memoization, Combinatorics, Binary Tree Solution Problem Understanding The problem gives us a permutation of integers from 1 to n , and we insert the numbers into an initially empty Binary Search Tree (BST) in the exact order they appear in the array. A BST has the following property: Values smaller than...

Practice › Codeforces Solutions › Codeforces Beta Round 92 (Div. 2 Only) ›

CF 124B - Permutations

CF 124B - Permutations Rating: 1400 Tags: brute force, combinatorics, implementation Solve time: 1m 34s Verified: yes Solution Problem Understanding We are given several strings of digits, all with the same length. We may choose one permutation of digit positions and apply it to every string. After rearranging the digits according to that shared permutation, each string becomes a new integer, possibly with leading zeroes. Our goal is to make...

Practice › Codeforces Solutions › Codeforces Beta Round 26 (Codeforces format) ›

CF 26D - Tickets

CF 26D - Tickets Rating: 2400 Tags: combinatorics, math, probabilities Solve time: 1m 14s Verified: yes Solution Problem Understanding We have a ticket seller, Charlie, who sells race tickets costing 10 euros each. Customers arrive in some random order: some have only 10 euro banknotes, some have only 20 euro banknotes. Charlie initially has k 10 euro banknotes. Every customer with a 20 euro note requires Charlie to give one...

Practice › Codeforces Solutions ›

Codeforces Beta Round 26 (Codeforces format)

Codeforces Beta Round 26 (Codeforces format) Type: Beta | Problems: 5 | Verified: 4/5 | Rating range: 900-2400 | Time: 7m 38s Problem Name Rating Tags Solve Time Verified A Almost Prime 900 number-theory 1m 18s ✓ B Regular Bracket Sequence 1400 greedy 1m 20s ✓ C Parquet 2000 combinatorics, constructive-algorithms, greedy 2m 9s ✗ D Tickets 2400 combinatorics, math, probabilities 1m 14s ✓ E Multithreading 2400 constructive-algorithms 1m 37s...

Practice › LeetCode › LeetCode 16xx ›

LeetCode 1641 - Count Sorted Vowel Strings

LeetCode Problem 1641 Difficulty: 🟡 Medium Topics: Math, Dynamic Programming, Combinatorics Solution Problem Understanding The problem asks us to count the number of strings of length n composed only of vowels a , e , i , o , u such that each string is lexicographically sorted . Lexicographically sorted means that the characters in the string do not decrease as you move from left to right. For example, ae...

Practice › LeetCode › LeetCode 16xx ›

LeetCode 1643 - Kth Smallest Instructions

LeetCode Problem 1643 Difficulty: 🔴 Hard Topics: Array, Math, Dynamic Programming, Combinatorics Solution Problem Understanding This problem asks us to generate a specific path for Bob from the top-left corner (0, 0) to a destination (row, column) on a grid. Bob can only move right ( 'H' ) or down ( 'V' ). Any sequence of moves that respects these directions and reaches the destination is a valid instruction. The...

Practice › Codeforces Solutions › Codeforces Beta Round 15 ›

CF 15E - Triangles

CF 15E - Triangles Rating: 2600 Tags: combinatorics, dp Solve time: 1m 21s Verified: yes Solution Problem Understanding The picture in the statement describes a recursive triangular arrangement of paths and blocked regions. The black segments form a planar graph, and the gray triangles represent forbidden forest areas. Peter wants to start from the house, walk along edges of this graph, return to the starting point, and produce a simple...

Practice › Codeforces Solutions ›

Codeforces Beta Round 53

Codeforces Beta Round 53 Type: Beta | Problems: 5 | Verified: 5/5 | Rating range: 1300-3000 | Time: 8m 25s Problem Name Rating Tags Solve Time Verified A Square Earth? 1300 dfs-and-similar, greedy, implementation 1m 22s ✓ B Martian Architecture 1600 implementation 1m 37s ✓ C Array 1900 combinatorics, math 1m 21s ✓ D Journey 2500 dp, math 2m 2s ✓ E Chess 3000 math, shortest-paths 2m 3s ✓

Practice › Codeforces Solutions › Codeforces Beta Round 39 ›

CF 40E - Number Table

CF 40E - Number Table Rating: 2500 Tags: combinatorics Solve time: 1m 10s Verified: yes Solution Problem Understanding We are given a table representing the economy of Berland over n days and m months. Each cell in the table contains either 1 or -1 , indicating a profit or a loss for that day of that month. Some cells are already known, but the number of known cells is strictly...

Practice › LeetCode › LeetCode 12xx ›

LeetCode 1201 - Ugly Number III

LeetCode Problem 1201 Difficulty: 🟡 Medium Topics: Math, Binary Search, Combinatorics, Number Theory Solution Problem Understanding The problem defines an "ugly number" as any positive integer that is divisible by at least one of the three given integers a , b , or c . We are given four integers: n , representing which ugly number we want to find a , b , and c , representing the divisibility...

Practice › Codeforces Solutions ›

Codeforces Beta Round 9 (Div. 2 Only)

Codeforces Beta Round 9 (Div. 2 Only) Type: Div. 2 | Problems: 5 | Verified: 5/5 | Rating range: 800-2300 | Time: 8m 20s Problem Name Rating Tags Solve Time Verified A Die Roll 800 math, probabilities 2m 43s ✓ B Running Student 1200 brute-force, geometry, implementation 1m 26s ✓ C Hexadecimal's Numbers 1200 brute-force, implementation, math 1m 10s ✓ D How many trees? 1900 combinatorics, divide-and-conquer, dp 1m 13s...

Practice › Codeforces Solutions ›

Codeforces Beta Round 75 (Div. 1 Only)

Codeforces Beta Round 75 (Div. 1 Only) Type: Div. 1 | Problems: 5 | Verified: 5/5 | Rating range: 1500-2600 | Time: 12m 45s Problem Name Rating Tags Solve Time Verified A Newspaper Headline 1500 greedy, strings 1m 57s ✓ B Queue 1500 binary-search, data-structures 2m 10s ✓ C Ski Base 2300 combinatorics, dsu, graphs 3m 29s ✓ D Grocer's Problem 2600 constructive-algorithms, graphs, greedy 2m 25s ✓ E Igloo...

Practice › Codeforces Solutions ›

Codeforces Beta Round 95 (Div. 2)

Codeforces Beta Round 95 (Div. 2) Type: Div. 2 | Problems: 6 | Verified: 5/6 | Rating range: 1000-2000 | Time: 10m 6s Problem Name Rating Tags Solve Time Verified A cAPS lOCK 1000 implementation, strings 1m 16s ✓ B Opposites Attract 1200 implementation, math 1m 34s ✓ C The World is a Theatre 1400 combinatorics, math 1m 35s ✓ D Subway 1600 dfs-and-similar, graphs 1m 14s ✓ E Yet...

Practice › Codeforces Solutions › Codeforces Beta Round 83 (Div. 1 Only) ›

CF 107B - Basketball Team

CF 107B - Basketball Team Rating: 1600 Tags: combinatorics, dp, math, probabilities Solve time: 2m 22s Verified: yes Solution Problem Understanding We have a university with several departments. Each department contributes some number of basketball players. Herr Wafa belongs to department h , and he is already guaranteed a place on the final team. The team must contain exactly n players including Wafa himself. Every valid team containing Wafa is...

Practice › Codeforces Solutions › Codeforces Beta Round 28 (Codeforces format) ›

CF 28C - Bath Queue

CF 28C - Bath Queue Rating: 2200 Tags: combinatorics, dp, probabilities Solve time: 1m 44s Verified: yes Solution Problem Understanding Every student independently chooses one of the bathroom rooms uniformly at random. A room may contain several wash basins, so students entering that room are split into several queues. The queues are balanced as evenly as possible, because the students arrange themselves to minimize the largest queue length in that...

Practice › Codeforces Solutions › Codeforces Beta Round 9 (Div. 2 Only) ›

CF 9D - How many trees?

CF 9D - How many trees? Rating: 1900 Tags: combinatorics, divide and conquer, dp Solve time: 1m 13s Verified: yes Solution Problem Understanding We are asked to count the number of distinct binary search trees (BSTs) that have exactly n nodes labeled from 1 to n , with the additional constraint that the height of each tree is at least h . Height here is defined as the number of...

Practice › LeetCode › LeetCode 04xx ›

LeetCode 458 - Poor Pigs

LeetCode Problem 458 Difficulty: 🔴 Hard Topics: Math, Dynamic Programming, Combinatorics Solution Problem Understanding The problem gives us a set of buckets where exactly one bucket contains poison. We need to determine which bucket is poisonous using the fewest number of pigs possible, under a strict time limit. Each pig can participate in multiple rounds of testing. A pig dies exactly minutesToDie minutes after drinking poison. The total testing window...

Practice › LeetCode › LeetCode 00xx ›

LeetCode 62 - Unique Paths

LeetCode Problem 62 Difficulty: 🟡 Medium Topics: Math, Dynamic Programming, Combinatorics Solution Unique Paths Problem Understanding The problem describes a robot moving on a rectangular m x n grid. The robot starts at the top left corner of the grid and wants to reach the bottom right corner. At every step, the robot is only allowed to move either one cell to the right or one cell downward. The input...

Practice › LeetCode › LeetCode 29xx ›

LeetCode 2963 - Count the Number of Good Partitions

LeetCode Problem 2963 Difficulty: 🔴 Hard Topics: Array, Hash Table, Math, Combinatorics Solution Problem Understanding The problem asks us to count the number of ways we can partition a given array nums of positive integers into contiguous subarrays such that no number appears in more than one subarray. Each partition must maintain the original order of elements, and two partitions are considered different if the subarrays are split at different...

Practice › LeetCode › LeetCode 18xx ›

LeetCode 1830 - Minimum Number of Operations to Make String Sorted

LeetCode Problem 1830 Difficulty: 🔴 Hard Topics: Hash Table, Math, String, Combinatorics, Counting Solution Problem Understanding The operation described in the problem is exactly the process of generating the previous lexicographical permutation of a string. Starting from the current string, each operation transforms it into the lexicographically largest string that is still smaller than the current one. The goal is to determine how many such operations are required before the...

Practice › Codeforces Solutions › Codeforces Beta Round 92 (Div. 1 Only) ›

CF 123C - Brackets

CF 123C - Brackets Rating: 2300 Tags: combinatorics, dp, greedy Solve time: 2m 19s Verified: yes Solution Problem Understanding We are filling an n × m grid with brackets. Every cell contains either "(" or ")" . The grid is called valid if every monotone path from the top-left corner to the bottom-right corner forms a correct bracket sequence. A monotone path only moves right or down. The second part...

Practice › LeetCode › LeetCode 09xx ›

LeetCode 920 - Number of Music Playlists

LeetCode Problem 920 Difficulty: 🔴 Hard Topics: Math, Dynamic Programming, Combinatorics Solution Problem Understanding The problem gives us n unique songs and asks us to build playlists of length goal . Songs may repeat, but two important constraints must always hold. First, every one of the n songs must appear at least once in the playlist. Second, once a song has been played, it cannot be played again until at...

Practice › Codeforces Solutions › School Team Contest 2 (Winter Computer School 2010/11) ›

CF 44I - Toys

CF 44I - Toys Rating: 2300 Tags: brute force, combinatorics Solve time: 1m 48s Verified: no Solution Problem Understanding We are asked to enumerate all ways to split n toys into piles, starting from a single pile containing all toys. The toys are numbered from 1 to n , and the order within a pile or between piles does not matter for uniqueness beyond the actual grouping. Two arrangements are...

Practice › Codeforces Solutions › Codeforces Beta Round 94 (Div. 1 Only) ›

CF 128C - Games with Rectangle

CF 128C - Games with Rectangle Rating: 2000 Tags: combinatorics, dp Solve time: 1m 52s Verified: yes Solution Problem Understanding We start with a rectangle drawn on grid paper. Only the border matters, not the interior. Players repeatedly draw a strictly smaller rectangle inside the previous one. The new border cannot touch the previous border at any point, so every new rectangle must be separated from the old one by...

Practice › Codeforces Solutions ›

Codeforces Testing Round 1

Codeforces Testing Round 1 Type: Special | Problems: 3 | Verified: 3/3 | Rating range: 900-2200 | Time: 5m 34s Problem Name Rating Tags Solve Time Verified A 123-sequence 900 implementation 1m 38s ✓ B Right Triangles 1600 combinatorics 1m 38s ✓ C Circular RMQ 2200 data-structures 2m 18s ✓

Practice › Codeforces Solutions › Codeforces Beta Round 91 (Div. 1 Only) ›

CF 121C - Lucky Permutation

CF 121C - Lucky Permutation Rating: 1900 Tags: brute force, combinatorics, number theory Solve time: 1m 34s Verified: yes Solution Problem Understanding We are asked to examine permutations of numbers from 1 to n and focus on "lucky numbers" - integers that contain only the digits 4 and 7. The problem specifically asks us to find a lexicographically k -th permutation of numbers from 1 to n , and count...

Practice › LeetCode › LeetCode 13xx ›

LeetCode 1359 - Count All Valid Pickup and Delivery Options

LeetCode Problem 1359 Difficulty: 🔴 Hard Topics: Math, Dynamic Programming, Combinatorics Solution Problem Understanding This problem asks us to count the number of valid sequences for performing pickups and deliveries for n orders. Each order consists of a pickup Pi and a delivery Di , and the key constraint is that the delivery for any order must happen after its corresponding pickup. The input is a single integer n representing...

Practice › Codeforces Solutions ›

Codeforces Beta Round 91 (Div. 1 Only)

Codeforces Beta Round 91 (Div. 1 Only) Type: Div. 1 | Problems: 5 | Verified: 5/5 | Rating range: 1100-2500 | Time: 9m 56s Problem Name Rating Tags Solve Time Verified A Lucky Sum 1100 implementation 1m 36s ✓ B Lucky Transformation 1500 strings 2m 26s ✓ C Lucky Permutation 1900 brute-force, combinatorics, number-theory 1m 34s ✓ D Lucky Segments 2500 binary-search, implementation, two-pointers 1m 59s ✓ E Lucky Array...

Practice › Codeforces Solutions ›

Codeforces Beta Round 83 (Div. 1 Only)

Codeforces Beta Round 83 (Div. 1 Only) Type: Div. 1 | Problems: 5 | Verified: 5/5 | Rating range: 1400-2700 | Time: 11m 41s Problem Name Rating Tags Solve Time Verified A Dorm Water Supply 1400 dfs-and-similar, graphs 2m 19s ✓ B Basketball Team 1600 combinatorics, dp, math 2m 22s ✓ C Arrangement 2400 bitmasks, dp 2m 35s ✓ D Crime Management 2400 dp, graphs, matrices 2m 6s ✓ E...

Practice › Codeforces Solutions ›

Codeforces Beta Round 37

Codeforces Beta Round 37 Type: Beta | Problems: 5 | Verified: 4/5 | Rating range: 1000-2600 | Time: 8m 37s Problem Name Rating Tags Solve Time Verified A Towers 1000 sortings 53s ✓ B Computer Game 1800 greedy, implementation 1m 56s ✓ C Old Berland Language 1900 data-structures, greedy, trees 1m 42s ✓ D Lesson Timetable 2300 combinatorics, dp, math 2m 23s ✗ E Trial for Chief 2600 graphs, greedy,...

Practice › Codeforces Solutions ›

Codeforces Beta Round 48

Codeforces Beta Round 48 Type: Beta | Problems: 6 | Verified: 4/6 | Rating range: 1300-2800 | Time: 13m 36s Problem Name Rating Tags Solve Time Verified A Cheaterius's Problem 1300 implementation 1m 37s ✓ B bHTML Tables Analisys 1700 expression-parsing 3m 37s ✓ C Three Base Stations 1800 binary-search, greedy 2m 13s ✗ D Geometrical problem 2200 implementation 1m 55s ✓ E Pentagon 2400 combinatorics, graphs, matrices 2m 2s...

Practice › Codeforces Solutions ›

Codeforces Beta Round 15

Codeforces Beta Round 15 Type: Beta | Problems: 5 | Verified: 5/5 | Rating range: 1200-2600 | Time: 11m 13s Problem Name Rating Tags Solve Time Verified A Cottage Village 1200 implementation, sortings 2m 21s ✓ B Laser 1800 math 2m 54s ✓ C Industrial Nim 2000 games 2m 25s ✓ D Map 2500 data-structures, implementation, sortings 2m 12s ✓ E Triangles 2600 combinatorics, dp 1m 21s ✓

Practice › LeetCode › LeetCode 06xx ›

LeetCode 634 - Find the Derangement of An Array

LeetCode Problem 634 Difficulty: 🟡 Medium Topics: Math, Dynamic Programming, Combinatorics Solution Problem Understanding The problem asks us to count how many permutations of the numbers 1 through n are valid derangements. A derangement is a permutation where no element remains in its original position. For example, when n = 3 , the original array is [1, 2, 3] . A permutation like [2, 3, 1] is valid because: 1...

Practice › LeetCode › LeetCode (archived) › LeetCode 10xx ›

LeetCode 1012: Numbers With Repeated Digits

Problem Restatement We are given an integer n . We need to return the count of positive integers up to n (inclusive) that have at least one repeated digit. The official constraints state that 1 <= n <= 10^9 . Input and Output Item Meaning Input Integer n Output Count of integers in [1, n] with at least one repeated digit Function shape: def numDupDigitsAtMostN(n: int) -> int: ... Examples...

Practice › LeetCode › LeetCode (archived) › LeetCode 09xx ›

LeetCode 923: 3Sum With Multiplicity

Problem Restatement We are given an integer array arr and an integer target . Return the number of index triples: i < j < k such that: arr[i] + arr[j] + arr[k] == target The array can contain duplicate values, and each valid index triple counts separately. Because the answer can be large, return it modulo: 10**9 + 7 The official problem asks for exactly this count of tuples i,...

Practice › LeetCode › LeetCode (archived) › LeetCode 09xx ›

LeetCode 920: Number of Music Playlists

Problem Restatement We have n different songs. We need to create a playlist of length goal . The playlist must satisfy two rules: Rule Meaning Use every song Each of the n songs must appear at least once Replay restriction A song can be replayed only after at least k other songs have been played Return the number of valid playlists modulo: 10**9 + 7 The official problem asks for...

Practice › LeetCode › LeetCode (archived) › LeetCode 08xx ›

LeetCode 891: Sum of Subsequence Widths

Problem Restatement We are given an integer array nums . For any non-empty subsequence, its width is: maximum value - minimum value Return the sum of widths of all non-empty subsequences. Because the answer can be very large, return it modulo: 10**9 + 7 A subsequence is formed by deleting zero or more elements without changing the order of the remaining elements. The problem asks for the sum of widths...

Practice › LeetCode › LeetCode (archived) › LeetCode 06xx ›

LeetCode 634: Find the Derangement of An Array

Problem Restatement We are given an integer n . We need to count how many permutations of the numbers: [1, 2, 3, ..., n] have no fixed positions. A fixed position means: perm[i] == i for some index. A permutation with no fixed positions is called a derangement. Because the answer can be very large, return it modulo: 10**9 + 7 Input and Output Item Meaning Input Integer n Output...

Practice › LeetCode › LeetCode (archived) › LeetCode 08xx ›

LeetCode 828: Count Unique Characters of All Substrings of a Given String

Problem Restatement We are given a string s . For any string t , define countUniqueChars(t) as the number of characters that appear exactly once in t . We need to return the sum of countUniqueChars(t) over every substring t of s . The answer is guaranteed to fit in a 32-bit integer. Input and Output Item Meaning Input A string s Output Sum of unique-character counts over all substrings...

Practice › LeetCode › LeetCode (archived) › LeetCode 09xx ›

LeetCode 902: Numbers At Most N Given Digit Set

Problem Restatement We are given: A set of allowed digits as strings. An integer n . We may use the given digits any number of times to build positive integers. We need to count how many numbers are less than or equal to n . For example: digits = ["1", "3", "5", "7"] n = 100 Valid numbers include: 1, 3, 5, 7, 11, 13, 15, 17, 31, 33, ......

Practice › LeetCode › LeetCode (archived) › LeetCode 00xx ›

LeetCode 62: Unique Paths

Problem Restatement A robot starts at the top-left corner of an m x n grid. The robot wants to reach the bottom-right corner. At each step, the robot may move only: Right Down We need to count how many different paths exist. The official constraints are 1 <= m, n <= 100 , and the answer is guaranteed to fit in a 32-bit integer. Input and Output Item Meaning Input...

Practice › LeetCode › LeetCode (archived) › LeetCode 04xx ›

LeetCode 458: Poor Pigs

Problem Restatement We are given buckets buckets of liquid. Exactly one bucket is poisonous. A pig dies minutesToDie minutes after drinking poison. We have minutesToTest total minutes to determine which bucket is poisonous. We need to return the minimum number of pigs needed to guarantee that we can identify the poisonous bucket within the time limit. The official problem asks for the minimum number of pigs needed given buckets ,...

Practice › LeetCode › LeetCode (archived) › LeetCode 03xx ›

LeetCode 357: Count Numbers with Unique Digits

Problem Restatement Given an integer n , count how many integers x satisfy: 0 <= x < 10**n and have no repeated digits. A number has unique digits if every digit appears at most once. Examples: 123 has unique digits 102 has unique digits 11 does not have unique digits 100 does not have unique digits The range includes 0 . The range does not include 10^n . The problem...

Practice › LeetCode › LeetCode (archived) › LeetCode 02xx ›

LeetCode 276: Paint Fence

Problem Restatement We are given n fence posts and k colors. Each post must be painted with exactly one color. The rule is: At most two adjacent fence posts may have the same color. So this is allowed: red, red, blue But this is invalid: red, red, red We need to return the number of valid ways to paint all n posts. The source statement also notes that n and...

Maths › 00. General Mathematics ›

07.5 Probabilistic and Combinatorial Proofs

7.5 Probabilistic and Combinatorial Proofs Probabilistic and combinatorial proofs establish a result by counting, arranging, or randomly selecting objects. They are especially useful for finite structures, existence statements, and identities involving numbers of configurations. A combinatorial proof shows that two expressions are equal by showing that they count the same thing. For example, the identity $$ \binom{n}{k} = \binom{n}{n-k} $$ has a direct combinatorial explanation. Choosing $k$ elements from an...

Maths ›

05. Combinatorics

This volume studies finite and discrete structures, with emphasis on counting, arrangement, structure, and extremal behavior, and it maintains a constructive and algorithm-aware perspective throughout. Part I. Basic Counting Principles Chapter 1. Counting Foundations This chapter develops fundamental counting principles and techniques for establishing combinatorial identities. 1.1 Addition and multiplication principles 1.2 Bijective counting 1.3 Double counting 1.4 Inclusion-exclusion principle 1.5 Counting via symmetry Chapter 2. Permutations and Combinations This...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2010 Shortlist ›

IMO 2010 Shortlist C5

IMO 2010 Shortlist C5 Category: Combinatorics Problem n ©4 players participated in a tennis tournament. Any two players have played exactly one game, and there was no tie game. We call a company of four players bad if one player was defeated by the other three players, and each of these three players won a game and lost another game among themselves. Suppose that there is no bad company in...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2007 Shortlist ›

IMO 2007 Shortlist C1

IMO 2007 Shortlist C1 Category: Combinatorics Problem Let n > 1 be an integer. Find all sequences a1,a2,...,an2+n satisfying the following conditions: (a) ai ∈ {0,1} for all 1 ≤ i ≤ n2 n; (b) ai+1 + ai+2 + ... + ai+n < ai+n+1 + ai+n+2 + ... + ai+2n for all 0 ≤ i ≤ n2 − n. (Serbia)

Practice › Mathematics › IMO › IMO Shortlist › IMO 2011 Shortlist ›

IMO 2011 Shortlist C5

IMO 2011 Shortlist C5 Category: Combinatorics Problem Let m be a positive integer and consider a checkerboard consisting of m by m unit squares. At the midpoints of some of these unit squares there is an ant. At time 0, each ant starts moving with speed 1 parallel to some edge of the checkerboard. When two ants moving in opposite directions meet, they both turn 90◦ clockwise and continue moving...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2024 Shortlist ›

IMO 2024 Shortlist C4

IMO 2024 Shortlist C4 Category: Combinatorics Problem On a board with 2024 rows and 2023 columns, Turbo the snail tries to move from the first row to the last row. On each attempt, he chooses to start on any cell in the first row, then moves one step at a time to an adjacent cell sharing a common side. He wins if he reaches any cell in the last row....

Practice › Mathematics › IMO › IMO Shortlist › IMO 2019 Shortlist ›

IMO 2019 Shortlist C6

IMO 2019 Shortlist C6 Category: Combinatorics Problem Let n ą 1 be an integer. Suppose we are given 2n points in a plane such that no three of them are collinear. The points are to be labelled A1, A2, ..., A2n in some order. We then consider the 2n angles =A1A2A3, =A2A3A4, ..., =A2n´2A2n´1A2n, =A2n´1A2nA1, =A2nA1A2. We measure each angle in the way that gives the smallest positive value (i.e....

Practice › Mathematics › IMO › IMO Shortlist › IMO 2018 Shortlist ›

IMO 2018 Shortlist C4

IMO 2018 Shortlist C4 Category: Combinatorics Problem An anti-Pas al pyramid is a nite set of numbers, pla ed in a triangle-shaped array so that the rst row of the array ontains one number, the se ond row ontains two numbers, the third row ontains three numbers and so on; and, ex ept for the numbers in the bottom row, ea h number equals the absolute value of the dieren...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2011 Shortlist ›

IMO 2011 Shortlist C2

IMO 2011 Shortlist C2 Category: Combinatorics Problem Suppose that 1000 students are standing in a circle. Prove that there exists an integer k with 100 ≤ k ≤ 300 such that in this circle there exists a contiguous group of 2k students, for which the first half contains the same number of girls as the second half.

Practice › Mathematics › IMO › IMO Shortlist › IMO 2023 Shortlist ›

IMO 2023 Shortlist C3

IMO 2023 Shortlist C3 Category: Combinatorics Problem Let n be a positive integer. We arrange 1 2 ¨¨¨ ` n circles in a triangle with n rows, such that the ith row contains exactly i circles. The following figure shows the case n “ 6. n “ 6 In this triangle, a ninja-path is a sequence of circles obtained by repeatedly going from a circle to one of the two...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2007 Shortlist ›

IMO 2007 Shortlist C8

IMO 2007 Shortlist C8 Category: Combinatorics Problem Given a convex n-gon P in the plane. For every three vertices of P, consider the triangle determined by them. Call such a triangle good if all its sides are of unit length. Prove that there are not more than 2 n good triangles. (Ukraine)

Practice › Mathematics › IMO › IMO Shortlist › IMO 2022 Shortlist ›

IMO 2022 Shortlist C3

IMO 2022 Shortlist C3 Category: Combinatorics Problem In each square of a garden shaped like a 2022 ˆ 2022 board, there is initially a tree of height 0. A gardener and a lumberjack alternate turns playing the following game, with the gardener taking the first turn: • The gardener chooses a square in the garden. Each tree on that square and all the surrounding squares (of which there are at...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2012 Shortlist ›

IMO 2012 Shortlist C1

IMO 2012 Shortlist C1 Category: Combinatorics Problem Several positive integers are written in a row. Iteratively, Alice chooses two adjacent numbers x and y such that x > y and x is to the left of y, and replaces the pair (x,y) by either (y + 1,x) or (x − 1,x). Prove that she can perform only finitely many such iterations. Solution 1. Note first that the allowed operation does...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2023 Shortlist ›

IMO 2023 Shortlist C4

IMO 2023 Shortlist C4 Category: Combinatorics Problem Let n ě 2 be a positive integer. Paul has a 1 ˆ n2 rectangular strip consisting of n2 unit squares, where the ith square is labelled with i for all 1 ď i ď n2 . He wishes to cut the strip into several pieces, where each piece consists of a number of consecutive unit squares, and then translate (without rotating or...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2019 Shortlist ›

IMO 2019 Shortlist C7

IMO 2019 Shortlist C7 Category: Combinatorics Problem There are 60 empty boxes B1, ..., B60 in a row on a table and an unlimited supply of pebbles. Given a positive integer n, Alice and Bob play the following game. In the ﬁrst round, Alice takes n pebbles and distributes them into the 60 boxes as she wishes. Each subsequent round consists of two steps: (a) Bob chooses an integer k...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2012 Shortlist ›

IMO 2012 Shortlist C3

IMO 2012 Shortlist C3 Category: Combinatorics Problem In a 999 × 999 square table some cells are white and the remaining ones are red. Let T be the number of triples (C1,C2,C3) of cells, the first two in the same row and the last two in the same column, with C1 and C3 white and C2 red. Find the maximum value T can attain. Solution. We prove that in an...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2006 Shortlist ›

IMO 2006 Shortlist C7

IMO 2006 Shortlist C7 Category: Combinatorics Problem Consider a convex polyhedron without parallel edges and without an edge parallel to any face other than the two faces adjacent to it. Call a pair of points of the polyhedron antipodal if there exist two parallel planes passing through these points and such that the polyhedron is contained between these planes. Let A be the number of antipodal pairs of vertices, and...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2014 Shortlist ›

IMO 2014 Shortlist C7

IMO 2014 Shortlist C7 Category: Combinatorics Problem Let M be a set of n ě 4 points in the plane, no three of which are collinear. Initially these points are connected with n segments so that each point in M is the endpoint of exactly two segments. Then, at each step, one may choose two segments AB and CD sharing a common interior point and replace them by the segments...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2024 Shortlist ›

IMO 2024 Shortlist C7

IMO 2024 Shortlist C7 Category: Combinatorics Problem Let N be a positive integer and let a1, a2, ... be an infinite sequence of positive integers. Suppose that, for each n ą N, an is equal to the number of times an´1 appears in the list a1, a2, ..., an´1. Prove that at least one of the sequences a1, a3, a5, ... and a2, a4, a6, ... is eventually periodic. (Australia)

Practice › Mathematics › IMO › IMO Shortlist › IMO 2012 Shortlist ›

IMO 2012 Shortlist C7

IMO 2012 Shortlist C7 Category: Combinatorics Problem There are given 2500 points on a circle labeled 1,2,...,2500 in some order. Prove that one can choose 100 pairwise disjoint chords joining some of these points so that the 100 sums of the pairs of numbers at the endpoints of the chosen chords are equal. Solution. The proof is based on the following general fact. Lemma. In a graph G each vertex...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2017 Shortlist ›

IMO 2017 Shortlist C1

IMO 2017 Shortlist C1 Category: Combinatorics Problem A re tangle R with odd integer side lengths is divided into small re tangles with integer side lengths. Prove that there is at least one among the small re tangles whose distan es from the four sides of R are either all odd or all even. (Singapore)

Practice › Mathematics › IMO › IMO Shortlist › IMO 2016 Shortlist ›

IMO 2016 Shortlist C4

IMO 2016 Shortlist C4 Category: Combinatorics Problem Find all positive integers n for which we can fill in the entries of an n × n table with the following properties: • each entry can be one of I, M and O; • in each row and each column, the letters I, M and O occur the same number of times; and • in any diagonal whose number of entries is...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2019 Shortlist ›

IMO 2019 Shortlist C3

IMO 2019 Shortlist C3 Category: Combinatorics Problem Let n be a positive integer. Harry has n coins lined up on his desk, each showing heads or tails. He repeatedly does the following operation: if there are k coins showing heads and k ą 0, then he ﬂips the kth coin over; otherwise he stops the process. (For example, the process starting with THT would be THT Ñ HHT Ñ HTT...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2012 Shortlist ›

IMO 2012 Shortlist C4

IMO 2012 Shortlist C4 Category: Combinatorics Problem Players A and B play a game with N ≥ 2012 coins and 2012 boxes arranged around a circle. Initially A distributes the coins among the boxes so that there is at least 1 coin in each box. Then the two of them make moves in the order B,A,B,A,... by the following rules: • On every move of his B passes 1 coin...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2007 Shortlist ›

IMO 2007 Shortlist C5

IMO 2007 Shortlist C5 Category: Combinatorics Problem In the Cartesian coordinate plane define the strip Sn = {(x,y) | n ≤ x < n + 1} for every integer n. Assume that each strip Sn is colored either red or blue, and let a and b be two distinct positive integers. Prove that there exists a rectangle with side lengths a and b such that its vertices have the same...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2008 Shortlist ›

IMO 2008 Shortlist C6

IMO 2008 Shortlist C6 Category: Combinatorics Problem For n ≥ 2, let S1,S2,...,S2n be 2n subsets of A = {1,2,3,...,2n+1 } that satisfy the following property: There do not exist indices a and b with a < b and elements x,y,z ∈ A with x < y < z such that y,z ∈ Sa and x,z ∈ Sb. Prove that at least one of the sets S1,S2,...,S2n contains no more...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2006 Shortlist ›

IMO 2006 Shortlist C6

IMO 2006 Shortlist C6 Category: Combinatorics Problem A holey triangle is an upward equilateral triangle of side length n with n upward unit triangular holes cut out. A diamond is a 60◦ −120◦ unit rhombus. Prove that a holey triangle T can be tiled with diamonds if and only if the following condition holds: Every upward equilateral triangle of side length k in T contains at most k holes, for...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2017 Shortlist ›

IMO 2017 Shortlist C5

IMO 2017 Shortlist C5 Category: Combinatorics Problem A hunter and an invisible rabbit play a game in the Eu lidean plane. The hunter's starting point H0 oin ides with the rabbit's starting point R0. In the nth round of the game (n ě 1), the following happens. (1) First the invisible rabbit moves se retly and unobserved from its urrent point Rn´1 to some new point Rn with Rn´1Rn “...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2009 Shortlist ›

IMO 2009 Shortlist C2

IMO 2009 Shortlist C2 Category: Combinatorics Problem For any integer n ≥ 2, let N(n) be the maximal number of triples (ai,bi,ci), i = 1,...,N(n), consisting of nonnegative integers ai,bi and ci such that the following two conditions are satis- fied: (1) ai + bi + ci = n for all i = 1,...,N(n), (2) If i 6= j, then ai 6= aj,bi 6= bj and ci 6= cj. Determine...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2007 Shortlist ›

IMO 2007 Shortlist C7

IMO 2007 Shortlist C7 Category: Combinatorics Problem Let α < 3 − √ be a positive real number. Prove that there exist positive integers n and p > α · 2n for which one can select 2p pairwise distinct subsets S1, ..., Sp, T1, ..., Tp of the set {1,2,...,n} such that Si ∩ Tj 6= ∅ for all 1 ≤ i,j ≤ p. (Austria)

Practice › Mathematics › IMO › IMO Shortlist › IMO 2009 Shortlist ›

IMO 2009 Shortlist C8

IMO 2009 Shortlist C8 Category: Combinatorics Problem For any integer n ≥ 2, we compute the integer h(n) by applying the following procedure to its decimal representation. Let r be the rightmost digit of n. (1) If r = 0, then the decimal representation of h(n) results from the decimal representation of n by removing this rightmost digit 0. (2) If 1 ≤ r ≤ 9 we split the decimal...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2023 Shortlist ›

IMO 2023 Shortlist C2

IMO 2023 Shortlist C2 Category: Combinatorics Problem Determine the maximal length L of a sequence a1,...,aL of positive integers satisfying both the following properties: • every term in the sequence is less than or equal to 22023 , and • there does not exist a consecutive subsequence ai,ai 1,...,aj (where 1 ď i ď j ď L) with a choice of signs si,si 1,...,sj P t1,´1u for which siai si...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2015 Shortlist ›

IMO 2015 Shortlist C6

IMO 2015 Shortlist C6 Category: Combinatorics Problem Let S be a nonempty set of positive integers. We say that a positive integer n is clean if it has a unique representation as a sum of an odd number of distinct elements from S. Prove that there exist infinitely many positive integers that are not clean. (U.S.A.)

Practice › Mathematics › IMO › IMO Shortlist › IMO 2008 Shortlist ›

IMO 2008 Shortlist C1

IMO 2008 Shortlist C1 Category: Combinatorics Problem In the plane we consider rectangles whose sides are parallel to the coordinate axes and have positive length. Such a rectangle will be called a box. Two boxes intersect if they have a common point in their interior or on their boundary. Find the largest n for which there exist n boxes B1,...,Bn such that Bi and Bj intersect if and only if...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2009 Shortlist ›

IMO 2009 Shortlist C7

IMO 2009 Shortlist C7 Category: Combinatorics Problem Variant 1. A grasshopper jumps along the real axis. He starts at point 0 and makes 2009 jumps to the right with lengths 1,2,...,2009 in an arbitrary order. Let M be a set of 2008 positive integers less than 1005 · 2009. Prove that the grasshopper can arrange his jumps in such a way that he never lands on a point from M....

Practice › Mathematics › IMO › IMO Shortlist › IMO 2020 Shortlist ›

IMO 2020 Shortlist C3

IMO 2020 Shortlist C3 Category: Combinatorics Problem Let n be an integer with n ě 2. On a slope of a mountain, n2 checkpoints are marked, numbered from 1 to n2 from the bottom to the top. Each of two cable car companies, A and B, operates k cable cars numbered from 1 to k; each cable car provides a transfer from some checkpoint to a higher one. For each...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2014 Shortlist ›

IMO 2014 Shortlist C2

IMO 2014 Shortlist C2 Category: Combinatorics Problem We have 2m sheets of paper, with the number 1 written on each of them. We perform the following operation. In every step we choose two distinct sheets; if the numbers on the two sheets are a and b, then we erase these numbers and write the number a ` b on both sheets. Prove that after m2m´1 steps, the sum of the...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2006 Shortlist ›

IMO 2006 Shortlist C3

IMO 2006 Shortlist C3 Category: Combinatorics Problem Let S be a finite set of points in the plane such that no three of them are on a line. For each convex polygon P whose vertices are in S, let a(P) be the number of vertices of P, and let b(P) be the number of points of S which are outside P. Prove that for every real number x X P...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2022 Shortlist ›

IMO 2022 Shortlist C1

IMO 2022 Shortlist C1 Category: Combinatorics Problem A ˘1-sequence is a sequence of 2022 numbers a1,...,a2022, each equal to either 1 or ´1. Determine the largest C so that, for any ˘1-sequence, there exists an integer k and indices 1 ď t1 ă ... ă tk ď 2022 so that ti 1 ´ ti ď 2 for all i, and k ÿ i“1 ati ě C. (Czech Republic)

Practice › Mathematics › IMO › IMO Shortlist › IMO 2022 Shortlist ›

IMO 2022 Shortlist C2

IMO 2022 Shortlist C2 Category: Combinatorics Problem The Bank of Oslo issues coins made out of two types of metal: aluminium (denoted A) and copper (denoted C). Morgane has n aluminium coins, and n copper coins, and arranges her 2n coins in a row in some arbitrary initial order. Given a fixed positive integer k ď 2n, she repeatedly performs the following operation: identify the largest subsequence containing the k-th...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2020 Shortlist ›

IMO 2020 Shortlist C6

IMO 2020 Shortlist C6 Category: Combinatorics Problem 4n coins of weights 1,2,3,...,4n are given. Each coin is colored in one of n colors and there are four coins of each color. Show that all these coins can be partitioned into two sets with the same total weight, such that each set contains two coins of each color. (Hungary) Shortlisted problems 7

Practice › Mathematics › IMO › IMO Shortlist › IMO 2015 Shortlist ›

IMO 2015 Shortlist C3

IMO 2015 Shortlist C3 Category: Combinatorics Problem For a finite set A of positive integers, we call a partition of A into two disjoint nonempty subsets A1 and A2 good if the least common multiple of the elements in A1 is equal to the greatest common divisor of the elements in A2. Determine the minimum value of n such that there exists a set of n positive integers with exactly...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2017 Shortlist ›

IMO 2017 Shortlist C7

IMO 2017 Shortlist C7 Category: Combinatorics Problem For any nite sets X and Y of positive integers, denote by fXpkq the kth smallest positive integer not in X, and let X ˚ Y “ X Y tfXpyq: y P Y u. Let A be a set of a ą 0 positive integers, and let B be a set of b ą 0 positive integers. Prove that if A ˚ B...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2007 Shortlist ›

IMO 2007 Shortlist C4

IMO 2007 Shortlist C4 Category: Combinatorics Problem Let A0 = (a1,...,an) be a finite sequence of real numbers. For each k ≥ 0, from the sequence Ak = (x1,...,xn) we construct a new sequence Ak+1 in the following way. We choose a partition {1,...,n} = I ∪ J, where I and J are two disjoint sets, such that the expression X i∈I xi − X j∈J xj attains the smallest...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2016 Shortlist ›

IMO 2016 Shortlist C6

IMO 2016 Shortlist C6 Category: Combinatorics Problem There are n ⩾ 3 islands in a city. Initially, the ferry company offers some routes between some pairs of islands so that it is impossible to divide the islands into two groups such that no two islands in different groups are connected by a ferry route. After each year, the ferry company will close a ferry route between some two islands X...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2010 Shortlist ›

IMO 2010 Shortlist C4

IMO 2010 Shortlist C4 Category: Combinatorics Problem Six stacks S1,...,S6 of coins are standing in a row. In the beginning every stack contains a single coin. There are two types of allowed moves: Move 1: If stack Sk with 1 ¨k ¨5 contains at least one coin, you may remove one coin from Sk and add two coins to Sk 1. Move 2: If stack Sk with 1 ¨ k...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2010 Shortlist ›

IMO 2010 Shortlist C6

IMO 2010 Shortlist C6 Category: Combinatorics Problem Given a positive integer k and other two integers b ¡ w ¡ 1. There are two strings of pearls, a string of b black pearls and a string of w white pearls. The length of a string is the number of pearls on it. One cuts these strings in some steps by the following rules. In each step: (i) The strings are...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2006 Shortlist ›

IMO 2006 Shortlist C2

IMO 2006 Shortlist C2 Category: Combinatorics Problem A diagonal of a regular 2006-gon is called odd if its endpoints divide the boundary into two parts, each composed of an odd number of sides. Sides are also regarded as odd diagonals. Suppose the 2006-gon has been dissected into triangles by 2003 nonintersecting diagonals. Find the maximum possible number of isosceles triangles with two odd sides. (Serbia)

Practice › Mathematics › IMO › IMO Shortlist › IMO 2010 Shortlist ›

IMO 2010 Shortlist C2

IMO 2010 Shortlist C2 Category: Combinatorics Problem On some planet, there are 2N countries (N © 4). Each country has a flag N units wide and one unit high composed of N fields of size 11, each field being either yellow or blue. No two countries have the same flag. We say that a set of N flags is diverse if these flags can be arranged into an N N...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2018 Shortlist ›

IMO 2018 Shortlist C5

IMO 2018 Shortlist C5 Category: Combinatorics Problem Let k be a positive integer. The organising ommittee of a tennis tournament is to s hedule the mat hes for 2k players so that every two players play on e, ea h day exa tly one mat h is played, and ea h player arrives to the tournament site the day of his rst mat h, and departs the day of his...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2012 Shortlist ›

IMO 2012 Shortlist C6

IMO 2012 Shortlist C6 Category: Combinatorics Problem Let k and n be fixed positive integers. In the liar’s guessing game, Amy chooses integers x and N with 1 ≤ x ≤ N. She tells Ben what N is, but not what x is. Ben may then repeatedly ask Amy whether x ∈ S for arbitrary sets S of integers. Amy will always answer with yes or no, but she might...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2009 Shortlist ›

IMO 2009 Shortlist C4

IMO 2009 Shortlist C4 Category: Combinatorics Problem For an integer m ≥ 1, we consider partitions of a 2m ×2m chessboard into rectangles consisting of cells of the chessboard, in which each of the 2m cells along one diagonal forms a separate rectangle of side length 1. Determine the smallest possible sum of rectangle perimeters in such a partition.

Practice › Mathematics › IMO › IMO Shortlist › IMO 2021 Shortlist ›

IMO 2021 Shortlist C7

IMO 2021 Shortlist C7 Category: Combinatorics Problem Consider a checkered 3m ˆ3m square, where m is an integer greater than 1. A frog sits on the lower left corner cell S and wants to get to the upper right corner cell F. The frog can hop from any cell to either the next cell to the right or the next cell upwards. Some cells can be sticky, and the frog...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2020 Shortlist ›

IMO 2020 Shortlist C4

IMO 2020 Shortlist C4 Category: Combinatorics Problem The Fibonacci numbers F0,F1,F2,... are defined inductively by F0 “ 0, F1 “ 1, and Fn 1 “ Fn Fn´1 for n ě 1. Given an integer n ě 2, determine the smallest size of a set S of integers such that for every k “ 2,3,...,n there exist some x,y P S such that x ´ y “ Fk. (Croatia)

Practice › Mathematics › IMO › IMO Shortlist › IMO 2018 Shortlist ›

IMO 2018 Shortlist C7

IMO 2018 Shortlist C7 Category: Combinatorics Problem Consider 2018 pairwise rossing ir les no three of whi h are on urrent. These ir les subdivide the plane into regions bounded by ir ular edges that meet at verti es. Noti e that there are an even number of verti es on ea h ir le. Given the ir le, alternately olour the verti es on that ir le red and...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2012 Shortlist ›

IMO 2012 Shortlist C2

IMO 2012 Shortlist C2 Category: Combinatorics Problem Let n ≥ 1 be an integer. What is the maximum number of disjoint pairs of elements of the set {1,2,...,n} such that the sums of the different pairs are different integers not exceeding n? Solution. Consider x such pairs in {1,2,...,n}. The sum S of the 2x numbers in them is at least 1+2+···+2x since the pairs are disjoint. On the other...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2013 Shortlist ›

IMO 2013 Shortlist C3

IMO 2013 Shortlist C3 Category: Combinatorics Problem A crazy physicist discovered a new kind of particle which he called an imon, after some of them mysteriously appeared in his lab. Some pairs of imons in the lab can be entangled, and each imon can participate in many entanglement relations. The physicist has found a way to perform the following two kinds of operations with these particles, one operation at a...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2019 Shortlist ›

IMO 2019 Shortlist C5

IMO 2019 Shortlist C5 Category: Combinatorics Problem On a certain social network, there are 2019 users, some pairs of which are friends, where friendship is a symmetric relation. Initially, there are 1010 people with 1009 friends each and 1009 people with 1010 friends each. However, the friendships are rather unstable, so events of the following kind may happen repeatedly, one at a time: Let A, B, and C be people...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2023 Shortlist ›

IMO 2023 Shortlist C5

IMO 2023 Shortlist C5 Category: Combinatorics Problem Elisa has 2023 treasure chests, all of which are unlocked and empty at first. Each day, Elisa adds a new gem to one of the unlocked chests of her choice, and afterwards, a fairy acts according to the following rules: • if more than one chests are unlocked, it locks one of them, or • if there is only one unlocked chest, it...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2013 Shortlist ›

IMO 2013 Shortlist C5

IMO 2013 Shortlist C5 Category: Combinatorics Problem Let r be a positive integer, and let a0,a1,... be an infinite sequence of real numbers. Assume that for all nonnegative integers m and s there exists a positive integer n P rm 1,m rs such that am am 1 ¨¨¨ am s “ an an 1 ¨¨¨ an s. Prove that the sequence is periodic, i.e. there exists some p ě 1...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2013 Shortlist ›

IMO 2013 Shortlist C4

IMO 2013 Shortlist C4 Category: Combinatorics Problem Let n be a positive integer, and let A be a subset of t1,...,nu. An A-partition of n into k parts is a representation of n as a sum n “ a1 ¨¨¨ ak, where the parts a1,...,ak belong to A and are not necessarily distinct. The number of different parts in such a partition is the number of (distinct) elements in the...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2022 Shortlist ›

IMO 2022 Shortlist C5

IMO 2022 Shortlist C5 Category: Combinatorics Problem Let m,n ě 2 be integers, let X be a set with n elements, and let X1,X2,...,Xm be pairwise distinct non-empty, not necessary disjoint subsets of X. A function f : X Ñ t1,2,...,n ` 1u is called nice if there exists an index k such that ÿ xPXk fpxq ą ÿ xPXi fpxq for all i ‰ k. Prove that the number...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2019 Shortlist ›

IMO 2019 Shortlist C2

IMO 2019 Shortlist C2 Category: Combinatorics Problem You are given a set of n blocks, each weighing at least 1; their total weight is 2n. Prove that for every real number r with 0 ď r ď 2n ´ 2 you can choose a subset of the blocks whose total weight is at least r but at most r ` 2. (Thailand)

Practice › Mathematics › IMO › IMO Shortlist › IMO 2023 Shortlist ›

IMO 2023 Shortlist C6

IMO 2023 Shortlist C6 Category: Combinatorics Problem Let N be a positive integer, and consider an N ˆ N grid. A right-down path is a sequence of grid cells such that each cell is either one cell to the right of or one cell below the previous cell in the sequence. A right-up path is a sequence of grid cells such that each cell is either one cell to the...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2010 Shortlist ›

IMO 2010 Shortlist C41

IMO 2010 Shortlist C41 Category: Combinatorics Problem . Same as Problem C4, but the constant 201020102010 is replaced by 20102010 . (Netherlands)

Practice › Mathematics › IMO › IMO Shortlist › IMO 2021 Shortlist ›

IMO 2021 Shortlist C1

IMO 2021 Shortlist C1 Category: Combinatorics Problem Let S be an infiniteset of positive integers, such that there exist four pairwise distinct a,b,c,d PS with gcdpa,bq‰gcdpc,dq. Prove that there exist three pairwise distinct x,y,z PS such that gcdpx,yq“gcdpy,zq‰gcdpz,xq.

Practice › Mathematics › IMO › IMO Shortlist › IMO 2010 Shortlist ›

IMO 2010 Shortlist C3

IMO 2010 Shortlist C3 Category: Combinatorics Problem 2500 chess kings have to be placed on a 100 100 chessboard so that (i) no king can capture any other one (i.e. no two kings are placed in two squares sharing a common vertex); (ii) each row and each column contains exactly 25 kings. Find the number of such arrangements. (Two arrangements differing by rotation or sym- metry are supposed to be...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2017 Shortlist ›

IMO 2017 Shortlist C2

IMO 2017 Shortlist C2 Category: Combinatorics Problem Let n be a positive integer. Dene a hameleon to be any sequen e of 3n letters, with exa tly n o urren es of ea h of the letters a, b, and c. Dene a swap to be the transposition of two adja ent letters in a hameleon. Prove that for any hameleon X, there exists a hameleon Y su h that...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2017 Shortlist ›

IMO 2017 Shortlist C4

IMO 2017 Shortlist C4 Category: Combinatorics Problem Let N ě 2 be an integer. NpN ` 1q so er players, no two of the same height, stand in a row in some order. Coa h Ralph wants to remove NpN ´ 1q people from this row so that in the remaining row of 2N players, no one stands between the two tallest ones, no one stands between the third and...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2020 Shortlist ›

IMO 2020 Shortlist C2

IMO 2020 Shortlist C2 Category: Combinatorics Problem In a regular 100-gon, 41 vertices are colored black and the remaining 59 vertices are colored white. Prove that there exist 24 convex quadrilaterals Q1, ..., Q24 whose corners are vertices of the 100-gon, so that • the quadrilaterals Q1, ..., Q24 are pairwise disjoint, and • every quadrilateral Qi has three corners of one color and one corner of the other color....

Practice › Mathematics › IMO › IMO Shortlist › IMO 2017 Shortlist ›

IMO 2017 Shortlist C6

IMO 2017 Shortlist C6 Category: Combinatorics Problem Let n ą 1 be an integer. An n ˆ n ˆ n ube is omposed of n3 unit ubes. Ea h unit ube is painted with one olor. For ea h nˆnˆ1 box onsisting of n2 unit ubes (of any of the three possible orientations), we onsider the set of the olors present in that box (ea h olor is listed only...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2018 Shortlist ›

IMO 2018 Shortlist C3

IMO 2018 Shortlist C3 Category: Combinatorics Problem Let n be a given positive integer. Sisyphus performs a sequen e of turns on a board onsisting of n 1 squares in a row, numbered 0 to n from left to right. Initially, n stones are put into square 0, and the other squares are empty. At every turn, Sisyphus hooses any nonempty square, say with k stones, takes one of those...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2011 Shortlist ›

IMO 2011 Shortlist C4

IMO 2011 Shortlist C4 Category: Combinatorics Problem Determine the greatest positive integer k that satisfies the following property: The set of positive integers can be partitioned into k subsets A1,A2,...,Ak such that for all integers n ≥ 15 and all i ∈ {1,2,...,k} there exist two distinct elements of Ai whose sum is n.

Practice › Mathematics › IMO › IMO Shortlist › IMO 2016 Shortlist ›

IMO 2016 Shortlist C2

IMO 2016 Shortlist C2 Category: Combinatorics Problem Find all positive integers n for which all positive divisors of n can be put into the cells of a rectangular table under the following constraints: • each cell contains a distinct divisor; • the sums of all rows are equal; and • the sums of all columns are equal.

Practice › Mathematics › IMO › IMO Shortlist › IMO 2011 Shortlist ›

IMO 2011 Shortlist C3

IMO 2011 Shortlist C3 Category: Combinatorics Problem Let S be a finite set of at least two points in the plane. Assume that no three points of S are collinear. By a windmill we mean a process as follows. Start with a line ℓ going through a point P ∈ S. Rotate ℓ clockwise around the pivot P until the line contains another point Q of S. The point Q...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2011 Shortlist ›

IMO 2011 Shortlist C6

IMO 2011 Shortlist C6 Category: Combinatorics Problem Let n be a positive integer and let W = ...x−1x0x1x2 ... be an infinite periodic word consisting of the letters a and b. Suppose that the minimal period N of W is greater than 2n . A finite nonempty word U is said to appear in W if there exist indices k ≤ ℓ such that U = xkxk+1 ...xℓ. A finite...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2018 Shortlist ›

IMO 2018 Shortlist C6

IMO 2018 Shortlist C6 Category: Combinatorics Problem Let a and b be distin t positive integers. The following innite pro ess takes pla e on an initially empty board. piq If there is at least a pair of equal numbers on the board, we hoose su h a pair and in rease one of its omponents by a and the other by b. piiq If no su h pair exists,...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2020 Shortlist ›

IMO 2020 Shortlist C8

IMO 2020 Shortlist C8 Category: Combinatorics Problem Players A and B play a game on a blackboard that initially contains 2020 copies of the number 1. In every round, player A erases two numbers x and y from the blackboard, and then player B writes one of the numbers x ` y and |x ´ y| on the blackboard. The game terminates as soon as, at the end of some...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2011 Shortlist ›

IMO 2011 Shortlist C1

IMO 2011 Shortlist C1 Category: Combinatorics Problem Let n > 0 be an integer. We are given a balance and n weights of weight 20 , 21 ,...,2n−1 . In a sequence of n moves we place all weights on the balance. In the first move we choose a weight and put it on the left pan. In each of the following moves we choose one of the remaining weights...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2013 Shortlist ›

IMO 2013 Shortlist C6

IMO 2013 Shortlist C6 Category: Combinatorics Problem In some country several pairs of cities are connected by direct two-way flights. It is possible to go from any city to any other by a sequence of flights. The distance between two cities is defined to be the least possible number of flights required to go from one of them to the other. It is known that for any city there are...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2022 Shortlist ›

IMO 2022 Shortlist C8

IMO 2022 Shortlist C8 Category: Combinatorics Problem Alice fills the fields of an n ˆ n board with numbers from 1 to n2 , each number being used exactly once. She then counts the total number of good paths on the board. A good path is a sequence of fields of arbitrary length (including 1) such that: (i) The first field in the sequence is one that is only adjacent...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2023 Shortlist ›

IMO 2023 Shortlist C7

IMO 2023 Shortlist C7 Category: Combinatorics Problem The Imomi archipelago consists of n ě 2 islands. Between each pair of distinct islands is a unique ferry line that runs in both directions, and each ferry line is operated by one of k companies. It is known that if any one of the k companies closes all its ferry lines, then it becomes impossible for a traveller, no matter where the...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2009 Shortlist ›

IMO 2009 Shortlist C5

IMO 2009 Shortlist C5 Category: Combinatorics Problem Five identical empty buckets of 2-liter capacity stand at the vertices of a regular pentagon. Cinderella and her wicked Stepmother go through a sequence of rounds: At the beginning of every round, the Stepmother takes one liter of water from the nearby river and distributes it arbitrarily over the five buckets. Then Cinderella chooses a pair of neighboring buckets, empties them into the...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2016 Shortlist ›

IMO 2016 Shortlist C5

IMO 2016 Shortlist C5 Category: Combinatorics Problem Let n ⩾ 3 be a positive integer. Find the maximum number of diagonals of a regular n-gon one can select, so that any two of them do not intersect in the interior or they are perpendicular to each other. 6 IMO 2016 Hong Kong

Practice › Mathematics › IMO › IMO Shortlist › IMO 2010 Shortlist ›

IMO 2010 Shortlist C1

IMO 2010 Shortlist C1 Category: Combinatorics Problem In a concert, 20 singers will perform. For each singer, there is a (possibly empty) set of other singers such that he wishes to perform later than all the singers from that set. Can it happen that there are exactly 2010 orders of the singers such that all their wishes are satisfied? (Austria)

Practice › Mathematics › IMO › IMO Shortlist › IMO 2024 Shortlist ›

IMO 2024 Shortlist C8

IMO 2024 Shortlist C8 Category: Combinatorics Problem Let n be a positive integer. Given an nˆn board, the unit cell in the top left corner is initially coloured black, and the other cells are coloured white. We then apply a series of colouring operations to the board. In each operation, we choose a 2 ˆ 2 square with exactly one cell coloured black and we colour the remaining three cells...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2008 Shortlist ›

IMO 2008 Shortlist C3

IMO 2008 Shortlist C3 Category: Combinatorics Problem In the coordinate plane consider the set S of all points with integer coordinates. For a positive integer k, two distinct points A,B ∈ S will be called k-friends if there is a point C ∈ S such that the area of the triangle ABC is equal to k. A set T ⊂ S will be called a k-clique if every two points...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2019 Shortlist ›

IMO 2019 Shortlist C1

IMO 2019 Shortlist C1 Category: Combinatorics Problem The inﬁnite sequence a0, a1, a2, ... of (not necessarily diﬀerent) integers has the following properties: 0 ď ai ď i for all integers i ě 0, and ˆ k a0 ˙ ˆ k a1 ˙ ¨¨¨ ` ˆ k ak ˙ “ 2k for all integers k ě 0. Prove that all integers N ě 0 occur in the sequence (that is,...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2018 Shortlist ›

IMO 2018 Shortlist C1

IMO 2018 Shortlist C1 Category: Combinatorics Problem Let n ě 3 be an integer. Prove that there exists a set S of 2n positive integers satisfying the following property: For every m “ 2,3,...,n the set S an be partitioned into two subsets with equal sums of elements, with one of subsets of ardinality m. (I eland)

Practice › Mathematics › IMO › IMO Shortlist › IMO 2016 Shortlist ›

IMO 2016 Shortlist C8

IMO 2016 Shortlist C8 Category: Combinatorics Problem Let n be a positive integer. Determine the smallest positive integer k with the following property: it is possible to mark k cells on a 2n × 2n board so that there exists a unique partition of the board into 1 × 2 and 2 × 1 dominoes, none of which contains two marked cells. Shortlisted problems 7

Practice › Mathematics › IMO › IMO Shortlist › IMO 2007 Shortlist ›

IMO 2007 Shortlist C3

IMO 2007 Shortlist C3 Category: Combinatorics Problem Find all positive integers n, for which the numbers in the set S = {1,2,...,n} can be colored red and blue, with the following condition being satisfied: the set S × S × S contains exactly 2007 ordered triples (x,y,z) such that (i) x,y,z are of the same color and (ii) x+y +z is divisible by n. (Netherlands)

Practice › Mathematics › IMO › IMO Shortlist › IMO 2014 Shortlist ›

IMO 2014 Shortlist C4

IMO 2014 Shortlist C4 Category: Combinatorics Problem Construct a tetromino by attaching two 2 ˆ 1 dominoes along their longer sides such that the midpoint of the longer side of one domino is a corner of the other domino. This construction yields two kinds of tetrominoes with opposite orientations. Let us call them S- and Z-tetrominoes, respectively. S-tetrominoes Z-tetrominoes Assume that a lattice polygon P can be tiled with S-tetrominoes....

Practice › Mathematics › IMO › IMO Shortlist › IMO 2020 Shortlist ›

IMO 2020 Shortlist C7

IMO 2020 Shortlist C7 Category: Combinatorics Problem Consider any rectangular table having finitely many rows and columns, with a real number apr,cq in the cell in row r and column c. A pair pR,Cq, where R is a set of rows and C a set of columns, is called a saddle pair if the following two conditions are satisfied: piq For each row r1 , there is r P R...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2013 Shortlist ›

IMO 2013 Shortlist C7

IMO 2013 Shortlist C7 Category: Combinatorics Problem Let n ě 2 be an integer. Consider all circular arrangements of the numbers 0,1,...,n; the n 1 rotations of an arrangement are considered to be equal. A circular arrangement is called beautiful if, for any four distinct numbers 0 ď a,b,c,d ď n with a c “ b d, the chord joining numbers a and c does not intersect the chord joining...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2014 Shortlist ›

IMO 2014 Shortlist C6

IMO 2014 Shortlist C6 Category: Combinatorics Problem We are given an infinite deck of cards, each with a real number on it. For every real number x, there is exactly one card in the deck that has x written on it. Now two players draw disjoint sets A and B of 100 cards each from this deck. We would like to define a rule that declares one of them a...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2021 Shortlist ›

IMO 2021 Shortlist C8

IMO 2021 Shortlist C8 Category: Combinatorics Problem Determine the largest N for which there exists a table T of integers with N rows and 100 columns that has the following properties: (i) Every row contains the numbers 1, 2, ..., 100 in some order. (ii) For any two distinct rows r and s, there is a column c such that |Tpr,cq´Tps,cq|ě2. Here Tpr,cq means the number at the intersection of...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2024 Shortlist ›

IMO 2024 Shortlist C2

IMO 2024 Shortlist C2 Category: Combinatorics Problem Let n be a positive integer. The integers 1, 2, 3, ..., n2 are to be written in the cells of an n ˆ n board such that each integer is written in exactly one cell and each cell contains exactly one integer. For every integer d with d | n, the d-division of the board is the division of the board into...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2017 Shortlist ›

IMO 2017 Shortlist C3

IMO 2017 Shortlist C3 Category: Combinatorics Problem Sir Alex plays the following game on a row of 9 ells. Initially, all ells are empty. In ea h move, Sir Alex is allowed to perform exa tly one of the following two operations: (1) Choose any number of the form 2j , where j is a non-negative integer, and put it into an empty ell. (2) Choose two (not ne essarily...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2013 Shortlist ›

IMO 2013 Shortlist C8

IMO 2013 Shortlist C8 Category: Combinatorics Problem Players A and B play a paintful game on the real line. Player A has a pot of paint with four units of black ink. A quantity p of this ink suffices to blacken a (closed) real interval of length p. In every round, player A picks some positive integer m and provides 1{2m units of ink from the pot. Player B then...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2020 Shortlist ›

IMO 2020 Shortlist C1

IMO 2020 Shortlist C1 Category: Combinatorics Problem Let n be a positive integer. Find the number of permutations a1,a2,...,an of the sequence 1,2,...,n satisfying a1 ď 2a2 ď 3a3 ď ... ď nan. (United Kingdom)

Practice › Mathematics › IMO › IMO Shortlist › IMO 2015 Shortlist ›

IMO 2015 Shortlist C1

IMO 2015 Shortlist C1 Category: Combinatorics Problem In Lineland there are n ě 1 towns, arranged along a road running from left to right. Each town has a left bulldozer (put to the left of the town and facing left) and a right bulldozer (put to the right of the town and facing right). The sizes of the 2n bulldozers are distinct. Every time when a right and a left...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2016 Shortlist ›

IMO 2016 Shortlist C1

IMO 2016 Shortlist C1 Category: Combinatorics Problem The leader of an IMO team chooses positive integers n and k with n > k, and announces them to the deputy leader and a contestant. The leader then secretly tells the deputy leader an n-digit binary string, and the deputy leader writes down all n-digit binary strings which differ from the leader’s in exactly k positions. (For example, if n = 3...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2021 Shortlist ›

IMO 2021 Shortlist C3

IMO 2021 Shortlist C3 Category: Combinatorics Problem A thimblerigger has 2021 thimbles numbered from 1 through 2021. The thimbles are arranged in a circle in arbitrary order. The thimblerigger performs a sequence of 2021 moves; in the kth move, he swaps the positions of the two thimbles adjacent to thimble k. Prove that there exists a value of k such that, in the kth move, the thimblerigger swaps some thimbles...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2019 Shortlist ›

IMO 2019 Shortlist C9

IMO 2019 Shortlist C9 Category: Combinatorics Problem For any two diﬀerent real numbers x and y, we deﬁne Dpx,yq to be the unique integer d satisfying 2d ď |x ´ y| ă 2d`1 . Given a set of reals F, and an element x P F, we say that the scales of x in F are the values of Dpx,yq for y P F with x ‰ y. Let k...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2008 Shortlist ›

IMO 2008 Shortlist C2

IMO 2008 Shortlist C2 Category: Combinatorics Problem For every positive integer n determine the number of permutations (a1,a2,...,an) of the set {1,2,...,n} with the following property: 2(a1 + a2 + ··· + ak) is divisible by k for k = 1,2,...,n.

Practice › Mathematics › IMO › IMO Shortlist › IMO 2014 Shortlist ›

IMO 2014 Shortlist C1

IMO 2014 Shortlist C1 Category: Combinatorics Problem Let n points be given inside a rectangle R such that no two of them lie on a line parallel to one of the sides of R. The rectangle R is to be dissected into smaller rectangles with sides parallel to the sides of R in such a way that none of these rectangles contains any of the given points in its interior....

Practice › Mathematics › IMO › IMO Shortlist › IMO 2009 Shortlist ›

IMO 2009 Shortlist C1

IMO 2009 Shortlist C1 Category: Combinatorics Problem Consider 2009 cards, each having one gold side and one black side, lying in parallel on a long table. Initially all cards show their gold sides. Two players, standing by the same long side of the table, play a game with alternating moves. Each move consists of choosing a block of 50 consecutive cards, the leftmost of which is showing gold, and turning...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2013 Shortlist ›

IMO 2013 Shortlist C2

IMO 2013 Shortlist C2 Category: Combinatorics Problem In the plane, 2013 red points and 2014 blue points are marked so that no three of the marked points are collinear. One needs to draw k lines not passing through the marked points and dividing the plane into several regions. The goal is to do it in such a way that no region contains points of both colors. Find the minimal value...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2015 Shortlist ›

IMO 2015 Shortlist C4

IMO 2015 Shortlist C4 Category: Combinatorics Problem Let n be a positive integer. Two players A and B play a game in which they take turns choosing positive integers k ď n. The rules of the game are: piq A player cannot choose a number that has been chosen by either player on any previous turn. piiq A player cannot choose a number consecutive to any of those the player...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2013 Shortlist ›

IMO 2013 Shortlist C1

IMO 2013 Shortlist C1 Category: Combinatorics Problem Let n be a positive integer. Find the smallest integer k with the following property: Given any real numbers a1,...,ad such that a1 a2 ¨¨¨ ` ad “ n and 0 ď ai ď 1 for i “ 1,2,...,d, it is possible to partition these numbers into k groups (some of which may be empty) such that the sum of the numbers in...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2015 Shortlist ›

IMO 2015 Shortlist C7

IMO 2015 Shortlist C7 Category: Combinatorics Problem In a company of people some pairs are enemies. A group of people is called unsociable if the number of members in the group is odd and at least 3, and it is possible to arrange all its members around a round table so that every two neighbors are enemies. Given that there are at most 2015 unsociable groups, prove that it is...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2014 Shortlist ›

IMO 2014 Shortlist C9

IMO 2014 Shortlist C9 Category: Combinatorics Problem There are n circles drawn on a piece of paper in such a way that any two circles intersect in two points, and no three circles pass through the same point. Turbo the snail slides along the circles in the following fashion. Initially he moves on one of the circles in clockwise direction. Turbo always keeps sliding along the current circle until he...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2009 Shortlist ›

IMO 2009 Shortlist C6

IMO 2009 Shortlist C6 Category: Combinatorics Problem On a 999×999 board a limp rook can move in the following way: From any square it can move to any of its adjacent squares, i.e. a square having a common side with it, and every move must be a turn, i.e. the directions of any two consecutive moves must be perpendicular. A non- intersecting route of the limp rook consists of a...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2008 Shortlist ›

IMO 2008 Shortlist C4

IMO 2008 Shortlist C4 Category: Combinatorics Problem Let n and k be fixed positive integers of the same parity, k ≥ n. We are given 2n lamps numbered 1 through 2n; each of them can be on or off. At the beginning all lamps are off. We consider sequences of k steps. At each step one of the lamps is switched (from off to on or from on to off)....

Practice › Mathematics › IMO › IMO Shortlist › IMO 2011 Shortlist ›

IMO 2011 Shortlist C7

IMO 2011 Shortlist C7 Category: Combinatorics Problem On a square table of 2011 by 2011 cells we place a finite number of napkins that each cover a square of 52 by 52 cells. In each cell we write the number of napkins covering it, and we record the maximal number k of cells that all contain the same nonzero number. Considering all possible napkin configurations, what is the largest value...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2022 Shortlist ›

IMO 2022 Shortlist C6

IMO 2022 Shortlist C6 Category: Combinatorics Problem Let n be a positive integer. We start with n piles of pebbles, each initially containing a single pebble. One can perform moves of the following form: choose two piles, take an equal number of pebbles from each pile and form a new pile out of these pebbles. For each positive integer n, find the smallest number of non-empty piles that one can...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2015 Shortlist ›

IMO 2015 Shortlist C2

IMO 2015 Shortlist C2 Category: Combinatorics Problem Let V be a finite set of points in the plane. We say that V is balanced if for any two distinct points A,B P V, there exists a point C P V such that AC “ BC. We say that V is center-free if for any distinct points A,B,C P V, there does not exist a point P P V such that...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2015 Shortlist ›

IMO 2015 Shortlist C5

IMO 2015 Shortlist C5 Category: Combinatorics Problem Consider an infinite sequence a1,a2,... of positive integers with ai ď 2015 for all i ě 1. Suppose that for any two distinct indices i and j we have i ai ‰ j aj. Prove that there exist two positive integers b and N such that ˇ ˇ ˇ ˇ ˇ n ÿ i“m`1 pai ´ bq ˇ ˇ ˇ ˇ ˇ ď...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2024 Shortlist ›

IMO 2024 Shortlist C6

IMO 2024 Shortlist C6 Category: Combinatorics Problem Let n and T be positive integers. James has 4n marbles with weights 1, 2, ..., 4n. He places them on a balance scale, so that both sides have equal weight. Andrew may move a marble from one side of the scale to the other, so that the absolute difference in weights of the two sides remains at most T. Find, in terms...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2014 Shortlist ›

IMO 2014 Shortlist C3

IMO 2014 Shortlist C3 Category: Combinatorics Problem Let n ě 2 be an integer. Consider an n ˆ n chessboard divided into n2 unit squares. We call a configuration of n rooks on this board happy if every row and every column contains exactly one rook. Find the greatest positive integer k such that for every happy configuration of rooks, we can find a k ˆ k square without a...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2023 Shortlist ›

IMO 2023 Shortlist C1

IMO 2023 Shortlist C1 Category: Combinatorics Problem Let m and n be positive integers greater than 1. In each unit square of an mˆn grid lies a coin with its tail-side up. A move consists of the following steps: select a 2 ˆ 2 square in the grid; flip the coins in the top-left and bottom-right unit squares; flip the coin in either the top-right or bottom-left unit square. Determine...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2019 Shortlist ›

IMO 2019 Shortlist C8

IMO 2019 Shortlist C8 Category: Combinatorics Problem Alice has a map of Wonderland, a country consisting of n ě 2 towns. For every pair of towns, there is a narrow road going from one town to the other. One day, all the roads are declared to be “one way” only. Alice has no information on the direction of the roads, but the King of Hearts has oﬀered to help her....

Practice › Mathematics › IMO › IMO Shortlist › IMO 2009 Shortlist ›

IMO 2009 Shortlist C3

IMO 2009 Shortlist C3 Category: Combinatorics Problem Let n be a positive integer. Given a sequence ε1,...,εn−1 with εi = 0 or εi = 1 for each i = 1,...,n − 1, the sequences a0,...,an and b0,...,bn are constructed by the following rules: a0 = b0 = 1, a1 = b1 = 7, ai+1 = ( 2ai−1 + 3ai, if εi = 0, 3ai−1 + ai, if εi = 1,...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2010 Shortlist ›

IMO 2010 Shortlist C7

IMO 2010 Shortlist C7 Category: Combinatorics Problem Let P1,...,Ps be arithmetic progressions of integers, the following conditions being satisfied: (i) each integer belongs to at least one of them; (ii) each progression contains a number which does not belong to other progressions. Denote by n the least common multiple of steps of these progressions; let n pα1 1 ...pαk k be its prime factorization. Prove that s ©1 k ¸...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2020 Shortlist ›

IMO 2020 Shortlist C5

IMO 2020 Shortlist C5 Category: Combinatorics Problem Let p be an odd prime, and put N “ 1 pp3 ´ pq ´ 1. The numbers 1,2,...,N are painted arbitrarily in two colors, red and blue. For any positive integer n ď N, denote by rpnq the fraction of integers in t1,2,...,nu that are red. Prove that there exists a positive integer a P t1,2,...,p ´ 1u such that rpnq ‰...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2021 Shortlist ›

IMO 2021 Shortlist C4

IMO 2021 Shortlist C4 Category: Combinatorics Problem ThekingdomofAnisotropyconsistsofn cities. Foreverytwocitiesthereexistsexactly one direct one-way road between them. We say that a path from X to Y is a sequence of roads such that one can move from X to Y along this sequence without returning to an already visited city. A collection of paths is called diverse if no road belongs to two or more paths in the collection. Let A...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2018 Shortlist ›

IMO 2018 Shortlist C2

IMO 2018 Shortlist C2 Category: Combinatorics Problem Queenie and Horst play a game on a 20ˆ20 hessboard. In the beginning the board is empty. In every turn, Horst pla es a bla k knight on an empty square in su h a way that his new knight does not atta k any previous knights. Then Queenie pla es a white queen on an empty square. The game gets nished when...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2007 Shortlist ›

IMO 2007 Shortlist C2

IMO 2007 Shortlist C2 Category: Combinatorics Problem A unit square is dissected into n > 1 rectangles such that their sides are parallel to the sides of the square. Any line, parallel to a side of the square and intersecting its interior, also intersects the interior of some rectangle. Prove that in this dissection, there exists a rectangle having no point on the boundary of the square. (Japan)

Practice › Mathematics › IMO › IMO Shortlist › IMO 2006 Shortlist ›

IMO 2006 Shortlist C4

IMO 2006 Shortlist C4 Category: Combinatorics Problem A cake has the form of an n × n square composed of n2 unit squares. Strawberries lie on some of the unit squares so that each row or column contains exactly one strawberry; call this arrangement A. Let B be another such arrangement. Suppose that every grid rectangle with one vertex at the top left corner of the cake contains no fewer...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2024 Shortlist ›

IMO 2024 Shortlist C1

IMO 2024 Shortlist C1 Category: Combinatorics Problem Let n be a positive integer. A class of n students run n races, in each of which they are ranked with no draws. A student is eligible for a rating pa,bq for positive integers a and b if they come in the top b places in at least a of the races. Their final score is the maximum possible value of a...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2019 Shortlist ›

IMO 2019 Shortlist C4

IMO 2019 Shortlist C4 Category: Combinatorics Problem On a ﬂat plane in Camelot, King Arthur builds a labyrinth L consisting of n walls, each of which is an inﬁnite straight line. No two walls are parallel, and no three walls have a common point. Merlin then paints one side of each wall entirely red and the other side entirely blue. At the intersection of two walls there are four corners:...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2016 Shortlist ›

IMO 2016 Shortlist C3

IMO 2016 Shortlist C3 Category: Combinatorics Problem Let n be a positive integer relatively prime to 6. We paint the vertices of a regular n-gon with three colours so that there is an odd number of vertices of each colour. Show that there exists an isosceles triangle whose three vertices are of different colours.

Practice › Mathematics › IMO › IMO Shortlist › IMO 2021 Shortlist ›

IMO 2021 Shortlist C6

IMO 2021 Shortlist C6 Category: Combinatorics Problem A hunter and an invisible rabbit play a game on an infinite square grid. First the hunter fixes acolouringofthecellswithfinitelymanycolours. The rabbitthen secretly chooses a cell to start in. Every minute, the rabbit reports the colour of its current cell to the hunter, and then secretly moves to an adjacent cellthat ithas not visited before (two cellsare adjacent if they share a side). The...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2022 Shortlist ›

IMO 2022 Shortlist C9

IMO 2022 Shortlist C9 Category: Combinatorics Problem Let Zě0 be the set of non-negative integers, and let f : Zě0 ˆ Zě0 Ñ Zě0 be a bijection such that whenever fpx1,y1q ą fpx2,y2q, we have fpx1 1,y1q ą fpx2 1,y2q and fpx1,y1 1q ą fpx2,y2 1q. Let N be the number of pairs of integers px,yq, with 0 ď x,y ă 100, such that fpx,yq is odd. Find the smallest...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2017 Shortlist ›

IMO 2017 Shortlist C8

IMO 2017 Shortlist C8 Category: Combinatorics Problem Let n be a given positive integer. In the Cartesian plane, ea h latti e point with nonnegative oordinates initially ontains a buttery, and there are no other butter- ies. The neighborhood of a latti e point c onsists of all latti e points within the axis-aligned p2n 1qˆp2n 1q square entered at c, apart from c itself. We all a buttery lonely,...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2021 Shortlist ›

IMO 2021 Shortlist C2

IMO 2021 Shortlist C2 Category: Combinatorics Problem Let n ě3 be an integer. An integer m ěn 1 is called n-colourful if, given infinitely many marbles in each of n colours C1,C2,...,Cn, it is possible to place m of them around a circle so that in any group of n 1 consecutive marbles there is at least one marble of colour Ci for each i “1,...,n. Prove that there are...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2022 Shortlist ›

IMO 2022 Shortlist C4

IMO 2022 Shortlist C4 Category: Combinatorics Problem Let n ą 3 be a positive integer. Suppose that n children are arranged in a circle, and n coins are distributed between them (some children may have no coins). At every step, a child with at least 2 coins may give 1 coin to each of their immediate neighbours on the right and left. Determine all initial distributions of coins from which...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2014 Shortlist ›

IMO 2014 Shortlist C5

IMO 2014 Shortlist C5 Category: Combinatorics Problem Consider n ě 3 lines in the plane such that no two lines are parallel and no three have a common point. These lines divide the plane into polygonal regions; let F be the set of regions having finite area. Prove that it is possible to colour Pa n{2 T of the lines blue in such a way that no region in F...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2006 Shortlist ›

IMO 2006 Shortlist C5

IMO 2006 Shortlist C5 Category: Combinatorics Problem An (n,k)-tournament is a contest with n players held in k rounds such that: (i) Each player plays in each round, and every two players meet at most once. (ii) If player A meets player B in round i, player C meets player D in round i, and player A meets player C in round j, then player B meets player D in...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2006 Shortlist ›

IMO 2006 Shortlist C1

IMO 2006 Shortlist C1 Category: Combinatorics Problem We have n ≥ 2 lamps L1,...,Ln in a row, each of them being either on or off . Every second we simultaneously modify the state of each lamp as follows: — if the lamp Li and its neighbours (only one neighbour for i = 1 or i = n, two neighbours for other i) are in the same state, then Li is...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2012 Shortlist ›

IMO 2012 Shortlist C5

IMO 2012 Shortlist C5 Category: Combinatorics Problem The columns and the rows of a 3n × 3n square board are numbered 1,2,...,3n. Every square (x,y) with 1 ≤ x,y ≤ 3n is colored asparagus, byzantium or citrine according as the modulo 3 remainder of x+y is 0, 1 or 2 respectively. One token colored asparagus, byzantium or citrine is placed on each square, so that there are 3n2 tokens of...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2016 Shortlist ›

IMO 2016 Shortlist C7

IMO 2016 Shortlist C7 Category: Combinatorics Problem Let n ⩾ 2 be an integer. In the plane, there are n segments given in such a way that any two segments have an intersection point in the interior, and no three segments intersect at a single point. Jeff places a snail at one of the endpoints of each of the segments and claps his hands n−1 times. Each time when he...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2022 Shortlist ›

IMO 2022 Shortlist C7

IMO 2022 Shortlist C7 Category: Combinatorics Problem Lucy starts by writing s integer-valued 2022-tuples on a blackboard. After doing that, she can take any two (not necessarily distinct) tuples v “ pv1,...,v2022q and w “ pw1,...,w2022q that she has already written, and apply one of the following operations to obtain a new tuple: v w “ pv1 w1,...,v2022 ` w2022q v _ w “ pmaxpv1,w1q,...,maxpv2022,w2022qq and then write this tuple...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2014 Shortlist ›

IMO 2014 Shortlist C8

IMO 2014 Shortlist C8 Category: Combinatorics Problem A card deck consists of 1024 cards. On each card, a set of distinct decimal digits is written in such a way that no two of these sets coincide (thus, one of the cards is empty). Two players alternately take cards from the deck, one card per turn. After the deck is empty, each player checks if he can throw out one of...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2024 Shortlist ›

IMO 2024 Shortlist C3

IMO 2024 Shortlist C3 Category: Combinatorics Problem Let n be a positive integer. There are 2n knights sitting at a round table. They consist of n pairs of partners, each pair of which wishes to shake hands. A pair can shake hands only when next to each other. Every minute, one pair of adjacent knights swaps places. Find the minimum number of exchanges of adjacent knights such that, regardless of...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2021 Shortlist ›

IMO 2021 Shortlist C5

IMO 2021 Shortlist C5 Category: Combinatorics Problem Let n and k be two integers with n ą k ě 1. There are 2n 1 students standing in a circle. Each student S has 2k neighbours— namely, the k students closest to S on the right, and the k students closest to S on the left. Suppose that n 1 of the students are girls, and the other n are boys....

Practice › Mathematics › IMO › IMO Shortlist › IMO 2024 Shortlist ›

IMO 2024 Shortlist C5

IMO 2024 Shortlist C5 Category: Combinatorics Problem Let N be a positive integer. Geoff and Ceri play a game in which they start by writing the numbers 1, 2, ..., N on a board. They then take turns to make a move, starting with Geoff. Each move consists of choosing a pair of integers pk,nq, where k ě 0 and n is one of the integers on the board, and...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2007 Shortlist ›

IMO 2007 Shortlist C6

IMO 2007 Shortlist C6 Category: Combinatorics Problem In a mathematical competition some competitors are friends; friendship is always mutual. Call a group of competitors a clique if each two of them are friends. The number of members in a clique is called its size. It is known that the largest size of cliques is even. Prove that the competitors can be arranged in two rooms such that the largest size...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2008 Shortlist ›

IMO 2008 Shortlist C5

IMO 2008 Shortlist C5 Category: Combinatorics Problem Let S = {x1,x2,...,xk+ } be a (k + )-element set of real numbers contained in the interval [0,1]; k and are positive integers. A k-element subset A ⊂ S is called nice if k X xi∈A xi − X xj∈S\A xj ≤ k + 2k . Prove that the number of nice subsets is at least k + k + k...

#combinatorics

CF 2217G - Down the Pivot

April Fools Day Contest

LeetCode 3621 - Number of Integers With Popcount-Depth Equal to K I

CF 1943D2 - Counting Is Fun (Hard Version)

Codeforces Round 277.5 (Div. 2)

CF 482D - Random Function and Tree

CF 1948F - Rare Coins

CF 1958F - Narrow Paths

CF 1976D - Invertible Bracket Sequences

CF 1967E2 - Again Counting Arrays (Hard Version)

CF 1954D - Colored Balls

Codeforces Round 946 (Div. 3)

CF 1942E - Farm Game

CF 1974C - Beautiful Triple Pairs

CF 1967E1 - Again Counting Arrays (Easy Version)

CF 1975F - Set

CF 1967C - Fenwick Tree

Kotlin Heroes: Episode 10

CF 1954F - Unique Strings

CF 1943D1 - Counting Is Fun (Easy Version)

Educational Codeforces Round 164 (Rated for Div. 2)

CF 1942G - Bessie and Cards

CF 489F - Special Matrices

Codeforces Round 275 (Div. 1)

CF 1976E - Splittable Permutations

CF 1951G - Clacking Balls

LeetCode 3881 - Direction Assignments with Exactly K Visible People

LeetCode 3855 - Sum of K-Digit Numbers in a Range

LeetCode 3757 - Number of Effective Subsequences

LeetCode 3821 - Find Nth Smallest Integer With K One Bits

LeetCode 3725 - Count Ways to Choose Coprime Integers from Rows

LeetCode 3539 - Find Sum of Array Product of Magical Sequences

LeetCode 3577 - Count the Number of Computer Unlocking Permutations

LeetCode 3518 - Smallest Palindromic Rearrangement II

LeetCode 3461 - Check If Digits Are Equal in String After Operations I

LeetCode 3470 - Permutations IV

LeetCode 3463 - Check If Digits Are Equal in String After Operations II

LeetCode 3428 - Maximum and Minimum Sums of at Most Size K Subsequences

LeetCode 3416 - Subsequences with a Unique Middle Mode II

Codeforces Round 261 (Div. 2)

Codeforces Round 258 (Div. 2)

MemSQL Start[c]UP 2.0 - Round 2

CF 452C - Magic Trick

CF 478B - Random Teams

CF 449D - Jzzhu and Numbers

CF 466D - Increase Sequence

CF 476B - Dreamoon and WiFi

CF 479E - Riding in a Lift

CF 459B - Pashmak and Flowers

CF 459C - Pashmak and Buses

Codeforces Round 272 (Div. 2)

CF 451E - Devu and Flowers

CF 457D - Bingo!

Codeforces Round 273 (Div. 2)

LeetCode 3405 - Count the Number of Arrays with K Matching Adjacent Elements

IMO 2004 SL C5

IMO 1996 SL C1

IMO 2002 SL C1

IMO 2000 SL C2

IMO 2004 SL C7

IMO 2000 SL C3

IMO 2004 SL C6

IMO 2002 SL C3

IMO 2003 SL C5

IMO 1996 SL C7

IMO 2001 SL C1

IMO 1994 SL C2

IMO 2002 SL C5

IMO 2002 SL C6

IMO 1994 SL C4

IMO 1996 SL C4

IMO 1999 SL C1

IMO 2003 SL C4

IMO 1999 SL C4

IMO 2003 SL C2

IMO 2003 SL C3

IMO 2002 SL C4

IMO 2000 SL C6

IMO 1996 SL C6