Best Edge Weight 题目描述You are given a connected weighted graph with $n$ vertices and $m$ edges. The graph doesn’t contain loops nor multiple edges. Consider some edge with id $i$. Let’s determine for this edge the maxi 2017-07-22 OI > Common Skill #Greedy #Lowest Common Ancestor #Minimum Spanning Tree #Union Find
Petya and Tree 题目描述One night, having had a hard day at work, Petya saw a nightmare. There was a binary search tree in the dream. But it was not the actual tree that scared Petya. The horrifying thing was that Petya 2017-07-22 OI > Number Theory #Probability #Depth-First-Search #Tree #Binary-Search
Sum of Medians 题目描述In one well-known algorithm of finding the $k$-th order statistics we should divide all elements into groups of five consecutive elements and find the median of each five. A median is called the m 2017-07-21 OI > Data Structure #Self-Balancing Binary Search Tree #Segment Tree #Discretization
Opening Portals 题目描述Pavel plays a famous computer game. A player is responsible for a whole country and he can travel there freely, complete quests and earn experience. This country has $n$ cities connected by $m$ bi 2017-07-20 OI > Data Structure #Minimum Spanning Tree #Union Find #Shortest Path
DZY Loves Fibonacci Numbers 题目描述In mathematical terms, the sequence $F_n$ of Fibonacci numbers is defined by the recurrence relation: $$F_1=1, \ F_2=1, \ F_n=F_{n-1}+F_{n-2} \ (n \gt 2)$$ DZY loves Fibonacci numbe 2017-07-20 OI > Data Structure #Segment Tree
DZY Loves Modification 题目描述As we know, DZY loves playing games. One day DZY decided to play with a $n \times m$ matrix. To be more precise, he decided to modify the matrix with exactly $k$ operations. Each modification is o 2017-07-20 OI > Common Skill #Greedy #Priority Queue
Skills 题目描述Lesha plays the recently published new version of the legendary game hacknet. In this version character skill mechanism was introduced. Now, each player character has exactly $n$ skills. Each skil 2017-07-20 OI > Common Skill #Greedy #Two Pointers
Peter and Snow Blower 题目描述Peter got a new snow blower as a New Year present. Of course, Peter decided to try it immediately. After reading the instructions he realized that it does not work like regular snow blowing machin 2017-07-19 OI > Computational Geometry #Plane Geometry
String Compression 题目描述Ivan wants to write a letter to his friend. The letter is a string $s$ consisting of lowercase Latin letters. Unfortunately, when Ivan started writing the letter, he realised that it is very long 2017-07-17 OI > Common Skill #Dynamic Programming
Minimal Labels 题目描述You are given a directed acyclic graph with $n$ vertices and $m$ edges. There are no self-loops or multiple edges between any pair of vertices. Graph can be disconnected. You should assign labels 2017-07-17 OI > Data Structure #Topological-Sort #Priority Queue