cho.sh

Problems

Pick a problem and write your solution in the built-in editor. The judge runs it against real test cases while you watch, and the wider archive is open to read whenever you like.

Total results333 problems
TitleLevelTopicsSolvedTime limitMemory limitJudge
GIGA Universe CupGiven four of the six group matches, compute the probability the starred team finishes in the top two, including tie-breaking and random lots.Medium7ProbabilityCombinatorics+2No attempts yet2s512 MBJudgeable
English RestaurantGiven n tables and random hourly group sizes from 1 to g, find the expected number of seated people after t hours, where each group takes the smallest table that fits.Medium7Dynamic programmingProbability+1No attempts yet2s512 MBJudgeable
Knockout TournamentArrange the starting line-up of a knockout tournament so that Dale's probability of winning, given pairwise win odds a/(a+b), is maximized.Medium7Dynamic programmingProbability+1No attempts yet2s512 MBJudgeable
CoinsMaintain the probability that the number of heads among N coins is odd, under M point updates to individual coin probabilities, and report which outcome is more likely after each update.Medium7MathProbability+2No attempts yet2s512 MBJudgeable
Explosion ExploitGiven up to 10 minions with health at most 6 and d up to 100, find the chance that uniformly random sequential damage kills every opposing minion.Medium7Dynamic programmingCombinatorics+1No attempts yet3s512 MBJudgeable
New SalariesSalaries are drawn from nested closed intervals. Compute the expected total pairwise salary gaps and output it divided by N squared.Medium7Prefix sumMath+2No attempts yet2s512 MBJudgeable
Back to the BonesGiven N rolled dice and a target K, reroll any subset once to maximize the chance the sum reaches K, and report 6^N times that probability together with one optimal subset.Medium7Dynamic programmingProbability+2No attempts yet1s256 MBJudgeable
Rainwater on a TreeWater starts at the root and each vertex sends 1 unit per second to a uniformly random child; find the average expected final water over vertices that hold any water.Medium7TreeProbability+2No attempts yet1s512 MBJudgeable
JackpotChoose how many of n doors to open first so that the probability of picking the prize times the reduced prize is largest; output that best expected payout.Medium7MathBinary search+2No attempts yet1s512 MBJudgeable
Research Productivity IndexChoose any subset of n papers with known acceptance probabilities to maximize the expected value of a^a/s, where s is the subset size and a the number accepted.Medium7Dynamic programmingProbability+2No attempts yet1s1024 MBJudgeable
Lucky DrawFor n players with k lives each flipping a biased coin every round, compute the probability the game ends in a draw.Medium7Dynamic programmingProbability+2No attempts yet2s512 MBJudgeable
RGB JengaTwo players alternately draw red, green, or blue blocks of given weights; the first draw that pushes the total removed weight to at least N loses, and you must say which player wins with higher probability.Medium7Dynamic programmingProbability+2No attempts yet1s256 MBJudgeable
AssassinsGiven chronological assassination attempts with success probabilities, find the probability each of n assassins is alive at the end, where a dead assassin's attempts are cancelled.Medium7ProbabilityDynamic programming+2No attempts yet1s512 MBJudgeable
Final StandingsGiven each team's strength, each problem's difficulty, and a frozen scoreboard, compute the probability that team t ends up in first place, assuming ties always go to team t.Medium7ProbabilityDynamic programming+1No attempts yet2s512 MBJudgeable
Bogo SortSort a hidden permutation using only calls that randomly shuffle a chosen contiguous segment and report the shuffled result.Medium7SortingProbability+2No attempts yet4s1024 MBJudgeable
Farming MarsFor each query interval, decide whether some exact pH value occurs more than half the time within that interval.Medium7Hash mapDivide and conquer+2No attempts yet2s512 MBJudgeable
Petr's AlgorithmGiven a permutation produced by randomly shuffling every length-k window left to right, recover k. The input guarantees 20k is at most n.Medium7ProbabilityMath+2No attempts yet1s512 MBJudgeable
Game Of ChanceFor each m, find the limit of the expected score difference in a two-player optimal-stopping game where the choice holder assigns a random number to themselves or the opponent.Medium7ProbabilityGame theory+2No attempts yet3s512 MBJudgeable
Baklava TrayFor a regular N-gon of area 1, nested polygons join midpoints forever; find the expected total nut types hit by 10^4 random points.Medium7MathGeometry+2No attempts yet12s512 MBJudgeable
Flipping El-fetieraEach of K operations picks a uniformly random rectangular submatrix and flips every cell in it; compute the expected number of cells holding 1 at the end.Medium7ProbabilityDynamic programming+2No attempts yet10s512 MBJudgeable
DotA QualsGiven 2^n players and Idned ranked k-th, compute the expected number of rounds he survives when opponents are randomly paired each round and the higher rating always wins.Medium7ProbabilityCombinatorics+2No attempts yet1s256 MBJudgeable
Coin Passing GameGiven biased left/right passing probabilities on a circle of N students starting at student K, compute the probability that student N is the last student to first receive the coin.Hard8ProbabilityDynamic programming+2No attempts yet2s128 MBJudgeable
Random SortCompute the expected number of random inversion swaps needed to sort a permutation of size at most 8 into increasing order.Hard8ProbabilityDynamic programming+2No attempts yet2s128 MBJudgeable
Expected Repaints for BallsGiven N colored balls, compute the expected number of random repaint operations needed until all balls share one color.Hard8ProbabilityDynamic programming+2No attempts yet2s128 MBJudgeable
MazeGiven a tree-like maze grid, compute the expected number of steps for a random depth-first exploration (choosing unvisited branches uniformly, backtracking on dead ends) to travel from entrance to exit.Hard8TreeDFS+2No attempts yet2s128 MBJudgeable
InterconnectGiven an initial graph on up to 30 towns, compute the exact expected number of random-edge additions needed until the graph becomes fully connected, as a reduced fraction.Hard8Union-findMath+2No attempts yet1s128 MBJudgeable
Teleport Out!Grid maze with exits; each step you either walk to an adjacent open cell or teleport to a uniformly random open cell. Find the minimum expected number of steps to reach an exit.Hard8Dynamic programmingBFS+2No attempts yet1s128 MBJudgeable
Cover UpGiven up to 5000 boards, each with d columns of distinct digits, compute the probability the contestant eventually wins Cover Up, assuming uniform random picks among untried digits in unfinished columns.Hard8ProbabilityDynamic programming+2No attempts yet1s128 MBJudgeable
Borg BoogieGiven a connected undirected graph and a fixed walk, find the probability that a random-walking sentry never collides or swaps with the captain during the walk.Hard8Dynamic programmingProbability+2No attempts yet1s128 MBJudgeable
BlackjackGiven the exact order of the remaining deck, decide which hands to play, how much to bet, and when to hit or stand, to maximize total profit.Hard8Dynamic programmingGame theory+2No attempts yet1s128 MBJudgeable
Another Dice GameCompute the probability that Jan reaches a target score of n in Pickomino with optimal play, given the dice, set-aside and worm rules.Hard8Dynamic programmingProbability+2No attempts yet1s128 MBJudgeable
Good CoalitionEach party has seats and a survival probability; find the party subset holding at least 76 seats whose product of probabilities is maximized, and print it as a percentage.Hard8Dynamic programmingProbability+2No attempts yet1s128 MBJudgeable
Prime SquareFind all 5x5 digit grids whose five rows, five columns and two diagonals are five-digit primes with the same given digit sum and a fixed top-left digit, printed in lexicographic order.Hard8BacktrackingNumber theory+2No attempts yet1s128 MBJudgeable
Square LotteryCount, over all permutations of 1 to N^2 on an N by N grid, the expected number of winning tickets for a random set of four corners forming a square, then divide the prize pool.Hard8CombinatoricsMath+2No attempts yet1s128 MBJudgeable
The (Bayesian) Hound and the HareMaintain a Bayesian belief over a hare's random-walk position, apply noisy observations, and greedily move the hound to the cell with least expected maze distance.Hard8ProbabilityBFS+2No attempts yet1s128 MBJudgeable
Drunken WalkIn a weighted DAG, remove at most one edge to maximize the expected number of edges walked from vertex 0 before reaching a sink.Hard8GraphDynamic programming+2No attempts yet2s512 MBJudgeable
Hey, Better BettorGiven a refund rate on final losses and a win chance below half per dollar bet, compute the maximum expected profit over any stopping strategy.Hard8ProbabilityDynamic programming+1No attempts yet4s128 MBJudgeable
Bribing the SyndicateChoose an adaptive bribery order within a fixed budget to maximize the chance of gaining at least c defectors.Hard8Dynamic programmingProbabilityNo attempts yet5s128 MBJudgeable
Crusher's CodeCompute the expected number of loop iterations for two randomized swap sorts on arrays of up to 8 values.Hard8ProbabilityDynamic programming+1No attempts yet10s128 MBJudgeable
Mixing ColoursThe player picks one colour per token and merges adjacent tokens under the rules to maximize the product of picked certainties, breaking ties in ASCII order.Hard8Dynamic programmingProbabilityNo attempts yet5s128 MBJudgeable
Palindrome TripCompute the chance that a uniform random walk from s to t spells a palindrome, stopping early when t becomes unreachable.Hard8ProbabilityGraph+2No attempts yet10s128 MBJudgeable
PachinkoA ball wanders a grid with random moves and absorbing targets, and each target needs its hit probability from a uniform top-row start.Hard8ProbabilityGraph+1No attempts yet6s512 MBJudgeable
Slave to Achievements 3Starting from M scraps, repeated crafting and dismantling ends with fewer than N scraps, and you must report each final remainder probability modulo 1e9+7.Hard8ProbabilityDynamic programming+2No attempts yet3s256 MBJudgeable
The last wizardTen counters start at 1 and grow through T random additive updates; output their expected product scaled by A to the T modulo 1000000007.Hard8ProbabilityCombinatorics+2No attempts yet1s256 MBJudgeable
Birthday PartyEach of N guests gives a present to a random other guest, and you must compute the probability that some k guests form a directed gift cycle.Hard8CombinatoricsProbability+1No attempts yet5s256 MBJudgeable
Absurdistan Roads IIN cities each build a road to one random other city; compute the probability that the N roads connect all cities.Hard8CombinatoricsProbability+2No attempts yet1s256 MBJudgeable
Just a QuizTeresa interrupts randomly drawn known questions at chosen words to maximize expected correct answers within t seconds.Hard8Dynamic programmingTrie+1No attempts yet1s256 MBJudgeable
Splitting into PrimesStarting from N, repeatedly split every composite into a random divisor pair and report the expected number of rounds until all parts are prime.Hard8ProbabilityDynamic programming+2No attempts yet1s256 MBJudgeable
Butterfly EffectDecide adaptively where to spend up to k double-die rolls across n chained chance events to maximize the chance the last event ends positive.Hard8Dynamic programmingProbabilityNo attempts yet5s256 MBJudgeable
ARAM (Large)Decide when to spend reroll currency on random champions to maximize the long-run win rate over many games.Hard8Dynamic programmingProbability+2No attempts yet120s512 MBJudgeable
Observation Wheel (Large)Compute the expected total fare collected as visitors starting at uniform random gondolas fill all free spots on a circular wheel.Hard8ProbabilityDynamic programming+1No attempts yet5s512 MBJudgeable
Falling Diamonds (Large)N diamonds drop onto x=0 and slide left or right at random, and each query asks the probability that a diamond rests exactly at (X, Y).Hard8ProbabilitySimulation+1No attempts yet5s512 MBJudgeable
Upstairs and DownstairsKonstantin chooses and orders at least K activities from limited copies to minimize the chance Ilia wakes after falling asleep.Hard8ProbabilityDynamic programming+2No attempts yet5s512 MBJudgeable
Upstairs and DownstairsKonstantin must order at least K activities with capped repeats to minimize the chance Ilia falls asleep and later wakes.Hard8ProbabilityGreedy+1No attempts yet100s512 MBJudgeable
Commute War (Large)Choose connecting services to minimize expected travel time when departures leave hourly and each ride faces repeated random inspection delays.Hard8Shortest pathProbability+1No attempts yet5s512 MBJudgeable
Google RoyalePick starting and doubling coin-flip bets to maximize the chance of growing A dollars into V dollars before going broke.Hard8Dynamic programmingProbability+1No attempts yet5s512 MBJudgeable
Champion Sort (Small)Compute the minimum expected number of random subset shuffles that sorts a permutation of 1 to N into increasing order.Hard8ProbabilityCombinatorics+1No attempts yet5s512 MBJudgeable
Test Passing Probability (Large Input)With M submissions allowed and independent per-question probabilities, choose answers to maximize the chance that one submission is fully correct.Hard8ProbabilityDynamic programming+1No attempts yet5s512 MBJudgeable
Becoming a MillionaireBet any fraction of your money each round to maximize the chance of ending with at least one million dollars.Hard8Dynamic programmingProbability+1No attempts yet5s512 MBJudgeable
Millionaire (Large)Bet any fraction of your money over M rounds with win probability P; maximize the chance of holding $1,000,000 at the end.Hard8Dynamic programmingProbabilityNo attempts yet20s512 MBJudgeable
Fly Swatter (Small)Compute the probability that a randomly placed fly disk touches a circular ring crossed by a grid of cylindrical strings, and print it to six decimals.Hard8GeometryMath+2No attempts yet5s512 MBJudgeable
Fly Swatter (Large)Given the racquet geometry, compute the probability that a fly of radius f, centered uniformly in the outer circle, overlaps the ring or any string.Hard8GeometryMath+2No attempts yet20s512 MBJudgeable
Points on a CircleGiven n random points on a unit circle and an angle p, compute -log2 of the probability that all n points fit inside some arc of central angle p.Hard8ProbabilityMath+2No attempts yet2s512 MBJudgeable
King of ChairsArrange N ladies, each sitting or standing with probability 1/2, to maximize the expected number of ordered pairs where the person behind is strictly taller.Hard8SortingGreedy+2No attempts yet1s32 MBJudgeable
WoodworkingGiven plank recovery probabilities for a box needing N planks, compute the expected number of boxes built starting with M planks.Hard8Dynamic programmingProbability+1No attempts yet7s512 MBJudgeable
HandshakesCompute the expected number of random handshakes until all N people belong to one acquaintance component, and output it modulo 1e9+7.Hard8ProbabilityDynamic programming+2No attempts yet4s512 MBJudgeable
Black and WhiteEach cell is black or white with probability 1/2; find the expected product of the number of all-black subrectangles and all-white subrectangles.Hard8CombinatoricsProbability+2No attempts yet2s512 MBJudgeable
CasinoWith N players, M areas, and K rounds of random elimination, find the best survival probability for the group.Hard8Dynamic programmingProbability+1No attempts yet2s512 MBJudgeable
Beauty of the sequenceGiven N trees with independent uniform height ranges, find the expected maximum beauty of a zigzag subsequence.Hard8Dynamic programmingProbabilityNo attempts yet2s512 MBJudgeable
Hot PotatoFor each query range, find the smallest X maximizing the gap between ending and not ending, given a functional graph walk from a uniform random start.Hard8GraphProbability+2No attempts yet2s512 MBJudgeable
ExamGiven each student's fixed semester points and a distribution of exam points, find the probability that the grade string avoids all forbidden substrings.Hard8Dynamic programmingString matching+2No attempts yet1.5s512 MBJudgeable
Expected Number of Connected ComponentsFor each node i with inclusion probability P_i, find the expected number of connected components of the subgraph where two selected nodes are adjacent when gcd > 1, then print E times 100^N mod 1e9+7.Hard8ProbabilityMath+2No attempts yet5s512 MBJudgeable
SortFor an array of at most 8 elements, compute the expected number of random-swap steps until sorted for two different swap schemes.Hard8ProbabilityDynamic programming+1No attempts yet2s128 MBJudgeable
Splitting Game LevelsPartition n levels into k consecutive groups to minimize the expected total time of a random coin-draw process, and print it to six decimals.Hard8Dynamic programmingDivide and conquer+2No attempts yet2s512 MBJudgeable
PianoGiven N equally likely piano tones, find the expected number of presses until a fixed M-tone sequence appears, for every prefix of it.Hard8String matchingDynamic programming+2No attempts yet1s64 MBJudgeable
Core Training (Small2)Distribute U training units among N cores, each unit adding 1 to a core's success probability (capped at 1), to maximize the chance that at least K cores succeed.Hard8Dynamic programmingGreedy+2No attempts yet5s512 MBJudgeable
GhostbustersGiven independent button press probabilities, find the most likely set of pressed buttons that produces the observed row-to-column connectivity signals.Hard8GraphDynamic programming+2No attempts yet2s512 MBJudgeable
The Uncertainty of PoliticsEach hearing has a start time and a uniform integer length in [a,b]; pick hearings to attend fully so the expected count is maximized.Hard8Dynamic programmingProbability+2No attempts yet2s512 MBJudgeable
Haggling With a WitcherGiven an unknown target fee uniform on [L,R], maximize expected gold by naming fees over time, where each attempt or save-reload costs 100 ms and time is capped by T.Hard8Dynamic programmingMath+2No attempts yet2s512 MBJudgeable
The Battle for WesnothChoose positive d and b with d*b <= m to maximize the chance that the total damage of b independent blows, each landing with probability p/100 and dealing d, kills a unit with h hitpoints; report the smallest-d, smallest-b optimum or 1 1 if impossible.Hard8ProbabilityMath+2No attempts yet0.1s1024 MBJudgeable
Gambling GuideOn an undirected graph, find the minimum expected number of random tickets (with rejection allowed) needed to travel from city 1 to city n.Hard8GraphProbability+2No attempts yet3s512 MBJudgeable
MultisectGiven a hidden failing revision among n candidates and up to K simultaneous tests per round, find the strategy that minimizes expected total cost when a round with i failures costs T_i.Hard8Dynamic programmingBinary search+2No attempts yet2s512 MBJudgeable
Catch the PlaneChoose an adaptive strategy of buses to maximize the probability of reaching station 1 by time k, where each bus runs independently with a known probability.Hard8Dynamic programmingProbability+2No attempts yet10s1024 MBJudgeable
Gem IslandAt each of d steps a uniformly random gem splits in two; find the expected total held by the r largest holders after d splits.Hard8ProbabilityDynamic programming+2No attempts yet3s1024 MBJudgeable
Random Number GeneratorGiven how many values from 1 to N have been seen zero or one time, find the expected number of draws until every value appears at least twice.Hard8ProbabilityDynamic programming+2No attempts yet2s512 MBJudgeable
HorsemeetTwo knights move randomly to legal knight-move squares on an 8x8 board; find which knight has the higher probability of being the first to land on the other's square.Hard8ProbabilityGraph+2No attempts yet2s512 MBJudgeable
Numbers GeneratorGiven up to ten H/T patterns of the same length, compute the expected number of fair coin flips until one pattern first appears contiguous.Hard8String matchingHash map+2No attempts yet2s512 MBJudgeable
Balance BeamChoose at each beam position a cash value or a fair coin random walk stopped at the ends, maximizing expected payment for every starting position.Hard8Dynamic programmingMath+2No attempts yet2s512 MBJudgeable
Gravity PointA random mass for tiles A and B is drawn from given ranges; find the chance the grid's center of gravity falls in a filled cell.Hard8GeometryProbability+2No attempts yet2s512 MBJudgeable
Heaps of FunGiven a rooted tree where each node i draws a uniform random real in [0, b_i], compute the probability that every parent's value is less than both its children's values, modulo 1e9+7.Hard8ProbabilityDynamic programming+2No attempts yet2s512 MBJudgeable
Cow DatingGiven probabilities p_i, choose a contiguous interval maximizing the chance that exactly one bull accepts, and print 10^6 times that probability rounded down.Hard8MathTwo pointers+2No attempts yet2s512 MBJudgeable
Dice and LaddersFind the minimum number of die rolls so that the probability of finishing a snakes-and-ladders board within that many rolls is at least p.Hard8ProbabilityDynamic programming+2No attempts yet2s512 MBJudgeable
Hold or Continue?For each query state (Catelyn score, Hoster score, current turn total) decide hold or continue to maximize Catelyn's win probability when both play optimally in Pig to exactly 75.Hard8Dynamic programmingProbability+2No attempts yet2s512 MBJudgeable
Gnoll HypothesisGiven n spawn probabilities and a random pool of k chosen types, compute each type's expected effective spawn chance after unchosen chances shift to the next chosen type cyclically.Hard8ProbabilityDynamic programming+2No attempts yet2s512 MBJudgeable
Expected ValueRepeatedly pick a random adjacent pair, replace the left value by its difference with the right, drop the right. Find the expected final value modulo 1e9+7.Hard8Dynamic programmingProbability+2No attempts yet3s16 MBJudgeable
Bus StopEach of n bus routes has independent waiting time uniform on [0, di]; find the expected minimum, output as a fraction modulo 998244353.Hard8ProbabilityMath+2No attempts yet2s512 MBJudgeable
Nonsense TimeElements of a random permutation are unfrozen one at a time; after each unfreeze report the longest increasing subsequence length among the currently available elements.Hard8Dynamic programmingBinary search+2No attempts yet12s512 MBJudgeable
AlakazamGiven an array and range shuffle operations that permute a segment uniformly at random, answer point queries for the expected value at a position.Hard8MathProbability+2No attempts yet2s512 MBJudgeable
QuicksortGiven a flawed quicksort with recursion depth limit k, find the expected number of inversions after running it on a uniformly random permutation of size n, times n! modulo 998244353.Hard8CombinatoricsProbability+2No attempts yet2s512 MBJudgeable
ExpEach of n independent monsters grants i experience (0 to k) with probability p_i, totals are capped at x, and the expected capped total must be computed modulo 998244353.Hard8ProbabilityDynamic programming+2No attempts yet5s512 MBJudgeable