Good Bye 2017

Solutions for Good Bye 2017 (contest 908). 6/8 problems verified against sample I/O. Difficulty range: 800-3100.

8 items

Good Bye 2017

Type: Special | Problems: 8 | Verified: 6/8 | Rating range: 800-3100 | Time: 53m 34s

Problem	Name	Rating	Tags	Solve Time	Verified
A	New Year and Counting Cards	800	brute-force, implementation	1m 34s	✓
B	New Year and Buggy Bot	1200	brute-force, implementation	8m 16s	✓
C	New Year and Curling	1500	brute-force, geometry, implementation	3m 31s	✗
D	New Year and Arbitrary Arrangement	2200	dp, math, probabilities	6m 34s	✓
E	New Year and Entity Enumeration	2500	bitmasks, combinatorics, dp	9m 9s	✗
F	New Year and Rainbow Roads	2400	graphs, greedy, implementation	4m 37s	✓
G	New Year and Original Order	2800	dp, math	17m 58s	✓
H	New Year and Boolean Bridges	3100	-	1m 55s	✓

Practice › Codeforces Solutions › Good Bye 2017 ›

CF 908G - New Year and Original Order

We are given a very large integer $X$, potentially with up to 700 decimal digits. This number is not something we can treat as a standard integer in memory, so any solution must work directly on its digit representation.

Practice › Codeforces Solutions › Good Bye 2017 ›

CF 908F - New Year and Rainbow Roads

We are given a sequence of points on the number line, each colored red, green, or blue. The goal is to connect the points with edges such that every point is reachable from every other point, and the total sum of edge lengths is minimized.

Practice › Codeforces Solutions › Good Bye 2017 ›

CF 908E - New Year and Entity Enumeration

We work with binary vectors of length m, which can be viewed as integers from 0 to 2^m - 1. A valid set S must satisfy three structural properties. First, it contains every vector from the given set T. Second, it is closed under XOR.

Practice › Codeforces Solutions › Good Bye 2017 ›

CF 908B - New Year and Buggy Bot

We have a robot placed in a 2D grid that represents a maze. Each cell of the maze is either empty, denoted by '.', or blocked, denoted by ''. There is a unique starting position 'S' and a unique exit 'E'.

Practice › Codeforces Solutions › Good Bye 2017 ›

CF 908D - New Year and Arbitrary Arrangement

We build a string one character at a time. At each step we append 'a' with probability $$frac{pa}{pa+pb}$$ and append 'b' with probability $$frac{pb}{pa+pb}.$$ For a fixed string, the number of subsequences equal to "ab" is easy to describe.

Practice › Codeforces Solutions › Good Bye 2017 ›

CF 908C - New Year and Curling

We are given a set of disks of equal radius that are initially positioned above the plane at a very high y coordinate.

Practice › Codeforces Solutions › Good Bye 2017 ›

CF 908H - New Year and Boolean Bridges

We are given an unknown directed graph with n nodes. For each pair of nodes u and v, we are told a Boolean condition that involves reachability in the graph: either the AND, OR, or XOR of whether u can reach v and whether v can reach u is true.

Practice › Codeforces Solutions › Good Bye 2017 ›

CF 908A - New Year and Counting Cards

We see one side of every card. A visible side can be either a lowercase letter or a digit. The statement we want to verify is: "Whenever a card has a vowel on one side, the other side contains an even digit." We may flip some cards.