Codeforces

This repository contains my solutions to Codeforces problems. These solutions are provided "as is" - I give no guarantees that they will work as expected.

Instructions

You can compile all the problems by issuing the following command:

$ ./build

If you want to compile only a specific problem, issue the following command, replacing <problem_id> with the section and identifier of the problem you want to compile (see section "Problems Solved" for the list of possible identifiers):

$ ./build <problem_id>

Running a compiled problem is just a matter of executing a command similar to the next one, replacing <problem_id> with the identifier of the desired problem:

$ ./<problem_id>

Unless stated otherwise, every problem in this repository reads from the standard input and writes to the standard output.

Problems Solved

The following is the list of the problems solved. Each problem identifier is specified between round brackets. Problems marked with ✓ are done, while problems with ✗ are not complete or aren't efficient enough for the problem's limits.

Codeforces Round #379 (Div. 2)

• ✓ A. Anton and Danik (734A)
• ✓ B. Anton and Digits (734B)
• ✓ C. Anton and Making Potions (734C)
• ✓ D. Anton and Chess (734D)
• ✓ E. Anton and Tree (734E)
• ✓ F. Anton and School (734F)

Codeforces Round #380 (Div. 2)

• ✓ A. Interview with Oleg (738A)
• ✓ B. Spotlights (738B)
• ✓ C. Road to Cinema (738C)
• ✓ D. Sea Battle (738D)
• ✓ E. Subordinates (738E)
• ✓ F. Financiers Game (738F)

Codeforces Round #381 (Div. 2)

• ✓ A. Alyona and copybooks (740A)
• ✓ B. Alyona and flowers (740B)

Codeforces Round #382 (Div. 2)

• ✓ A. Ostap and Grasshopper (735A)
• ✓ B. Urbanization (735B)
• ✓ C. Tennis Championship (735C)
• ✓ D. Taxes (735D)

Codeforces Round #383 (Div. 2)

• ✓ A. Arpa’s hard exam and Mehrdad’s naive cheat (742A)
• ✓ B. Arpa’s obvious problem and Mehrdad’s terrible solution (742B)
• ✓ C. Arpa's loud Owf and Mehrdad's evil plan (742C)
• ✓ D. Arpa's weak amphitheater and Mehrdad's valuable Hoses (742D)

Codeforces Round #385 (Div. 2)

• ✓ A. Hongcow Learns the Cyclic Shift (745A)
• ✓ B. Hongcow Solves A Puzzle (745B)
• ✓ C. Hongcow Builds A Nation (745C)
• ✓ D. Hongcow's Game (745D)
• ✓ E. Hongcow Buys a Deck of Cards (745E)

Codeforces Round #388 (Div. 2)

• ✓ A. Bachgold Problem (749A)
• ✓ B. Parallelogram is Back (749B)
• ✓ C. Voting (749C)
• ✓ D. Leaving Auction (749D)

Good Bye 2016

• ✓ A. New Year and Hurry (750A)
• ✓ B. New Year and North Pole (750B)
• ✓ C. New Year and Rating (750C)
• ✓ D. New Year and Fireworks (750D)
• ✓ E. New Year and Old Subsequence (750E)
• ✓ F. New Year and Finding Roots (750F)

Codeforces Round #390 (Div. 2)

• ✓ A. Lesha and array splitting (754A)
• ✓ B. Ilya and tic-tac-toe game (754B)
• ✓ C. Vladik and chat (754C)
• ✓ D. Fedor and coupons (754D)

Codeforces Round #393 (Div. 2) (8VC Venture Cup 2017 - Final Round Div. 2 Edition)

• ✓ A. Petr and a calendar (760A)
• ✓ B. Frodo and pillows (760B)
• ✓ C. Pavel and barbecue (760C)
• ✓ D. Travel Card (760D)

Tinkoff Challenge - Elimination Round

