表示言語

Problem Statement

Zye is writing AI inference code to run on REGULUS using Mobilint's SDK. Since Zye is a developer who is not very good at coding, the code he writes can compute only tree-shaped graphs.

Using this code, Zye wants to compute a rooted tree-shaped computation graph consisting of N tensors. The root of the tree is node 1. Node i of the tree represents a tensor of size w_i MiB.

A tensor represented by a leaf node is called an input tensor, and a tensor represented by a non-leaf node is called a result tensor. Input tensors already exist in memory in the initial state. The memory usage in the initial state is at most M MiB.

To compute the result tensor represented by node i, all tensors represented by the children of i must currently exist in memory. When computing the result tensor represented by node i, first the result tensor of size w_i MiB is allocated in memory. After the computation is finished, all tensors represented by the children of i are removed from memory.

The memory usage at a certain moment is defined as the sum of the sizes of all tensors that exist in memory at that moment.

Zye wants to choose the computation order so that the peak memory usage while computing the tensor represented by the root node is minimized. The peak memory usage is the maximum memory usage over the initial state and all moments during the computation.

The memory limit of the computer is M MiB. During the computation, the memory usage must always be at most M MiB.

Find the minimum peak memory usage needed to compute the result tensor represented by the root node.

Constraints

• 2 \leq N \leq 5\,000
• M = 8\,192
• w_i = 1
• 1 \leq p_i \leq N
• The given graph is a rooted tree with root node 1.
• All input values are integers.

Sample Input 1

8 8192
1 1 1 1 1 1 1 1
1 1 2 2 4 3 3

Sample Output 1

5

In the initial state, the tensors that exist in memory are the input tensors represented by leaf nodes 5,6,7,8. Therefore, the memory usage is 1+1+1+1=4 MiB.

For example, the result tensors can be computed in the following order.

1. Compute the result tensor represented by node 4. The maximum memory usage during this step is 4+1=5 MiB.
2. Compute the result tensor represented by node 3. The maximum memory usage during this step is 4+1=5 MiB.
3. Compute the result tensor represented by node 2. The maximum memory usage during this step is 3+1=4 MiB.
4. Compute the result tensor represented by node 1. The maximum memory usage during this step is 2+1=3 MiB.

The peak memory usage for this computation order is 5 MiB. It is impossible to make the peak memory usage at most 4 MiB, so the answer is 5.

表示言語

Problem Statement

SCSC has N members. Each member has one spade card and one club card. Member i's spade card has integer S_i written on it, and their club card has integer C_i written on it.

The members of SCSC are standing in a line in the order from member 1 to member N to play the SCSC card game. Terra, the host of the game, must choose two adjacent members and make them play one of the following two duels.

• The two members each reveal the spade card with the smallest integer among their spade cards. The member who reveals the card with the larger integer wins. The losing member gives all of their club cards to the winning member and leaves.

• The two members each reveal the club card with the smallest integer among their club cards. The member who reveals the card with the larger integer wins. The losing member gives all of their spade cards to the winning member and leaves.

Any cards that the leaving member does not give to the winning member are no longer used in the game. If there were members on both sides of the leaving member, those two members become adjacent to each other.

After N-1 duels, exactly one member remains.

The last remaining member gives Terra one card with the smallest integer among their spade cards and one card with the smallest integer among their club cards, then leaves.

Let S_{\mathrm{sum}} be the sum of the integers written on all spade cards initially held by all members, and let C_{\mathrm{sum}} be the sum of the integers written on all club cards initially held by all members. Let S_f be the integer written on the spade card Terra receives at the end, and let C_f be the integer written on the club card Terra receives at the end. Then Terra's final score is (S_{\mathrm{sum}} - S_f)(C_{\mathrm{sum}} - C_f).

Terra wants the final score to be as small as possible. Find the minimum possible score Terra can obtain.

Constraints

• 1 \leq N \leq 5\,000
• 1 \leq S_i, C_i \leq 50\,000
• For all 1 \leq i < j \leq N, S_i \neq S_j and C_i \neq C_j.
• All given numbers are integers.

Sample Input 1

2
3 4
4 5

Sample Output 1

15

表示言語

Problem Statement

You are given an integer array A=[A_1,\dots,A_N] of length N and an integer array B=[B_1,\dots,B_M] of length M.

Find a rearrangement of A in which the number of occurrences of B as a contiguous subsequence is maximized. Here, a rearrangement of A means an array A' satisfying the following condition.

• A' is an integer array of length N, and there exists a permutation P of 1,\dots,N such that A'_i=A_{P_i}(1 \le i \le N).

Constraints

