Jaehyun has a bead which consists of $$$N$$$ jewels arranged from left to right. Each jewel is in one of the three colors: Red, Blue, and Violet, which is represented as a single character R, B, V. As one of the committees in an important contest, Jaehyun wants to use it as a souvenir for some participant.
Jaehyun likes a bead with diverse colors, so he defines a bead beautiful if every adjacent jewel has different colors. For example, RBVBV is a beautiful bead because every adjacent jewel has a different color. V is a beautiful bead because it does not have adjacent pairs. However, RBBV is not a beautiful bead, because two Bs in the middle are adjacent in the string.
Not only Jaehyun likes a bead with diverse colors, but he likes a contest with diversity. This time, Jaehyun wants to make a bead that is also colorful to colorblind people. For convenience, we will only consider three kinds of people in this problem.
- Non-colorblind people, who can tell all three colors.
- Red-colorblind people (Protanopia), who can't tell apart red and violet: They consider violet jewels as red jewels.
- Blue-colorblind people (Tritanopia), who can't tell apart blue and violet: They consider violet jewels as blue jewels.
Jaehyun wants to pick some contiguous part of the bead and cut it out to give as a souvenir. The part Jaehyun cuts should be colorful to all three kinds of people. Note that, if the whole bead is beautiful, then Jaehyun does not necessarily cut it out, but just give the whole bead. What is the length of the longest bead he can give?
The first line contains an integer $$$N$$$, denoting the length of the bead. ($$$1 \le N \le 250\,000$$$)
The next line contains string of length $$$N$$$, where every character is either R, B, or V.
Print the maximum possible length of contiguous beads, which is colorful for all three kinds of people.
4 RBBB
2
5 RBRBB
4
Ho is an expert in martial arts called Taebo. She runs a Taebo school, and there are $$$N$$$ students in her school. Since Ho is too old to teach Taebo, she is going to hand over her school to one of her students. To find a suitable candidate, Ho made all $$$\frac{N(N-1)}{2}$$$ pairs of students do a Taebo matchup with each other, and wrote all the results. In a Taebo matchup, exactly one person wins the match, and another person loses the match. Ho thinks that a student is good enough to receive her school if the student is a Gosu of Taebo.
Gosu is a Korean word which means a person who is very good at games, sports, competitive programming, etc. In Taebo, Gosu has a different meaning.
Let's define a winning path from player $$$x$$$ to player $$$y$$$ as a sequence of $$$K+1$$$ integers $$$a_0 = x,\ a_1,\ \cdots ,\ a_K = y$$$, where student $$$a_i$$$ has won student $$$a_{i+1}$$$ for all $$$0 \le i \lt K$$$. We call $$$K$$$ as the length of this winning path. For example, if there exists a winning path of length 1, we can immediately know that $$$x$$$ has won student $$$y$$$. If there exists a winning path of length 2, then $$$x$$$ may not win $$$y$$$ directly, but there exists some other player $$$z$$$ that $$$x$$$ has won, and has won $$$y$$$.
The distance $$$d(x,\ y)$$$ is defined as a minimum length of winning path from $$$x$$$ to $$$y$$$, if such exists. There could be a case that $$$x$$$ can not find a winning path to $$$y$$$. In that case, we define $$$d(x,\ y) = 9000$$$. Note that, the path can have zero length, thus $$$d(i,\ i)$$$ is always $$$0$$$.
Ho wants her student to be strong to all kind of opponents, so she defines the weakness of student $$$i$$$, as a maximum value among $$$d(i,\ 1),\ d(i,\ 2),\ \cdots,\ d(i,\ N)$$$. A student $$$i$$$ is a Gosu in Taebo when the weakness of student $$$i$$$ is minimum among all weakness values. By this definition, there can be multiple Gosu-s.
Since Ho is too old to tell who is Gosu, your task is to find a Gosu and weakness value of Gosu to help Ho. If there exist multiple Gosu-s, you can print any of them.
In the first line, the number of students $$$N$$$ is given.
In the $$$i$$$-th line of next $$$N$$$ lines, a string $$$s_i$$$ consists of W, L, and -. Let's denote $$$j$$$-th character of $$$s_i$$$ as $$$s_{i,j}$$$. $$$s_{i,j}$$$ is given as follows:
- $$$s_{i,j}=$$$ -, if $$$i=j$$$.
- $$$s_{i,j}=$$$ W, if student $$$i$$$ won student $$$j$$$.
- $$$s_{i,j}=$$$ L, if student $$$j$$$ won student $$$i$$$.
- $$$2 \le N \le 3\,000$$$
- $$$s_{i, i} =$$$ - ($$$1 \le i \le N$$$)
- If $$$i \neq j$$$, then $$$s_{i, j}=$$$ W or $$$s_{i, j}=$$$ L. ($$$1 \le i \le N$$$)
- If $$$s_{i, j} = $$$ W, then $$$s_{j, i} = $$$ L. ($$$1 \le i,\ j \le N$$$)
- If $$$s_{i, j} = $$$ L, then $$$s_{j, i} = $$$ W. ($$$1 \le i,\ j \le N$$$)
Print two space-separated integers, $$$d$$$ and $$$u$$$, where student $$$u$$$ is Gosu, and $$$d$$$ is weakness of student $$$u$$$.
If there are multiple answers, you can print any of them.
2 -W L-
1 1
3 -LW W-L LW-
2 1
5 -WLLW L-LLW WW-LL WWW-W LLWL-
1 4
Figure: Voronoi Diagram of size 4.
In the 2-dimensional Cartesian coordinate system, we define the Voronoi Diagram of a non-empty set of points $$$S$$$, as a diagram that divides the plane by the criteria "which point in the set $$$S$$$ is closest in this location?". More precisely, the Voronoi diagram of a given non-empty point set $$$\{P_1, P_2, \cdots, P_n\}$$$ is a collection of regions: A point $$$K$$$ is included in region $$$i$$$ if and only if $$$d(P_i, K) \le d(P_j, K)$$$ holds for all $$$1 \le j \le n$$$.
While the usual Voronoi Diagram uses Euclidean distance, we use Manhattan distance in this problem. $$$d(X, Y)$$$ denotes the Manhattan distance between point $$$X$$$ and $$$Y$$$. Manhattan distance between two points is the sum of the absolute differences of their $$$X$$$, $$$Y$$$ coordinates. Thus, the Manhattan distance between two points $$$(X_1, Y_1)$$$, $$$(X_2, Y_2)$$$ can be written as $$$|X_2 - X_1| + |Y_2 - Y_1|$$$.
For example, in the picture above, every location over the plane is colored by the closest point with such location. The points which belongs to a single region is colored by a light color indicating a region, and the points which belongs to more than one region forms lines and points colored black.
The region is unbounded if for any real number $$$R$$$, there exists point $$$P$$$ in the region such that $$$d(O, P) \gt R$$$ where $$$O$$$ is the origin. You have to find the number of unbounded regions in the Voronoi Diagram.
In the first line, the number of points consisting Voronoi diagram $$$N$$$ is given.
In the $$$i$$$-th line of next $$$N$$$ lines, two integers $$$x_i,\ y_i$$$ indicating $$$x$$$ and $$$y$$$ coordinate of $$$P_i$$$ are given. These are the points in the Voronoi diagram.
- $$$1 \le N \le 250\,000$$$
- $$$-10^9 \le x_i,\ y_i \le 10^9$$$ ($$$1 \le i \le N$$$)
- All $$$N$$$ points are distinct.
Print a single integer, denoting the number of unbounded regions in the Voronoi Diagram.
4 0 0 -4 0 3 4 4 -2
4
5 1 1 2 2 3 3 4 4 5 5
5
9 -4 -4 -4 0 -4 4 0 -4 0 0 0 4 4 -4 4 0 4 4
8
In example 2, overlapping region is indicated as subtractive mixing of two or more colors. All points with $$$(x \ge 5 \wedge y \le 1) \vee (x \le 1 \wedge y \ge 5)$$$ is included in all five region, and colored as darkest.
A + B is a problem used to test one's basic knowledge for competitive programming. Here is yet another boring variation of it.
You have two integers, A and B. You want to make them equal. To do so, you can perform several steps, where each step is one of the following:
- A+=A
- A+=B
- B+=A
- B+=B
Unfortunately, A + B is a hard problem for us, so you are allowed to make at most 5000 steps.
Two integers A, B are given. (1 ≤ A, B ≤ 1018).
In the first line, print a single integer n (0 ≤ n ≤ 5000) denoting the number of steps.
In next n lines, print one of the following strings to denote your desired operation: "A+=A", "A+=B", "B+=A", or "B+=B".
Any sequence of steps that yields the desired result will be judged correct.
2 3
4
B+=B
B+=A
A+=A
A+=A
Donghyun lives in 2D plane, having $$$x$$$-axis as ground. It rains a lot in 2D plane, and the rain falls from $$$y = \inf$$$.
Recently, Donghyun read a book called "Water Knows the Answer", and got impressed by the book. He now believes that he will be super intelligent and smart if he has water with him.
Figure: The book "Water Knows the Answer".
Donghyun has $$$N$$$ rectangular boxes with (possibly) different heights and widths. He is going to rearrange those boxes in order to collect the rainfall. Then, the water will give him the answer. To achieve this, he have to place the box in a row. The ground absorbs the rainfall, so no empty space is allowed between the boxes. He may rotate some of the boxes or not, but he should make its edges parallel to the ground.
The water can flow to left or right, until it has space to flow. Formally, water in certain point can stay in its place if that point is not inside the box and has a box both somewhere to its left and somewhere to its right at the same height.
Donghyun wants to know the maximum area of water he can store. (In 2D plane, area means volume.) But, he doesn't have water yet, so he doesn't know the answer. Do you know the answer?
The first line contains an integer $$$N$$$, the number of boxes. ($$$3 \le N \le 250000$$$) For the next $$$N$$$ lines, $$$i$$$-th line contains two integer $$$w_i$$$ and $$$h_i$$$, the width and height of $$$i$$$-th box. ($$$1 \le w_i, h_i \le 10^6$$$)
Print a single integer, denoting the maximum area of water you can store if you arrange the boxes optimally.
3 4 3 2 6 5 1
15
Figure: Best arrangement for example input.
Ho has arrived in a secret place for her secret business trip. She knows her trip will take at most N days or shorter but doesn't know the exact number of days she'll be there. So, the perfectionist Ho wants to make the daily meal lists for every possible trip length, 1 day to N days.
There is the only food court that offers exactly 2N kinds of menus (by accident) in this secret place. The food court opens only lunch time and dinner time, and oddly, the prices of lunch and dinner for the same menu can be different.
She will eat exactly one menu per lunch and dinner respectively and never eat the same menu for the entire of the trip. She never minds about which kind of menu will be her meal, the only important thing is the entire price of meals must be minimized.
Under these conditions, she can make her meal lists but realizes that writing every N(N + 1) menu is hard and tiresome. So, instead of making the meal lists, she calculates the minimized entire price for i lunch menus and i dinner menus where i = 1 to N.
You, the big fan of Ho, has a supreme task. Print the N prices she calculated.
The first line contains an integer N. (1 ≤ N ≤ 250000)
In the next 2N lines, each line contains two integer l, d denoting the prices of the menus when lunch and dinner respectively. (1 ≤ l, d ≤ 109)
Print N lines. The i-th line should contain an integer denoting the minimized entire price for i lunch menus and i dinner menus.
1
4 9
5 3
7
2
1 6
2 4
5 3
3 1
2
7
4
7 5
5 7
7 4
4 2
2 5
6 4
3 2
1 9
3
7
16
26
You are given a permutation of size $$$N$$$. For each $$$i$$$, print the number of indices $$$j \neq i$$$, which when removed, decreases the maximum possible length of an increasing subsequence that contains index $$$i$$$.
The first line contains an integer $$$N$$$. ($$$1 \le N \le 250000$$$).
The next line contains $$$N$$$ integers $$$A_1, A_2, \cdots, A_N$$$ denoting the permutation. ($$$1 \le A_i \le N$$$, all $$$A_i$$$s are distinct).
Print $$$N$$$ integers, separated by spaces, denoting the answers for $$$i = 1, 2, 3, \cdots, N$$$.
1 1
0
6 1 2 3 4 5 6
5 5 5 5 5 5
6 6 5 4 3 2 1
0 0 0 0 0 0
4 2 1 4 3
0 0 0 0
9 1 2 3 6 5 4 7 8 9
5 5 5 6 6 6 5 5 5
There are $$$N$$$ teachers and $$$N$$$ students in the Seoul Science High School. Each student bought $$$N$$$ flowers because tomorrow is a teacher's day in Korea. However, one of the students quit, and now only $$$N-1$$$ students remain in the school.
Teachers are very jealous, so they will give an F grade to students when they receive fewer flowers from that student than others. Therefore, every teacher should receive exactly $$$N-1$$$ flowers. A student can only give flowers to teachers who have taught him or her, and you know which students have learned from which teachers.
Younghun is the student of Seoul Science High School, and he needs your help in organizing this event.
The first line contains two integers $$$N$$$ and $$$M$$$ ($$$2 \le N \le 100 000$$$, $$$1 \le M \le 200 000$$$) describing the number of teachers and the number of (student, teacher) pairs where the student learned from the teacher.
In the next $$$M$$$ lines describe the relations: $$$j$$$-th line contains two integers $$$s_j$$$, $$$t_j$$$ ($$$1 \le s_j \le N-1$$$, $$$1 \le t_j \le N$$$) indicating that $$$s_j$$$-th student can give flowers to the $$$t_j$$$-th teacher. It is guaranteed that all pairs are different.
If it is impossible to give all teachers the same number of flowers ($$$N-1$$$ flowers), print a single number $$$-1$$$ in the first line.
Otherwise, your program should output $$$M$$$ lines. In $$$j$$$-th line, there should be a single integer denoting the number of flowers which $$$s_j$$$-th student gave to $$$t_j$$$-th teacher.
If there are multiple possible answers, you can output any of them.
6 12 1 3 1 4 1 5 2 2 2 4 3 1 3 3 4 1 4 2 4 4 5 4 5 6
1 0 5 5 1 2 4 3 0 3 1 5
6 12 1 2 1 3 1 4 2 2 2 4 3 1 3 3 4 1 4 2 4 4 5 5 5 6
-1
To celebrate your team's victory at ICPC World Finals, Edsger W. Dijkstra (The inventor and namesake of Dijkstra's algorithm) will throw a fabulous party at your house in New York City. The party starts in 5 hours, so he should better start moving.
New York City is modeled as a 2-dimensional plane. Dijkstra is now in coordinate $$$(s_x, s_y)$$$, and your house is located in coordinate $$$(e_x, e_y)$$$. Dijkstra should come to your house by only moving in a direction parallel to the coordinate axes (you remember the Manhattan distance, right?). Also, there are $$$N$$$ skyscraper in an axis-parallel rectangular shape, which you can pass through its boundary, but cannot pass through anywhere strictly inside of it.
You got a phone call from Dijkstra, saying that it's too hard for him to compute the shortest path between his location and your house. Somehow, he is losing his edge. However, that's not bad news, because it's a chance for you to be cool in front of the great Dijkstra. Can you?
It is guaranteed that all $$$x$$$ coordinates are distinct and all $$$y$$$ coordinates are distinct. It is also guaranteed that no pair of rectangles overlap. It is also guaranteed that your house and Dijkstra's starting location are not inside of any rectangles.
The first line contains five integers $$$N, s_x, s_y, e_x, e_y$$$. ($$$1 \le N \le 250 000, 0 \le s_x, s_y, e_x, e_y \le 10^8$$$)
The next $$$N$$$ lines contain four integers $$$a_i, b_i, c_i, d_i$$$. This indicates that $$$i$$$-th skyscraper is a rectangle with its four corners located in $$$(a_i, b_i), (a_i, d_i), (c_i, b_i), (c_i, d_i)$$$. ($$$0 \le a_i \lt c_i \le 10^8$$$, $$$0 \le b_i \lt d_i \le 10^8$$$).
It is guaranteed that:
- Let $$$X = \{s_x, e_x, a_1, a_2, \cdots, a_N, c_1, c_2, \cdots, c_N\}, Y = \{s_y, e_y, b_1, b_2, \cdots, b_N, d_1, d_2, \cdots, d_N\}$$$. All elements in $$$X$$$ are distinct, and all elements in $$$Y$$$ are distinct.
- No pair of rectangles share a common point.
- Dijkstra's location and your house's location are not in any of the rectangles.
Print the length of the shortest path between Dijkstra's location and your house, using the Manhattan metric.
3 2 14 5 1 4 6 6 10 0 7 3 9 1 2 8 5
20
1 0 500 100 503 1 0 99 1000
1097
2 2 8 10 3 3 6 6 10 7 1 8 7
15