This is an array problem.

Given $$$N$$$ numbers, $$$A_1, \dots A_N$$$, answer $$$Q$$$ queries as follows:

Given $$$L, R$$$ where $$$R - L + 1 \geq 4$$$, among all possible $$$L \lt X \lt Y \lt R$$$, maximise $$$A_L \times A_X \times A_Y \times A_R$$$. Output on a single line this maximised value.

$$$1 \leq N, Q \leq 5 \times 10^5$$$

$$$-10^4 \leq A_i \leq 10^4$$$

$$$1 \leq L_i \lt L_i+3 \leq R_i \leq N$$$

As we know, the security of the RSA problem relies on the difficulty of factoring integers.

Generally, the RSA modulus is generated as follows:

• Pick two large prime integers $$$p$$$ and $$$q$$$,
• Compute $$$n = p \cdot q$$$.

Generally speaking, if $$$p$$$ and $$$q$$$ are large enough (e.g. $$$1024$$$-bit primes), then it is infeasible to factorize $$$n$$$, which is our only known strategy to break the security of RSA.

The problem with this strategy, however, is that if we have two modulus $$$n = p \cdot q$$$ and $$$n' = p \cdot q'$$$ for $$$q \ne q'$$$, then we can compute $$$p = \gcd(n, n')$$$, thus factoring both $$$n$$$ and $$$n'$$$. See https://crypto.stackexchange.com/q/76757 for some recent researches on this topic, the most recent research can factors $$$1$$$ in $$$172$$$ in RSA certificates.

Usually, the cause of such collision is poor randomization in the devices used to generate the random primes. Some ways to mitigate the issue is discussed in the question linked above.

If you have a huge collection of, for example, 340 million integers, it would be completely infeasible to compute the $$$\gcd$$$ of each pair. Instead, a batch GCD algorithm is needed. Common implementation of that algorithm is the following:

• Divide the set of modulus into two sets $$$A$$$ and $$$B$$$ of roughly equal sizes.
• Use divide and conquer, compute the product $$$\prod A$$$ of all elements in $$$A$$$, as well as the product $$$\prod B$$$ of all elements in $$$B$$$.

  Using one of the fast integer multiplication algorithms based on FFT, this step can be done in time $$$\tilde O(n)$$$, where $$$n$$$ is the total number of bits representing the numbers in the input.

• Compute $$$\gcd(\prod A,\prod B)$$$. With the half-GCD algorithm, this step can also be done in time $$$\tilde O(n)$$$.

In this problem, you will be solving a much simpler instance with smaller size of integers: Given $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$, determine if there exists any pair with $$$\gcd(a_i, a_j) \gt 1$$$.

It's SoCCat's birthday, and they have baked a delicious cake for the occasion. Unfortunately, there are too many students in SoC who is attending the party and interested in eating the cake. It is not feasible to cut the cake into sectors, otherwise the angle of each sector would be too small.

We model the cake on the Cartesian coordinate plane as a circle with radius $$$10000$$$ (in some unknown unit) with center $$$(0, 0)$$$. $$$N$$$ SoC students are invited to cut the cake, and each of them will be making a single straight cut. The $$$i$$$-th student will make a cut on the straight line from point $$$(x_i, y_i)$$$ to point $$$(x'_i, y'_i)$$$, where $$$(x_i, y_i)$$$ and $$$(x'_i, y'_i)$$$ are distinct points lying on the circumference of the circle.

Obviously, the cake will be divided into several pieces by the cuts. SoCCat wants to know the number of pieces that the cake will be divided into after all the cuts are made, in order to call the correct number of students to eat the cake.

Mara hates the word "perfect" - it means there's nothing left to improve! That's why she really hates graphs with perfect matchings - surely there's something that can be done to make them better, so they shouldn't be called perfect!

You are given a randomly generated tree $$$T$$$ with $$$N$$$ vertices. The $$$i$$$-th edge connects vertices $$$P_{i+1}$$$ and $$$i+1$$$ ($$$1 \leq i \leq N-1$$$). The value of $$$P_i$$$ ($$$2 \leq i \leq N$$$) is uniformly and independently chosen from the set $$$\{1, 2, \ldots, i-1\}$$$.

According to Mara, a graph $$$G = (V, E)$$$ is good (but definitely not perfect) if all of the following conditions are satisfied:

• The graph is simple, connected, and has no self-loops.
• The graph has $$$N$$$ vertices.
• For every edge $$$(u, v) \in E(T)$$$ in the tree, the edge $$$(u, v) \in E(G)$$$ is in the graph $$$G$$$ as well.
• The graph $$$G$$$ has no perfect matching. A perfect matching in a graph exists if and only if there is a set of edges $$$M \subseteq E(G)$$$ such that each vertex in the graph is incident to exactly one edge in the set $$$M$$$.
• For all pairs of vertices such that $$$1 \leq u \lt v \leq N$$$ and the edge $$$(u, v) \not\in E(G)$$$ is not in the graph $$$G$$$, if we add the edge $$$(u, v)$$$ to the graph $$$G$$$, the graph will have a perfect matching. In other words, there is no way to add an additional edge to the graph $$$G$$$ such that the graph remains simple, connected, has no self-loops, and does not have a perfect matching.

As a gift for Mara, you want to construct a set $$$S$$$ of good graphs, such that the size of the set $$$S$$$ is maximum possible. However, you realize that two isomorphic graphs are really just duplicates of each other, so you also want to ensure that no two graphs in the set $$$S$$$ are isomorphic to each other.

Find the maximum value of $$$|S|$$$. Since the value of $$$|S|$$$ may be very large, you only need to output the value of $$$|S| \bmod 998\,244\,353$$$.

Formally, let $$$\mathcal{G}$$$ be the set of all good graphs. You want to construct a set $$$S \subseteq \mathcal{G}$$$ of good graphs, such that for any distinct pairs of graphs $$$G_1, G_2 \in S$$$, $$$G_1$$$ and $$$G_2$$$ are not isomorphic, and the size of the set $$$S$$$ is maximum possible.

There is an event involving $$$N$$$ banks and $$$M$$$ stakeholders, where Bob is stakeholder 1. The banks are giving money to the stakeholders, where bank $$$i$$$ needs to give out a total of $$$A_i$$$ dollars, and each bank can give each person at most $$$K$$$ dollars, to mitigate blatant favouritism. The banks can only give an integer number of dollars to each person, and bank $$$i$$$ must give out all $$$A_i$$$ dollars in this event. Additionally, person $$$i$$$ starts with $$$B_i$$$ dollars, but can only have at most $$$C_i$$$ dollars after receiving money from the banks, as a measure to reduce collusion.

However, Bob has blackmail material on all of the banks, and thus he has the power to decide how much each bank gives each person. He has a nasty and greedy personality, so he wants to be as rich as possible compared to the other $$$M - 1$$$ people. In particular, after the event, let $$$X$$$ be the amount of money (in dollars) that Bob (stakeholder 1) has, and $$$Y$$$ be the maximum amount of money (in dollars), that any of the stakeholders $$$2, 3, \dots, M$$$ has. Then Bob wants to maximise $$$X - Y$$$ (though it can be negative). Help Bob determine the maximum possible value of $$$X - Y$$$.

At the other side of Kivotos, the Trinity General School detected an abnormally high number of monsters in the school's underground system. While many students are trying their best to fend off the monsters, Mika charges in to the center of the anomaly, hoping to find a way to stop the monster raid. Mika finds an obelisk with high concentrations of energy, which is the source of energy of the monsters.

Upon touching the obelisk, a lowercase alphabet letter string $$$S$$$ of length $$$N$$$ is displayed in a hologram. From the given string $$$S$$$, a key must be retrieved to shut down the obelisk. The key of the string $$$S$$$ is defined to be the shortest substring such that it is possible to construct the original string $$$S$$$ from the substring by concatenating and overlapping operations.

For example, the key to the string abbabbababbab is abbab, as the string can be composed of the key like the following:

S   = abbabbababbab
key = abbab
         abbab
              abbab

As the beloved Sensei of Kivotos students, you decide to help Mika to find the key of string $$$S$$$.

Gear wheels can be connected to form chains, where the teeth of adjacent gears interlock. This helps to transmit rotary motion over a long distance.

Now, you have $$$N$$$ gear wheels arranged on a straight line, numbered from $$$1$$$ to $$$N$$$ from left to right. Gear wheel $$$i$$$ has $$$T_i$$$ teeth.

If we connect gear wheel $$$i$$$ to gear wheel $$$j$$$, we can calculate the gear ratio as $$$T_i / T_j$$$ (or $$$T_j / T_i$$$). For the transmission to work perfectly, the gear ratio must be an integer.

