As per tradition, we are collecting your favorite phrases!
However, this time, there are some rules. Christian particularly likes phrases that have exactly $$$n$$$ space-free substrings — substrings that don't contain the space character. For example, the phrase "$$$\mathrm{Hey \; yo}$$$" has $$$9$$$ space-free substrings: $$$\mathrm{Hey}$$$, $$$\mathrm{He}$$$, $$$\mathrm{ey}$$$, $$$\mathrm{H}$$$, $$$\mathrm{e}$$$, $$$\mathrm{y}$$$, as well as $$$\mathrm{yo}$$$, $$$\mathrm{y}$$$, and $$$\mathrm{o}$$$.
If one space-free substring appears multiple times, it is counted that many times. In other words, we count the total number of space-free substrings, not the number of unique space-free subtrings.
Given a positive integer $$$n$$$, output a phrase with exactly $$$n$$$ space-free substrings.
The input contains a single integer $$$n$$$ ($$$1 \leq n \leq 100$$$) — the number of space-free substrings in your phrase.
Output a phrase with exactly $$$n$$$ space-free substrings on one line. You may use lowercase and uppercase English letters and spaces. Your phrase may have at most 10 words. The words in your phrase don't have to be actual English words.
9
Hey yo
21
Proof by AC
For an array $$$a$$$ of length $$$n$$$, we define the aura of the array to be the number of indices $$$i$$$ ($$$1 \leq i \leq n-1$$$) such that at least one of the following conditions holds:
- $$$a_i = 6$$$ and $$$a_{i+1} = 7$$$
- $$$a_i = 7$$$ and $$$a_{i+1} = 6$$$
You are given an array $$$a$$$ of length $$$n$$$. You may perform the following operation any number of times:
- Choose an index $$$i$$$ ($$$1 \leq i \leq n-1$$$) and swap the elements $$$a_i$$$ and $$$a_{i+1}$$$ in the array $$$a$$$.
After performing the operation some number of times (possibly zero), you would like to know the maximum possible aura of the resulting array $$$a$$$.
The first line of input contains a single integer $$$n$$$ ($$$2 \leq n \leq 100$$$).
The second line of input contains $$$n$$$ integers $$$a_1, a_2, ..., a_n$$$ ($$$1 \leq a_i \leq 100$$$).
Output a single integer — the maximum possible aura of the array $$$a$$$ after performing any number of operations.
41 2 3 4
0
72 6 1 7 3 5 4
1
56 6 7 7 7
4
In the first example, no number of operations can result in an aura greater than 0.
In the second example, the elements $$$1$$$ and $$$6$$$ can be swapped to obtain $$$[2, 1, 6, 7, 3, 5, 4]$$$, which has an aura of $$$1$$$.
You are given an array of $$$n$$$ positive integers and $$$q$$$ queries.
On each query, you are given a positive integer $$$x$$$. You need to output $$$\max\limits_{i=1}^n \left[\mathrm{lcm}{(x, a_i)} \right]$$$.
In other words, what is the maximum least common multiple of $$$x$$$ with any number from $$$a$$$?
The first line contains two integers $$$n, q$$$ ($$$1 \leq n, q \leq 5 \cdot 10^5$$$) — the size of the array $$$a$$$, and the number of queries.
The second line contains $$$n$$$ space-separated integers $$$a_1, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^6$$$) — the array.
The third line contains $$$q$$$ space-separated integers $$$x_1, \ldots, x_q$$$ ($$$1 \leq x_i \leq 10^6$$$) — the queries.
Output a single line containing $$$q$$$ space-separated integers — the answers to the queries.
We strongly recommend using fast I/O for this problem.
5 56 4 1 10 85 6 7 8 20
40 30 70 40 60
In the example test case, the optimal pairs are $$$\mathrm{lcm}(5, 8) = 40, \; \mathrm{lcm}(6, 10) = 30, \; \mathrm{lcm}(7, 10) = 70, \; \mathrm{lcm}(8, 10) = 40, \; \mathrm{lcm}(20, 6) = 60$$$.
You originally joined Columbia Space Initiative to build and program rockets, but ever since Columbia Housing colonized a distant planet and finished a set of new constructions, your duties have been reassigned. You are about to board the spaceship to the new planet, Carlton Legs, when you remember you'll need to buy metal house numbers to affix to the front of your new house (so it can be identified for maintenance). Unfortunately, the 250 light-year journey back is reserved for Columbia Housing staff, so you'll need to buy your house numbers before you leave.
You know that there are only $$$n$$$ houses on the planet, numbered from $$$1$$$ to $$$n$$$, but you aren't sure which one you've been assigned. University Hardware sells individual metal digits $$$0$$$–$$$9$$$ for $$$1$$$ dollar apiece, with an infinite supply of each digit, and you can buy as many digits as necessary to label your house. What is the minimal amount you must spend to ensure that, regardless of which house number you are assigned, you'll be able to label your house using the digits you bought?
The first and only line of input contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^9$$$), the maximal house number you could be assigned.
Output one integer — the minimal number of digits $$$0$$$–$$$9$$$ you'll need to buy to ensure that any house number from $$$1$$$ to $$$n$$$ can be written using them.
7
7
17
11
6666667
66
In example 1, you can buy the digits $$$1$$$ through $$$7$$$, which can be used to make each house number from $$$1$$$ through $$$7$$$.
In example 2, you can buy one $$$0$$$, two $$$1$$$s, and one of each digit $$$2$$$–$$$8$$$. It can be shown that the numbers $$$1$$$–$$$17$$$ can each be created using only these digits. For example, $$$11$$$ uses both of the $$$1$$$s, and $$$17$$$ uses one $$$1$$$ and one $$$7$$$.
The next season of Squid Game is about to begin! The Frontman put you in charge of the third game of the season, Mingle.
Mingle is defined by an initial number of players $$$p$$$, the number of safe rooms $$$m$$$, and a sequence of $$$k$$$ positive integers $$$b_1, \ldots, b_k$$$.
The game consists of $$$k$$$ rounds. In the $$$i$$$-th round, the remaining players need to form teams of size exactly $$$b_i$$$, and each team must hide in one of the $$$m$$$ safe rooms. Each safe room admits at most one team. If a player doesn't join a team of size $$$b_i$$$, or their team doesn't hide in a safe room, they are eliminated.
All players who survive the $$$i$$$-th round advance to the next, $$$i+1$$$-th round. Teams may change arbitrarily between rounds. Players who have made it past round $$$k$$$ are declared the winners of Mingle.
The Frontman is interested in computing the maximum possible number of winners in the game. However, since neither the initial number of players nor the sequence itself has been determined yet, you need to answer multiple queries about the game.
At the start, you are given a sequence $$$a$$$ of size $$$n$$$ and the number of safe rooms $$$m$$$, fixed for all queries. Then, $$$q$$$ queries follow. Each query is one of two types:
- $$$1 \; i \; x$$$ ($$$1 \leq i \leq n$$$, $$$1 \leq x \leq 10^9$$$) — update $$$a_i := x$$$.
- $$$2 \; l \; r \; p$$$ ($$$1 \leq l \leq r \leq n$$$, $$$1 \leq p \leq 10^9$$$) — what is the maximum number of winners in Mingle played on the sequence $$$a_l, a_{l+1}, \ldots, a_r$$$ with $$$m$$$ safe rooms and $$$p$$$ initial players?
For each query of type $$$2$$$, output the maximum possible number of winners. Note that queries of type $$$2$$$ are independent from each other.
The first line contains two integers $$$n, m$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq m \leq 100$$$) — the size of $$$a$$$, and the number of safe rooms.
The second line contains $$$n$$$ space-separated integers $$$a_1, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the initial sequence.
The third line contains a single integer $$$q$$$ ($$$1 \leq q \leq 2 \cdot 10^5$$$) — the number of queries.
The next $$$q$$$ lines describe the queries, one per line, in the format specified above.
Output the answers to the queries of type $$$2$$$, one per line, in the order that they appear in the input.
5 5010 4 3 6 252 1 5 2551 3 132 1 4 4561 5 72 3 5 150
100 192 133
6 3018 55 19 30 87 1062 2 4 5401 4 412 1 6 3501 1 492 1 5 6662 3 6 210
480 260 522 170
3 10040 50 6042 1 3 40001 1 301 3 452 1 3 4000
3960 2970
In the first query of the first test case, no more than $$$100$$$ players can survive the $$$5$$$-th round due to the limited number of safe rooms.
In the third query of the first test case, no more than $$$200$$$ players can survive the $$$2$$$-nd round. Then, in the $$$3$$$-rd round, these $$$200$$$ players can form up to $$$15$$$ teams of size $$$13$$$, leaving $$$5$$$ players behind. In the $$$4$$$-th round, the remaining $$$195$$$ players can form up to $$$32$$$ teams of size $$$6$$$, resulting in $$$192$$$ winners.
The NYPD is making a plan for patrolling a neighborhood of Manhattan.
The neighborhood can be represented by a $$$n \times m$$$ grid of square blocks with coordinates from $$$(1, 1)$$$ to $$$(n, m)$$$. Each block is patrolled by one particular officer. For training purposes, every once in a while the NYPD wants to change assignments of officers to blocks. However, to maintain the existing cooperations, they want to preserve the Manhattan distance between each pair of officers.
More formally, let $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$ be the initial coordinates of two officers, and $$$(x_1', y_1')$$$ and $$$(x_2', y_2')$$$ be their final coordinates after reassignment. Then, the following must hold: $$$|x_1-x_2|+|y_1-y_2| = |x_1'-x_2'| + |y_1'-y_2'|$$$.
How many possible assignments of officers to blocks are there which preserve the pairwise Manhattan distances?
Two assignments are considered different if some officer is moved to a different block. The officers are allowed to stay in original positions. Since the answer might be large, output its remainder modulo $$$998244353$$$.
The problem consists of $$$T$$$ independent test cases.
The first line contains a single integer $$$T$$$ ($$$1 \leq T \leq 10^4$$$) — the number of independent test cases to process.
Each of the next $$$T$$$ lines contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 5000$$$) — the dimensions of the neighborhood grid.
For each test case, output a single line — the number of assignments of officers to blocks which preserve the pairwise Manhattan distances modulo $$$998244353$$$.
21 12 3
1 4
In the first test case, there is only one assignment for a $$$1 \times 1$$$ grid.
In the second test case, there are 4 valid assignments for a $$$2 \times 3$$$ grid. Two of them are shown below. On the right, an invalid assignment is shown: the distance between officers $$$2$$$ and $$$5$$$ changes from $$$1$$$ to $$$3$$$.
The students at Rubgers University are organizing a programming contest. Since a lot of strong teams will participate, they expect some of them to solve all problems. To distinguish between them, a special prize will be awarded to the team with a special solve order.
The contest consists of $$$N \leq 26$$$ problems labelled $$$\mathrm{A}$$$, $$$\mathrm{B}$$$, etc: the first $$$N$$$ letters of the English alphabet.
A solve order for a team is a sequence of letters denoting the order in which it solved all the problems: e.g., for $$$N=3$$$, a possible solve order is $$$\mathrm{BAC}$$$ — $$$\mathrm{B}$$$ solved first, then $$$\mathrm{A}$$$, then $$$\mathrm{C}$$$. We only consider teams which solve every problem exactly once, so, e.g., $$$\mathrm{AC}$$$ or $$$\mathrm{ABAC}$$$ are not valid solve orders.
Solve order $$$a$$$ is lexicographically smaller than solve order $$$b$$$ if, at the first position where they differ, the character in $$$a$$$ comes in the alphabet before the character in $$$b$$$. E.g., $$$\mathrm{ACB}$$$ is lexicographically smaller than $$$\mathrm{BAC}$$$, which is lexicographically smaller than $$$\mathrm{BCA}$$$.
Consider all possible solve orders of the $$$N$$$ problems. Let their number be $$$M$$$. Sort the $$$M$$$ solve orders from lexicographically smallest to largest. In this list, the median solve order is located at position $$$\lceil \frac{M}{2} \rceil$$$ ($$$\frac{M}{2}$$$ rounded up).
Any team with the median solve order will get a special prize. Help Rubgers students decide what the order is!
The problem consists of $$$T$$$ independent test cases.
The first line contains a single integer $$$T$$$ ($$$1 \leq T \leq 26$$$) — the number of independent test cases to process.
Each of the next $$$T$$$ lines contains a single integer $$$N$$$ ($$$1 \leq N \leq 26$$$) — the number of problems in the contest.
For each test case, output a single line containing the median solve order for the contest with $$$N$$$ problems.
3123
A AB BAC
In the first test case, $$$N=1$$$, so the only solve order is $$$\mathrm{A}$$$.
In the second test case, the solve orders in lexicographical order are $$$\mathrm{AB}, \mathrm{BA}$$$. The median is $$$\mathrm{AB}$$$.
In the third test case, the solve orders in lexicographical order are $$$\mathrm{ABC}, \mathrm{ACB}, \mathrm{BAC}, \mathrm{BCA}, \mathrm{CAB}, \mathrm{CBA}$$$. The median is $$$\mathrm{BAC}$$$.
You are given an undirected graph. You must color each vertex of the graph in such a way that the following two conditions are met:
- There is no monochromatic cycle$$$^*$$$ in the graph, i.e., there is no cycle whose vertices are all of the same color.
- For each pair of distinct colors $$$c_1$$$, $$$c_2$$$ that appear in the graph, there exists a bichromatic cycle with colors $$$c_1$$$ and $$$c_2$$$, i.e., there is a cycle that contains at least one vertex of color $$$c_1$$$, at least one vertex of color $$$c_2$$$, and no vertices of any other color.
Report whether or not it is possible to do so, and, if it is, provide a valid coloring.
$$$^*$$$ A cycle in a graph is a list of distinct vertices $$$(v_1, \ldots, v_c)$$$, where $$$c \geq 3$$$, such that for all $$$1 \leq i \lt c$$$ there is an edge between vertices $$$v_i$$$ and $$$v_{i+1}$$$, and there is also an edge between $$$v_c$$$ and $$$v_1$$$.
The first line contains an integer $$$T$$$ ($$$1 \leq T \leq 2000$$$), the number of independent test cases to process.
Each case begins with a line containing two integers $$$n$$$ and $$$m$$$ ($$$2 \leq n \leq 10^6$$$, $$$1 \leq m \leq 3 \cdot 10^6$$$), the number of vertices and the number of edges in the graph, respectively.
This is followed by $$$m$$$ lines, the $$$i$$$-th of which contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$u_i \neq v_i$$$) — the vertices that the $$$i$$$-th edge connects. There is at most one edge between every pair of vertices.
The sum of $$$(n+m)$$$ for all cases is at most $$$4 \cdot 10^6$$$.
For each case, if there is no valid coloring, print a single line with the word "NO". Otherwise, print a line with the word "YES" followed by an integer $$$C$$$ ($$$1 \leq C \leq n$$$), the number of colors you will use.
Then, print a new line with $$$n$$$ integers between $$$1$$$ and $$$C$$$, the $$$i$$$-th of which is the color assigned to vertex $$$i$$$. For all $$$1 \leq i \leq C$$$, there should be no cycle with vertices of color $$$i$$$, and for all $$$1 \leq i \lt j \leq C$$$, there should be a cycle with vertices of colors $$$i$$$ and $$$j$$$. If there are multiple possible colorings, you can print any of them.
We strongly recommend using fast I/O for this problem.
2 5 8 1 2 1 3 1 4 2 3 5 1 4 3 4 5 5 2 4 2 1 2 3 4
YES 3 1 2 2 3 3 YES 1 1 1 1 1
The figure below shows one possible coloring for the first example. There are no cycles with vertices of the same color, and, for each pair of colors, there exists a cycle with just those two colors: for colors $$$1$$$ and $$$2$$$, the cycle is $$$(1, 2, 3)$$$; for colors $$$1$$$ and $$$3$$$, it is $$$(1, 4, 5)$$$; and for colors $$$2$$$ and $$$3$$$, it is $$$(2, 3, 4, 5)$$$.
This is an interactive problem.
The Entomology department at Columbia wants to expand its colony of ants.
The colony currently consists of $$$n$$$ male and $$$n$$$ female ants, each numbered $$$1$$$ through $$$n$$$. The scientists want to find a female ant to mate with each male ant. Since ants are polyandrous, one female can mate with multiple males at once.
Two ants can mate only if they are attracted to each other. One male ant may be attracted to multiple female ants, and vice versa.
To find which pairs of ants are attracted to each other, the scientists can run experiments with the aid of an AI (Ant Inspection) tool by Ant-ropic. In one experiment, they take $$$x$$$ male ants and $$$y$$$ female ants, and place them in a cell. The AI observes their behaviour and reports one pair of ants which are attracted to each other, or that none exist. The cost of this experiment is $$$x + y$$$ dollars.
More formally, you can make the following queries to the interactor:
- "? $$$x \; i_1 \; i_2 \ldots i_x \; y \; j_1 \; j_2 \; \ldots j_y$$$" — run the experiment on male ants $$$i_1, i_2, \ldots, i_x$$$ and female ants $$$j_1, j_2, \ldots, j_y$$$. The interactor replies with some pair of attracted ants "$$$i_k \; j_\ell$$$", meaning that $$$i_k$$$-th male ant can mate with $$$j_\ell$$$-th female ant, or "$$$-1 \; -1$$$" if no such pair exists. The same pair may be reported in multiple experiments. The cost of this query is $$$x + y$$$ dollars.
After running some experiments, the scientists need to report, for each male ant, which female ant it can mate with, or $$$-1$$$ if no such ant exists. Since the scientists are on a budget, the total cost of all experiments may not exceed $$$35 \, 000$$$ dollars.
The only line of input contains an integer $$$n$$$ ($$$1 \leq n \leq 400$$$) — the size of the male and the female ant colonies.
After you read this line of input, the interaction begins with your first query.
To make a query, output a line (without quotes) in the following format:
- "? $$$x \; i_1 \; i_2 \ldots i_x \; y \; j_1 \; j_2 \; \ldots j_y$$$" ($$$1 \leq x, y \leq n$$$, $$$1 \leq i_1, i_2, \ldots i_x \leq n$$$, $$$1 \leq j_1, j_2, \ldots j_y \leq n$$$).
After each query, read two space-separated integers — the answer to the query. If an attracted pair exists, the answer will be "$$$i_k \; j_\ell$$$" for some $$$k$$$ and $$$\ell$$$ ($$$1 \leq k \leq x$$$, $$$1 \leq \ell \leq y$$$), indicating the attracted pair. Otherwise, the answer will be "$$$-1 \; -1$$$".
The cost of this query is $$$x + y$$$.
The total cost of all queries must not exceed $$$35 \, 000$$$.
An answer to the problem is a sequence $$$p_1, p_2, \ldots, p_n$$$, where $$$p_i$$$ is the index of a female ant with which the $$$i$$$-th male ant can mate, or $$$-1$$$ if no such ant exists.
Once you have determined an answer to the problem, print the line (without quotes) in the following format:
- "! $$$p_1 \; p_2 \ldots p_n$$$" ($$$p_i = -1$$$ or $$$1 \leq p_i \leq n$$$)
If there are multiple correct answers, output any.
After this, terminate the program.
The interactor in this task is not adaptive. In other words, the pairs of attracted ants do not change throughout the interaction.
If you make queries of total cost more than $$$35 \, 000$$$, your program must terminate immediately, and you will receive the Wrong Answer verdict. Otherwise, you can get an arbitrary verdict because your solution will continue to read from a closed stream.
After printing each line, do not forget to output the end of line and flush the output buffer. Otherwise, you will receive the Idleness Limit Exceeded verdict. To flush, use:
- fflush(stdout) or cout.flush() in C++;
- System.out.flush() in Java;
- stdout.flush() in Python;
- see the documentation for other languages.
2 1 2 -1 -1
? 1 1 2 1 2 ? 1 2 2 1 2 ! 2 -1
In the sample test case, male ant $$$1$$$ is attracted to both female ants, and male ant $$$2$$$ is attracted to none. In the first query, the AI reveals one of the two attractions. In the second query, no attractions are found. The total cost of these queries is $$$6$$$.
It is a sunny day on Columbia campus, and Alice and Bob decide to go to Butler Lawns to play their favorite game: Permutation Game. Since the weather is so nice, Alice wants to stay on the lawns as long as possible, while Bob has a midterm the next day and wants to get home to study.
Permutation Game is played as follows:
- Alice receives a permutation $$$a$$$ and Bob receives a permutation $$$b$$$, both of size $$$n$$$$$$^{\text{∗}}$$$.
- Alice chooses an index $$$i$$$ ($$$1 \leq i \leq n$$$) and places a token on position $$$i$$$ of her permutation $$$a$$$.
- Bob, after seeing where Alice has placed her token, chooses an index $$$j$$$ ($$$1 \leq j \leq n$$$) and places his own token on position $$$j$$$ of his permutation $$$b$$$.
- Alice and Bob each follow their permutation one step at a time:
- Alice moves her token to index $$$a_i$$$, then $$$a_{a_i}$$$, and so on.
- Bob moves his token to index $$$b_j$$$, then $$$b_{b_j}$$$, and so on.
$$$^{\text{∗}}$$$A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, [$$$2$$$, $$$3$$$, $$$1$$$, $$$5$$$, $$$4$$$] is a permutation, but [$$$1$$$, $$$2$$$, $$$2$$$] is not a permutation ($$$2$$$ appears twice in the array), and [$$$1$$$, $$$3$$$, $$$4$$$] is also not a permutation ($$$n = 3$$$ but there is a $$$4$$$ in the array).
The first line of input contains a single integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$).
The second line of input contains $$$n$$$ distinct integers $$$a_1, a_2, ..., a_n$$$ — Alice's permutation $$$a$$$.
The third line of input contains $$$n$$$ distinct integers $$$b_1, b_2, ...,b_n$$$ — Bob's permutation $$$b$$$.
Output a single integer — the number of steps that will be performed in the game, assuming both players play optimally.
31 2 31 2 3
1
52 1 4 5 33 4 5 2 1
3
102 8 1 5 4 7 6 10 9 37 3 9 10 2 1 6 8 4 5
5
In the first sample, regardless of which indices Alice and Bob place their tokens on to start, the process will last for just one step.
In the second example, Alice may place her token at index $$$3$$$, and Bob, seeing where Alice has placed her token, places his at index $$$1$$$. After one step, Alice's token will be at index $$$4$$$ and Bob's will be at index $$$3$$$. After two steps, Alice's token will be at index $$$5$$$ and Bob's will be at $$$5$$$. And after three steps, Alice's token returns to index $$$3$$$, while Bob's returns to index $$$1$$$.
For an array of integers $$$a$$$, a triplet of elements is defined by 3 distinct indices $$$(a_i, a_j, a_k)$$$, and their order does not matter.
Consider the triplets from $$$a$$$ that sum to zero.
For example, the array $$$a = [1, 1, 1, 2, -2, 0]$$$ has $$$4$$$ triplets that sum to zero: $$$(a_1, a_2, a_5)$$$, $$$(a_1, a_3, a_5)$$$, $$$(a_2, a_3, a_5)$$$, and $$$(a_4, a_5, a_6)$$$.
Given an integer $$$k$$$, construct an array of integers $$$a$$$ such that exactly $$$k$$$ triplets of elements from $$$a$$$ sum to zero.
Your array must have size at most $$$5000$$$.
The single line of the input contains an integer $$$k$$$ ($$$0 \leq k \leq 10^9$$$) — the required number of triplets that sum to zero.
Output two lines.
On the first line, output a single integer $$$n$$$ ($$$0 \leq n \leq 5000$$$) — the size of $$$a$$$.
On the second line, output $$$n$$$ space-separated integers $$$a_1, \ldots, a_n$$$ ($$$-10^9 \leq a_i \leq 10^9$$$).
If there are multiple arrays satisfying these conditions, output any of them.
It can be shown that a valid answer always exists.
0
4 1 2 3 4
1
5 -1 1 -2 2 -3
4
6 1 1 1 2 -2 0
In sample 1, no triples in the array $$$a$$$ sum to zero.
In sample 2, the only triple that sums to zero is $$$(a_2, a_4, a_5)$$$.
You are given $$$n$$$ points on a plane. Find the largest area triangle or quadrilateral with vertices at some of these points.
The first line contains one integer $$$n$$$ ($$$3 \leq n \leq 4000$$$) — the number of points.
Each of the next $$$n$$$ lines contains two integers $$$x_i, y_i$$$ ($$$-10^9 \leq x_i, y_i \leq 10^9$$$) — the $$$i$$$-th point. No two points coincide.
It is guaranteed that no three points are collinear.
On the first line, output one integer $$$m$$$ ($$$m \in \{3, 4\}$$$) — the number of points in an optimal polygon.
On the second line, output a space-separated list of indices $$$i_1, \ldots, i_m$$$ — the indices of the vertices in an optimal polygon. No index must repeat, and no two edges of the polygon may intersect internally. Output the vertices in either clockwise or counterclockwise order.
If there are multiple triangles or quadrilaterals with the same maximum area, output any.
40 01 1-1 10 -1
3 2 3 4
51 01 1-1 1-1 -10 -1
4 4 1 2 3
The only optimal shape in the first test case is the triangle of area $$$2$$$ with vertices at points $$$2, 3, 4$$$.
In the second test case, there are two optimal quadrilaterals indicated below. Any one of them is considered correct.
One week before the contest, CULC organizers learned that a certain highly rated coder will participate. In shock, they quickly opened TaskGPT, and, with trembling fingers, typed:
| ikaurov | can u make task for benq asap? make no mistakes |
| TaskGPT | Fantastic question! The following task would be a great fit. |
| You are given a list $$$a$$$ of $$$n$$$ non-negative integers, where $$$n \leq 1000$$$. You can perform the following operation on this list zero or more times. Choose two distinct positions $$$1 \le x,y \le n$$$ and assign: $$$$$$a_x := a_x \oplus a_y$$$$$$ Above, $$$\oplus$$$ is the bitwise XOR of the two numbers. You need to perform these operations so that the resulting list is sorted in non-decreasing order — i.e., $$$a_i \le a_{i+1}$$$ for each position $$$i$$$ from $$$1$$$ to $$$n-1$$$. The final set of numbers does not have to match the initial one. You must sort the list using at most $$$2500$$$ operations. Would you like to know the solution? |
The first line contains the number $$$n$$$ ($$$1 \leq n \leq 1000$$$), the size of the list.
The second line contains $$$n$$$ integers $$$a_1, \ldots, a_n$$$ ($$$0 \leq a_i \leq 2^{20}-1$$$), the list to be sorted.
On the first line, print the number of operations $$$m$$$ ($$$0 \leq m \leq 2500$$$).
On the following $$$m$$$ lines, print $$$x$$$ and $$$y$$$ ($$$1 \leq x, y \leq n$$$, $$$x \neq y$$$) — the positions selected on each operation.
The list must be sorted in non-decreasing order after the $$$m$$$ operations.
It can be shown that it is always possible to sort the list using at most $$$2500$$$ operations.
5 0 1 1 1 2
0
5 4 3 2 1 0
5 5 1 1 5 2 3 2 4 4 3
In the first test case, the list is already sorted, so nothing needs to be done.
In the second test case, the list evolves as follows: $$$[4, 3, 2, 1, 0] \to [4, 3, 2, 1, 4] \to [0, 3, 2, 1, 4] \to [0, 1, 2, 1, 4] \to [0, 0, 2, 1, 4] \to [0, 0, 2, 3, 4]$$$.