• ✓ A. Oleg and shares (793A)
• ✓ B. Igor and his way to work (793B)
• ✓ C. Mice problem (793C)
• ✓ D. Presents in Bankopolis (793D)
• ✓ E. Problem of offices (793E)

Codeforces Round #409 (rated, Div. 2, based on VK Cup 2017 Round 2)

• ✓ A. Vicious Keyboard (801A)
• ✓ B. Valued Keys (801B)
• ✓ C. Voltage Keepsake (801C)
• ✓ D. Volatile Kite (801D)

Codeforces Round #412 (rated, Div. 2, based on VK Cup 2017 Round 3)

• ✓ A. Is it rated? (807A)
• ✓ B. T-Shirt Hunt (807B)
• ✓ C. Success Rate (807C)
• ✓ D. Dynamic Problem Scoring (807D)
• ✓ E. Prairie Partition (807E)

Codeforces Round #415 (Div. 2)

• ✓ A. Straight <<A>> (810A)
• ✓ B. Summer sell-off (810B)
• ✓ C. Do you want a date? (810C)
• ✓ D. Glad to see you! (810D)

Codeforces Round #424 (Div. 2, rated, based on VK Cup Finals)

• ✓ A. Unimodal Array (831A)
• ✓ B. Keyboard Layouts (831B)

Codeforces Round #439 (Div. 2)

• ✓ A. The Artful Expedient (869A)
• ✓ B. The Eternal Immortality (869B)
• ✓ C. The Intriguing Obsession (869C)
• ✓ E. The Untended Antiquity (869E)

Codeforces Round #440 (Div. 2, based on Technocup 2018 Elimination Round 2)

• ✓ A. Search for Pretty Integers (872A)
• ✓ B. Maximum of Maximums of Minimums (872B)
• ✓ C. Maximum splitting (872C)
• ✓ E. Points, Lines and Ready-made Titles (872E)

Educational Codeforces Round 31

• ✓ A. Book Reading (884A)
• ✓ B. Japanese Crosswords Strike Back (884B)
• ✓ C. Bertown Subway (884C)

Codeforces Round #445 (Div. 2, based on Technocup 2018 Elimination Round 3)

• ✓ A. ACM (890A)
• ✓ B. Vlad and Cafes (890B)
• ✓ C. Petya and Catacombs (890C)
• ✓ D. Restoration of string (890D)

Codeforces Round #447 (Div. 2)

• ✓ A. QAQ (894A)
• ✓ C. Marco and GCD Sequence (894C)
• ✓ D. Ralph And His Tour in Binary Country (894D)

Good Bye 2017

• ✓ A. New Year and Counting Cards (908A)
• ✓ B. New Year and Buggy Bot (908B)
• ✓ C. New Year and Curling (908C)
• ✓ D. New Year and Arbitrary Arrangement (908D)

Educational Codeforces Round 36 (Rated for Div. 2)

• ✓ A. Garden (915A)
• ✓ B. Browser (915B)
• ✓ C. Permute Digits (915C)

Codeforces Round #468 (Div. 2, based on Technocup 2018 Final Round)

• ✓ A. Friends Meeting (931A)
• ✓ B. World Cup (931B)
• ✓ C. Laboratory Work (931C)
• ✓ D. Peculiar apple-tree (931D)

Codeforces Round #470 (Div. 2, based on VK Cup 2018 Round 1)

• ✓ A. Protect Sheep (948A)
• ✓ B. Primal Sport (948B)
• ✓ C. Producing Snow (948C)
• ✓ D. Perfect Security (948D)
• ✓ E. Picking Strings (948E)

Educational Codeforces Round 43 (Rated for Div. 2)

• ✓ A. Minimum Binary Number (976A)
• ✓ B. Lara Croft and the New Game (976B)
• ✓ C. Nested Segments (976C)
• ✓ D. Degree Set (976D)
• ✓ E. Well played! (976E)

Microsoft Q# Coding Contest - Summer 2018 - Warmup

