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
| Title | Level | Topics | Solved | Time limit | Memory limit | Judge |
|---|---|---|---|---|---|---|
| SeatsGiven n prize values, choose one probability distribution over seats so that a player's expected prize, accounting for random contests at each seat, is maximized. | Hard8 | ProbabilityMath+2 | No attempts yet | 1.5s | 256 MB | Judgeable |
| Brother and SisterGiven a functional graph on n labeled girls plus node 0, compute the expected number of queries before reaching 0 under a randomized probing process, modulo 1e9+7. | Hard8 | GraphMath+2 | No attempts yet | 1.5s | 512 MB | Judgeable |
| KolmogorovIn a connected undirected graph where each minute one random edge lights up, find the minimum expected time for an optimal walker to travel from node 1 to node N. | Hard8 | GraphDynamic programming+2 | No attempts yet | 1s | 512 MB | Judgeable |
| Fibonacci's NightmareFor a random sequence built by summing two earlier terms, find the variance of the n-th term modulo 10^9+7. | Hard8 | ProbabilityDynamic programming+2 | No attempts yet | 2s | 256 MB | Judgeable |
| Expected LCPCompute the expected length of the longest common prefix among n independent uniform random infinite binary strings, output as a fraction mod 1e9+7. | Hard8 | ProbabilityCombinatorics+2 | No attempts yet | 1.5s | 256 MB | Judgeable |
| CowboysGiven N cowboys shooting in turns with hit probabilities and optimal target choice under strategic play, compute each cowboy's probability of being the sole survivor. | Hard9 | Game theoryDynamic programming+2 | No attempts yet | 2s | 128 MB | Judgeable |
| Cheating or NotGiven g groups, seeded teams, pots, and confederation constraints, compute the average total strength of a given team's group opponents over all valid draws. | Hard9 | CombinatoricsProbability+2 | No attempts yet | 1s | 128 MB | Judgeable |
| Success Probability of the Card-Pile GameGiven n decks of k cards each shuffled into n piles, find the probability that the follow-the-number drawing game succeeds within m restarts, printed to r decimals. | Hard9 | ProbabilityCombinatorics+2 | No attempts yet | 1s | 128 MB | Judgeable |
| Parallel ExpectationsGiven two programs run by randomly interleaving their instructions, find the expected final value of every shared variable. | Hard9 | ProbabilityDynamic programming+1 | No attempts yet | 1s | 128 MB | Judgeable |
| ExamGiven each student's distribution over exam scores, find the exact probability that the sequence of European marks from all students avoids every listed unpleasant string. | Hard9 | Dynamic programmingString matching+2 | No attempts yet | 2s | 128 MB | Judgeable |
| Markov TrainsFind the station list maximizing the chance of arriving by a deadline when each train may be cancelled and the traveler waits for the next one after a cancellation. | Hard9 | Dynamic programmingProbability+1 | No attempts yet | 1s | 128 MB | Judgeable |
| Dragon MilkdrinkerCompute the probability that the sum of n independent uniform [m, M] yields is strictly less than h, printed truncated to d decimals. | Hard9 | ProbabilityMath+2 | No attempts yet | 1s | 128 MB | Judgeable |
| Video PokerFor a given video poker payout table, count how many of the 2,598,960 dealt hands make the optimal expected-value strategy discard exactly 0, 1, 2, 3, 4, and 5 cards. | Hard9 | Brute forceCombinatorics+2 | No attempts yet | 1s | 128 MB | Judgeable |
| TollgateFind the road with the largest expected toll income when every resident visits every restaurant by a random shortest round trip. | Hard9 | Shortest pathGraph+2 | No attempts yet | 2s | 256 MB | Judgeable |
| Hidden MazeCompute the expected median edge weight over all tree node pairs at odd distance, and print it as a reduced fraction. | Hard9 | Divide and conquerTree+2 | No attempts yet | 2s | 256 MB | Judgeable |
| Overwriting GameYou repeat random prefix-rectangle repaints until the board matches the target, and report the expected total of painted cells as a reduced fraction. | Hard9 | ProbabilityMatrix+1 | No attempts yet | 8s | 512 MB | Judgeable |
| Slave to Achievements 2Repeatedly craft as many N-scrap daggers as possible and reclaim 0 to K scraps per dagger, then find the distribution of the final leftover under N scraps. | Hard9 | ProbabilityDynamic programming+1 | No attempts yet | 3s | 256 MB | Judgeable |
| Random signalsCompute the expected plane integral of the strongest covering signal when each of up to 20 stations draws an independent uniform power that activates its disks. | Hard9 | GeometryProbability+1 | No attempts yet | 12s | 256 MB | Judgeable |
| Card Rarity EncodingGiven N draws over four rarities with known probabilities, find the smallest possible expected length of a prefix-free binary code for the N-draw sequences. | Hard9 | GreedyHeap+2 | No attempts yet | 3s | 128 MB | Judgeable |
| CasinoWith m dollars, a goal of n dollars and win chance p percent per play, pick each stake to maximize the chance of reaching the goal. | Hard9 | ProbabilityDynamic programming+1 | No attempts yet | 2s | 256 MB | Judgeable |
| SheepwalkingTwo sheepdogs block two neighboring cells each turn to steer a randomly moving sheep home and minimize its expected number of moves there. | Hard9 | ProbabilityGame theory+1 | No attempts yet | 20s | 1024 MB | Judgeable |
| Drawing lotsCompute the expected number of draws until a blue lot has been drawn K times, where red lots are removed and green and blue lots are returned. | Hard9 | ProbabilityMath+1 | No attempts yet | 2s | 512 MB | Judgeable |
| Risky LotteryFind the unique symmetric Nash equilibrium mixed strategy for a lottery where the winner is the player holding the smallest number written exactly once, and print each pick probability to five decimals. | Hard9 | Game theoryProbability+2 | No attempts yet | 2s | 512 MB | Judgeable |
| Tarot Sham BoastGiven up to 10 equal-length strings over {R,P,S} and a length n random string, sort the strings by the probability each occurs as a contiguous block. | Hard9 | String matchingProbability+2 | No attempts yet | 2s | 512 MB | Judgeable |
| Expected value of the greatest common divisorEach of K values is chosen uniformly from its own interval; find the expected gcd of the K chosen numbers as a fraction mod 1e9+7. | Hard9 | ProbabilityMath+2 | No attempts yet | 2s | 512 MB | Judgeable |
| Sweet and SourChoose which Candy Country players drink a potion that randomizes their sweetness and sourness, maximizing Candy's expected match points under all random player orders and event coin flips. | Hard9 | ProbabilityCombinatorics+2 | No attempts yet | 1s | 512 MB | Judgeable |
| Sum of Equivalent Resistances Between Every Pair of Vertices Joined by an Edge, Given a Connected Graph with Unit Resistance EdgesGiven a connected unit-resistance graph, compute the sum of effective resistances over all m edges, using the fact that each equals the probability a random walk crosses that edge in the commute. | Hard9 | GraphMatrix+2 | No attempts yet | 1s | 512 MB | Judgeable |
| Laser IntensificationFind probability p so that one photon entering the lower-left of a w by h grid, with nodes independently faulty with probability 1-p except n known faulty cells, yields k photons in expectation at the upper-right; print -1 if impossible. | Hard9 | MathCombinatorics+2 | No attempts yet | 2s | 64 MB | Judgeable |
| RMQ Similar SequenceGiven sequence A, count the expected sum of a random real sequence B in [0,1] that has identical RMQ answers to A for every subarray, modulo 1e9+7. | Hard9 | TreeCombinatorics+2 | No attempts yet | 2s | 256 MB | Judgeable |
| Airport Check-inEach counter has a random per-passenger time and a random remaining time for the current passenger; find the probability that the counter finishing first is also the one with the smallest per-passenger time. | Hard9 | ProbabilityMath+1 | No attempts yet | 1s | 256 MB | Judgeable |
| EarthquakeEach route is usable only if all its bridges survive; pick an adaptive inspection order of bridges to minimize the expected number of inspections before deciding whether any route connects the two lands. | Hard9 | ProbabilityDynamic programming+2 | No attempts yet | 1s | 512 MB | Judgeable |
| Flip a CoinTwo players each pick a heads/tails string of length up to 20; a fair coin is flipped until one or both strings appear, and we must output the probabilities of Alice winning, Bob winning, and a tie. | Hard9 | ProbabilityDynamic programming+2 | No attempts yet | 1s | 256 MB | Judgeable |
| Human ErrorGiven a grid of Justin and Donald pieces where each turn a player must capture an adjacent piece, and each player may restrict their candidate moves to a set of fixed size, compute Justin's win probability under optimal play with random move choice. | Hard9 | Game theoryBit manipulation+2 | No attempts yet | 1s | 512 MB | Judgeable |