2018-2019 Summer Petrozavodsk Camp, Oleksandr Kulkov Contest 2

9 problems from 2018-2019 Summer Petrozavodsk Camp, Oleksandr Kulkov Contest 2 (contest 102354), difficulty -. 4/9 solutions verified against sample I/O.

9 items

2018-2019 Summer Petrozavodsk Camp, Oleksandr Kulkov Contest 2

Special | 9 problems | 4/9 verified | Difficulty - | 1h

#	Problem	Time	✓
A	Square Root Partitioning	2m 28s	✓
B	Yet Another Convolution	16m 18s
C	Money Sharing	2m 43s
D	Magic Strings	7m	✓
E	Decimal Expansion	1m 30s	✓
F	Cosmic Crossroads	10m 10s
H	Defying Gravity	5m 57s
I	From Modular to Rational	5m 15s
J	Tree Automorphisms	9m 36s	✓

Practice › Codeforces Solutions › 2018-2019 Summer Petrozavodsk Camp, Oleksandr Kulkov Contest 2 ›

CF 102354I - From Modular to Rational

We need to recover a positive rational number (x=p/q), where both (p) and (q) are at most (10^9). We cannot see (p) and (q) directly. Instead, for a chosen prime modulus (m), the judge gives the integer (r) in the range (0le r<m) satisfying [ requiv p q^{-1}pmod m.

Practice › Codeforces Solutions › 2018-2019 Summer Petrozavodsk Camp, Oleksandr Kulkov Contest 2 ›

CF 102354B - Yet Another Convolution

We have two arrays, (a) and (b), both indexed from (1) to (n). For every possible greatest common divisor (k), we must find the largest absolute difference ( The (10^5) bound rules out anything close to quadratic.

Practice › Codeforces Solutions › 2018-2019 Summer Petrozavodsk Camp, Oleksandr Kulkov Contest 2 ›

CF 102354C - Money Sharing

We process one chronological sequence containing two kinds of events. A positive value means that this much money is added to the shared account. A negative value represents a borrowing request whose size is the absolute value of that number.

Practice › Codeforces Solutions › 2018-2019 Summer Petrozavodsk Camp, Oleksandr Kulkov Contest 2 ›

CF 102354H - Defying Gravity

We have a collection of point satellites around the origin. Each satellite has an angular position, a distance from the origin, and a mass.

Practice › Codeforces Solutions › 2018-2019 Summer Petrozavodsk Camp, Oleksandr Kulkov Contest 2 ›

CF 102354F - Cosmic Crossroads

We are given two collections of (n) unoriented lines through the origin. Each line is represented by its two intersections with the unit sphere, so every collection contains (2n) unit vectors and every vector occurs together with its negation.

Practice › Codeforces Solutions › 2018-2019 Summer Petrozavodsk Camp, Oleksandr Kulkov Contest 2 ›

CF 102354J - Tree Automorphisms

We are given an undirected tree with vertices numbered from 1 to (n). An automorphism is a permutation of the vertices that preserves adjacency, so after applying the permutation, every edge must still connect exactly the same structural positions in the tree.

Practice › Codeforces Solutions › 2018-2019 Summer Petrozavodsk Camp, Oleksandr Kulkov Contest 2 ›

CF 102354E - Decimal Expansion

The constant can be rewritten as [ varphi=prod{k=1}^{infty}(1-10^{-k}), ] because the (k)-th factor is exactly ((10^k-1)/10^k). We need the digit occupying position (n) after the decimal point, where (n) may be as large as (10^{18}). There are up to (10^5) independent queries.

Practice › Codeforces Solutions › 2018-2019 Summer Petrozavodsk Camp, Oleksandr Kulkov Contest 2 ›

CF 102354D - Magic Strings

We need the number of different subsequences of a recursively defined binary string. The first string is ab, and every next string is obtained by taking the previous string twice and then appending one more b. Thus the strings themselves become exponentially long.

Practice › Codeforces Solutions › 2018-2019 Summer Petrozavodsk Camp, Oleksandr Kulkov Contest 2 ›

CF 102354A - Square Root Partitioning

We have an array of positive integers (a1,dots,an). The first square root is always taken with a plus sign, while every later term may independently receive either (+) or (-). We need to count how many choices make [ sqrt{a1}pmsqrt{a2}pmcdotspmsqrt{an}=0.