chinese-remainder-theorem

Practice › Codeforces Solutions › Codeforces Round 488 by NEAR (Div. 1) ›

CF 993E - Nikita and Order Statistics

CF 993E - Nikita and Order Statistics Rating: 2300 Tags: chinese remainder theorem, fft, math Solve time: 1m 42s Verified: no Solution Problem Understanding We are given an array and a threshold value x . For every possible integer k from 0 to n , we need to count how many subarrays have exactly k elements strictly smaller than x . Each subarray contributes to exactly one k , depending...

Practice › Codeforces Solutions › Mail.Ru Cup 2018 Round 1 ›

CF 1054H - Epic Convolution

CF 1054H - Epic Convolution Rating: 3500 Tags: chinese remainder theorem, fft, math, number theory Solve time: 7m 10s Verified: no Solution Problem Understanding We are given two sequences, one indexed by $i$ and one indexed by $j$, and we are asked to combine every pair $(i, j)$ into a single weighted contribution. The weight is not linear or even separable in the usual sense: each pair contributes $$a_i \cdot...

Practice › Codeforces Solutions › Codeforces Round 454 (Div. 1, based on Technocup 2018 Elimination Round 4) ›

CF 906D - Power Tower

CF 906D - Power Tower Rating: 2700 Tags: chinese remainder theorem, math, number theory Solve time: 14m 47s Verified: yes Solution Problem Understanding We are asked to compute a "power tower" modulo a given number. Conceptually, imagine a sequence of rocks, each with a positive integer power. To construct the tower from rocks numbered l through r , we start from the top rock r and work down to l...

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

CF 1117E - Decypher the String

CF 1117E - Decypher the String Rating: 2200 Tags: bitmasks, chinese remainder theorem, constructive algorithms, interactive, math Solve time: 1m 34s Verified: no Solution Problem Understanding We are given a string t of length n which is the result of applying an unknown sequence of swaps to an original string s . Each swap exchanges two characters at positions a_i and b_i in s . The sequence of swaps could...

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

CF 1438C - Engineer Artem

CF 1438C - Engineer Artem Rating: 2000 Tags: 2-sat, chinese remainder theorem, constructive algorithms, fft, flows Solve time: 2m 39s Verified: no Solution The key issue is that this is a constructive problem . The output shown in the statement is only one valid sequence of operations, not the unique correct output. Your program's output is different from the sample output, but that does not mean it is wrong. For...

Practice › Codeforces Solutions ›

Codeforces Round 707 (Div. 1, based on Moscow Open Olympiad in Informatics)

Codeforces Round 707 (Div. 1, based on Moscow Open Olympiad in Informatics) Type: Div. 1 | Problems: 6 | Verified: 1/6 | Rating range: 1800-3500 | Time: 26m 58s Problem Name Rating Tags Solve Time Verified A Going Home 1800 brute-force, hashing, implementation 19m 39s ✗ B Two chandeliers 2200 binary-search, brute-force, chinese-remainder-theorem 1m 3s ✗ C Matrix Sorting 2600 bitmasks, brute-force, constructive-algorithms 2m 46s ✗ D Tiles for Bathroom...

Practice › Codeforces Solutions › Codeforces Round 707 (Div. 1, based on Moscow Open Olympiad in Informatics) ›

CF 1500B - Two chandeliers

CF 1500B - Two chandeliers Rating: 2200 Tags: binary search, brute force, chinese remainder theorem, math, number theory Solve time: 1m 3s Verified: no Solution Problem Understanding We have two cyclic sequences of colors. The first chandelier repeats an array a of length n , and the second chandelier repeats an array b of length m . On day d , the first chandelier shows position (d - 1) mod...

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

CF 1536F - Omkar and Akmar

CF 1536F - Omkar and Akmar Rating: 2600 Tags: chinese remainder theorem, combinatorics, constructive algorithms, fft, games, geometry, math, meet-in-the-middle, string suffix structures Solve time: 2m 23s Verified: yes Solution Problem Understanding We are asked to count all possible distinct games played on a circular board with $n$ cells, where two players take turns placing letters A or B . Akmar moves first. A letter cannot be placed adjacent to...

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

CF 1665D - GCD Guess

CF 1665D - GCD Guess Rating: 2000 Tags: bitmasks, chinese remainder theorem, constructive algorithms, games, interactive, math, number theory Solve time: 1m 46s Verified: no Solution Problem Understanding We are asked to find a hidden positive integer $x$ between 1 and $10^9$. Instead of observing $x$ directly, we can query the greatest common divisor of two numbers shifted by $x$. Specifically, for any two positive integers $a$ and $b$, the...

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

CF 1748D - ConstructOR