• ✓ A. Generate plus state or minus state (1001A)
• ✓ B. Generate Bell state (1001B)
• ✓ C. Generate GHZ state (1001C)
• ✓ D. Distinguish plus state and minus state (1001D)
• ✓ E. Distinguish Bell states (1001E)
• ✓ F. Distinguish multi-qubit basis states (1001F)
• ✓ G. Oracle for f(x) = k-th element of x (1001G)
• ✓ H. Oracle for f(x) = parity of the number of 1s in x (1001H)
• ✓ I. Deutsch-Jozsa algorithm (1001I)

Microsoft Q# Coding Contest - Summer 2018

• ✓ A1. Generate superposition of all basis states (1002A1)
• ✓ A2. Generate superposition of zero state and a basis state (1002A2)
• ✓ A3. Generate superposition of two basis states (1002A3)
• ✓ A4. Generate W state (1002A4)
• ✓ B1. Distinguish zero state and W state (1002B1)
• ✓ B2. Distinguish GHZ state and W state (1002B2)
• ✓ B3. Distinguish four 2-qubit states (1002B3)
• ✓ B4. Distinguish four 2-qubit states - 2 (1002B4)
• ✓ C1. Distinguish zero state and plus state with minimum error (1002C1)
• ✓ C2. Distinguish zero state and plus state without errors (1002C2)
• ✓ D1. Oracle for f(x) = b * x mod 2 (1002D1)
• ✓ D2. Oracle for f(x) = b * x + (1 - b) * (1 - x) mod 2 (1002D2)
• ✓ D3. Oracle for majority function (1002D3)
• ✓ E1. Bernstein-Vazirani algorithm (1002E1)
• ✓ E2. Another array reconstruction algorithm (1002E2)

Codeforces Round #497 (Div. 2)

• ✓ A. Romaji (1008A)
• ✓ B. Turn the Rectangles (1008B)
• ✓ C. Reorder the Array (1008C)
• ✓ E. Guess two numbers (1008E)

Codeforces Round #499 (Div. 2)

• ✓ A. Stages (1011A)
• ✓ B. Planning The Expedition (1011B)
• ✓ C. Fly (1011C)
• ✓ D. Rocket (1011D)
• ✓ E. Border (1011E)

Codeforces Round #503 (by SIS, Div. 2)

• ✓ A. New Building for SIS (1020A)
• ✓ B. Badge (1020B)
• ✓ C. Elections (1020C)
• ✓ D. The hat (1020D)

AIM Tech Round 5 (rated, Div. 1 + Div. 2)

• ✓ A. Find Square (1028A)
• ✓ B. Unnatural Conditions (1028B)
• ✓ C. Rectangles (1028C)
• ✓ D. Order book (1028D)

Codeforces Round #511 (Div. 1)

• ✓ A. Enlarge GCD (1034A)
• ✓ B. Little C Loves 3 II (1034B)

Manthan, Codefest 18 (rated, Div. 1 + Div. 2)

• ✓ A. Packets (1037A)
• ✓ B. Reach Median (1037B)
• ✓ C. Equalize (1037C)
• ✓ D. Valid BFS? (1037D)
• ✓ E. Trips (1037E)
• ✓ F. Maximum Reduction (1037F)

Codeforces Round #512 (Div. 1, based on Technocup 2019 Elimination Round 1)

• ✓ A. Vasya and Triangle (1053A)

Mail.Ru Cup 2018 Round 2

• ✓ A. Metro (1055A)
• ✓ B. Alice and Hairdresser (1055B)
• ✓ C. Lucky Days (1055C)

Good Bye 2018

• ✓ A. New Year and the Christmas Ornament (1091A)
• ✓ B. New Year and the Treasure Geolocation (1091B)
• ✓ C. New Year and the Sphere Transmission (1091C)
• ✓ D. New Year and the Permutation Concatenation (1091D)