• 1 \le M \le N \le 1\,000\,000
• 0 \le A_i, B_i \le 1\,000\,000
• All given numbers are integers.

Sample Input 1

4 2
1 2 3 4
2 1

Sample Output 1

2 1 3 4 

Sample Input 2

4 2
1 2 1 2
2 1

Sample Output 2

2 1 2 1 

表示言語

Problem Statement

Lulu and Terra are playing with red, green, and blue paints.

Lulu and Terra want to paint a picture consisting of N square cells arranged in a row. Terra first painted part of the picture and then handed the rest over to Lulu. The picture painted by Terra can be represented by a string S of length N consisting of R, G, B, and X. If the i-th character of S is R, the i-th cell is painted red; if it is G, it is painted green; if it is B, it is painted blue; and if it is X, it is an unpainted empty cell.

Lulu does not like the picture Terra painted, so Lulu decided to cut out a certain interval of the picture and make that interval into a perfect picture. According to Lulu, a perfect picture is a picture satisfying the following two conditions.

1. Every cell must be painted one of red, green, and blue.

2. Lulu likes colorful things, so any two adjacent cells must always have different colors.

Lulu can paint empty cells that Terra did not paint in any desired color, and can also repaint cells Terra has already painted in a different color.

The interval Lulu cuts out is represented by two integers l and r, meaning the consecutive interval from the l-th cell to the r-th cell from the left. For each of the Q ways to cut out a certain interval, tell Lulu the minimum number of cells that must be repainted to make the interval a perfect picture.

Constraints

• 1 \leq N, Q \leq 300\,000
• The string S consists only of uppercase letters R, G, B, and X.
• For each query, 1 \leq l_i \leq r_i \leq N.
• All given numbers are integers.

Sample Input 1

8 3
RRXGGGBR
1 8
4 5
2 7

Sample Output 1

2
1
1

表示言語

Problem Statement

Lulu found a magical box containing treasure. The box has N distinct spells cast on it, one of each type, and it can be opened only by dispelling all of them in the correct order. Lulu, a genius magician, has identified all N types of spells on the box, but does not know the correct order in which they must be dispelled.

To open the box, Lulu attempts the following procedure.

1. Lulu chooses one spell that is still cast on the box among the N spells and tries to dispel it. When Lulu tries to dispel the i-th spell, M_i magic power is consumed.

2. If the attempted spell is the correct spell in the order, the dispelling succeeds. If it is not the correct spell in the order, the box returns to the state where all N spells are cast on it. Lulu can immediately tell whether the dispelling attempt succeeded. The order required for dispelling the spells does not change.

3. Once all N spells are dispelled, the box opens.

Given N and the magic power cost M_i of each spell, find the expected total amount of magic power Lulu will consume if Lulu opens the box using an optimal strategy. The correct order of spells is one of the N! possible orders, and all possible orders are equally likely.

Constraints

• 1 \leq N \leq 100\,000
• 1 \leq M_i \leq 100\,000
• All given numbers are integers.

Sample Input 1

1
10

Sample Output 1

10

Sample Input 2

2
10 20

Sample Output 2

35

表示言語

Problem Statement

An infinite sequence (a_n) satisfies the following property.

• For every positive integer i satisfying i>N, a_i is equal to the K-th element of a_{i-N},a_{i-N+1},\dots,a_{i-1} after these values are sorted in nondecreasing order.

Once the values of a_1,\dots,a_N are determined, the values of a_{N+1},a_{N+2},\dots are uniquely determined.

You are given the values of N, K, M and a_1,\dots,a_N. Find a_M.

Constraints

• 1 \leq K \leq N \leq 300\,000
• 1 \leq M \leq 10^{18}
• -10^9 \leq a_i \leq 10^9
• All input values are integers.

Sample Input 1

8 6 9
2 0 2 6 0 5 1 6

Sample Output 1

5

Sorting [2,0,2,6,0,5,1,6] in nondecreasing order, we have [0,0,1,2,2,5,6,6]. Since K=6, we have a_9=5.

Sample Input 2

1 1 1
1

Sample Output 2

1

表示言語

Problem Statement

This year, FuriosaAI officially announced mass production of RNGD, its second-generation AI accelerator. RNGD is specialized for processing language models and multimodal models, and provides powerful computing performance even with low power consumption.

At SCSC, AI agents Lulu and Terra were created using RNGD chips, and SCSC had them play the SCSC game for performance testing.

