Tony loves tacos! Tony also loves cats! Tacocat?
Anyways, Tony received a string for his birthday from his favorite taco joint, Torchy's. Since Tony clearly has an affinity for palindromes, he wants to find out whether or not it is possible for him to turn his string into a palindrome by changing at most one of its letters to another letter of his choosing. A string is a palindrome if it reads the same forwards and backwards. Put more formally, if his letters were labelled $$$s_1, s_2, \dots, s_n$$$, then it is the case that $$$s_i = s_{n - i + 1}$$$ for each $$$i \in \{1, 2, \dots, n\}$$$.
The input will begin with a single line containing a single integer $$$n\ (1 \leq n \leq 10^5)$$$, denoting the length of Tony's string.
The next line will contain a single string $$$s$$$ of length $$$n$$$, Tony's string, consisting of only lowercase English letters.
The output should consist of a single line containing either "YES" or "NO" (case insensitive, with no quotation marks), based on whether or not Tony can turn his string into a palindrome.
7tacocat
YES
9brushfire
NO
In the first example test case, Tony's string is already a palindrome.
In the second example test case, it can be proven that Tony's string cannot possibly be turned into a palindrome by changing at most one of its letters.
The Baja Shrimp Taco is one of Torchys' most popular tacos. As the shrimp taco is so popular, customers have already scheduled their orders for the next $$$n$$$ days!
Initially, the store has 0 pounds of shrimp. Every morning, the store is scheduled to receive a shipment of $$$s_i$$$ pounds of shrimp. Any leftover shrimp will carry over into the next day. Alice, the store manager, is worried that the store will not have enough shrimp to fulfill the customers' orders on any given day. Being the diligent manager she is, Alice may contact the shrimp supplier and ask that the delivery dates of a single pair of shipments be swapped. She may do this operation exactly once, or not at all.
Can Alice ensure that the store always has enough shrimp to fulfill the customers' orders on any given day?
The first line will contain the integer $$$n$$$ $$$(1 \leq n \leq 2 \cdot 10^5)$$$, the number of days.
The second line will contain the array $$$s$$$ of length $$$n$$$. On the $$$i$$$th day, the store will receive $$$s_i$$$ $$$(0 \leq s_i \leq 10^9)$$$ pounds of shrimp before opening for business.
The third line will contain the array $$$c$$$ of length $$$n$$$. On the $$$i$$$th day, customers will demand $$$c_i$$$ $$$(0 \leq c_i \leq 10^9)$$$ pounds of shrimp.
Output a single line: "Yes" if every customer's order can be fulfilled, or "No" if they cannot.
54 3 1 6 104 4 3 5 6
Yes
51 2 3 4 55 4 3 2 1
No
53 2 3 1 74 3 3 3 3
Yes
In the first testcase, Alice should swap the first and fifth shipment. In the second testcase, it can be shown that there will be a day in which the customers' orders cannot be fulfilled. In the third testcase, Alice must swap the first and fifth shipment.
Mike recently bought a new trailer and is very excited to use it. However, it is too big to fit in his garage, so he needs to park it in a trailer park. He has found a park, but needs your help figuring out how much it will cost to park his trailer in the park.
The park can be represented as an $$$n \times m$$$ grid, where the $$$j$$$th entry in the $$$i$$$th row costs $$$c_{i,j}$$$ to park in. Some squares will already be occupied, which will be denoted by $$$c_{i,j}=-1$$$.
Mike's trailer can be thought of as an $$$a \times b$$$ rectangle, and he wants to find the cheapest place in the park to park his trailer. Help Mike find how much money he needs to park his trailer, or let him know that the park his no room for his trailer. He can park his trailer in any open $$$a \times b$$$ rectangle in the grid, and costs the sum of $$$c_{i,j}$$$ that he is parked on. Note that the rectangle must be axis-aligned, but it could be rotated by $$$90$$$ degrees.
The first line contains 4 space-seperated integers. The first line contains 4 space-separated integers $$$n$$$, $$$m$$$, $$$a$$$, and $$$b$$$ ($$$1 \leq n,m \leq 2000$$$, $$$1 \leq a \leq n$$$, $$$1 \leq b \leq m$$$) — the number of rows in the grid, columns of the grid, the length of the trailer, and the width of the tralier.
The following $$$n$$$ lines contain $$$m$$$ integers each, describing the trailer park. The $$$j$$$-th element of the $$$i$$$th line $$$a_{i,j}$$$ is -1 if that square foot is taken, and otherwise represents the cost of that square foot, where $$$1 \leq a_{i,j}\leq 10^9$$$.
If it is possible for Mike to park his trailer in the described park, output the minimum cost needed. If it is impossible, output -1.
3 3 1 21 5 -17 -1 12 3 -1
5
3 3 1 2-1 5 -17 -1 1-1 3 -1
-1
It is early fall. The weather is just turning chilly, and the leaves are beginning to display their vibrant hues. You've just started a new job at Torchy's Tacos. You are looking forward to a long and prosperous career here.
On your very first day, a surprising order comes in from the landlord: Make me a perfect Fresh Avocado taco, or your rent goes up.
The talented Torchy's staff immediately sets upon this task. The first step to preparing the Fresh Avocado taco is to cut the avocados in half. As the new hire, that job has been given to you.
An avocado can be represented as a circle of radius $$$r$$$ centered at the origin $$$(0,0)$$$. You know you have the skills to perform $$$n$$$ different types of cuts, each represented by the equation of a line that splits the avocado into two halves. Constructing the Fresh Avocado taco is a precise art, and so the avocado must be cut in as close to perfect halves as possible. Thus, you must choose a cut to perform which splits the avocado into halves that are closest in area.
If you choose the optimal cut, what proportion of the avocado is in each half of the cut?
The first line of input contains two integers $$$n\ (1\leq n \leq 10^5)$$$ and $$$r\ (1\leq r\leq 10^4)$$$ — the number of different cuts you can do and the radius of the avocado.
The next $$$n$$$ lines contain three integers $$$A_i, B_i, C_i\ (|A_i|, |B_i|, |C_i|\leq 10^4)$$$ describing the equation $$$A_ix + B_iy + C_i = 0$$$ for the $$$i$$$th cut.
It is guaranteed that each cut intersects the avocado at exactly two points, and for each cut, either $$$A_i\not=0$$$ or $$$B_i\not=0$$$.
Output the proportion of the avocado's area of the smaller half and then the bigger half of the optimal cut. Your answer will be considered correct if its absolute or relative error doesn't exceed $$$10^{-6}$$$.
2 20 1 01 0 1
0.5 0.5
1 102 -2 -1
0.4774967821 0.5225032179
In the first test case, the avocado is the green circle, the first cut is the blue dotted line and the second cut is the red dotted line. Choosing the first cut is optimal as it splits the avocado in exact halves.
Michael Rypka is eating at Torchy's as part of a group of $$$n$$$ friends, and they are sat evenly spaced around a circular table labeled from $$$1$$$ to $$$n$$$ going clockwise around the circle. After getting their tacos and sauces, they realized everyone had a lot of the wrong items. So, they all need to exchange items. Specifically, each person needs to exchange items directly with every other person at the table. However, they want to avoid cross contamination, so no two pairs of people can exchange items if the direct line between each pair intersects. In a given round, any two people can agree to exchange items given it meets the conditions above. Please help Michael figure out the minimum number of rounds it will take his friends to exchange all their items, and provide a series of exchanges they can conduct to do so.
The input will contain a single integer $$$n$$$ ($$$2 \leq n \leq 10^3$$$) indicating how many people are sitting around the table.
The first line should indicate a single integer $$$r$$$ denoting the minimum number of rounds that it takes Michael and his friends to exchange all their items. For each round, output a single integer $$$k$$$ denoting the number of exchanges that will occur in that round followed by $$$k$$$ lines each containing two space separated integers $$$i$$$ and $$$j$$$ indicating that friends $$$i$$$ and $$$j$$$ agreed to exchange in this round.
Note: if there is an exchange between friends $$$i$$$ and $$$j$$$, no other exchange in that round should include either $$$i$$$ or $$$j$$$. Additionally, not every friend needs to make an exchange in every round.
2
1 1 1 2
4
4 1 3 1 2 3 2 1 4 1 4 2 2 4 3 1 2
A group of $$$n$$$ chicks is waiting in a chicken coop. In order to pass the time, they decide to shake each other's wings. They shake wings according to the following rules:
- Each chick shakes wings with at most one other chick at each distinct round.
- At the end, for every pair of chicks $$$a$$$ and $$$b$$$, there is a path of wing-shakes that connects $$$a$$$ and $$$b$$$. Note that these wing-shakes do not have to happen in any specific round, but a path that includes wing-shakes over multiple rounds is fine.
They would like to minimize the number of rounds needed. In addition, because their wing aren't fully grown yet, they want to minimize the maximum distance between any two chicks who shake wings (while still minimizing the number of rounds). Output the number of rounds needed, and because they like integers, output the square of the minimum maximum wing-shake distance.
The first line contains a single integer $$$n$$$ ($$$2 \leq n \leq 18$$$) — the number of chicks.
The next $$$n$$$ lines contain two space-separated integers $$$x$$$ and $$$y$$$ ($$$1 \leq x, y \leq 10^3$$$) — denoting that there is a chick at location $$$(x, y)$$$. It is guaranteed that all pairs of points are distinct.
On a single line, output two integers — the minimum number of rounds needed and the minimum maximum wing-shake distance needed.
31 12 23 2
2 2
In the sample, it is optimal for chick 1 and chick 2 to shake hands on the first round and chick 2 and chick 3 to shake hands on the second round.
In Universe 1120, the Torchy's mafia is going after the popular chain Babo Cob's for sniping their business with the UTPC competitions. However, they have too much internal rivalry, thereby making resistance futile. The leader of the chain of Babo Cob's wants to figure out what the best case scenario is - what's the maximum number of people in the Torchy's mafia who die from this rivalry.
The Torchy's mafia has $$$n$$$ members, numbered $$$1, 2, ... n$$$. They all have a single rival who they want to target — member $$$i$$$ wants to shoot down member $$$s_i$$$. Note that it is possible for $$$i = s_i$$$ (the nerves ... ). They shoot in a predetermined order, one after the other. The leader of Babo Cob's has a mole in the Torchy's mafia who can influence the order, and wants to know the maximum number of people who can die, given that they are ordered optimally.
The first line of input contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of members.
The second line contains $$$n$$$ space separated integers $$$s_1, s_2, ... s_n$$$ ($$$1 \le s_i \le n$$$) — the member who the $$$i$$$th member wants to shoot down, respectively.
A single integer that gives the maximum number of casualties across all permutations of members.
82 3 2 2 6 7 8 5
5
In the first sample, we can achieve 5 deaths (and no better) from the order - 2 1 3 4 5 8 7 6. Members 2, 3, 5, 6 and 8 die from this sequence.
Neossie is a new UTPC officer! Today is her first time helping organize a UTPC contest, and it is time to serve Torchy's! She has noticed in the past that some of the most popular tacos appear near the end of the line, while some less popular ones appear closer to the front. She wants to experiment with grouping the tacos in ways that maximize the efficiency of the line.
There are $$$n$$$ types of tacos, numbered $$$1, 2, ..., n$$$, that were ordered by UTPC, and thanks to UTPC's generous sponsor, Jane Street, there are is an infinite quantity of each type of taco, and all tacos of a given type are in a single box. There are also $$$m$$$ students attending the contest. Each student wants two tacos, with types $$$a_i$$$ and $$$b_i$$$. Initially, the boxes of tacos are arranged in a line along a very big table. The arrangement of the boxes can be represented by a permutation of $$$1, 2, ..., n$$$. Neossie can split the table into two by cutting it between any adjacent pair of boxes. She can do this as many times as she wants. We will call a sequence of cuts parallelizable if for any student, both of the tacos that they want are on the same table. Neossie wants to maximize the number of tables while performing a sequence of parallelizable cuts.
It is almost 5:30 and the students are beginning to line up for tacos. Every time a student joins the back of the line, Neossie wonders what the maximum number of tables she can form is, over all initial arrangements of boxes. She also wants to know how many initial arrangements of boxes allow her to form that many tables. Note that it is still not 5:30, so none of the students have left the line by the time any student joins the line. Please help Neossie by finding both of these values every time a student joins the line!
The first line of input will contain two integers $$$n$$$ and $$$m$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq m \leq 2 \cdot 10^5$$$) — the number of types of tacos and the number of students, respectively.
The $$$i$$$th of the next $$$m$$$ lines of input will contain two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \leq a_i, b_i \leq n$$$), denoting the two types of tacos wanted by the $$$i$$$th student to join the line.
For each student in the order that they join the line, output a line with two space-separated integers, denoting the maximum number of tables and the number of permutations of the boxes which allow Neossie to form the maximum number of tables, respectively. Since the second number may be huge, output it modulo $$$998244353$$$.
3 31 21 31 2
2 4 1 6 1 6
4 53 41 23 22 33 4
3 12 2 8 1 24 1 24 1 24