2020 ICPC Universidad Nacional de Colombia Programming Contest

13 problems from 2020 ICPC Universidad Nacional de Colombia Programming Contest (contest 102700), difficulty -. 12/13 solutions verified against sample I/O.

13 items

2020 ICPC Universidad Nacional de Colombia Programming Contest

ICPC/IOI | 13 problems | 12/13 verified | Difficulty - | 1h 3m

#	Problem	Time	✓
A	Approach	3m 48s	✓
C	Cipher count	8m 21s	✓
D	Dice	1m 58s	✓
E	Enter to the best problem of this contest!	1m 21s	✓
F	Free restricted flights	6m 4s	✓
G	Great dinner	5m 50s	✓
H	Happy game	36s	✓
I	Incredible photography	1m 2s
J	Java exam	7m 31s	✓
K	Katastrophic sort	57s	✓
L	Lonely day	7m 46s	✓
M	Magic spells	13m 7s	✓
N	Name this problem	5m 5s	✓

Practice › Codeforces Solutions › 2020 ICPC Universidad Nacional de Colombia Programming Contest ›

CF 102700M - Magic spells

We have one reference string s. Every non-empty subsequence of s is considered a valid spell. For each input string a, some original spell has been followed by an arbitrary suffix, so the useful part of a is exactly its longest prefix that can still be embedded as a…

Practice › Codeforces Solutions › 2020 ICPC Universidad Nacional de Colombia Programming Contest ›

CF 102700N - Name this problem

Jolany has a year consisting of n days. On each day she can try the time machine once. If the machine succeeds, she immediately reaches her next birthday.

Practice › Codeforces Solutions › 2020 ICPC Universidad Nacional de Colombia Programming Contest ›

CF 102700J - Java exam

Each student points to exactly one favorite partner. If we draw an edge from a student to their favorite partner, the anti-symmetry condition means that there cannot be a directed cycle involving two different students.

Practice › Codeforces Solutions › 2020 ICPC Universidad Nacional de Colombia Programming Contest ›

CF 102700C - Cipher count

The key observation is that two different key strings do not necessarily represent two different Vigenère ciphers. If a key is itself a repetition of a shorter string, extending either key periodically produces exactly the same sequence of shifts.

Practice › Codeforces Solutions › 2020 ICPC Universidad Nacional de Colombia Programming Contest ›

CF 102700L - Lonely day

We have an N × M grid whose cells are either clean or dirty. The cells containing S and E are also clean. Vitor may move between side-adjacent clean cells in one step.

Practice › Codeforces Solutions › 2020 ICPC Universidad Nacional de Colombia Programming Contest ›

CF 102700G - Great dinner

We have (N) distinct students who must be arranged in a line. Among them, there are (M) disjoint bully-victim pairs. For every input pair ((A,B)), student (A) must appear before student (B). The statement describes this as (B) not being ahead of (A).

Practice › Codeforces Solutions › 2020 ICPC Universidad Nacional de Colombia Programming Contest ›

CF 102700F - Free restricted flights

Think of the countries as vertices of a directed weighted graph. A flight from country u to country v is a directed edge with positive cost w. Alice starts at country a, Bob starts at country b, and they must choose some third country where they can meet.

Practice › Codeforces Solutions › 2020 ICPC Universidad Nacional de Colombia Programming Contest ›

CF 102700A - Approach

There are two friends moving simultaneously on the plane. The first starts at point (A) and walks straight toward (B). The second starts at (C) and walks straight toward (D).

Practice › Codeforces Solutions › 2020 ICPC Universidad Nacional de Colombia Programming Contest ›

CF 102700K - Katastrophic sort

Each input string has a very specific structure. It begins with a non-empty sequence of lowercase letters, followed immediately by a non-empty sequence of digits. We are given two such strings and must compare them using a custom ordering.

Practice › Codeforces Solutions › 2020 ICPC Universidad Nacional de Colombia Programming Contest ›

CF 102700I - Incredible photography

I can't write a correct editorial for this problem because the statement alone is not sufficient to reconstruct the intended algorithm with confidence. The crucial ambiguity is the movement rule. The statement says Paula repeatedly chooses a building that: 1.

Practice › Codeforces Solutions › 2020 ICPC Universidad Nacional de Colombia Programming Contest ›

CF 102700H - Happy game

A comparison table between the brute-force and optimal solutions. A proof sketch explaining why the algorithm is correct. A complete accepted Python 3 implementation using: followed by a detailed explanation of every part of the implementation.

Practice › Codeforces Solutions › 2020 ICPC Universidad Nacional de Colombia Programming Contest ›

CF 102700E - Enter to the best problem of this contest!

A direct approach is to query every node in the tree until finding a node whose distance is zero. This is correct because the device gives the exact distance, so a zero response identifies Osman immediately.

Practice › Codeforces Solutions › 2020 ICPC Universidad Nacional de Colombia Programming Contest ›

CF 102700D - Dice

We have a collection of identical loaded dice. A single die can show every number from 1 to k except numbers divisible by m. All allowed faces are equally likely, so the only thing that matters for the final sum is the remainder of each roll modulo m.