版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
title: "比赛记录 - Codeforces Round #831 (Div. 1 + Div. 2)" date: 2022-10-30 20:10:31 categories:
进度: 5 / 9
<!-- more -->Pak Chanek has a prime number$^\dagger$ $n$. Find a prime number $m$ such that $n + m$ is not prime.
$^\dagger$ A prime number is a number with exactly $2$ factors. The first few prime numbers are $2,3,5,7,11,13,\ldots$. In particular, $1$ is not a prime number.
Each test contains multiple test cases. The first line contains an integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. The following lines contain the description of each test case.
The only line of each test case contains a prime number $n$ ($2 \leq n \leq 10^5$).
For each test case, output a line containing a prime number $m$ ($2 \leq m \leq 10^5$) such that $n + m$ is not prime. It can be proven that under the constraints of the problem, such $m$ always exists.
If there are multiple solutions, you can output any of them.
3
7
2
75619
2
7
47837
In the first test case, $m = 2$, which is prime, and $n + m = 7 + 2 = 9$, which is not prime.
In the second test case, $m = 7$, which is prime, and $n + m = 2 + 7 = 9$, which is not prime.
In the third test case, $m = 47837$, which is prime, and $n + m = 75619 + 47837 = 123456$, which is not prime.
Pak Chanek has $n$ two-dimensional slices of cheese. The $i$-th slice of cheese can be represented as a rectangle of dimensions $a_i \times b_i$. We want to arrange them on the two-dimensional plane such that:
Note that we can arrange them in any order (the leftmost slice of cheese is not necessarily the first slice of cheese). Also note that we can rotate each slice of cheese in any way as long as all conditions still hold.
Find the minimum possible perimeter of the constructed shape.
Each test contains multiple test cases. The first line contains an integer $t$ ($1 \leq t \leq 2 \cdot 10^4$) — the number of test cases. The following lines contain the description of each test case.
The first line of each test case contains an integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the number of slices of cheese Pak Chanek has.
The $i$-th of the next $n$ lines of each test case contains two integers $a_i$ and $b_i$ ($1 \leq a_i,b_i \leq 10^9$) — the dimensions of the $i$-th slice of cheese.
It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
For each test case, output a line containing an integer representing the minimum possible perimeter of the constructed shape.
3
4
4 1
4 5
1 1
2 3
3
2 4
2 6
2 3
1
2 65
26
24
134
In the first test case, a way of getting the minimum possible perimeter is to arrange the slices of cheese as follows.
We can calculate that the perimeter of the constructed shape is $2+5+1+1+1+1+3+1+5+1+2+3=26$. It can be shown that we cannot get a smaller perimeter.
Consider the following invalid arrangement.
Even though the perimeter of the shape above is $24$, it does not satisfy all conditions of the problem. The bottom edge of the $1 \times 1$ slice of cheese is not a segment of the x-axis.
In the second test case, a way of getting the minimum possible perimeter is to arrange the slices of cheese as follows.
We can calculate that the perimeter of the constructed shape is $2+2+2+3+2+3+2+2+2+4=24$. It can be shown that we cannot get a smaller perimeter.
There are $n$ bricks numbered from $1$ to $n$. Brick $i$ has a weight of $a_i$.
Pak Chanek has $3$ bags numbered from $1$ to $3$ that are initially empty. For each brick, Pak Chanek must put it into one of the bags. After this, each bag must contain at least one brick.
After Pak Chanek distributes the bricks, Bu Dengklek will take exactly one brick from each bag. Let $w_j$ be the weight of the brick Bu Dengklek takes from bag $j$. The score is calculated as $|w_1 - w_2| + |w_2 - w_3|$, where $|x|$ denotes the absolute value of $x$.
It is known that Bu Dengklek will take the bricks in such a way that minimises the score. What is the maximum possible final score if Pak Chanek distributes the bricks optimally?
Each test contains multiple test cases. The first line contains an integer $t$ ($1 \leq t \leq 2 \cdot 10^4$) — the number of test cases. The following lines contain the description of each test case.
The first line of each test case contains an integer $n$ ($3 \leq n \leq 2 \cdot 10^5$) — the number of bricks.
The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$) — the weights of the bricks.
It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
For each test case, output a line containing an integer representing the maximum possible final score if Pak Chanek distributes the bricks optimally.
3
5
3 1 5 2 3
4
17 8 19 45
8
265 265 265 265 265 265 265 265
6
63
0
In the first test case, one way of achieving a final score of $6$ is to do the following:
If Pak Chanek distributes the bricks that way, a way Bu Dengklek can take the bricks is:
The score is $|a_5 - a_3| + |a_3 - a_2| = |3 - 5| + |5 - 1| = 6$. It can be shown that Bu Dengklek cannot get a smaller score from this distribution.
It can be shown that there is no other distribution that results in a final score bigger than $6$.
Pak Chanek, a renowned scholar, invented a card puzzle using his knowledge. In the puzzle, you are given a board with $n$ rows and $m$ columns. Let $(r, c)$ represent the cell in the $r$-th row and the $c$-th column.
Initially, there are $k$ cards stacked in cell $(1, 1)$. Each card has an integer from $1$ to $k$ written on it. More specifically, the $i$-th card from the top of the stack in cell $(1, 1)$ has the number $a_i$ written on it. It is known that no two cards have the same number written on them. In other words, the numbers written on the cards are a permutation of integers from $1$ to $k$. All other cells are empty.
You need to move the $k$ cards to cell $(n, m)$ to create another stack of cards. Let $b_i$ be the number written on the $i$-th card from the top of the stack in cell $(n, m)$. You should create the stack in cell $(n, m)$ in such a way so that $b_i = i$ for all $1 \leq i \leq k$.
In one move, you can remove the top card from a cell and place it onto an adjacent cell (a cell that shares a common side). If the target cell already contains one or more cards, you place your card on the top of the stack. You must do each operation while satisfying the following restrictions:
Given the values of $n$, $m$, $k$ and the array $a$, determine if the puzzle is solvable.
Each test contains multiple test cases. The first line contains an integer $t$ ($1 \leq t \leq 2 \cdot 10^4$) — the number of test cases. The following lines contain the description of each test case.
The first line of each test case contains three integers $n$, $m$, and $k$ ($3 \leq n, m \leq 10^6$, $nm \leq 10^6$, $1 \leq k \leq 10^5$) — the size of the board and the number of cards.
The second line of the test case contains $k$ integers $a_1, a_2, \ldots, a_k$ — the array $a$, representing the numbers written on the cards. The values of $a$ are a permutation of integers from $1$ to $k$.
It is guaranteed that the sum of $nm$ and $k$ over all test cases do not exceed $10^6$ and $10^5$ respectively.
For each test case, output "YA" (without quotes) if it is possible and "TIDAK" (without quotes) otherwise, which mean yes and no in Indonesian respectively.
You can output "YA" and "TIDAK" in any case (for example, strings "tiDAk", "tidak", and "Tidak" will be recognised as a negative response).
4
3 3 6
3 6 4 1 2 5
3 3 10
1 2 3 4 5 6 7 8 9 10
5 4 4
2 1 3 4
3 4 10
10 4 9 3 5 6 8 2 7 1
YA
TIDAK
YA
YA
In the first test case, the following is one way the puzzle can be done:
An animated illustration regarding the process mentioned above is as follows:
Pak Chanek has $n$ blank heart-shaped cards. Card $1$ is attached directly to the wall while each of the other cards is hanging onto exactly one other card by a piece of string. Specifically, card $i$ ($i > 1$) is hanging onto card $p_i$ ($p_i < i$).
In the very beginning, Pak Chanek must write one integer number on each card. He does this by choosing any permutation $a$ of $[1, 2, \dots, n]$. Then, the number written on card $i$ is $a_i$.
After that, Pak Chanek must do the following operation $n$ times while maintaining a sequence $s$ (which is initially empty):
After that, Pak Chanek will have a sequence $s$ with $n$ elements. What is the maximum length of the longest non-decreasing subsequence$^\dagger$ of $s$ at the end if Pak Chanek does all the steps optimally?
$^\dagger$ A sequence $b$ is a subsequence of a sequence $c$ if $b$ can be obtained from $c$ by deletion of several (possibly, zero or all) elements. For example, $[3,1]$ is a subsequence of $[3,2,1]$, $[4,3,1]$ and $[3,1]$, but not $[1,3,3,7]$ and $[3,10,4]$.
The first line contains a single integer $n$ ($2 \le n \le 10^5$) — the number of heart-shaped cards.
The second line contains $n - 1$ integers $p_2, p_3, \dots, p_n$ ($1 \le p_i < i$) describing which card that each card hangs onto.
Print a single integer — the maximum length of the longest non-decreasing subsequence of $s$ at the end if Pak Chanek does all the steps optimally.
6
1 2 1 4 2
4
2
1
2
The following is the structure of the cards in the first example.
Pak Chanek can choose the permutation $a = [1, 5, 4, 3, 2, 6]$.
Let $w_i$ be the number written on card $i$. Initially, $w_i = a_i$. Pak Chanek can do the following operations in order:
One of the longest non-decreasing subsequences of $s = [2, 6, 2, 4, 4, 1]$ is $[2, 2, 4, 4]$. Thus, the length of the longest non-decreasing subsequence of $s$ is $4$. It can be proven that this is indeed the maximum possible length.
Pak Chanek is given an array $a$ of $n$ integers. For each $i$ ($1 \leq i \leq n$), Pak Chanek will write the one-element set ${a_i}$ on a whiteboard.
After that, in one operation, Pak Chanek may do the following:
After performing zero or more operations, Pak Chanek will construct a multiset $M$ containing the sizes of all sets written on the whiteboard. In other words, each element in $M$ corresponds to the size of a set after the operations.
How many distinct$^\dagger$ multisets $M$ can be created by this process? Since the answer may be large, output it modulo $998\,244\,353$.
$^\dagger$ Multisets $B$ and $C$ are different if and only if there exists a value $k$ such that the number of elements with value $k$ in $B$ is different than the number of elements with value $k$ in $C$.
The first line contains a single integer $n$ ($1 \le n \le 2000$).
The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq n$).
Output the number of distinct multisets $M$ modulo $998\,244\,353$.
6
1 1 2 1 4 3
7
7
3 5 4 3 7 4 5
11
In the first example, the possible multisets $M$ are ${1,1,1,1,1,1}$, ${1,1,1,1,2}$, ${1,1,1,3}$, ${1,1,2,2}$, ${1,1,4}$, ${1,2,3}$, and ${2,2,2}$.
As an example, let's consider a possible sequence of operations.
Pak Chanek has an $n \times m$ grid of portals. The portal on the $i$-th row and $j$-th column is denoted as portal $(i,j)$. The portals $(1,1)$ and $(n,m)$ are on the north-west and south-east corner of the grid respectively.
The portal $(i,j)$ has two settings:
Each portal has $4$ faces labelled with integers $0,1,2,3$, which correspond to the north, east, south, and west direction respectively.
When a laser enters face $k$ of portal $(i, j)$ with speed $x\text{in}$, it leaves the portal going out of face $(k+2+t{i,j}) \bmod 4$ with speed $x\text{out} = \max(x\text{in},s{i,j})$. The portal also has to consume $x\text{out} - x_\text{in}$ units of energy.
Pak Chanek is very bored today. He will shoot $4nm$ lasers with an initial speed of $1$, one into each face of each portal. Each laser will travel throughout this grid of portals until it moves outside the grid or it has passed through $10^{100}$ portals.
At the end, Pak Chanek thinks that a portal is good if and only if the total energy consumed by that portal modulo $2$ is equal to its type. Given the strength settings of all portals, find a way to assign the type settings of each portal such that the number of good portals is maximised.
The first line contains two integers $n$ and $m$ ($1 \le n, m \le 1000$) — the number of rows and columns in the grid.
The $i$-th of the next $n$ lines contains $m$ integers, with the $j$-th integer being $s{i,j}$ ($1 \leq s{i,j} \leq 10^9$) — the strength of portal $(i, j)$.
Print $n$ lines with each line containing a string of length $m$ consisting of characters $0$ or $1$ representing the type settings. The $j$-th character in the $i$-th string is the type setting of portal $(i, j)$.
If there are multiple solutions, you can output any of them.
2 3
8 8 2
6 5 7
110
100
1 2
420 69
10
In the first example, let's consider the laser Pak Chanek shoots into face $1$ of portal $(2, 2)$. The laser travels as follows:
The illustration of the travel of the laser above is as follows.
As an example, consider portal $(2, 3)$. We can calculate that the total energy consumed by that portal in the end will be $32$. Since $32 \bmod 2 = 0$ and $t_{2,3} = 0$, then it is a good portal.
Given a rooted tree, define the value of vertex $u$ in the tree recursively as the MEX$^\dagger$ of the values of its children. Note that it is only the children, not all of its descendants. In particular, the value of a leaf is $0$.
Pak Chanek has a rooted tree that initially only contains a single vertex with index $1$, which is the root. Pak Chanek is going to do $q$ queries. In the $i$-th query, Pak Chanek is given an integer $x_i$. Pak Chanek needs to add a new vertex with index $i+1$ as the child of vertex $x_i$. After adding the new vertex, Pak Chanek needs to recalculate the values of all vertices and report the sum of the values of all vertices in the current tree.
$^\dagger$ The MEX (minimum excluded) of an array is the smallest non-negative integer that does not belong to the array. For example, the MEX of $[0,1,1,2,6,7]$ is $3$ and the MEX of $[6,9]$ is $0$.
The first line contains a single integer $q$ ($1 \le q \le 3 \cdot 10^5$) — the number of operations.
Each of the next $q$ lines contains a single integer $x_i$ ($1 \leq x_i \leq i$) — the description of the $i$-th query.
For each query, print a line containing an integer representing the sum of the new values of all vertices in the tree after adding the vertex.
7
1
1
3
2
5
2
1
1
1
3
2
4
4
7
8
1
1
1
1
5
6
7
8
1
1
1
1
3
2
4
3
In the first example, the tree after the $6$-th query will look like this.
The sum of the values of all vertices is $0+0+1+0+1+2+0=4$.
In the world of Compfestnesia, Pak Chanek discovers a secret underground dungeon. Inside it, there is a treasure chest that is surrounded by $n$ statues that are arranged in a circular manner. The statues are numbered from $0$ to $n-1$ with statue $i$ being to the left of statue $i+1$ and statue $n-1$ being to the left of statue $0$.
Pak Chanek observes that each statue is holding a crystal ball with an integer between $0$ and $m-1$ inclusive. Let's say the integer in the crystal ball of statue $i$ is $a_i$.
The dungeon provides instructions that every integer in the crystal balls must be $0$ in order to open the treasure chest. To achieve that, Pak Chanek is given an integer $k$, and he can do zero or more operations. In a single operation, Pak Chanek does the following:
Help Pak Chanek find the minimum possible number of operations to open the treasure chest.
The first line contains three integers $n$, $m$, and $k$ ($2 \leq n,m \leq 10^6$, $nm \leq 2 \cdot 10^6$, $1 \leq k < n$) — the number of statues, the bound of the integers in the crystal balls, and the number of statues that can be operated in a single operation.
The second line contains $n$ integers $a_0,a1,\ldots,a{n-1}$ ($0 \leq a_i < m$) — the integers in the crystal balls.
If it is possible to perform zero or more operations so that $a_0=a1=\ldots=a{n-1}=0$, output the minimum number of operations required. Otherwise, output $-1$.
5 9 3
8 1 4 5 0
7
4 4 2
1 0 0 0
-1
5 5 2
1 0 0 0 0
10
In the first example, Pak Chanek can do the following operations: