probabilities

Practice › Codeforces Solutions ›

Codeforces Beta Round 81

Codeforces Beta Round 81 Type: Beta | Problems: 5 | Verified: 4/5 | Rating range: 1700-2700 | Time: 13m 32s Problem Name Rating Tags Solve Time Verified A Transmigration 1700 implementation 3m 6s ✓ B Dark Assembly 1800 brute-force, probabilities 2m 19s ✓ C Item World 2200 brute-force, implementation, sortings 3m 26s ✗ D Entertaining Geodetics 2700 brute-force, dsu, implementation 2m 8s ✓ E Lift and Throw 2500 brute-force 2m...

Practice › Codeforces Solutions › Codeforces Beta Round 81 ›

CF 105B - Dark Assembly

CF 105B - Dark Assembly Rating: 1800 Tags: brute force, probabilities Solve time: 2m 19s Verified: yes Solution Problem Understanding We have a small assembly of n senators, each defined by a level and a loyalty score. Loyalty is a probability that a senator votes in favor of a proposal, given in 10% increments. If more than half of senators vote yes, the proposal passes. If the vote fails, the...

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

CF 494C - Helping People

CF 494C - Helping People Rating: 2600 Tags: dp, probabilities Solve time: 42s Verified: yes Solution Problem Understanding We are tasked with calculating the expected maximum wealth of a group of people after a series of charitable recommendations. Each person starts with a known amount of money. There are several recommendations, each specifying a segment of people to receive one dollar, and each recommendation has a probability that it will...

Practice › Codeforces Solutions ›

Codeforces Round 282 (Div. 1)

Codeforces Round 282 (Div. 1) Type: Div. 1 | Problems: 4 | Verified: 1/4 | Rating range: 2000-3200 | Time: 24m 13s Problem Name Rating Tags Solve Time Verified B Obsessive String 2000 dp, strings 10m 58s ✗ C Helping People 2600 dp, probabilities 42s ✓ D Birthday 2700 data-structures, dfs-and-similar, dp 1m 4s ✗ E Sharti 3200 data-structures, games 11m 29s ✗

Practice › Codeforces Solutions ›

European Championship 2024 - Online Mirror (Unrated, ICPC Rules, Teams Preferred)

European Championship 2024 - Online Mirror (Unrated, ICPC Rules, Teams Preferred) Type: ICPC/IOI | Problems: 11 | Verified: 5/11 | Rating range: 1500-3300 | Time: 28m 1s Problem Name Rating Tags Solve Time Verified A Grove 3300 brute-force, dfs-and-similar, dp 2m 41s ✓ B Charming Meals 1500 binary-search, brute-force, greedy 1m 44s ✓ C Annual Ants' Gathering 1900 dfs-and-similar, dp, greedy 4m 48s ✓ D Funny or Scary? 2600 constructive-algorithms...

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 › Codeforces Solutions › European Championship 2024 - Online Mirror (Unrated, ICPC Rules, Teams Preferred) ›

CF 1949A - Grove

CF 1949A - Grove Rating: 3300 Tags: brute force, dfs and similar, dp, geometry, probabilities Solve time: 2m 41s Verified: yes Solution Problem Understanding Every tree is planted at an integer lattice point. Around that point we place a disk of radius r , representing the root system. Two conditions must hold. The entire disk must stay inside the square lawn. Since the lawn is the square [0,n] × [0,n]...

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

CF 482C - Game with Strings

CF 482C - Game with Strings Rating: 2600 Tags: bitmasks, dp, probabilities Solve time: 1m 44s Verified: no Solution Problem Understanding We are given a collection of distinct strings of the same length. One string is secretly chosen uniformly at random. Our goal is to determine the expected number of questions needed to identify the chosen string. Each question asks for the character at a position that has not been...

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

Codeforces Round 259 (Div. 1)

Codeforces Round 259 (Div. 1) Type: Div. 1 | Problems: 5 | Verified: 4/5 | Rating range: 1600-3100 | Time: 8m 34s Problem Name Rating Tags Solve Time Verified A Little Pony and Expected Maximum 1600 probabilities 1m 46s ✓ B Little Pony and Harmony Chest 2000 bitmasks, brute-force, dp 1m 19s ✓ C Little Pony and Summer Sun Celebration 2200 constructive-algorithms, dfs-and-similar, graphs 2m 13s ✗ D Little Pony...

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 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 259 (Div. 1) ›