The SCSC game is played with a string S consisting of uppercase letters S and C that does not contain SCSC as a substring. Lulu and Terra take turns, with Terra going first. On each turn, the current player chooses one character from the string and removes it. If, after the removal, the string contains SCSC as a substring, that player wins and the other player loses. If the current player can no longer choose any character to remove, that player loses and the other player wins.

Thanks to the powerful computing performance of the RNGD chips, Lulu and Terra have become able to always find optimal moves to win. Given the string S, determine which agent wins the game if both Lulu and Terra play optimally.

Constraints

• 1 \leq T \leq 10\,000
• 1 \leq |S| \leq 200\,000
• S consists only of uppercase letters S and C, and does not contain SCSC as a substring.
• The sum of |S| over all test cases does not exceed 200\,000.

Sample Input 1

2
SCSSCCS
SSSS

Sample Output 1

Terra
Lulu

表示言語

Problem Statement

A CUBRID HA cluster is a system consisting of N servers. The servers are numbered from 1 to N.

Jank has become the server administrator of SCSC and wants to choose some of the servers in the CUBRID HA cluster to use. Jank turns on the servers he chooses and turns off the servers he does not choose.

Jank, who rules SCSC, chooses whether each chosen server operates as a Master or as a Slave when turning it on. A Master server can process RW requests and RO requests, and a Slave server can process RO requests and SO requests. Each server can process at most one request at the same time.

If there is no Master server among the currently turned-on servers and at least one Slave server is currently turned on, the currently turned-on Slave server with the smallest number immediately becomes a Master server.

Jank, who rules SCSC, must process Q queries of the following two types in order.

• 1 i: Turn off server i. If it is already turned off, ignore this query.
• 2 a b c: a RW requests, b RO requests, and c SO requests arrive simultaneously.

The requests that arrive in a type-2 query must all be processed using only the servers that are currently turned on. Each request must be assigned to a server that can process that request, and at most one request can be assigned to each server. A request that is not assigned when the query is given cannot be processed.

When all requests have been assigned, each server processes its assigned request and discards the processed request. A server with no remaining request becomes ready to process another request again.

Find the minimum number of servers Jank, who rules SCSC, must choose initially in order to process all requests. If it is impossible to process all requests by any method, output -1 instead.

Constraints

• 1 \leq N,Q \leq 2\,000
• 1 \leq i \leq N
• 0 \leq a,b,c \leq N
• There is at least one query of the second type.
• All input values are integers.

Sample Input 1

3 4
2 2 0 0
1 1
2 0 0 1
2 1 0 1

Sample Output 1

3

表示言語

Problem Statement

Terra is studying how to transform pairs of integers using sums and differences. The transformation method Terra is studying uses the following two operations.

Operation 1: (A, B) \rightarrow (A+B, A-B)

Operation 2: (A, B) \rightarrow (B-A, A+B)

Each transformation process can be represented as a string according to the order in which the operations are used. If the i-th character is 1, operation 1 was chosen as the i-th operation; if it is 2, operation 2 was chosen. A transformation process in which no operation is performed is represented by the empty string, and the length of the string is equal to the number of operations applied.

Terra wants to list all transformation processes that turn (A, B) into (C, D) in order. When each transformation process is represented as a string, strings of shorter length come first, and among strings of the same length, lexicographically smaller strings come first.

The number of test cases T is given, and for each test case, (A, B), (C, D), and P are given. Find the string of the P-th transformation process in this order among the transformation processes that turn (A, B) into (C, D). If the P-th string does not exist in this order, output -1; if the P-th string is the empty string, output EMPTY.

Constraints

• 1 \leq T \leq 100\,000
• -10^9 \leq A, B, C, D \leq 10^9
• 1 \leq P \leq 10^9
• All given numbers are integers.

Sample Input 1

3
1 0 1 0 1
1 0 0 1 1
1 0 2 0 2

Sample Output 1

EMPTY
-1
22

In the first test case, the shortest transformation that turns (1,0) into (1,0) is to do nothing, so EMPTY should be output.

In the second test case, there is no transformation that turns (1,0) into (0,1), so -1 should be output.

表示言語

Problem Statement

N students, numbered from 1 to N, are seated in a circle in numerical order. Each student wears a name tag marked with either O or X. Each student can see the name tags of N-1 students, excluding their own. No three or more students sitting next to each other have name tags with the same letter, and all students are aware of this fact.

The game continues until every student has correctly guessed the letter on their own name tag. The rules of the game are as follows:

• In each round, all students who are certain of the letter on their name tag raise their hands at the same time.
• Once all students have confirmed which students raised their hands in this round, the next round begins.

During the game, no student may exchange name tags with others, remove their name tag, or change the letter on their name tag.

You are given T test cases. For each test case, determine in which round each student will raise their hand for the first time.

