ternary-search

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

CF 455C - Civilization

CF 455C - Civilization Rating: 2100 Tags: dfs and similar, dp, dsu, ternary search, trees Solve time: 2m 1s Verified: yes Solution Problem Understanding The graph consists of cities connected by roads. The condition that between any two connected cities there is exactly one simple path means every connected component is a tree. Since the graph may be disconnected, the whole graph is a forest. Two types of operations must...

Practice › Codeforces Solutions ›

Codeforces Round 177 (Div. 2)

Codeforces Round 177 (Div. 2) Type: Div. 2 | Problems: 1 | Verified: 1/1 | Rating range: 1400-1400 | Time: 1m 16s Problem Name Rating Tags Solve Time Verified B Polo the Penguin and Matrix 1400 brute-force, dp, implementation 1m 16s ✓

Practice › Codeforces Solutions ›

Codeforces Round 126 (Div. 2)

Codeforces Round 126 (Div. 2) Type: Div. 2 | Problems: 3 | Verified: 3/3 | Rating range: 800-2400 | Time: 7m 2s Problem Name Rating Tags Solve Time Verified B Drinks 800 implementation, math 1m 33s ✓ C Football Championship 1800 brute-force, implementation 3m 43s ✓ E Tractor College 2400 implementation, math, number-theory 1m 46s ✓

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

CF 439D - Devu and his Brother

CF 439D - Devu and his Brother Rating: 1700 Tags: binary search, sortings, ternary search, two pointers Solve time: 57s Verified: yes Solution Problem Understanding We are given two integer arrays, one belonging to Devu and the other to his brother. We are allowed to repeatedly increase or decrease any single element of either array by 1 in one operation. The goal is to transform the arrays so that the...

Practice › Codeforces Solutions ›

Codeforces Round 127 (Div. 1)

Codeforces Round 127 (Div. 1) Type: Div. 1 | Problems: 5 | Verified: 4/5 | Rating range: 1700-2600 | Time: 7m 7s Problem Name Rating Tags Solve Time Verified A Clear Symmetry 1700 constructive-algorithms, dp, math 1m 9s ✓ B Guess That Car! 1800 math, ternary-search 1m ✓ C Fragile Bridges 2000 dp 1m 40s ✓ D Brand New Problem 2600 bitmasks, brute-force, dp 1m 39s ✓ E Thoroughly Bureaucratic...

Practice › Codeforces Solutions ›

Codeforces Round 251 (Div. 2)

Codeforces Round 251 (Div. 2) Type: Div. 2 | Problems: 2 | Verified: 2/2 | Rating range: 900-1700 | Time: 2m 9s Problem Name Rating Tags Solve Time Verified A Devu, the Singer and Churu, the Joker 900 greedy, implementation 1m 12s ✓ D Devu and his Brother 1700 binary-search, sortings, ternary-search 57s ✓

Practice › Codeforces Solutions ›

CROC-MBTU 2012, Final Round (Online version, Div. 2)

CROC-MBTU 2012, Final Round (Online version, Div. 2) Type: Div. 2 | Problems: 5 | Verified: 2/5 | Rating range: 1000-2000 | Time: 11m 54s Problem Name Rating Tags Solve Time Verified A Paper Work 1000 greedy 3m 9s ✗ B Restoring IPv6 1500 implementation, strings 1m 5s ✓ C Movie Critics 1600 greedy 3m 12s ✗ D Building Bridge 1900 geometry, ternary-search, two-pointers 1m 13s ✓ E Mad Joe...

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

CF 431E - Chemistry Experiment

CF 431E - Chemistry Experiment Rating: 2200 Tags: binary search, data structures, ternary search Solve time: 2m 3s Verified: yes Solution Problem Understanding We are given a set of containers, each containing some fixed amount of mercury. Over time, two kinds of operations happen. The first operation changes the mercury amount in a single container. Conceptually, that tube is emptied and then refilled so that its mercury level becomes exactly...

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

CF 201B - Guess That Car!

CF 201B - Guess That Car! Rating: 1800 Tags: math, ternary search Solve time: 1m Verified: yes Solution Problem Understanding The problem places us in a grid-like parking lot of size 4·n by 4·m meters, divided into squares of 4 by 4 meters, each containing a car with a known "rarity" value. Yura, the player, must choose a starting point at one of the intersections of these dividing lines and...

Practice › Codeforces Solutions ›

Codeforces Round 118 (Div. 1)

Codeforces Round 118 (Div. 1) Type: Div. 1 | Problems: 4 | Verified: 3/4 | Rating range: 1300-2600 | Time: 6m 44s Problem Name Rating Tags Solve Time Verified A Plant 1300 math 1m 38s ✓ B Mushroom Scientists 1800 math, ternary-search 1m 19s ✓ C Clever Fat Rat 2500 dp 1m 25s ✓ D Visit of the Great 2600 math, number-theory 2m 22s ✗

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

CF 289B - Polo the Penguin and Matrix

CF 289B - Polo the Penguin and Matrix Rating: 1400 Tags: brute force, dp, implementation, sortings, ternary search Solve time: 1m 16s Verified: yes Solution Problem Understanding We are given a matrix of integers and a number d . The penguin can either add or subtract d from any matrix element in a single move. The goal is to make all elements equal using the fewest moves possible. The output...

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