CF 453A - Little Pony and Expected Maximum

CF 453A - Little Pony and Expected Maximum Rating: 1600 Tags: probabilities Solve time: 1m 46s Verified: yes Solution Problem Understanding We roll a fair die with faces numbered from 1 to m , exactly n times. Every roll is independent, and each face appears with probability 1 / m . Among those n rolls, we look only at the largest value that appeared. The task is to compute the...

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 › Codeforces Round 265 (Div. 1) ›

CF 464D - World of Darkraft - 2

CF 464D - World of Darkraft - 2 Rating: 2700 Tags: dp, probabilities Solve time: 5m 15s Verified: no Solution

Practice › Codeforces Solutions ›

Codeforces Round 265 (Div. 1)

Codeforces Round 265 (Div. 1) Type: Div. 1 | Problems: 3 | Verified: 0/3 | Rating range: 2000-3000 | Time: 15m 43s Problem Name Rating Tags Solve Time Verified B Restore Cube 2000 brute-force, geometry 5m 14s ✗ D World of Darkraft - 2 2700 dp, probabilities 5m 15s ✗ E The Classic Problem 3000 data-structures, graphs, shortest-paths 5m 14s ✗

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 #FF (Div. 1)

Codeforces Round #FF (Div. 1) Type: Div. 1 | Problems: 3 | Verified: 0/3 | Rating range: 2400-3100 | Time: 9m 38s Problem Name Rating Tags Solve Time Verified C DZY Loves Fibonacci Numbers 2400 data-structures, math, number-theory 6m 32s ✗ D DZY Loves Games 2800 math, matrices, probabilities 1m 41s ✗ E DZY Loves Bridges 3100 math, matrices 1m 25s ✗

Practice › Codeforces Solutions › Codeforces Round #FF (Div. 1) ›

CF 446D - DZY Loves Games

CF 446D - DZY Loves Games Rating: 2800 Tags: math, matrices, probabilities Solve time: 1m 41s Verified: no Solution Problem Understanding We are given an undirected connected graph representing a maze of rooms. DZY starts at room 1 with a fixed number of lives. Each time he is in a room, he randomly chooses one of its outgoing corridors uniformly and moves to the adjacent room. Every time he enters...

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 › MemSQL start[c]up Round 2 - online version ›

CF 335E - Counting Skyscrapers

CF 335E - Counting Skyscrapers Rating: 2800 Tags: dp, math, probabilities Solve time: 2m 50s Verified: no Solution Problem Understanding We have a sequence of skyscrapers, each with a height chosen randomly and independently according to a geometric distribution where floor i exists with probability 2⁻ⁱ. The number of skyscrapers is unknown, but uniformly distributed between 2 and 314!. We are asked to relate two counting strategies across these skyscrapers....

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

CF 277D - Google Code Jam

CF 277D - Google Code Jam Rating: 2800 Tags: dp, probabilities Solve time: 2m 17s Verified: no Solution Problem Understanding Each problem in the contest has two stages. You may solve the Small version first, gaining some fixed score. After that, you may continue and attempt the Large version, gaining additional score if it succeeds. Small submissions are always correct, but Large submissions succeed only probabilistically. The contest lasts t...

Practice › Codeforces Solutions › Codeforces Round 115 ›

CF 175D - Plane of Tanks: Duel

CF 175D - Plane of Tanks: Duel Rating: 2400 Tags: brute force, dp, math, probabilities Solve time: 2m 32s Verified: yes Solution Problem Understanding Two tanks fight each other. Each tank has hit points, a reload time, a damage interval, and a probability that its shot fails to penetrate armor. Whenever a tank fires, one of two things happens. Either the shell does not penetrate, in which case the target...

Practice › Codeforces Solutions ›

Codeforces Round 170 (Div. 1)