You would like to form a longest chain of gear wheels such that the transmission between every pair of adjacent gear wheels works perfectly. Also, as moving the gears around is a lot of work, you are not allowed to reorder the gears on a chain. That is, if gear wheels $$$w_1, w_2, \ldots, w_k$$$ are connected in this order from left to right, then $$$w_1 \lt w_2 \lt \ldots \lt w_k$$$.

That is an easy task for you, so you would like to challenge yourself further. On top of finding one longest chain of gear wheels, you wish to find the maximum number of longest chains of gear wheels that can be formed, while each gear wheel can only be used in one chain.

This is an array problem.

Given two arrays of $$$N$$$ numbers with values $$$A_1, \dots, A_N$$$ and $$$B_1, \dots, B_N$$$. Let $$$A_{L, R}$$$ be the sum of elements in the subarray of $$$A$$$ from index $$$L$$$ to $$$R$$$ inclusive. Let $$$B_{L, R}$$$ be defined similarly.

Minimise $$$A_{L, R}^2 + B_{L, R}^2$$$ across all $$$1\leq L \leq R \leq N$$$.

$$$1 \leq N \leq 5 \times 10^5$$$

$$$-10^9 \leq A_i, B_i \leq 10^9$$$

Alice and Bob will play in a directed graph $$$H$$$. The $$$i$$$-th vertex in $$$H$$$ initially has a value $$$Y_i$$$. The game will proceed as follows.

If $$$H$$$ contains a cycle, then the game is a tie.

Otherwise, Alice and Bob will take turns to choose a vertex in $$$H$$$ to start a chain. Alice starts first. Each player will do all of the following in their turn:

• Choose a vertex $$$v$$$ in $$$H$$$ that has a value $$$x$$$ strictly greater than $$$0$$$.
• Choose any directed path $$$P$$$ starting from $$$v$$$ in $$$H$$$. Note that since the graph is acyclic, all such paths $$$P$$$ is simple. A path is a sequence of vertices $$$v = v_1, v_2, \ldots, v_k$$$ such that $$$(v_i, v_{i+1})$$$ is an edge in $$$H$$$ for all $$$1 \leq i \leq k-1$$$.
• For every vertex $$$u \in P$$$, do the following:
  • If $$$u = v$$$, the player can change the value of vertex $$$v$$$ to any non-negative value strictly less than $$$x$$$. In other words, the player chooses a value $$$y$$$ such that $$$0 \leq y \lt x$$$, and sets the value of vertex $$$v$$$ to $$$y$$$.
  • Otherwise, the player can change the value of vertex $$$u$$$ to any non-negative value.

The player who cannot make a move loses the game.

Note that, because a player can change the value of a vertex to an arbitrarily large value, the number of moves in a game might be unbounded; i.e., "infinite". However, it turns out that the game will eventually always end; i.e., "finite". We shall leave this philosophical question of the "finite" and "infinite" nature of the game to the reader.

We want to find out if Bob can win the game, assuming both players play optimally.

There's a twist: the author of this problem is too lazy to generate strong test cases, so the graph $$$H$$$ and initial values $$$Y_i$$$ are generated randomly, according to the following rules.

You are given a simple undirected graph $$$G = (V, E)$$$ (with no self-loops, and the graph is not necessarily connected) with $$$N$$$ vertices and $$$M$$$ edges. The vertices are numbered from $$$1$$$ to $$$N$$$, where vertex $$$i$$$ has a value $$$X_i$$$. Each edge $$$j$$$ also has a value $$$A_j$$$, $$$B_j$$$, and $$$C_j$$$.

Create the directed graph $$$H$$$ and values $$$Y_i$$$ as follows:

• The vertices of $$$H$$$ are the same as the vertices of $$$G$$$.
• For each vertex $$$v \in H$$$, the value of vertex $$$v$$$ is a independent random integer uniformly chosen between $$$0$$$ and $$$X_v$$$, inclusive.
• For each edge $$$(u, v) \in E$$$, exactly one of the following will happen:
  • with probability $$$\frac{A_i}{A_i + B_i + C_i}$$$, add a directed edge from $$$u$$$ to $$$v$$$ in $$$H$$$;
  • with probability $$$\frac{B_i}{A_i + B_i + C_i}$$$, add a directed edge from $$$v$$$ to $$$u$$$ in $$$H$$$;
  • with probability $$$\frac{C_i}{A_i + B_i + C_i}$$$, do nothing.

