#graphs
CF 2222G - Statistics on Tree
CF 2222G - Statistics on Tree Rating: - Tags: binary search, brute force, dfs and similar, divide and conquer, graphs, trees Solve time: 6m 33s Verified: no Solution Problem Understanding We are given a tree. For a pair of vertices $(u,v)$, we remove every edge belonging to the unique simple path between them. After those edges are deleted, the tree breaks into several connected components. The value of the pair...
CF 1949J - Amanda the Amoeba
CF 1949J - Amanda the Amoeba Rating: 2600 Tags: graphs, implementation, trees, two pointers Solve time: 1m 3s Verified: no Solution Problem Understanding We are asked to guide Amanda the Amoeba from an initial configuration to a target configuration on a rectangular grid. Each configuration marks Amanda's body with * , free pixels with . , and blocked pixels with X . Her body is connected and contains at least...
CF 1949G - Scooter
CF 1949G - Scooter Rating: 2300 Tags: graphs, greedy Solve time: 3m 15s Verified: no Solution Problem Understanding Each building has two independent pieces of information. The first string describes what class is held there. A building may need a mathematics professor, a computer science professor, or no professor at all. The second string describes which professor is initially located there. A building may contain a mathematics professor, a computer...
CF 241E - Flights
CF 241E - Flights Rating: 2600 Tags: graphs, shortest paths Solve time: 1m 54s Verified: yes Solution Problem Understanding We are given a directed acyclic graph of cities and one-way flights. Every flight initially takes 1 hour. We may independently change any flight duration to either 1 or 2 hours. The goal is to assign durations so that every possible path from city 1 to city n has exactly the...
CF 46F - Hercule Poirot Problem
CF 46F - Hercule Poirot Problem Rating: 2300 Tags: dsu, graphs Solve time: 1m 1s Verified: yes Solution Problem Understanding We are given a house with a certain number of rooms connected by doors, and each door has a unique key. There are several residents in the house, each initially in some room with some keys. We also know the positions and key holdings of every resident at a later...
CF 48E - Ivan the Fool VS Gorynych the Dragon
CF 48E - Ivan the Fool VS Gorynych the Dragon Rating: 2100 Tags: dp, games, graphs Solve time: 2m 21s Verified: yes Solution Problem Understanding The game state is completely described by two numbers: how many heads and how many tails the dragon currently has. From a state (h, t) Ivan may choose one of two move types. If he cuts i heads, where 1 ≤ i ≤ n and...