Codeforces Round 170 (Div. 1) Type: Div. 1 | Problems: 3 | Verified: 1/3 | Rating range: 1400-2800 | Time: 6m 6s Problem Name Rating Tags Solve Time Verified A Learning Languages 1400 dfs-and-similar, dsu 1m 44s ✓ D Google Code Jam 2800 dp, probabilities 2m 17s ✗ E Binary Tree on Plane 2400 flows, trees 2m 5s ✗

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

CF 248E - Piglet's Birthday

CF 248E - Piglet's Birthday Rating: 2600 Tags: dp, math, probabilities Solve time: 2m 17s Verified: no Solution Problem Understanding We are asked to compute the expected number of shelves that have no untasted honey pots after a series of actions. Each shelf starts with some number of honey pots. Winnie moves a small number of pots from one shelf to another, tasting them in the process. Every pot on...

Practice › Codeforces Solutions ›

Friday the 13th, Programmers Day

Friday the 13th, Programmers Day Type: Special | Problems: 3 | Verified: 2/3 | Rating range: 1500-2700 | Time: 5m 36s Problem Name Rating Tags Solve Time Verified A Expecting Trouble 1500 *special, probabilities 1m 31s ✓ D Chain Letter 2200 *special, dfs-and-similar, graphs 2m 12s ✓ F Superstitions Inspection 2700 *special 1m 53s ✗

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 164 (Div. 2) ›

CF 268E - Playlist

CF 268E - Playlist Rating: 2100 Tags: math, probabilities, sortings Solve time: 1m 45s Verified: yes Solution Problem Understanding We are asked to determine the maximum expected total listening time for Manao's playlist, given that each song has a certain probability of being liked and a fixed length. The playlist is dynamic: every time Manao encounters a song he dislikes, he replays all previously liked songs before moving on. The...

Practice › Codeforces Solutions ›

Codeforces Round 253 (Div. 1)

Codeforces Round 253 (Div. 1) Type: Div. 1 | Problems: 2 | Verified: 1/2 | Rating range: 1800-3100 | Time: 3m 6s Problem Name Rating Tags Solve Time Verified B Andrey and Problem 1800 greedy, math, probabilities 1m 14s ✓ E Gena and Second Distance 3100 geometry 1m 52s ✗

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

CF 258D - Little Elephant and Broken Sorting

CF 258D - Little Elephant and Broken Sorting Rating: 2600 Tags: dp, math, probabilities Solve time: 3m 30s Verified: yes Solution Problem Understanding We are given a permutation of the numbers from 1 to n, and a sequence of m operations. Each operation targets two positions in the array. When the program runs, each operation is uncertain: independently, it either does nothing or swaps the two elements at those positions,...

Practice › Codeforces Solutions › Croc Champ 2012 - Final ›

CF 183D - T-shirt

CF 183D - T-shirt Rating: 2700 Tags: dp, greedy, probabilities Solve time: 1m 15s Verified: yes Solution Problem Understanding We are tasked with distributing T-shirts to a line of engineers where each engineer has a probability distribution over which T-shirt size fits them. We know how many engineers, n , there are, and the total number of T-shirt sizes, m . Each engineer has exactly one size that fits them,...

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

CF 150C - Smart Cheater

CF 150C - Smart Cheater Rating: 2200 Tags: data structures, math, probabilities Solve time: 2m 11s Verified: yes Solution Problem Understanding We have a straight bus route with fixed stop coordinates. A passenger normally pays the full distance between their boarding and exit stops. The conductor is allowed to "hide" at most one continuous segment of that trip from the ticket. If a passenger travels from stop a to stop...

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

CF 442B - Andrey and Problem

CF 442B - Andrey and Problem Rating: 1800 Tags: greedy, math, probabilities Solve time: 1m 14s Verified: yes Solution Problem Understanding We are given a set of friends, where each friend independently succeeds in producing a contest problem with a known probability. Andrey will invite some subset of these friends. Once invited, each friend either contributes a problem or does not, independently of the others. The outcome we care about...

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

CF 167B - Wizards and Huge Prize