CF 1748D - ConstructOR Rating: 2100 Tags: bitmasks, chinese remainder theorem, combinatorics, constructive algorithms, math, number theory Solve time: 1m 28s Verified: no Solution Exploration Let the triangle be $ABC$, let $H$ be its orthocenter, and let $\omega$ be its incircle with center $I$ and radius $r$. The beetles move along the altitudes. Since they all move with the same speed, after time $\tau$ the distances traveled from the vertices...

Practice › Codeforces Solutions ›

Good Bye 2022: 2023 is NEAR

Good Bye 2022: 2023 is NEAR Type: Special | Problems: 8 | Verified: 3/8 | Rating range: 1000-3500 | Time: 16m 49s Problem Name Rating Tags Solve Time Verified A Koxia and Whiteboards 1000 brute-force, greedy 3m ✓ B Koxia and Permutation 1000 constructive-algorithms 2m 29s ✗ C Koxia and Number Theory 1700 brute-force, chinese-remainder-theorem, math 1m 21s ✓ D Koxia and Game 2000 constructive-algorithms, data-structures, dfs-and-similar 1m 51s ✗...

Practice › Codeforces Solutions › Good Bye 2022: 2023 is NEAR ›

CF 1770C - Koxia and Number Theory

CF 1770C - Koxia and Number Theory Rating: 1700 Tags: brute force, chinese remainder theorem, math, number theory Solve time: 1m 21s Verified: yes Solution Problem Understanding We are given an array of positive integers and we are allowed to choose a single positive shift value $x$. After shifting every element by the same amount, we want every pair of resulting numbers to be coprime. Equivalently, we transform the array...

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

CF 2098E - Bermuda Triangle

CF 2098E - Bermuda Triangle Rating: 2400 Tags: chinese remainder theorem, geometry, number theory Solve time: 1m 26s Verified: no Solution Problem Understanding We are asked to model a simplified version of the Bermuda Triangle as a right triangle on a 2D coordinate plane, with vertices at $(0,0)$, $(0,n)$, and $(n,0)$. A plane starts inside this triangle at $(x,y)$ and moves with a velocity vector $(v_x,v_y)$. The plane moves continuously,...

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

CF 1993F2 - Dyn-scripted Robot (Hard Version)

CF 1993F2 - Dyn-scripted Robot (Hard Version) Rating: 2800 Tags: chinese remainder theorem, math, number theory Solve time: 2m 58s Verified: no Solution Problem Understanding We are asked to simulate the movement of a robot inside a bounded rectangle, starting at the bottom-left corner. The robot follows a script of movements, each of which is one of the four cardinal directions. If a move would take the robot outside the...

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

CF 1993F1 - Dyn-scripted Robot (Easy Version)

CF 1993F1 - Dyn-scripted Robot (Easy Version) Rating: 2400 Tags: brute force, chinese remainder theorem, constructive algorithms, math, number theory Solve time: 1m 50s Verified: no Solution Problem Understanding We are simulating a deterministic robot moving on a grid that is bounded by a rectangle. The robot starts at the origin and repeatedly executes a fixed instruction string consisting of unit moves in four directions. The twist is that the...

Practice › Codeforces Solutions ›

Rayan Programming Contest 2024 - Selection (Codeforces Round 989, Div. 1 + Div. 2)

Rayan Programming Contest 2024 - Selection (Codeforces Round 989, Div. 1 + Div. 2) Type: Div. 1+2 | Problems: 10 | Verified: 3/10 | Rating range: 800-3500 | Time: 23m 2s Problem Name Rating Tags Solve Time Verified A King Keykhosrow's Mystery 800 brute-force, chinese-remainder-theorem, math 1m 20s ✓ B Rakhsh's Revival 1000 data-structures, greedy, implementation 1m 42s ✗ C Trapped in the Witch's Labyrinth 1400 constructive-algorithms, dfs-and-similar, graphs 3m...

Practice › Codeforces Solutions › Rayan Programming Contest 2024 - Selection (Codeforces Round 989, Div. 1 + Div. 2) ›

CF 2034A - King Keykhosrow's Mystery

CF 2034A - King Keykhosrow's Mystery Rating: 800 Tags: brute force, chinese remainder theorem, math, number theory Solve time: 1m 20s Verified: yes Solution Problem Understanding The problem asks us to find a number that satisfies two properties relative to two given numbers, $a$ and $b$. Specifically, we want the smallest integer $m$ such that $m$ is at least as large as one of the two numbers and the remainder...

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

CF 2097C - Bermuda Triangle

CF 2097C - Bermuda Triangle Rating: 2400 Tags: chinese remainder theorem, geometry, implementation, math, number theory Solve time: 1m 42s Verified: no Solution Problem Understanding The plane moves inside a right triangle with corners at $(0,0)$, $(n,0)$, and $(0,n)$. The aircraft starts strictly inside this triangle at $(x,y)$ and moves with a constant velocity vector $(v_x, v_y)$. Whenever it touches one of the triangle’s sides (except at vertices), it reflects...

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

