After a long day of work, $$$q$$$ corporate workers across the world are angry and want to get home as soon as possible. Luckily, all they have to do is to walk in a straight line. For each corporate worker $$$i$$$, let $$$N_i$$$ be the position of their workplace and $$$1$$$, the position of their home.
Corporate employees can move in three ways:
However, it is not a joke. They really want to get home quickly. Therefore, to calm them down, each corporate worker must be told the minimum number of movements that they have to make in order to get home. Moreover, they must be told in how many different ways they can minimize the number of movements. That way, they are sure to calm down!
Formally, you are given $$$q$$$ queries - each of them representing a worker. For each worker, you start at a position $$$N_{i}$$$. Given the starting position, what are the minimum number of moves that the worker will need to get to position 1? Moreover, in how many ways can he get home in the minimum amount of moves?
The first line consists of an integer $$$q$$$ ($$$1 \leq q \leq 10^{3}$$$), representing the number of corporate workers that you have to help.
The next $$$q$$$ lines will contain one integer $$$N_{i}$$$ ($$$1 \leq i \leq q$$$ and $$$1 \leq N_{i} \leq 10^{18}$$$), representing the position of worker $$$i$$$'s home.
You must print $$$q$$$ lines. On every line $$$i$$$, output two integers: the minimum number of moves that the corporate worker $$$i$$$ has to make and the different ways in which he can take a minimum number of moves.
6 7 5 3 10 9 4
3 1 3 2 1 1 3 1 2 1 2 1
Attention! Original plot! You have $$$N$$$ circularly placed chambers full of dragons which you must get rid of! Each of the dragons, however, has a specific power coefficient $$$x_i$$$ - just like you also have an initial power coefficient, $$$p$$$. Naturally, you can only defeat a dragon if your coefficient is greater than or equal to his.
After you defeat a dragon, your power increases. More specifically, $$$p$$$ will increase to $$$x_i|p$$$, where $$$x_i$$$ is the power of the dragon that you just defeated and $$$p$$$ is the power you had at that moment. Moreover, you can freely move to chambers $$$i-1$$$ or $$$i+1$$$. Since the rooms are circularly placed, it follows that you can move from room $$$1$$$ to $$$N$$$ and from room $$$N$$$ to $$$1$$$. Note that if the room that you move to has a dragon, it is your moral duty to defeat it.
By $$$x_i|p$$$ we refer to the bitwise or operator. In other words, if $$$x_i$$$ is equal to 3 (011 in binary) and $$$p$$$ is equal to 5 (101 in binary), the final result, $$$x_i|p$$$ will be equal to 7 (111 in binary).
Knowing that you must, eventually, defeat all of the dragons, and that you can begin in any room from $$$1$$$ to $$$N$$$, what is the minimum power coefficient that you must start with in order to finish this task of bravery?
The first line of input will contain an integer $$$N$$$ ($$$1 \leq N \leq 10^5$$$), denoting the number of rooms (and dragons). The second line of input will contain $$$N$$$ integers $$$x_i$$$ ($$$1 \leq x_i \leq 10^9$$$), where $$$x_i$$$ represents the power coefficient of the dragon placed in room $$$i$$$.
The output should contain the minimum power coefficient $$$p$$$ that you must start with in order to defeat all dragons.
5 5 1 4 7 2
4
In the world of competitive programming, a good IDE became a powerful tool. You are an exceptional programmer, but even you understand the need of such a tool, therefore you started implementing your own IDE. After you analyzed your coding style and read about the main operations an IDE is supposed to make, you decided to focus on finding the redundant code in a method. To start simple, you will consider a method that receives a list of $$$N$$$ booleans ($$$True$$$ or $$$False$$$) as parameters, and the body is formed of a list of $$$M$$$ statements like the following one $$$if$$$ $$$(X_i$$$ $$$\&$$$ $$$X_j)$$$ $$$ return;$$$, where $$$X_i$$$ and $$$X_j$$$ can be either parameters of this method or the negation of parameters of this method, $$$\&$$$ is the $$$AND$$$ operator, and $$$return$$$ will stop the execution of the method once it is reached. Finally, given such a method, you want your IDE to find out how many of these statements are redundant. A statement is considered redundant if and only if, no matter the values of the parameters, the method will never reach that statement. A statement is NOT considered redundant if its result is always $$$True$$$ or $$$False$$$ (i.e. its result is known before the execution of the method) as long as it is reached!
The first line of the input contains two numbers, $$$1 \leq N \leq 10^5$$$, the number of parameters, indexed from $$$1$$$, and $$$1 \leq M \leq 10^5$$$, the number of statements .
The following $$$M$$$ lines will each contain integers ($$$X, Y$$$) -not necessarily distinct- signifying that we have a statement of form $$$if$$$ $$$(X$$$ $$$\&$$$ $$$Y)$$$ $$$ return;$$$. $$$X$$$ and $$$Y$$$ are non-zero integers with an absolute value smaller or equal than $$$N$$$. Negative values are used to represent the negation of the parameters, while the positive values are used to represent the parameters themselves.
The output should contain one number, representing how many statements are redundant.
2 5 -1 2 -1 -2 1 -2 1 2 -1 -2
1
In the given examples, the only statement that will not be reached no matter the values of the parameters is the last one. This happens since the first $$$4$$$ statements exhaust all the possibilities of values for $$$2$$$ parameters (i.e. $$$False$$$ and $$$True$$$, $$$False$$$ and $$$False$$$, $$$True$$$ and $$$False$$$, $$$True$$$ and $$$True$$$). Please note that the $$$4^{th}$$$ statements is not redundant even if we know that its value is going to be $$$True$$$ once it is reached.
Summer is upon us, so Bob started eating watermelons. As everybody knows, spitting the seeds out (on a plate) makes the experience of eating watermelon that much more enjoyable.
Bob noticed on this particular day that the seeds formed a tree. He gave each of them a value and started applying the following queries on the tree:
Your task is to help Bob answer his queries!
The first line of the input contains an integer $$$N$$$ ($$$1 \leq N \leq 2 \cdot 10^5$$$), the size of the tree.
The second line contains $$$N$$$ integers $$$v_1,\ v_2,\dots,\ v_n$$$ ($$$0 \leq v_i \leq 10^9$$$, $$$1 \leq i \leq N$$$), the values corresponding to the nodes in the tree.
The next $$$N-1$$$ lines each contain two integers $$$a$$$ and $$$b$$$ ($$$1\leq a,b \leq N$$$, $$$a \ne b$$$), the description of the tree.
The next line contains an integer $$$Q$$$ ($$$1 \leq Q \leq 2 \cdot 10^5$$$), the number of queries.
The next $$$Q$$$ lines contain the queries in either one of the following formats:
The output should contain, on separate lines, the answer for each query of type $$$1$$$.
5 0 4 1 2 3 1 3 3 2 1 4 4 5 3 1 4 5 0 4 3 2 1 4 5
2 0
Wonderland offers a wide range of beautiful landscapes, one of them being the one from the jungle of palindromic trees. In this jungle there is a lot of diversification in terms of creatures, many of them being interested in solving problems with ... palindromes.
A problem which has been declared NP-complete in the jungle is the following one: you are given a 1-indexed lowercase string $$$S$$$ of length $$$N$$$ and $$$Q$$$ operations of four types. The operations are the following:
Can you prove to the jungle that this problem is actually in P?
The first line of the input will contain an integer $$$N$$$ ($$$1 \leq N \leq 10^5$$$), the length of $$$S$$$.
The second line of the input will contain the lowercase string $$$S$$$, having the length $$$N$$$.
The third line of the input will contain an integer $$$Q$$$ ($$$1 \leq Q \leq 10^5$$$), the number of operations.
The next $$$Q$$$ lines will contain a query of type $$$1$$$, $$$2$$$, $$$3$$$ or $$$4$$$. The format is as follows:
The output will contain $$$Q_4$$$ lines, where $$$Q_4$$$ is the number of operations of type $$$4$$$. Each of these lines will contain an integer, the maximum length of the palindrome found.
5 xxxxu 15 2 5 1 2 3 4 y 2 9 1 8 2 3 3 5 m 4 3 4 5 4 2 4 4 3 4 r 2 5 2 6 3 4 a
1 1 1 1
Alice has always dreamt about becoming a Security Software Engineer. She has recently been reading about how secure storage systems work. In one such system, there are documents and policies. Each document is tagged with a policy and policies are modelled as a DAG (Directed Acylic Graph). Each policy node may require a special key $$$k$$$ to access it. Additionally, access to a particular policy is dependant on access to all of its dependencies' policy.
Bob is a user of such system. Alice wants to determine at any given point the documents that Bob has access to. In particular, any document in the system is tagged with a policy and has a particular value - Alice wants to know the sum of values across the documents that Bob has access to.
Bob initially has zero keys. As time passes by, he gets access to different keys, which may unlock further access in the system for him. After every such new key, Alice needs to update her assessment of the sum of values across the documents Bob can see. Help her out with this task and she may return the favour in the future!
The first line of input will contain five integers: $$$ 1 \leq N \leq 2 \cdot 10^5$$$, $$$ 1 \leq M \leq 5 \cdot 10^5 $$$, $$$ 1 \leq D \leq 5 \cdot 10^5 $$$, $$$ 1 \leq K \leq 2 \cdot 10^5$$$, $$$ 1 \leq Q \leq 2 \cdot 10^5 $$$. $$$N$$$ is the total number of policy nodes in the system. $$$M$$$ is the number of dependencies between different policy nodes. $$$D$$$ is the total number of documents in the system. $$$K$$$ is the number of distinct keys that exist in the system. $$$Q$$$ is the number of queries that Alice has to answer to.
The next $$$M$$$ lines contain 2 integers each $$$x$$$ and $$$y$$$, meaning that access to policy $$$x$$$ requires access to policy $$$y$$$ first.
The next line contains $$$N$$$ numbers $$$p_i$$$ corresponding to the required key to access node $$$i$$$. If $$$p_i = -1$$$, that means no key is required to access node $$$i$$$. Where a key is required, it is guaranteed that $$$1 \leq p_i \leq K$$$.
The next $$$D$$$ lines contain a description of each document in the system. Each line has two values: $$$ 1 \leq policy_i \leq N$$$ and $$$0 \leq value_i \leq 10^9$$$.
The last $$$Q$$$ lines contain a key $$$1 \leq k_i \leq K$$$ Bob encounters over over time.
Print $$$Q$$$ lines. After each new key $$$k_i$$$, output the sum of documents' values Bob has access to. Note that he maintains access of all his previously found keys $$$k_j$$$ with $$$j \le i$$$.
4 1 6 4 4 3 1 -1 2 1 3 3 6 3 2 2 9 2 1 3 6 2 3 3 1 4 2
0 14 14 27
The forgotten country SigSegv of AGM consists of $$$N$$$ cities, connected with each other through $$$M$$$ bidirectional roads. The country has a very rich fauna, and hence, each road has an associated positive integer beauty value. Moreover, the country road infrastructure has a very interesting property: all cycles of the country that are made of distinct roads (but not necessarily distinct cities) have an odd length.
We define the beauty value of a simple path in the country (i.e., a path that contains distinct cities) as the sum of the beauty values associated to the roads of the path. The president of the country needs your help to find out the answer of the following question: What is the sum of the beauty values of all the simple paths of the country SigSegv of AGM?
The first line of input will contain two integers $$$N$$$ and $$$M$$$ ($$$1 \leq N \leq 10^6$$$, $$$1 \leq M \leq 10^6$$$), representing the number of cities and the number of bidirectional roads, respectively.
The next $$$M$$$ lines will each contain three integers $$$X$$$, $$$Y$$$, $$$B$$$ ($$$1 \leq X \leq N$$$, $$$1 \leq Y \leq N$$$, $$$X \neq Y$$$, $$$1 \leq B \leq 10^9$$$), representing that there is a bidirectional road between the cities $$$X$$$ and $$$Y$$$ with the associated beauty value $$$B$$$. It is guaranteed that the obtained graph is connected and that there are no self loops or multiple edges.
The output must contain one integer value that is equal to the sum of the beauty values of all the simple paths of the country SigSegv of AGM, modulo $$$998244353$$$.
3 3 1 2 1 2 3 2 1 3 3
18
10 12 1 2 2 2 3 1 3 4 2 4 5 3 4 6 1 5 6 2 1 7 3 7 2 1 7 8 4 8 9 2 8 10 3 9 10 1
1352
For his last mission in the espionage business, James Bond was tasked to determine how many spies he can send from the left side of the country to the right side, without raising any suspicions. The country has a total of N cities, where cities from $$$1$$$ to $$$\frac{N}{2}$$$ are placed on a line on the left side (ordered from $$$1$$$ to $$$\frac{N}{2}$$$), and cities from $$$\frac{N}{2} + 1$$$ to $$$N$$$ are on a line on the right side (ordered from $$$\frac{N}{2} + 1$$$ to $$$N$$$). There are no connections between cities on the same side of the country, but there are between cities on opposing sides, and between two cities, there can be at most one road that connects them.
Each road can only be travelled by one spy, and in order to not raise any suspicions, the roads of any two spies are not allowed to intersect, otherwise the enemy intelligence department would start thinking that the two are working together.
To clarify, James Bond is looking for a bipartite matching between the left side of the country and the right side, where no two roads intersect each other.
You are tasked to help James Bond find out the maximum number of spies he can send from the left side of the country to the right without raising suspicions, and in how many ways that can happen.
The first line of the input contains two numbers, $$$2 \leq N \leq 2 \cdot 10^5$$$ and $$$1 \leq M \leq min(\frac{N^2}{4}, 10^6)$$$. $$$N$$$ is guaranteed to always be an even number.
The following $$$M$$$ lines each contain two numbers, $$$1 \leq A \leq \frac{N}{2}$$$ and $$$\frac{N}{2} + 1 \leq B \leq N$$$, meaning there is a road from city $$$A$$$ to city $$$B$$$.
The output files should contain two numbers, the maximum numbers of spies that can be sent without raising suspicions and the numbers of ways they can be sent. Because the ways they can be sent can become very large, you are asked to print it modulo $$$\mathbf{998244353}$$$.
4 2 1 4 2 3
1 2
James Bond can only send at most $$$1$$$ spy, otherwise the roads they would intersect and would raise suspicions. There are $$$2$$$ ways in which James could send his spies.
You take a piece of paper and, from the middle of the page, you start completing a counter clock-wise number spiral, with $$$1$$$ as a starting point. After reaching $$$49$$$, you see that you ended up with a complete spiral with a side of $$$7$$$.
37 36 35 34 33 32 31
38 17 16 15 14 13 30
39 18 5 4 3 12 29
40 19 6 1 2 11 28
41 20 7 8 9 10 27
42 21 22 23 24 25 26
43 44 45 46 47 48 49
Interestingly, you notice that a lot of the prime numbers are occurring on the diagonals. For no particular reason, you start wondering how many prime numbers there are on the bottom left diagonal, i.e. from the center of the spiral to its bottom left corner. In the example above, note that the numbers in question are $$$1$$$, $$$7$$$, $$$21$$$, $$$43$$$.
The first line consists of:
Then, there are $$$Q$$$ lines containing two odd integers $$$a$$$ and $$$b$$$ ($$$3 \leq a \lt b \leq N$$$) representing the query "How many prime numbers are there on the bottom left diagonal between the spirals with the sides of a and b (inclusive)?". For example, in your original spiral, for $$$a = 3$$$, $$$b = 7$$$, the numbers are $$$7$$$, $$$21$$$, $$$43$$$.
The output should contain $$$Q$$$ lines, the answer to each query.
7 1 1 3 7
2
7 10000001 1 3 7
0
The Kingdom of AGM is the next target of the emperor. The kingdom is shaped as a directed acyclic graph. Commander Nix would have to guide his soldiers through the country starting from city $$$X$$$ (the border), all the way to city $$$Y$$$ (the capital). Alongside some of the roads in the kingdom, there are important settlements that also need to be conquered. Thus, before reaching the capital, the commander would have to make sure that for the road going from city $$$a_i$$$ to $$$b_i$$$ at least $$$c_i$$$ soldiers will traverse it. Having studied the resources available in the area, he also concluded that it would be impossible to have more than $$$d_i$$$ soldiers travel the road going from city $$$a_i$$$ to $$$b_i$$$.
In order to figure out if the mission should be approved, the emperor asked you to find out how many soldiers can reach the capital, considering Commander Nix's insight.
Keep in mind that no soldier should be abandoned. Thus, if not all soldiers that would take the mission can reach the capital, the mission is considered a failure.
The first line of the input contains two integers $$$N$$$ and $$$M$$$ ($$$1 \leq N \leq 500$$$ and $$$1 \leq M \leq 1100$$$), the number of cities, the number of rules and the number of soldiers that must reach the capital.
The second line will contain two integers $$$X$$$ and $$$Y$$$ ($$$1 \leq X, Y \leq N$$$, $$$X \ne Y$$$), the border and the capital, respectively.
The next $$$M$$$ lines will each contain four integers $$$a_i$$$ ($$$1 \leq a_i \leq N$$$), $$$b_i$$$ ($$$1 \leq b_i \leq N$$$, $$$a_i \ne b_i$$$), $$$c_i$$$, $$$d_i$$$ ($$$0 \leq c_i \leq d_i \leq 10^9$$$), signifying that along the road from city $$$a_i$$$ to city $$$b_i$$$ should travel at least $$$c_i$$$ and at most $$$d_i$$$ soldiers.
If the mission can be accomplished output the maximum number of soldiers that can reach the capital, otherwise output 0.
4 5 1 3 1 2 0 7 1 4 0 4 2 3 0 2 4 2 1 1 4 3 1 5
5
Bob has one more thing to do before he is happy with his new home. He must paint his bathroom floor tiles, which can be seen as a $$$N \times M$$$ matrix, in a specific colour plan. The only issue is that Bob is simply not capable of only painting one tile. He can either paint all tiles from a column or all tiles from a row.
Each row and column can be painted with a specific colour, each of them represented through an integer $$$c$$$, where $$$1 \leq c \leq K$$$. Bob is now wondering what is the minimum number of times he will have to paint rows and columns in order to get to the desired colour scheme - or if he will be able to get to it at all.
That is to say, for each row $$$i$$$ and each column $$$j$$$ of an $$$N \times M$$$ matrix, you are given a colour that you can paint it with. Moreover, you are given a matrix $$$a$$$ of size $$$N \times M$$$, where cell $$$a_{ij}$$$ ($$$1 \leq i \leq N$$$, $$$1 \leq j \leq M$$$) represents the colour that tile should end up having.
Knowing this, let Bob know the minimum number of times he has to paint rows and columns in order to get to the desired colour scheme. Moreover, tell him how. If he cannot get to his plan, just reply with -1. He might cry about it, but it is his fault.
The first line of input contains three integers: N, M,($$$1 \leq N \times M \leq 10^5$$$), and K ($$$1 \leq K \leq N+M$$$). They represent the number of rows, the number of columns and the maximum integer representation of a colour.
The second line will contain $$$N$$$ integers $$$RC_i$$$ ($$$1 \leq RC_i \leq K$$$), where $$$RC_i$$$ represents the colour that you can paint row $$$i$$$ with.
The third line will contain $$$M$$$ integers $$$CC_j$$$ ($$$1 \leq CC_j \leq K$$$), where $$$CC_j$$$ represents the colour you can paint column $$$j$$$ with.
After will follow a $$$N \times M$$$ matrix $$$a$$$, representing the colour scheme that Bob desires. Note that for all $$$a_{ij}$$$, it holds that $$$1\leq a_{ij} \leq K$$$.
On the first line, print an integer $$$X$$$ denoting how many times Bob must paint rows or columns.
On the next $$$X$$$ lines, print an integer $$$y_i$$$. If a row is painted, $$$y_i$$$ shall be a negative integer such that ($$$-N \leq y_i \leq -1$$$). If a column is painted, it shall be a positive integer such that ($$$1 \leq y_i \leq M$$$). If there are several solutions with a minimum number of steps, any of them is considered correct.
Alternatively, print -1 in case the desired colour scheme cannot be reached.
2 2 2 1 2 1 2 1 2 2 2
3 -1 -2 2
2 2 3 1 2 1 2 1 2 2 3
-1
In order to convince his friends that he is the smartest of them all, Tim is trying to compute the biggest XorAnd sum that a subsequence of an array of numbers of length $$$N$$$ can have.
A subsequence of $$$S$$$ is a non-empty sequence $$$S_{p_1}, S_{p_2}, \ldots, S_{p_K}$$$ with $$$1 \le p_1 \lt p_2 \lt \ldots \lt p_K \le N$$$ for some $$$2 \le K \le N$$$. Two subsequences $$$S_{p_1}, S_{p_2}, \ldots, S_{p_K}$$$ and $$$S_{q_1}, S_{q_2}, \ldots, S_{q_L}$$$ are different if the sequences $$$p$$$ and $$$q$$$ are different (either $$$K \ne L$$$, or there exists $$$1 \le i \le K$$$ such that $$$p_i \ne q_i$$$).
The XorAnd sum of a subsequence $$$S_{p_1}, S_{p_2}, ..., S_{p_k}$$$ is computed as:
$$$$$$ (S_{p_1} \oplus S_{p_2}) \ \&\ (S_{p_2} \oplus S_{p_3}) \ \&\ \dots \ \&\ (S_{p_{k-1}} \oplus S_{p_k}) $$$$$$
where $$$\oplus$$$ is the bitiwise xor operator and $$$\&$$$ is the bitwise and operator.
Help Tim find the largest XorAnd sum in $$$S$$$.
he first line of the input contains $$$2 \le N \le 10^6$$$, the length of the array.
The second line of the input contains $$$N$$$ integers, $$$S_1, S_2, \ldots, S_N$$$, representing Tim's array.
$$$0 \le S_i \le 10^9$$$ for all $$$1 \le i \le N$$$.
The only line in the output should contain an integer representing the biggest XorAnd sum a subsequence in $$$S$$$ can have.
4 3 1 2 1
3
The subsequence with the highest XorAnd sum is: [1, 2, 1].