CF 167B - Wizards and Huge Prize Rating: 1800 Tags: dp, math, probabilities Solve time: 1m 38s Verified: no Solution Problem Understanding We are asked to calculate the probability of performing well in a sequence of wizard contests, given both your chances of winning each contest and the types of prizes you may receive. There are n contests, and for each contest, you know your probability of winning and whether...

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

CF 138C - Mushroom Gnomes - 2

CF 138C - Mushroom Gnomes - 2 Rating: 2200 Tags: binary search, data structures, probabilities, sortings Solve time: 2m Verified: yes Solution Problem Understanding We have trees placed on a number line. Each tree may fall left, fall right, or remain standing. The probabilities for these three outcomes are given independently for every tree. A falling tree destroys mushrooms in a half-open interval determined by the tree position and height....

Practice › Codeforces Solutions ›

MemSQL start[c]up Round 2 - online version

MemSQL start[c]up Round 2 - online version Type: Special | Problems: 3 | Verified: 1/3 | Rating range: 1900-2800 | Time: 8m 55s Problem Name Rating Tags Solve Time Verified B Palindrome 1900 constructive-algorithms, dp 2m 24s ✗ D Rectangles and Square 2400 brute-force, dp 3m 41s ✓ E Counting Skyscrapers 2800 dp, math, probabilities 2m 50s ✗

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

CF 261B - Maxim and Restaurant

CF 261B - Maxim and Restaurant Rating: 1900 Tags: dp, math, probabilities Solve time: 2m 19s Verified: no Solution

Practice › Codeforces Solutions ›

Codeforces Round 114 (Div. 1)

Codeforces Round 114 (Div. 1) Type: Div. 1 | Problems: 5 | Verified: 3/5 | Rating range: 1600-3000 | Time: 10m 57s Problem Name Rating Tags Solve Time Verified A Wizards and Trolleybuses 1600 implementation, math 1m 40s ✓ B Wizards and Huge Prize 1800 dp, math, probabilities 1m 38s ✗ C Wizards and Numbers 2300 games, math 1m 39s ✗ D Wizards and Roads 3000 data-structures, divide-and-conquer, graph-matchings 2m...

Practice › Codeforces Solutions › Friday the 13th, Programmers Day ›

CF 345A - Expecting Trouble

CF 345A - Expecting Trouble Rating: 1500 Tags: *special, probabilities Solve time: 1m 31s Verified: yes Solution Problem Understanding We are given a sequence of recollections of Fridays the 13th. Each day is represented by a character: "0" for a normal day, "1" for a bad day, and "?" for an unknown day. Along with this sequence, we are provided a probability p that a "?" corresponds to a bad...

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

CF 424E - Colored Jenga

CF 424E - Colored Jenga Rating: 2500 Tags: dfs and similar, dp, probabilities Solve time: 6m 29s Verified: no Solution Problem Understanding We are given a vertical stack of levels, each level containing three colored blocks arranged left, middle, right. The tower has a physical constraint: it is only stable if every non-top level has at least one remaining block, and additionally a level is unstable if it is reduced...

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

CF 303E - Random Ranking

CF 303E - Random Ranking Rating: 3000 Tags: dp, math, probabilities Solve time: 3m 7s Verified: no Solution Problem Understanding Each participant receives a real-valued score chosen uniformly from an interval $[l_i, r_i]$. Scores are independent. After all scores are generated, participants are sorted by score. Smaller score means better rank, so the participant with the largest score finishes last. For every participant $i$ and every rank $j$, we must...

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

CF 204C - Little Elephant and Furik and Rubik

CF 204C - Little Elephant and Furik and Rubik Rating: 2000 Tags: math, probabilities Solve time: 1m 23s Verified: no Solution Problem Understanding We are given two strings of equal length. From each string we independently pick a substring, and both substrings must have the same length. After choosing them, we compare them character by character and count how many positions match. The selection is uniform over all possible choices...

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

CF 441E - Valera and Number

CF 441E - Valera and Number Rating: 2400 Tags: bitmasks, dp, math, probabilities Solve time: 1m 40s Verified: no Solution Problem Understanding We are asked to model a simple randomized iterative process. We start with a number $x$ and perform $k$ steps. In each step, a random number between 1 and 100 is drawn. With probability $p/100$, the current number is doubled; otherwise, it is incremented by 1. After performing...