CF 2077G - RGB Walking

CF 2077G - RGB Walking Rating: 3500 Tags: bitmasks, chinese remainder theorem, dfs and similar, graphs, number theory Solve time: 47s Verified: yes Solution Problem Understanding The problem gives a connected graph with n vertices and m edges. Each edge has three pieces of information: its endpoints, a positive integer weight no larger than x , and a color which is either red, green, or blue. The task is to...

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

CF 2174E2 - Game of Scientists (Version 2)

CF 2174E2 - Game of Scientists (Version 2) Rating: 3200 Tags: binary search, chinese remainder theorem, dfs and similar, interactive, math Solve time: 3m 37s Verified: no Solution Problem Understanding We are interacting with a hidden integer $x$ that is fixed for each game and always lies in the range $[1, c]$, where $c = 2 \cdot 10^9$. Our goal is to determine this number using at most three queries....

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

CF 2174E1 - Game of Scientists (Version 1)

CF 2174E1 - Game of Scientists (Version 1) Rating: 3100 Tags: chinese remainder theorem, constructive algorithms, interactive, math Solve time: 1m 52s Verified: no Solution Problem Understanding We are asked to guess a hidden number x between 1 and c by making queries about the sum of its digits in a chosen base. Each query specifies a base b (between 2 and c ) and returns either the sum of...

Practice › Codeforces Solutions ›

Codeforces Round 1091 (Div. 2) and CodeCraft 26

Codeforces Round 1091 (Div. 2) and CodeCraft 26 Div. 2 | 8 problems | 0/8 verified | Difficulty 800-2800 | 14m 29s # Problem Rating Tags Accepted Time ✓ A The Equalizer 800 math 21,629 1m 40s B Flip the Bit (Easy Version) 1000 greedy, implementation 15,960 1m 42s C Grid Covering 1300 chinese-remainder-theorem, math, number-theory 10,362 1m 40s D Flip the Bit (Hard Version) 1900 greedy, implementation, math 3,312...

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

CF 2217C - Grid Covering

CF 2217C - Grid Covering Rating: 1300 Tags: chinese remainder theorem, math, number theory Solve time: 1m 40s Verified: no Solution Problem Understanding The problem asks whether a person starting at the top-left corner of a grid can eventually visit every cell by jumping in a very specific pattern. The grid has n rows and m columns, and the jumps are modulo-based, meaning the grid wraps around: moving past the...

Practice › Codeforces Solutions ›

Codeforces Round 196 (Div. 1)

Codeforces Round 196 (Div. 1) Div. 1 | 2 problems | 2/2 verified | Difficulty 2600-2900 | 3m 26s # Problem Rating Tags Accepted Time ✓ D GCD Table 2900 chinese-remainder-theorem, math, number-theory 1,403 1m 33s ✓ E Optimize! 2600 data-structures 1,186 1m 53s ✓

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

CF 338D - GCD Table

CF 338D - GCD Table Rating: 2900 Tags: chinese remainder theorem, math, number theory Solve time: 1m 33s Verified: yes Solution Problem Understanding We are asked to determine whether a given sequence of numbers appears as consecutive elements in some row of a hypothetical GCD table. The table has n rows and m columns, where each element at row i and column j is the greatest common divisor of i...

#chinese-remainder-theorem

CF 993E - Nikita and Order Statistics

CF 1054H - Epic Convolution

CF 906D - Power Tower

CF 1117E - Decypher the String

CF 1438C - Engineer Artem

Codeforces Round 707 (Div. 1, based on Moscow Open Olympiad in Informatics)

CF 1500B - Two chandeliers

CF 1536F - Omkar and Akmar

CF 1665D - GCD Guess

CF 1748D - ConstructOR

Good Bye 2022: 2023 is NEAR

CF 1770C - Koxia and Number Theory

CF 2098E - Bermuda Triangle

CF 1993F2 - Dyn-scripted Robot (Hard Version)

CF 1993F1 - Dyn-scripted Robot (Easy Version)

Rayan Programming Contest 2024 - Selection (Codeforces Round 989, Div. 1 + Div. 2)

CF 2034A - King Keykhosrow's Mystery

CF 2097C - Bermuda Triangle

CF 2077G - RGB Walking

CF 2174E2 - Game of Scientists (Version 2)

CF 2174E1 - Game of Scientists (Version 1)

Codeforces Round 1091 (Div. 2) and CodeCraft 26

CF 2217C - Grid Covering

Codeforces Round 196 (Div. 1)

CF 338D - GCD Table