The 17th Zhejiang Provincial Collegiate Programming Contest

12 problems from The 17th Zhejiang Provincial Collegiate Programming Contest (contest 102770), difficulty -. 10/12 solutions verified against sample I/O.

12 items

The 17th Zhejiang Provincial Collegiate Programming Contest

Special | 12 problems | 10/12 verified | Difficulty - | 18m 28s

#	Problem	Time	✓
A	AD 2020	1m 30s	✓
B	Bin Packing Problem	1m 26s	✓
C	Crossword Validation	1m 13s	✓
D	Dividing the Points	3m 45s
E	Easy DP Problem	1m 4s	✓
F	Finding a Sample	1m 18s	✓
G	Gliding	2m	✓
H	Huge Clouds	1m 53s	✓
I	Invoking the Magic	44s	✓
J	Just an Old Problem	1m 18s
K	Killing the Brute-force	59s	✓
L	List of Products	1m 18s	✓

Practice › Codeforces Solutions › The 17th Zhejiang Provincial Collegiate Programming Contest ›

CF 102770J - Just an Old Problem

I can write this editorial, but I do not have a verified derivation of the intended algorithm for Codeforces 102770J - Just an Old Problem from the information provided alone.

Practice › Codeforces Solutions › The 17th Zhejiang Provincial Collegiate Programming Contest ›

CF 102770D - Dividing the Points

I can write this editorial, but the requested version is too large to fit in a single response here. It requires a full proof, a complete Python implementation, two detailed traces, a test harness, and an edge-case section, which together exceed the available response length.

Practice › Codeforces Solutions › The 17th Zhejiang Provincial Collegiate Programming Contest ›

CF 102770B - Bin Packing Problem

We have a sequence of items arriving one by one. Each item has a volume, and every bin has the same maximum capacity. The task is not to find the optimal packing.

Practice › Codeforces Solutions › The 17th Zhejiang Provincial Collegiate Programming Contest ›

CF 102770H - Huge Clouds

The sky is represented by a collection of points, which are stars, and line segments, which are clouds. A point on the x-axis is a possible place where DreamGrid can stand.

Practice › Codeforces Solutions › The 17th Zhejiang Provincial Collegiate Programming Contest ›

CF 102770G - Gliding

Link moves over a lake using a paraglider. The only way to move horizontally is while the paraglider is open, and the fastest horizontal movement is a straight line at speed vh.

Practice › Codeforces Solutions › The 17th Zhejiang Provincial Collegiate Programming Contest ›

CF 102770A - AD 2020

We need count how many calendar days inside a given inclusive interval have the property that their YYYYMMDD representation contains the three consecutive digits 202. A date is not compared as a number with the property. The actual eight-character representation matters.

Practice › Codeforces Solutions › The 17th Zhejiang Provincial Collegiate Programming Contest ›

CF 102770L - List of Products

We are given two collections of integers. Instead of comparing products by their usual numeric value, we compare them by looking at their prime exponent vectors from the smallest prime upward.

Practice › Codeforces Solutions › The 17th Zhejiang Provincial Collegiate Programming Contest ›

CF 102770K - Killing the Brute-force

The problem describes two algorithms that solve the same graph task. For every possible input size n, we know the running time of the intended algorithm and the running time of a slower brute-force algorithm.

Practice › Codeforces Solutions › The 17th Zhejiang Provincial Collegiate Programming Contest ›

CF 102770I - Invoking the Magic

After the first washing stage, every sock color appears exactly twice, but the two socks of the same color may be located in different pairs. We can view each original pair as a connection between two colors.

Practice › Codeforces Solutions › The 17th Zhejiang Provincial Collegiate Programming Contest ›

CF 102770F - Finding a Sample

The input describes two binary classifiers. Each classifier takes an N-dimensional sample vector and computes a weighted sum of its coordinates, then shifts that value by a bias. The sign of this final number is the classifier's answer.

Practice › Codeforces Solutions › The 17th Zhejiang Provincial Collegiate Programming Contest ›

CF 102770E - Easy DP Problem

The straightforward approach is to compute the DP for every query independently. For a segment of length m, we can maintain the states dp[i][j] while scanning its elements. This is correct because the recurrence directly describes the optimal choice among the first i elements.

Practice › Codeforces Solutions › The 17th Zhejiang Provincial Collegiate Programming Contest ›

CF 102770C - Crossword Validation

A crossword board is a square grid where some cells are blocked and the remaining cells already contain letters. A word in this grid is not chosen by clues; instead, it is every maximal continuous sequence of letters that appears horizontally or vertically.