Practice › Codeforces Solutions ›

Codeforces Beta Round 99 (Div. 1)

Codeforces Beta Round 99 (Div. 1) Type: Div. 1 | Problems: 5 | Verified: 4/5 | Rating range: 1600-2900 | Time: 9m 53s Problem Name Rating Tags Solve Time Verified A Literature Lesson 1600 implementation 2m ✓ B Digits Permutations 1900 greedy 2m 29s ✗ C Mushroom Gnomes - 2 2200 binary-search, data-structures, probabilities 2m ✓ D World of Darkraft 2500 dp, games 2m 6s ✓ E Hellish Constraints 2900...

Practice › Codeforces Solutions › RCC 2014 Warmup (Div. 2) ›

CF 417E - Square Table

CF 417E - Square Table Rating: 2400 Tags: constructive algorithms, math, probabilities Solve time: 1m 48s Verified: yes Solution Problem Understanding We are asked to fill an $n \times m$ grid with positive integers not exceeding $10^8$. The constraint is not about individual cells but about structure: for every row and every column, if we square all numbers in that line and sum them, the result must itself be a...

Practice › Codeforces Solutions ›

Codeforces Round 164 (Div. 2)

Codeforces Round 164 (Div. 2) Type: Div. 2 | Problems: 4 | Verified: 3/4 | Rating range: 800-2300 | Time: 7m 8s Problem Name Rating Tags Solve Time Verified A Games 800 brute-force 1m 29s ✓ C Beautiful Sets of Points 1500 constructive-algorithms, implementation 1m 33s ✗ D Wall Bars 2300 dp 2m 21s ✓ E Playlist 2100 math, probabilities, sortings 1m 45s ✓

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

CF 293D - Ksusha and Square

CF 293D - Ksusha and Square Rating: 2700 Tags: geometry, math, probabilities, two pointers Solve time: 1m 59s Verified: yes Solution Problem Understanding We are given a convex polygon with integer coordinates. Inside this polygon, including its boundary, there are finitely many lattice points. We choose two distinct lattice points uniformly at random, then construct a square whose diagonal is the segment between those two points. The task is to...

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

CF 148D - Bag of mice

CF 148D - Bag of mice Rating: 1800 Tags: dp, games, math, probabilities Solve time: 1m 55s Verified: yes Solution Problem Understanding We have a bag containing white and black mice. The princess moves first, then the dragon, then the princess again, and so on. Whoever draws a white mouse immediately wins. If someone draws a black mouse, the game continues. There is one extra rule during the dragon’s turn....

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 › 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 69 (Div. 1 Only)

Codeforces Beta Round 69 (Div. 1 Only) Type: Div. 1 | Problems: 5 | Verified: 2/5 | Rating range: 1400-2800 | Time: 11m 16s Problem Name Rating Tags Solve Time Verified A Heroes 1400 brute-force, implementation 1m 49s ✓ B Falling Anvils 1800 math, probabilities 2m 36s ✓ C Beavermuncher-0xFF 2100 dfs-and-similar, dp, dsu 2m 30s ✗ D Domino Carpet 2300 dp, implementation 1m 59s ✗ E Martian Food 2800...

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

CF 77B - Falling Anvils

CF 77B - Falling Anvils Rating: 1800 Tags: math, probabilities Solve time: 2m 36s Verified: yes Solution Problem Understanding We are given two real parameters chosen uniformly at random. The victim height p lies in the interval [0, a] , and the wind parameter q lies in [-b, b] . For every pair (p, q) , the anvil hits successfully if a certain quadratic equation has at least one real...

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 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 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 84 (Div. 1 Only) ›

CF 109B - Lucky Probability

CF 109B - Lucky Probability Rating: 1900 Tags: brute force, probabilities Solve time: 2m 23s Verified: yes Solution Problem Understanding We are asked to calculate the probability that if Petya and Vasya each pick an integer randomly from their respective intervals, the interval between the two chosen numbers contains exactly k lucky numbers. Lucky numbers are those containing only the digits 4 and 7. The input provides the bounds of...

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

