Deltix Round, Spring 2021 (open for everyone, rated, Div. 1 + Div. 2)
Solutions for Deltix Round, Spring 2021 (open for everyone, rated, Div. 1 + Div. 2) (contest 1523). 2/8 problems verified against sample I/O. Difficulty range: 800-3500.
Deltix Round, Spring 2021 (open for everyone, rated, Div. 1 + Div. 2)
Type: Div. 1+2 | Problems: 8 | Verified: 2/8 | Rating range: 800-3500 | Time: 31m 35s
| Problem | Name | Rating | Tags | Solve Time | Verified |
|---|---|---|---|---|---|
| A | Game of Life | 800 | implementation | 12m | ✗ |
| B | Lord of the Values | 1100 | constructive-algorithms | 6m 5s | ✗ |
| C | Compression and Expansion | 1600 | brute-force, data-structures, greedy | 1m 13s | ✗ |
| D | Love-Hate | 2400 | bitmasks, brute-force, dp | 2m 6s | ✓ |
| E | Crypto Lights | 2600 | combinatorics, dp, math | 2m 17s | ✗ |
| F | Favorite Game | 3300 | bitmasks, dp | 2m 24s | ✗ |
| G | Try Booking | 3200 | data-structures, divide-and-conquer | 3m 24s | ✗ |
| H | Hopping Around the Array | 3500 | data-structures, dp | 2m 6s | ✓ |
CF 1523A - Game of Life
The empty output indicates a runtime crash before any printing happens, not a logical error in the math. Tracing the execution on the input: The program first reads t = 3, then processes three test cases.
CF 1523H - Hopping Around the Array
We are asked to help a grasshopper hop across a sequence of tiles represented by an array a. Each tile i contains a number a[i] that defines the maximum distance the grasshopper can jump forward from that tile.
CF 1523G - Try Booking
We are given a flat available for n days and m booking requests. Each request is a segment (li, ri) representing consecutive days someone wants to rent. Requests arrive in chronological order.
CF 1523F - Favorite Game
We are asked to maximize the number of quests William can complete in a 2D grid game with two interacting mechanics: movement and fast travel towers.
CF 1523B - Lord of the Values
We are given an array of even length, representing internal variables of a system. Each variable has an initial positive integer value.
CF 1523E - Crypto Lights
We are asked to compute the expected number of lights that turn on in a line of $n$ lights, given a stopping condition based on consecutive segments of length $k$. Each light starts off, and in each step, one random light that is still off is turned on.
CF 1523D - Love-Hate
We are given a set of n friends, each with their own preferences over m currencies. Each friend likes at most p currencies, so the like-lists are sparse. The goal is to find the largest set of currencies such that at least half of the friends like all the currencies in that set.
CF 1523C - Compression and Expansion
We are given a sequence of integers, each representing the last number of a nested list item after William accidentally erased everything else. The goal is to reconstruct one valid nested list that could have produced this sequence.