Constraints

• 1 \le T \le 100\,000
• 3 \le N \le 100\,000
• S is a string of length N consisting only of O and X.
  • The ith character of S is the character written on the name tag of the ith student.
• None of the three students sitting consecutively are wearing name tags with the same characters written on them.
• The sum of N over all test cases is at most 300\,000.
• All input numbers are integers.

Sample Input 1

4
4
XOXO
3
OOX
3
OXX
6
OXOOXX

Sample Output 1

1 1 1 1 
2 2 1 
1 2 2 
1 1 2 1 1 2 

In the first test case, four students are seated in a circle, each wearing a name tag labeled X, O, X, and O, respectively.

In the first round, Student 2 observes that both Student 1 and Student 3 are wearing name tags labeled X. If Student 2 were wearing a badge marked with X, then Students 2, 3, and 4 would all be wearing badges marked with X, which contradicts the rule that three students sitting consecutively cannot all have badges marked with the same character.

Therefore, Student 2 cannot be wearing a name tag marked with an X and can be certain that they are wearing a name tag marked with an O, so they raise their hand in the first round. The other students also raise their hands in the first round based on the same reasoning.

表示言語

Problem Statement

While exploring the galaxy, Navi and Hyeongtae discovered a cosmic playground! The cosmic playground consists of N points and N-1 bidirectional passages. Each point in the cosmic playground is numbered from 1 to N. The ith passage connects points u_i and v_i in both directions. It is always possible to travel between any two distinct points using only the passages. In other words, the cosmic playground has a tree structure.

Each point is connected to a single slide. For a permutation P=[P_1, P_2, \dots, P_N] of length N, sliding down the slide at point i moves you to point P_i.

Navi wants to slide down the slides non-stop to enjoy the thrill of speed. On the other hand, Hyeongtae is worried that if Navi travels too far, Navi might get lost in space. After much deliberation, Navi and Hyeongtae defined the risk level f(r) of point r as follows:

• The distance between points a and b is the minimum number of passages one must traverse to reach point b from point a using only the passages.
• Navi starts at point s and continues moving using only slides, while Hyeongtae watches Navi from point r. The maximum distance between point r and any point Navi can reach is defined as the maximum distance d(r, s).
• The risk level f(r) when Hyeongtae remains at point r is the sum of the maximum distances \sum\limits_{s = 1}^{N}{d(r, s)} when Navi starts from each point.

Hyeongtae wants to stay at the point where the risk level is minimized. Let us help Hyeongtae by calculating the risk level for each point.

Constraints

• 3 \le N \le 100\,000
• 1 \le u_i < v_i \le N
• The given graph is a tree.
• P is a permutation.
• All input values are integers.

Sample Input 1

6
3 1 2 4 6 5
1 3
2 3
3 4
4 5
4 6

Sample Output 1

14 14 8 8 14 14 

表示言語

Problem Statement

ChannelTalk, an all-in-one AI messenger that facilitates real-time communication with customers, offers a workflow feature that allows anyone to easily create chatbots. Using ChannelTalk Workflow, you can combine triggers and actions like building blocks based on the customer and the situation to automate the entire process from the start to the end of a consultation. Additionally, frequently used functions can be created as modules and reused multiple times.

Ino intends to build a chatbot using ChannelTalk Workflow to handle N different types of questions. Each question is assigned a unique number from 1 to N.

Ino wants to add M modules to the workflow and number them from 0 to M-1 in the order they are added. Since Ino cannot manage too many modules, at most 2\,048 modules can be used.

When question x is entered, module i operates as follows.

• If x = i, it answers the question and ends the consultation.
• If x \neq i, it enters question x to module L_i if x \le F_i, and module G_i if x \gt F_i.

When a question is received, it is first input to module 0, and executing each module takes 1 second. That is, the time taken to process question i is equal to the total number of modules passed through, including module 0 and module i, until the consultation ends. If the same module is passed through multiple times, it is counted as many times as it was passed through.

Ino wants to ensure that the consultation ends in exactly K seconds regardless of which question from 1 to N is asked. Given the number of question types N and the ending time K, choose the number of modules M and the values of F_i, L_i, and G_i for each module so that the consultation always ends exactly at K seconds using at most 2\,048 modules. Note that M does not need to be minimized.

Constraints

• 2 \le K \le N \le 1\,000
• All input values are integers.

Sample Input 1

6 6

Sample Output 1

11
1 7 1
2 7 2
3 7 3
4 7 4
5 5 6
4 0 0
5 0 0
3 8 4
2 9 3
1 10 2
0 0 1