CF 98B - Help King

CF 98B - Help King Rating: 2200 Tags: implementation, probabilities, trees Solve time: 1m 17s Verified: yes Solution Problem Understanding We are asked to simulate a fair random selection of one knight out of n using a coin that can only produce two outcomes. Each coin flip has an equal probability of landing heads or tails. The goal is to find the expected number of flips required to select a...

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

CF 30C - Shooting Gallery

CF 30C - Shooting Gallery Rating: 1800 Tags: dp, probabilities Solve time: 1m Verified: yes Solution Problem Understanding We are asked to help King Copa maximize his expected number of hits in a shooting gallery. The gallery is represented as a 2D plane, and each target appears at a specific point $(x_i, y_i)$ exactly at a specific time $t_i$ and disappears immediately afterward. If the king’s gun sight is aimed...

Practice › Codeforces Solutions ›

Codeforces Beta Round 78 (Div. 1 Only)

Codeforces Beta Round 78 (Div. 1 Only) Type: Div. 1 | Problems: 5 | Verified: 5/5 | Rating range: 1700-2700 | Time: 10m 13s Problem Name Rating Tags Solve Time Verified A Help Victoria the Wise 1700 brute-force, implementation 2m 12s ✓ B Help King 2200 implementation, probabilities, trees 1m 17s ✓ C Help Greg the Dwarf 2500 geometry, ternary-search 2m 29s ✓ D Help Monks 2500 constructive-algorithms 1m 50s...

Practice › Codeforces Solutions › Codeforces Beta Round 24 ›

CF 24D - Broken robot

CF 24D - Broken robot Rating: 2400 Tags: dp, math, probabilities Solve time: 1m 34s Verified: yes Solution Problem Understanding The board has N rows and M columns. A robot starts at cell (i, j) and repeatedly performs one random move. From an interior cell it has four equally likely choices: stay in place, move left, move right, or move down. On the left border, moving left is impossible, so...

Practice › Codeforces Solutions ›

Codeforces Beta Round 30 (Codeforces format)

Codeforces Beta Round 30 (Codeforces format) Type: Beta | Problems: 5 | Verified: 4/5 | Rating range: 1400-2800 | Time: 7m 26s Problem Name Rating Tags Solve Time Verified A Accounting 1400 brute-force, math 1m 23s ✓ B Codeforces World Finals 1700 implementation 1m 1s ✓ C Shooting Gallery 1800 dp, probabilities 1m ✓ D King's Problem? 2600 geometry, greedy 2m 12s ✗ E Tricky and Clever Password 2800 binary-search,...

Practice › Codeforces Solutions ›

Codeforces Beta Round 84 (Div. 1 Only)

Codeforces Beta Round 84 (Div. 1 Only) Type: Div. 1 | Problems: 5 | Verified: 5/5 | Rating range: 1000-2700 | Time: 11m 6s Problem Name Rating Tags Solve Time Verified A Lucky Sum of Digits 1000 brute-force, implementation 2m 22s ✓ B Lucky Probability 1900 brute-force, probabilities 2m 23s ✓ C Lucky Tree 1900 dp, dsu, trees 2m 23s ✓ D Lucky Sorting 2000 constructive-algorithms, sortings 1m 47s ✓...

Practice › Codeforces Solutions › Codeforces Beta Round 62 ›

CF 68D - Half-decay tree

CF 68D - Half-decay tree Rating: 2500 Tags: data structures, divide and conquer, dp, math, probabilities Solve time: 2m 50s Verified: yes Solution Problem Understanding We have a complete binary tree of height h . Every vertex may store some number of electrons, and queries gradually add more electrons to vertices. A decay operation chooses one leaf uniformly at random and deletes every edge on the path from the root...

Practice › Codeforces Solutions ›

Codeforces Beta Round 50

Codeforces Beta Round 50 Type: Beta | Problems: 5 | Verified: 5/5 | Rating range: 1300-2700 | Time: 8m 47s Problem Name Rating Tags Solve Time Verified A Presents 1300 implementation 1m 19s ✓ B Cutting Jigsaw Puzzle 1800 hashing, implementation 1m 29s ✓ C First Digit Law 2000 dp, math, probabilities 1m 10s ✓ D Writing a Song 2100 brute-force, dp, strings 1m 3s ✓ E Vacuum \u0421leaner 2700...

Practice › Codeforces Solutions › Codeforces Beta Round 47 ›

CF 50D - Bombing

CF 50D - Bombing Rating: 2100 Tags: binary search, dp, probabilities Solve time: 1m 42s Verified: no Solution Problem Understanding We are given a set of enemy objects, each at a fixed 2D coordinate, and a fixed strike point. The objective is to determine the minimum impact radius of a nuclear warhead such that the probability of failing to deactivate at least K of these objects is at most ε...

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

CF 98E - Help Shrek and Donkey

CF 98E - Help Shrek and Donkey Rating: 2700 Tags: dp, games, math, probabilities Solve time: 2m 25s Verified: yes Solution Problem Understanding There are m + n + 1 distinct cards in total. Shrek initially knows his own m cards, Donkey knows his own n cards, and one card is hidden on the table. Nobody knows the hidden card directly. Players alternate turns, with Shrek moving first. On each...

Practice › Codeforces Solutions › Codeforces Beta Round 50 ›

CF 54C - First Digit Law

CF 54C - First Digit Law Rating: 2000 Tags: dp, math, probabilities Solve time: 1m 10s Verified: yes Solution Problem Understanding We are given a set of N random integers, where each integer i can take any value in a given inclusive range [L_i, R_i] , all values equally likely. The task is to compute the probability that at least K% of these N integers start with the digit 1...

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

CF 101D - Castle

CF 101D - Castle Rating: 2300 Tags: dp, greedy, probabilities, sortings, trees Solve time: 2m 6s Verified: yes Solution Problem Understanding We are given a weighted tree rooted at hall 1, where Gerald starts. The treasure is hidden uniformly at random in one of the other halls. Gerald only discovers the treasure when he first enters the correct hall. The restriction that changes the problem completely is that every corridor...

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

CF 9A - Die Roll

CF 9A - Die Roll Rating: 800 Tags: math, probabilities Solve time: 2m 43s Verified: yes Solution Problem Understanding We are asked to calculate the probability that Dot wins a simple dice game against Yakko and Wakko. Each character rolls a standard six-sided die. Dot wins if her roll is at least as large as the maximum of Yakko’s and Wakko’s rolls. Yakko and Wakko’s rolls are given as input,...

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

CF 113D - Museum

CF 113D - Museum Rating: 2700 Tags: math, matrices, probabilities Solve time: 1m 55s Verified: yes Solution Problem Understanding We are asked to model the random movements of two friends inside a museum represented as an undirected connected graph with n rooms and m corridors. Each room has a probability of staying in place for a minute, and otherwise the person moves uniformly to a neighboring room. The task is...

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

CF 16E - Fish

CF 16E - Fish Rating: 1900 Tags: bitmasks, dp, probabilities Solve time: 1m 34s Verified: yes Solution Problem Understanding We have n fish in a lake. Every day, exactly one unordered pair of currently alive fish is chosen uniformly at random. When fish i meets fish j , fish i eats fish j with probability a[i][j] , and fish j eats fish i with probability a[j][i] = 1 - a[i][j]...

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 24

Codeforces Beta Round 24 Type: Beta | Problems: 5 | Verified: 5/5 | Rating range: 1400-2400 | Time: 11m 12s Problem Name Rating Tags Solve Time Verified A Ring road 1400 graphs 3m 36s ✓ B F1 Champions 1500 implementation 2m 19s ✓ C Sequence of points 1800 geometry, implementation, math 2m 35s ✓ D Broken robot 2400 dp, math, probabilities 1m 34s ✓ E Berland collider 2300 binary-search 1m...

Practice › Codeforces Solutions › Yandex.Algorithm 2011: Round 1 ›

CF 85C - Petya and Tree

CF 85C - Petya and Tree Rating: 2200 Tags: binary search, dfs and similar, probabilities, sortings, trees Solve time: 2m 4s Verified: yes Solution Problem Understanding We are given a valid binary search tree where every internal node has exactly two children. Each node stores a unique key. We are also given several query keys that are guaranteed not to appear in the tree. A normal BST search starts at...

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

