2020-2021 ACM-ICPC Nordic Collegiate Programming Contest (NCPC 2020)
13 problems from 2020-2021 ACM-ICPC Nordic Collegiate Programming Contest (NCPC 2020) (contest 105444), difficulty -. 13/13 solutions verified against sample I/O.
2020-2021 ACM-ICPC Nordic Collegiate Programming Contest (NCPC 2020)
ICPC/IOI | 13 problems | 13/13 verified | Difficulty - | 13m 30s
| # | Problem | Rating | Tags | Accepted | Time | ✓ |
|---|---|---|---|---|---|---|
| A | Array of Discord | 55s | ✓ | |||
| B | Big Brother | 56s | ✓ | |||
| C | Coin Stacks | 58s | ✓ | |||
| D | Dams in Distress | 1m 7s | ✓ | |||
| E | Exhaustive Experiment | 1m 23s | ✓ | |||
| F | Film Critics | 1m 19s | ✓ | |||
| G | Gig Combinatorics | 51s | ✓ | |||
| H | Hiring and Firing | 1m 1s | ✓ | |||
| I | Infection Estimation | 55s | ✓ | |||
| J | Joining Flows | 53s | ✓ | |||
| K | Keep Calm And Carry Off | 1m 13s | ✓ | |||
| L | Language Survey | 1m 6s | ✓ | |||
| M | Methodic Multiplication | 53s | ✓ |
CF 105444M - Methodic Multiplication
We are given two natural numbers, but they are not written in decimal form. Instead, each number is encoded using Peano arithmetic, where a number is represented as repeated applications of a successor function applied to zero.
CF 105444K - Keep Calm And Carry Off
We are given two very large positive integers written in decimal, each potentially up to one million digits. Petra can modify these numbers using a very specific operation: she picks one of the two numbers, adds 1 to it, and simultaneously subtracts 1 from the other number, so…
CF 105444L - Language Survey
We are given an $n times m$ grid, and each cell contains only partial information about how many of three unknown languages are spoken there. Every cell is marked either with 1 or 2.
CF 105444J - Joining Flows
We are given a small number of chocolate faucets, each faucet producing chocolate at a fixed temperature, but with a controllable flow rate constrained to an interval.
CF 105444H - Hiring and Firing
We are given a fixed schedule of how a company’s workforce changes over time. Each day, a known number of workers are fired and a known number are hired, and the system guarantees that the number of firings never exceeds the number of currently employed workers.
CF 105444I - Infection Estimation
We are interacting with a system that hides an unknown number of infected people inside a population of fixed size. The only tool we have is a probabilistic group test: we choose a subset size k, and the judge randomly selects k distinct people.
CF 105444G - Gig Combinatorics
We are given a sequence of songs in the order they were written. Each song has a label, which can only be 1, 2, or 3. We want to count how many contiguous subsequences of these songs form a valid “setlist”.
CF 105444E - Exhaustive Experiment
Each component is a point on a plane with integer coordinates, and each point is labeled either as untested, positively tested, or negatively tested. We are asked to assume that some subset of these points are “leaking sources”.
CF 105444F - Film Critics
We are asked to arrange a set of film critics in an order that determines how they score a movie, where each critic’s final rating is not only based on their own initial opinion but also on the current average score produced by earlier critics. The process works sequentially.
CF 105444D - Dams in Distress
The system is a rooted tree where every node is a dam, and the root represents the war camp. Each dam has a capacity and a current stored amount of water. Water can be added at exactly one chosen node.
CF 105444C - Coin Stacks
We are given several stacks of coins. In one move, two players jointly choose two different stacks and remove exactly one coin from each of those stacks. They keep doing this until no coins remain anywhere.
CF 105444B - Big Brother
We are given the boundary of a simple polygon representing a floor plan. The vertices are listed in clockwise order, and the polygon can have a very large number of vertices, up to half a million.
CF 105444A - Array of Discord
We are given a nondecreasing sequence of integers, where each value is written in decimal form. The gods want the sequence to stay sorted, meaning each element must remain less than or equal to the next.