Now, the problem becomes: given the graph $$$G$$$ and the values $$$X_i$$$, $$$A_i$$$, $$$B_i$$$, and $$$C_i$$$, find the probability that Bob wins the game, modulo $$$998\,244\,353$$$. It can be proven that the probability that Bob wins the game can be represented as an irreducible fraction $$$\frac{P}{Q}$$$, where $$$P$$$ and $$$Q$$$ are integers, and $$$Q$$$ is coprime to $$$998\,244\,353$$$. You need to output the value of $$$P \cdot Q^{-1} \bmod 998\,244\,353$$$.

After watching the novel "Around the World in Eighty Days", Alice becomes enthusiastic in travelling abroad. However, due to the lack of flights during the COVID-19 pandemic, Alice decides to travel around the world on foot!

However, Alice is suffering from decidophobia, so she is unable to decide how to travel around the world. Hence, she develops an innovative method for generating her path: she randomly generates a grid with size $$$n \times m$$$, with each cell containing an arrow pointing one of the four directions (north, east, south or west). Then, she packs the grid infinitely many times on the map without rotation. The following figure shows what the map looks like after packing the grid:

Demonstration on how Alice packs the grid on the map

It is known that the initial position of Alice matches the top-left corner of the grid. After packing the grids on the map, she starts moving on the map according to the direction of the arrows. Once she reaches another cell, she will continue moving according to the arrow on that new cell. She never stops moving.

When Alice draws her journey on the map, she discovers that some grids may lead to a infinite path: none of the cells she visits will be visited infinitely many times. She doesn't like infinite paths as these paths will often lead to a lonely and boring experience. She likes repetitive paths instead: some of the cells she visits will be visited infinitely many times. The figures below shows an example of a repetitive path and an infinite path:

An example of a repetitive path

An example of an infinite path

Alice plans to change some of the cells in her grid so that the path will become repeating. Once she changes a cell in the grid, all occurrences of the cell in the map will be changed. For example, the infinite path in the figure above can be made repetitive by changing the cell at $$$(3, 3)$$$ to 'S'. The new map is shown below:

The repetitive path after changing the cell at $$$(3, 3)$$$ to 'S'

Can you help Alice to determine the minimum number of cells she needs to change in order to make the path repetitive?

This is an array problem.

You are given an array $$$A$$$ that contains $$$N$$$ numbers, $$$A_1, \dots, A_N$$$. Count the number of distinct subarrays of $$$A$$$ where the sum of the elements in the subarray is even.

Note that an subarray is a contiguous part of an array (E.g. $$$[2, 3, 4]$$$ is a subaarray of $$$[1, 2, 3, 4, 5]$$$). Two subarrays $$$B_i$$$ and $$$C_i$$$ are considered identical if they are of the same length $$$k$$$ and for $$$1 \leq i \leq k, B_i = C_i$$$.

$$$1 \leq N \leq 10^6$$$

$$$-10^9 \leq A_i \leq 10^9$$$

Consider a grid of $$$n$$$ columns and $$$m$$$ rows. Number the columns from $$$0$$$ to $$$n-1$$$ from left to right.

Within the grid, some double-sided mirrors of the form "\" or "/" are placed.

When a laser is shined from the top, it will travel down the grid and might get reflected through the mirrors. For example:

In the example above, the laser ray entering column $$$2$$$ from the top travels out at column $$$4$$$ at the bottom.

Given an integer $$$n$$$ and a permutation $$$p = (p_0, p_1, \dots, p_{n-1})$$$ of $$$\{ 0, 1, \dots, n-1 \}$$$. Find a grid with the minimum nonnegative number of rows $$$m$$$, such that for every $$$i = 0, \dots, n-1$$$, the laser entering column $$$i$$$ from the top will travel out at column $$$p_i$$$ at the bottom.

Each file has at least one test case.

The sum of $$$n$$$ for each file does not exceed $$$10^4$$$.

The output file size does not exceed $$$5 \cdot 10^6$$$ bytes.

There are $$$N$$$ planets in Vita's galaxy. In order to improve the security of the planets, Vita assigned each planet to guard exactly one other planet. In particular, the $$$i$$$-th planet guards the $$$A_i$$$-th planet for every $$$1 \le i \le N$$$.

Vita wants to construct a protective barrier surrounding multiple planets. Let the set of planets to be protected by the barrier be $$$S$$$, then each planet in $$$S$$$ must be guarding a planet not in $$$S$$$.

Help Vita determine the maximum number of planets to be protected by the barrier.