CF 123E - Maze

CF 123E - Maze Rating: 2500 Tags: dfs and similar, dp, probabilities, trees Solve time: 2m 39s Verified: no Solution Problem Understanding We are given a tree, and two independent probability distributions over its vertices. One distribution chooses the starting vertex of a DFS, the other chooses the target vertex where the search stops. The DFS behaves randomly: before exploring a node, it shuffles the adjacency list uniformly at random,...

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

CF 107E - Darts

CF 107E - Darts Rating: 2700 Tags: geometry, probabilities Solve time: 2m 19s Verified: yes Solution Problem Understanding We have several rectangles on the plane. Each rectangle represents a photo hanging on a wall. The rectangles may overlap, may share edges, may coincide completely, and may also be rotated arbitrarily. A dart is thrown uniformly at random over the entire wall, but we only care about throws that hit at...

#probabilities

Codeforces Beta Round 81

CF 105B - Dark Assembly

CF 494C - Helping People

Codeforces Round 282 (Div. 1)

European Championship 2024 - Online Mirror (Unrated, ICPC Rules, Teams Preferred)

CF 1951G - Clacking Balls

CF 1949A - Grove

CF 482C - Game with Strings

Codeforces Round 275 (Div. 1)

CF 1948F - Rare Coins

Codeforces Round 259 (Div. 1)

CF 457D - Bingo!

CF 476B - Dreamoon and WiFi

CF 453A - Little Pony and Expected Maximum

MemSQL Start[c]UP 2.0 - Round 2

CF 464D - World of Darkraft - 2

Codeforces Round 265 (Div. 1)

CF 452C - Magic Trick

Codeforces Round #FF (Div. 1)

CF 446D - DZY Loves Games

Codeforces Round 157 (Div. 1)

CF 335E - Counting Skyscrapers

CF 277D - Google Code Jam

CF 175D - Plane of Tanks: Duel

Codeforces Round 170 (Div. 1)

CF 248E - Piglet's Birthday

Friday the 13th, Programmers Day

CF 229E - Gifts

CF 268E - Playlist

Codeforces Round 253 (Div. 1)

CF 258D - Little Elephant and Broken Sorting

CF 183D - T-shirt

CF 150C - Smart Cheater

CF 442B - Andrey and Problem

CF 167B - Wizards and Huge Prize

CF 138C - Mushroom Gnomes - 2

MemSQL start[c]up Round 2 - online version

CF 261B - Maxim and Restaurant

Codeforces Round 114 (Div. 1)

CF 345A - Expecting Trouble

CF 424E - Colored Jenga

CF 303E - Random Ranking

CF 204C - Little Elephant and Furik and Rubik

CF 441E - Valera and Number

Codeforces Beta Round 99 (Div. 1)

CF 417E - Square Table

Codeforces Round 164 (Div. 2)

CF 293D - Ksusha and Square

CF 148D - Bag of mice

Codeforces Round 129 (Div. 1)

CF 28C - Bath Queue

Codeforces Beta Round 69 (Div. 1 Only)

CF 77B - Falling Anvils

Codeforces Beta Round 9 (Div. 2 Only)

Codeforces Beta Round 83 (Div. 1 Only)

CF 26D - Tickets

CF 109B - Lucky Probability

CF 98B - Help King

CF 30C - Shooting Gallery

Codeforces Beta Round 78 (Div. 1 Only)

CF 24D - Broken robot

Codeforces Beta Round 30 (Codeforces format)

Codeforces Beta Round 84 (Div. 1 Only)

CF 68D - Half-decay tree

Codeforces Beta Round 50

CF 50D - Bombing

CF 98E - Help Shrek and Donkey

CF 54C - First Digit Law

CF 101D - Castle

CF 9A - Die Roll

CF 113D - Museum

CF 16E - Fish

CF 107B - Basketball Team

Codeforces Beta Round 24

CF 85C - Petya and Tree

CF 123E - Maze

CF 107E - Darts