Problem Set 1
Problem 1. Counting Segments Inside an Interval
Metadata
- Author: Aiyiyi
- Date proposed: February 25, 2021
- Origin: Original
- Acknowledgements: Thanks to Kinesis and LightningUZ for their contributions to the problem discussion.
Statement
There are initially \(k\) segments on the positive integer number line. Each segment is represented by a pair of integers \((L, R)\), where \(L < R\).
You need to maintain the set of segments while processing \(m\) operations. There are two types of operations:
- \(\texttt{add}\ L\ R\): insert the segment \((L, R)\).
- \(\texttt{query}\ L\ R\): count how many currently stored segments are fully contained in the interval \([L, R]\).
In other words, a segment \((L', R')\) is counted for a query \((L, R)\) if and only if
\[ L \le L' < R' \le R. \]
Constraints
\[ 1 \le m,\ k \le 10^{6}, \qquad 1 \le L < R \le 10^{9}. \]
Problem 2. Totient LCM Sum
Metadata
- Author: Aiyiyi
- Date proposed: February 25, 2021
- Origin: Original
- Acknowledgements: Thanks to Kinesis and LightningUZ for their contributions to the problem discussion.
Statement
Given a positive integer \(n\), compute
\[ \sum_{i=1}^{n} \sum_{j=1}^{n} \lambda(i, j), \]
where
\[ \lambda(x, y) = \operatorname{lcm}\bigl(\varphi(x), \varphi(y)\bigr). \]
Here \(\varphi\) denotes Euler's totient function, and \(\operatorname{lcm}\) denotes the least common multiple.
Output the answer modulo \(998244353\).
Constraints
\[ 1 \le n \le 10^{6}. \]
Problem 3. Counting Vertex Sets on a Common Path
Metadata
- Author: Aiyiyi
- Date proposed: February 25, 2021
- Origin: Independently discovered by Aiyiyi
- Acknowledgements: Thanks to Yoluko for their contribution to the problem discussion.
- Related reference: Library Checker: Frequency Table of Tree Distance
Statement
You are given a tree with \(n\) vertices.
For every integer \(K\) such that \(1 \le K \le n\), count the number of ways to choose exactly \(K\) vertices such that all selected vertices lie on a single simple path of the tree.
Output each answer modulo \(998244353\).
Constraints
\[ 1 \le n \le 10^{5}. \]
Comments have been disabled for this content