Codecraft-18 and Codeforces Round 458 (Div. 1 + Div. 2, combined)
8 problems from Codecraft-18 and Codeforces Round 458 (Div. 1 + Div. 2, combined) (contest 914), difficulty 900-3400. 6/8 solutions verified against sample I/O.
Codecraft-18 and Codeforces Round 458 (Div. 1 + Div. 2, combined)
Div. 1+2 | 8 problems | 6/8 verified | Difficulty 900-3400 | 38m 3s
| # | Problem | Rating | Tags | Accepted | Time | ✓ |
|---|---|---|---|---|---|---|
| A | Perfect Squares | 900 | brute-force, implementation, math | 15,720 | 4m 38s | ✓ |
| B | Conan and Agasa play a Card Game | 1200 | games, greedy, implementation | 9,058 | 2m 35s | ✓ |
| C | Travelling Salesman and Special Numbers | 1800 | brute-force, combinatorics, dp | 4,209 | 4m | ✓ |
| D | Bash and a Tough Math Puzzle | 1900 | data-structures, number-theory | 6,382 | 4m | ✓ |
| E | Palindromes in a Tree | 2400 | bitmasks, data-structures, divide-and-conquer | 1,920 | 4m 42s | |
| F | Substrings in a String | 3000 | bitmasks, brute-force, data-structures | 2,141 | 2m 54s | ✓ |
| G | Sum the Fibonacci | 2600 | bitmasks, divide-and-conquer, dp | 1,135 | 5m 10s | |
| H | Ember and Storm's Tree Game | 3400 | combinatorics, dp, games | 277 | 10m 4s | ✓ |
CF 914G - Sum the Fibonacci
We are given a sequence of integers, each of which can be thought of as a 17-bit mask. From this array we must form ordered selections of five positions.
CF 914E - Palindromes in a Tree
We are given a tree where each node carries a lowercase character from a limited alphabet of size 20. The task is to examine every simple path in the tree and determine whether the multiset of characters along that path can be rearranged into a palindrome.
CF 914H - Ember and Storm's Tree Game
The game begins with Ember choosing a tree on $n$ labeled vertices, with the restriction that no vertex has degree exceeding $d$. After that, Storm selects an ordered pair of vertices $(u, v)$, which determines a simple path in the tree.
CF 914A - Perfect Squares
We are given an array of integers and need to find the largest element that is not a perfect square. A perfect square is a number that can be expressed as the square of an integer. The input consists of a number n, the size of the array, followed by the array elements.
CF 914C - Travelling Salesman and Special Numbers
We are given an upper bound n, but n is not provided as a decimal integer. Instead, it is given directly as a binary string whose length can be as large as 1000 bits.
CF 914D - Bash and a Tough Math Puzzle
We maintain an array that supports two kinds of operations. The first operation asks about a segment [l, r] and a value x. We want to know whether it is possible to modify at most one element inside that segment so that the gcd of the entire segment becomes exactly x.
CF 914F - Substrings in a String
We are given a mutable string and a sequence of queries. Each query either changes a character at a specific position or asks how many times a smaller string appears as a substring within a specific substring of the main string.
CF 914B - Conan and Agasa play a Card Game
We have a game where Conan and Agasa take turns removing cards from a pile. Each card has a positive integer written on it. When a player chooses a card, not only does that card get removed, but all cards with strictly smaller numbers are removed as well.