Avito Code Challenge 2018

4 problems from Avito Code Challenge 2018 (contest 981), difficulty 900-3100. 3/4 solutions verified against sample I/O.

4 items

Avito Code Challenge 2018

Special | 4 problems | 3/4 verified | Difficulty 900-3100 | 7m 46s

#	Problem	Rating	Tags	Accepted	Time	✓
A	Antipalindrome	900	brute-force, implementation, strings	10,327	1m 8s	✓
C	Useful Decomposition	1400	implementation, trees	6,856	2m 15s	✓
E	Addition on Segments	2200	bitmasks, data-structures, divide-and-conquer	2,535	2m 22s	✓
H	K Paths	3100	combinatorics, data-structures, dp	288	2m 1s

Practice › Codeforces Solutions › Avito Code Challenge 2018 ›

CF 981H - K Paths

We are given a tree and we choose an ordered list of $k$ simple paths, where each path is defined by two endpoints in the tree. Because paths are on a tree, each pair of vertices determines a unique simple path.

Practice › Codeforces Solutions › Avito Code Challenge 2018 ›

CF 981E - Addition on Segments

We start with an array of length $n$ filled with zeros. There are $q$ operations, each operation adds a positive value $xi$ to every position in a contiguous segment $[li, ri]$. We are not forced to apply all operations.

Practice › Codeforces Solutions › Avito Code Challenge 2018 ›

CF 981C - Useful Decomposition

We are given an undirected tree, and we must split all its edges into a collection of simple paths so that every edge belongs to exactly one path. The extra requirement is global and restrictive: if we pick any two of these paths, they must share at least one common vertex.

Practice › Codeforces Solutions › Avito Code Challenge 2018 ›

CF 981A - Antipalindrome

We are given a single short string made of lowercase English letters. From this string, we are allowed to choose any contiguous substring. Among all such substrings, we are interested in those that are not palindromes, meaning they do not read the same forwards and backwards.