CF 185B - Mushroom Scientists

CF 185B - Mushroom Scientists Rating: 1800 Tags: math, ternary search Solve time: 1m 19s Verified: yes Solution Problem Understanding We are asked to find a point in three-dimensional space, with non-negative coordinates, such that the sum of the coordinates does not exceed a given value $S$. The “distance” of this point is defined not by the usual Euclidean metric, but by the mushroom scientists’ metric: $x^a \cdot y^b \cdot...

Practice › Codeforces Solutions › CROC-MBTU 2012, Final Round (Online version, Div. 2) ›

CF 250D - Building Bridge

CF 250D - Building Bridge Rating: 1900 Tags: geometry, ternary search, two pointers Solve time: 1m 13s Verified: yes Solution Problem Understanding We are choosing a path from a western village at the origin to a river bank located at a vertical line $x = a$, then crossing the river in a straight line to another point on the eastern bank $x = b$, and finally following a pre-determined path...

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

CF 427E - Police Patrol

CF 427E - Police Patrol Rating: 2000 Tags: greedy, implementation, math, ternary search Solve time: 1m 54s Verified: yes Solution Problem Understanding All criminals stand on the x-axis, and we must choose one integer coordinate for the police station. The patrol car starts from the station, visits some criminals, brings them back to the station, then repeats until everyone is arrested. Each trip can carry at most m criminals. The...

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

CF 200E - Tractor College

CF 200E - Tractor College Rating: 2400 Tags: implementation, math, number theory, ternary search Solve time: 1m 46s Verified: yes Solution Problem Understanding We are given the final exam results of a college where every student receives exactly one of three grades: 3, 4, or 5. Every student with the same grade must receive the same scholarship amount. If we denote these amounts as k3 , k4 , and k5...

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

CF 106E - Space Rescuers

CF 106E - Space Rescuers Rating: 2100 Tags: geometry, ternary search Solve time: 5m 23s Verified: no Solution Problem Understanding We are asked to place a space rescue station in three-dimensional space such that the maximum distance from it to any of the given planets is minimized. Each planet is represented by its coordinates $(x, y, z)$. The input consists of an integer $n$ representing the number of planets followed...

Practice › Codeforces Solutions ›

Codeforces Beta Round 82 (Div. 2)

Codeforces Beta Round 82 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 4/5 | Rating range: 1000-2100 | Time: 13m 18s Problem Name Rating Tags Solve Time Verified A Card Game 1000 implementation 1m 37s ✓ B Choosing Laptop 1000 brute-force, implementation 2m 3s ✓ C Buns 1700 dp 1m 50s ✓ D Treasure Island 1700 brute-force, implementation 2m 25s ✓ E Space Rescuers 2100 geometry, ternary-search 5m...

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

CF 98C - Help Greg the Dwarf

CF 98C - Help Greg the Dwarf Rating: 2500 Tags: geometry, ternary search Solve time: 2m 29s Verified: yes Solution Problem Understanding We have an L-shaped corridor with widths a and b on the two branches. A rectangular coffin of fixed length l must be moved through the corner. The coffin can slide and rotate freely in the plane, but it can never leave the floor, so every intermediate position...

Wiki › Algorithms › 01. Searching and Sorting › 2. Binary Search and Ordered Search ›

Discrete Ternary Search

Discrete Ternary Search Discrete ternary search finds the maximum or minimum of a unimodal function defined over integer indices. A function is unimodal if it strictly increases up to a point and then strictly decreases, or the reverse. Unlike binary search, which relies on a monotone predicate, ternary search relies on a unimodal shape. Problem Given a function $f(i)$ defined on integer indices $i \in [0, n-1]$, find an index...

Wiki › Algorithms › 01. Searching and Sorting › 2. Binary Search and Ordered Search ›

Continuous Ternary Search

Continuous Ternary Search Continuous ternary search finds the maximum or minimum of a unimodal function defined over a real interval. It applies when the domain is continuous and the function has a single peak or valley. Unlike the discrete version, there is no final scan. The algorithm stops when the interval becomes sufficiently small. Problem Given a function $f(x)$ defined over a real interval $[l, r]$, find a point $x$...

#ternary-search

CF 455C - Civilization

Codeforces Round 177 (Div. 2)

Codeforces Round 126 (Div. 2)

CF 439D - Devu and his Brother

Codeforces Round 127 (Div. 1)

Codeforces Round 251 (Div. 2)

CROC-MBTU 2012, Final Round (Online version, Div. 2)

CF 431E - Chemistry Experiment

CF 201B - Guess That Car!

Codeforces Round 118 (Div. 1)

CF 289B - Polo the Penguin and Matrix

CF 185B - Mushroom Scientists

CF 250D - Building Bridge

CF 427E - Police Patrol

CF 200E - Tractor College

Codeforces Beta Round 78 (Div. 1 Only)

CF 106E - Space Rescuers

Codeforces Beta Round 82 (Div. 2)

CF 98C - Help Greg the Dwarf

Discrete Ternary Search

Continuous Ternary Search