Microsoft Q# Coding Contest - Winter 2019

• ✓ A1. Generate state |00⟩ + |01⟩ + |10⟩ (1116A1)
• ✓ A2. Generate equal superposition of four basis states (1116A2)
• ✓ C1. Alternating bits oracle (1116C1)
• ✓ C2. "Is the bit string periodic?" oracle (1116C2)
• ✓ C3. "Is the number of ones divisible by 3?" oracle (1116C3)
• ✓ D1. Block diagonal matrix (1116D1)
• ✗ D2. Pattern of increasing blocks (1116D2)

Codeforces Round #584

• ✓ A. Paint the Numbers (1209A)
• ✓ B. Koala and Lights (1209B)
• ✓ C. Paint the Digits (1209C)

Educational Codeforces Round 78

• ✓ A. Shuffle Hashing (1278A)
• ✓ B. A and B (1278B)
• ✓ C. Berry Jam (1278C)
• ✓ D. Segment Tree (1278D)

Educational Codeforces Round 81

• ✓ A. Display The Number (1295A)
• ✓ B. Infinite Prefixes (1295B)

Educational Codeforces Round 82

• ✓ A. Erasing Zeroes (1303A)
• ✓ B. National Project (1303B)
• ✓ C. Perfect Keyboard (1303C)
• ✓ D. Fill The Bag (1303D)
• ✓ E. Erase Subsequences (1303E)

Codeforces Round #626 (Div. 1)

• ✓ A. Unusual Competitions (1322A)
• ✓ B. Present (1322B)

Codeforces Round #633 (Div. 2)

• ✓ A. Filling Diamonds (1339A)
• ✓ B. Sorted Adjacent Differences (1339B)
• ✓ C. Powered Addition (1339C)
• ✓ D. Edge Weight Assignment (1339D)

Microsoft Q# Coding Contest - Summer 2020 - Warmup

• ✓ A1. Distinguish I from X (1356A1)
• ✓ A2. Distinguish I from Z (1356A2)
• ✓ A3. Distinguish Z from S (1356A3)
• ✓ A4. Distinguish I ⊗ X from CNOT (1356A4)
• ✓ A5. Distinguish Z from -Z (1356A5)
• ✓ B1. Increment (1356B1)
• ✓ B2. Decrement (1356B2)
• ✓ C. Prepare state |01⟩ + |10⟩ + |11⟩ (1356C)
• ✓ D1. Quantum Classification - 1 (1356D1)
• ✓ D2. Quantum Classification - 2 (1356D2)

Microsoft Q# Coding Contest - Summer 2020

• ✓ A1. Figure out direction of CNOT (1357A1)
• ✓ A2. Distinguish I, CNOTs and SWAP (1357A2)
• ✓ A3. Distinguish H from X (1357A3)
• ✓ A4. Distinguish Rz from R1 (1357A4)
• ✓ A5. Distinguish Rz(θ) from Ry(θ) (1357A5)
• ✓ A6. Distinguish four Pauli gates (1357A6)
• ✓ A7. Distinguish Y, XZ, -Y and -XZ (1357A7)
• ✓ B1. "Is the bit string balanced?" oracle (1357B1)

Codeforces Round 680 (Div. 2, based on Moscow Team Olympiad)

• ✓ A. Array Rearrangment (1445A)
• ✓ B. Elimination (1445B)

Codeforces Round #802 (Div. 2)

• ✓ A. Optimal Path (1700A)
• ✓ B. Palindromic Numbers (1700B)
• ✓ C. Helping the Nature (1700C)
• ✓ D. River Locks (1700D)

Codeforces Round 893 (Div. 2)

• ✓ A. Buttons (1858A)
• ✓ B. The Walkway (1858B)
• ✓ C. Yet Another Permutation Problem (1858C)
• ✓ D. Trees and Segments (1858D)

Interactive Problem Training Contest

• ✓ A. Guess the Number (101021A)