Your favourite local farmer firmly believes that aliens do, in fact, exist. Even more so, he is sure that they are trying to communicate with him - through crop circles, no less.
These circles are quite peculiar - they are shaped in the form of a tree, and it seems like each circle contains one letter. The farmer is absolutely convinced that the letters represent, in fact, a codified message - simply because he has dreamed of a string which might be found (or not) as a chain in the tree of crop circles.
Since it is hard to believe, you must verify this. Given this tree with N nodes, each of them containing a lowercase letter of the Latin alphabet, how often does the string that the farmer has dreamed of occur as a simple path?
The first line of input will contain an integer $$$N$$$ ($$$1 \leq N \leq 10^5$$$), representing the number of nodes, and a string $$$s$$$ of at least $$$1$$$ and at most $$$10^{5}$$$ characters, representing the string that the farmer has dreamed of. Note that the string only consists of lowercase Latin alphabet letters: namely, for any element of the string, $$$s_i$$$, it holds that ($$$'a'$$$ $$$\leq s_i \leq$$$ $$$'z'$$$).
The next line will contain another string $$$x$$$ of $$$N$$$ characters. Character $$$x_i$$$ represents the letter which is found at node $$$i$$$.
Next will follow $$$N-1$$$ other lines, each of them with two integers $$$a$$$, $$$b$$$ ($$$1 \leq a,b \leq N$$$). These lines represent that an edge is drawn from node $$$a$$$ to node $$$b$$$.
The output should only have one integer - the number of times the farmer's string has been found as a simple path in the given tree.
Two simple paths of the same length $$$k$$$: $$$x_1, x_2, ..., x_k$$$ and $$$y_1, y_2, ..., y_k$$$ are considered different if there is at least one $$$i$$$ such that $$$x_i$$$, $$$y_i$$$ are different.
13 aba babaabaaabbaa 1 2 1 7 1 9 2 3 3 4 3 5 6 7 7 8 9 10 10 11 11 12 11 13
14
Wonderland is a territory which any AGM contestant (especially finalist!) would like to visit. However, at the border control, apart from a crazy guy yelling "Yeeeeeeeeeeeeeeeee" there is also another one who might yell "Uooooooooooh" at you and deny your entry. This tragic moment will happen unless you will be able to figure out the solution for the question below:
Given two integers $$$A$$$ and $$$B$$$, you have to find $$$N$$$ ($$$1 \leq N \leq 1000$$$) and a sequence of integers $$$x_1$$$, $$$x_2$$$, ... $$$x_N$$$ such that
In order to fully deserve your "Yeeeeeeeeeeeeee", you will have to solve correctly $$$Q$$$ problems like this.
The first line of input will contain an integer $$$Q$$$ ($$$1 \leq Q \leq 100$$$).
The next $$$Q$$$ lines will contain a pair of integers $$$A$$$ ($$$-10^{18} \leq A \leq 10^{18}$$$), $$$B$$$ ($$$-10^{18} \leq B \leq 10^{18}$$$, $$$B \neq 0$$$).
The output will contain $$$Q$$$ lines. Each line will contain $$$N$$$ followed by the sequence $$$x_1$$$, $$$x_2$$$, ... $$$x_N$$$ ($$$-10^{18} \leq x_i \leq 10^{18}$$$, for $$$1 \leq i \leq N$$$) on the same line, all separated by spaces. In case there are multiple solutions, you could output any.
In order to protect the platform, an additional output limit of 5000 kB has been set to this problem.
Any sequence $$$x_1$$$, $$$x_2$$$, ... $$$x_N$$$ which would imply a division by zero will be awarded with a wrong-answer verdict and not with a runtime error.
2 1 1 2 1
1 1 2 1 1
Your friend, Ron, is a very gifted student, but he has one problem: he almost finishes high-school and has yet to publish his first paper. How tragic! Being under the pressure of his limited time, he decided to invent a new concept called the $$$Girth$$$ of a set of at least $$$3$$$ points in the euclidean plane, no $$$3$$$ of which are collinear.
The $$$Girth$$$ of a set of points is calculated in the following way:
- You compute the Convex Hull of the set of points.
- You sum up the squares of lengths of all segments forming the convex hull.
Now, as a last effort to see if this new concept is revolutionary, he asks for you help. Now, he gives you a set $$$S$$$ of distinct points in the euclidean plane, no $$$3$$$ of which are collinear. He would like you to calculate $$$\sum Girth(S')$$$, where $$$S' \subseteq S$$$ and $$$|S'| \geq 3$$$, i.e. he wants you to sum up the $$$Girth$$$ over all subsets of at least $$$3$$$ points of the initial set.
The first line of the input contains a single integer: $$$N$$$ ($$$3 \leq N \leq 1000$$$), the number of points in the set.
The next $$$N$$$ lines will contain $$$2$$$ integers: $$$X_i$$$ ($$$-10^9 \leq X_i \leq 10^9$$$) and $$$Y_i$$$ ($$$-10^9 \leq Y_i \leq 10^9$$$), the coordinates of each point.
It is guaranteed that all points are pairwise distinct and that there are no $$$3$$$ collinear points.
The output should contain one integer, representing the sum of the $$$Girth$$$ of each subsets of at least 3 points, modulo $$$998244353$$$.
6 1 1 0 2 -3 2 -4 1 -2 0 0 -3
2068
4 0 0 0 1 1 1 1 0
20
Marko, the bartender, has a long night ahead of him. He has $$$N$$$ glasses (of infinite capacity) arranged in a sequence, numbered from $$$1$$$ to $$$N$$$. Initially all glasses are empty, but he will perform some operations on it:
- given 4 integers $$$L, R, X, Y$$$, he will add $$$X^Y$$$ milliliters of lemon juice to each glass in the interval $$$[L, R]$$$
- given 3 integers $$$L, R, M$$$, he wonders if $$$M$$$ of his friends will come to the bar and he needs to serve them with lemon juice from the glasses in interval $$$[L, R]$$$, how much lemon juice will remain in total in these glasses. Marko always serves his friends with the maximum amount of lemon juice such that each friend receives the same amount of lemon juice. (No quantity of lemon juice is removed from the glasses, Marko just asks about this imaginary scenario)
Knowing the queries that Marko needs to perform through the night, help him answer his questions.
The first line of the input contains two integers $$$1 \leq N \leq 10^5$$$ and $$$1 \leq Q \leq 10^5$$$, the number of glasses and the number of queries.
The following $$$Q$$$ lines each describe a query, being one of the following types:
- $$$0\ L\ R\ X\ Y$$$, with $$$1 \le L \le R \le N$$$ and $$$0 \le X, Y \le 10^9$$$, describing the first type of query, meaning that Marko adds $$$X^Y$$$ milliliters of lemon juice in each of glasses in interval $$$[L, R]$$$.
- $$$1\ L\ R\ M$$$, with $$$1 \le L \le R \le N$$$ and $$$2 \le M \le 100$$$, describing the second type of query, meaning that Marko asks for the quantity of lemon juice in the glasses in interval $$$[L, R]$$$ modulo $$$M$$$.
The output should contain a line for each query of the second type with a single integer representing the answer to that query.
3 2 0 1 2 1 1 1 1 2 100
2
It's like you are from The Matrix movies...
For any positive integer $$$N$$$, let's consider the $$$N \times N$$$ matrix $$$A$$$, where A_{i,j} = ((j - i) mod N) + 1 for every $$$1 \le i,j \le N$$$.
For example, for $$$N = 4$$$, the matrix is:
Given two integers $$$2 \le N \le 10^6$$$ and $$$1 \le K \le 10^6$$$, such that $$$2 \le N \cdot K \le 10^6$$$, find the matrix $$$A' = A^K$$$.
Since the matrix can be huge, given a prime integer $$$2 \le B \lt 998244353$$$ you need to output the following encoding of $$$A'$$$:
$$$\sum_{i=1}^n \sum_{j=1}^n (A_{i, j}' \cdot B^{(N-i) * N + (N - j)}) \mod 998244353$$$
The only line of the input contains 3 integers $$$N, K, B$$$, having the meaning as in the statement.
The output should contain one line, representing the answer modulo $$$\mathbf{998244353}$$$.
15 19 666013
693191805
2 2 7
1944
This year at the Olympics a new event was introduced: the mixed distance relay race. In this event, all of the athletes from each delegation try to run a $$$D$$$ meter race as fast as possible. Compared to the traditional competitions, there is one key difference: each team decides how to split the total distance among all of its runners.
The rules are:
- The athletes must run a total distance of $$$D$$$ meters.
- Each athlete starts running as soon as the previous teammate finishes his split.
- Each athlete must run an integer amount of meters.
- Each athlete must run at least 1 meter.
- The delegation's time is the sum of all individual runners' times.
As the chief strategist of your country's delegation, you must come up with a way of splitting the distance such that the total time is as small as possible.
You know that your delegation is composed of $$$N$$$ runners. Each one of them is characterized by two numbers: an initial speed, $$$a_i$$$, and a slowing down rate, $$$b_i$$$.
Initially, runner $$$k$$$ can advance a meter in $$$a_k$$$ seconds and, after that, each subsequent meter takes $$$b_k$$$ more seconds than the previous one. To be precise, the time it takes for athlete $$$k$$$ to run the $$$j^{th}$$$ meter is $$$a_k + b_k * (j - 1)$$$.
Knowing all the details about your delegation, you are asked to compute the smallest amount of time you could obtain with a valid way of splitting the distance among your athletes.
The first line of the input contains $$$2$$$ integers: $$$1 \leq N \leq 10^5$$$, the number of runners in the delegation, and $$$N \leq D \leq 10^9$$$, the length of the race.
Each of the following $$$N$$$ lines contains two integers $$$1 \leq a_i \leq 10^9$$$ and $$$1 \leq b_i \leq 10^9$$$, the description of each runner.
The output should contain one integer, representing the minimum possible time to complete the race. Since the value might become too large, print the result modulo $$$998244353$$$.
3 9 2 3 1 3 4 1
41
3 3 2 3 1 3 4 1
7
Petrick has a very complicated schedule. He is a busy businessman and has a lot of tasks to do during the day, one of them being to propose some easy to implement problems that contestants enjoy working on. Coming back to Petrick, he needs to take care that some of its tasks must start way before others and he does not care when he finishes them. Also, he can solve more tasks at the same time! Petrick got $$$N$$$ jobs during the day (numbered from $$$0$$$ to $$$N -- 1$$$) and $$$M$$$ restrictions of two types. The first type of restriction says that the job number $$$X$$$ must start no later than $$$L$$$ seconds before the job number $$$Y$$$ starts. In this case, the job number $$$Y$$$ must start at least $$$L$$$ seconds after the beginning of the day. The second type of restriction says that the job number $$$X$$$ must start no later than $$$L$$$ seconds after the job number $$$Y$$$ starts. Petrick has only one day to solve his tasks and his day starts at second $$$0$$$ and ends at second $$$10^{12}$$$. Help him find out if there is a way to solve each task in the interval of seconds $$$[0, 10^{12}]$$$.
The first line of the input contains a number $$$1 \leq T \leq 13$$$, the number of tests. The first line of each test contains 2 integers $$$2 \leq N \leq 1000$$$, the number of tasks, and $$$1 \leq M \leq 1000$$$, the number of restrictions. The following $$$M$$$ lines each contain integers ($$$R, X, Y, L$$$) signifying that we have a restriction of type $$$R$$$ ($$$1 \leq R \leq 2$$$) between job number $$$X$$$ and job $$$Y$$$ as described above ($$$0 \leq X, Y \leq N - 1,$$$ $$$0 \leq L \leq 10^{9}$$$).
The output should contain $$$T$$$ lines, each containing an answer to a test, the starting times (in seconds) of each task separated by spaces or $$$-1$$$ in a case with no solution. If there are more solutions over the interval of time $$$[0, 10^{12}]$$$ you can output any of them.
2 3 2 2 0 1 0 1 1 2 1 2 2 1 0 1 10 1 1 0 10
0 0 1 -1
Bob is currently infatuated with arrays of numbers - so much that he wants to analyze every single pattern that he can. Namely, for a given pair of two arrays, Bob wants to see as many longest common subsequences as possible.
Formally, Bob will give you two arrays $$$a$$$, $$$b$$$, and $$$q$$$ queries. Each query will contain an integer $$$k_i$$$. You are asked to find, among all longest common subsequences ordered lexicographically, the $$$k_i^{th}$$$ one. If there are not at least $$$k_i$$$ such subsequences, the answer will be $$$-1$$$.
Note that two subsequences with the same elements are not necessarily identical. For two of them to be different, it is enough that they are obtained from different positions in the arrays, although the actual integers are the same.
The first line of input will contain two integers $$$N$$$, $$$M$$$, $$$Q$$$, denoting the length of the arrays of integers and the number of queries. Note that $$$1 \leq N, M, Q \leq 100$$$.
The next two lines of input will contain two arrays of integers $$$a_i$$$ ($$$1 \leq i \leq N$$$, $$$1 \leq a_i \leq 10^9$$$) and $$$b_j$$$ ($$$ 1 \leq j \leq M $$$, $$$1 \leq b_j \leq 10^9$$$) - the arrays that Bob is currently infatuated with.
The next $$$Q$$$ lines will each contain an integer $$$k_i$$$, ($$$1 \leq k_i \leq 10^{18}$$$), representing the number of the subsequence from the ordering that Bob wants to see.
Print, on $$$q$$$ lines, the answer to Bob's queries, in the order that they are given. Namely, print -1 if a $$$k^{th}$$$ lexicographically ordered longest common subsequence does not exist. Otherwise, print the $$$k^{th}$$$ subsequence.
20 16 10 6 96 56 9 20 96 26 45 23 22 59 96 64 1 1 15 17 1 16 17 26 20 56 6 45 96 9 96 64 96 59 22 23 5 6 4 1 2 3 4 5 6 7 8 9 10
6 96 9 96 22 6 96 9 96 22 6 96 9 96 23 6 96 9 96 23 6 96 9 96 59 6 96 9 96 59 6 96 9 96 64 6 96 9 96 64 6 96 9 96 96 -1
4 5 5 1 3 2 4 2 1 4 5 3 1 2 3 4 5
1 3 1 4 2 4 -1 -1
You are given a tree and two possible operations that can be applied to the tree:
- First operation, with cost $$$c_1$$$: Pick a chain $$$x_1$$$ - $$$x_2$$$ - $$$x_3$$$ ($$$x_1$$$ connected to $$$x_2$$$, $$$x_2$$$ connected to $$$x_3$$$). For each of $$$x_3$$$'s neighbors (except for $$$x_2$$$), we remove their edges to $$$x_3$$$ and instead connect them to $$$x_1$$$. $$$x_3$$$ also removes it's edge to $$$x_2$$$ and connect it to $$$x_1$$$.
- Second operation, with cost $$$c_2$$$: Pick a chain $$$x_1$$$ - $$$x_2$$$ - $$$x_3$$$ ($$$x_1$$$ connected to $$$x_2$$$, $$$x_2$$$ connected to $$$x_3$$$). For each of $$$x_3$$$'s neighbors (except for $$$x_2$$$), we remove their edges to $$$x_3$$$ and instead connect them to $$$x_1$$$. Then, remove $$$x_3$$$ from the tree. (The same as the previous operation, but instead of connecting to $$$x_1$$$, node $$$x_3$$$ is completely removed from the tree)
Find the minimum cost necessary to transform the tree into a star.
A star is a special type of tree with $$$n$$$ nodes, in which $$$n - 1$$$ vertices have degree $$$1$$$ and a single vertex has degree $$$n - 1$$$ (is connected to all other vertices).
The first line of the input contains the number of nodes, $$$3 \le N \le 10^5$$$, and the costs of the two operations, $$$1 \le c_1, c_2 \le 10^9$$$.
The following $$$n - 1$$$ lines each contain two integers $$$a, b$$$, with $$$1 \le a, b \le n$$$, meaning that there is a bidirectional edge between node $$$a$$$ and node $$$b$$$.
The only line in the output should contain an integer representing the minimum cost necessary to transform the tree into a star.
5 10 15 1 2 2 3 3 4 4 5
10
A funny tree is a perfect binary tree - that is, all of the internal vertices have two children and all of the leaves are situated at the same depth in the tree.
For a funny tree with $$$N$$$ levels, the root of the tree is labelled with $$$1$$$. For each node $$$x$$$ its children are labelled with $$$2 * x$$$ (left child) and $$$2 * x + 1$$$ (right child). See the diagram below for an example with $$$N = 3$$$.
Moreover, a funny tree has friendships between some of its leaves. A friendship is defined as a pair $$$(x, y)$$$ where both $$$x$$$ and $$$y$$$ are leaves of the tree. We define the funness of a funny tree $$$T$$$ as:
- $$$F$$$ is the set of friendships of $$$T$$$
- $$$LCA(x, y)$$$ is the lowest common ancestor of nodes $$$x$$$ and $$$y$$$
- $$$SubtreeSize(z)$$$ is the number of nodes in the subtree of $$$T$$$ rooted at $$$z$$$
You are given a funny tree $$$T$$$ and its set of friendships $$$F$$$, as well as a number of operations. An operation can have one of the following types:
- type $$$0$$$: add new friendship $$$(x, y)$$$ to $$$F$$$
- type $$$1$$$: remove friendship $$$(x, y)$$$ from $$$F$$$
- type $$$2$$$: compute the funness of $$$T$$$ if leaves $$$x$$$ and $$$y$$$ are swapped (that is, if $$$x$$$ was placed where $$$y$$$ is in the original tree and the other way around)
The first line of the input contains an integer $$$N$$$ representing the height of the tree.
The second line of the input contains an integer $$$M$$$ representing the number of friendships.
The next $$$M$$$ lines contain the $$$M$$$ friendships $$$(x_i, y_i)$$$.
The following line contains an integer $$$Q$$$ representing the number of operations.
The last $$$Q$$$ lines of the input contain 3 integers $$$(t_i, x_i, y_i)$$$ representing the type of the operation and the two leaves for which the operation is intended.
$$$1 \leq N \leq 30$$$
$$$1 \leq M, Q \leq 10^5$$$
It is guaranteed that the initial $$$M$$$ friendships only contain leaves of the tree. Moreover, it is guaranteed that when the operation is to add a new friendship that friendship doesn't exist already in the set of friendships $$$F$$$. Likewise, when removing a friendship it is guaranteed that it exists in $$$F$$$. No friendship will be between a leaf $$$x$$$ and itself. Note that $$$(x, y)$$$ and $$$(y, x)$$$ represent the same friendship and it can appear in both forms in the input.
Note that operations of type $$$2$$$ leave the tree intact (no swap actually takes place).
The output should contain one integer per line representing the answers to the operations of type $$$2$$$ in the order they are received.
3 3 4 5 4 6 5 7 5 2 5 6 0 5 6 2 4 7 1 4 5 2 4 5
13 20 21
After a lot of work and many solved problems, you decided to take a holiday to Wonderland. Unfortunately, right before going to the beach to have a well deserved day off, the president of this land came to you with a list of requests.
Wonderland can be seen as a connected graph, containing $$$N$$$ touristic attractions, connected with each other through $$$M$$$ bidirectional roads. Each touristic attraction has a happiness factor $$$H_i$$$ which defines the happiness of a tourist after visiting it.
The president is currently working on the best strategy to get the economy back on track after the pandemic, therefore he wants to find out the answer to $$$Q$$$ questions of the following type. Given two, not necessarily distinct, touristic attractions $$$X$$$ and $$$Y$$$, an excitement factor $$$V$$$ of a tourist and a value $$$K$$$, the president wants to find out the following: Considering the set of touristic attractions that can be visited on any path from $$$X$$$ to $$$Y$$$ with the property that you do not use the same road twice, what is the level of interest of the $$$K^{th}$$$ least interesting touristic attraction for the given tourist? The level of interest of the given tourist towards the $$$i^{th}$$$ touristic attraction is given by the value $$$V$$$ $$$XOR$$$ $$$H_i$$$ (bitwise exclusive or operator). Please note that the $$$K^{th}$$$ least interesting touristic attraction for the given tourist is the one having the $$$K^{th}$$$ least level of interest.
This is a task way too hard for the programmers of this land, so the president is asking you to answer his questions.
The first line of input will contain three integers $$$N$$$, $$$M$$$, $$$Q$$$ ($$$1 \leq N \leq 10^5$$$, $$$1 \leq M \leq 2*10^5$$$, $$$1 \leq Q \leq 10^5$$$), representing the number of touristic attractions, the number of roads and the number of questions.
The next line will contain $$$N$$$ values $$$H_i$$$ ($$$0 \leq H_i \leq 10^6$$$), representing the happiness factors of the touristic attractions.
The next $$$M$$$ lines will each contain two values $$$X$$$ and $$$Y$$$ ($$$1 \leq X \leq N$$$, $$$1 \leq Y \leq N$$$, $$$X \neq Y$$$), representing that there is a bidirectional road between the tourist attractions $$$X$$$ and $$$Y$$$. It is guaranteed that the obtained graph is connected and that there are no self loops or multiple edges.
The last $$$Q$$$ lines will each contain four values $$$X$$$, $$$Y$$$, $$$V$$$ and $$$K$$$ ($$$1 \leq X \leq N$$$, $$$1 \leq Y \leq N$$$, $$$0 \leq V \leq 10^6$$$, $$$1 \leq K \leq 10^6$$$), representing a question.
The output contains $$$Q$$$ lines, representing the answers to the questions in the same order that they were given in the input. If there are at least $$$K$$$ tourist attractions on the paths between $$$X$$$ and $$$Y$$$ (with the property that you do not use the same road twice - note that this means that any touristic attraction can be repeated throughout the path), then print the level of interest $$$H_i$$$ $$$XOR$$$ $$$V$$$ of the $$$K^{th}$$$ least interesting one, otherwise print $$$-1$$$.
12 15 10 2 3 1 3 2 1 2 1 3 1 2 3 1 2 1 3 2 3 2 4 1 4 4 6 2 5 5 7 7 8 5 8 8 9 2 11 11 10 11 12 10 12 9 11 0 1 9 11 0 2 9 11 0 3 9 11 0 4 9 11 0 5 9 11 0 6 9 11 0 11 9 11 0 12 6 2 1 3 6 2 2 3
1 1 1 2 2 2 3 -1 2 1
Bob finally found a new home - with exactly $$$N$$$ rooms, all of them in a line - and he is extremely excited!
Now, the last thing he needs to do in order to be fully happy with his purchase is to paint all of the rooms in several colours. Although it would normally be hard work, Bob has a machine and $$$N$$$ paint buckets containing those colours. Naturally, he knows what colour each of the rooms should have. Therefore, every room will require a colour $$$c_{i}$$$ ($$$1 \leq c_{i} \leq K$$$).
Note that multiple rooms can have the same colour, but they will require different buckets. Moreover, Bob has a bucket for every room - meaning that if there are two rooms with colour number 2, he will have two buckets of that colour. This way, it is sure that he will get to his desired colour plan.
Bob starts at whatever room he desires and charges the machine with a colour. However, he is so excited that he cannot even think about what he must pick - indeed, Bob charges the machine with a random bucket. Therefore, two things can happen: Bob either picks the correct colour to charge the machine with, or he does not. If he does, he can paint the room and move to a room of his liking that was not painted yet. If he does not, he has to recharge the machine with another random bucket, up until he gets it right. Note that he always puts back the buckets that he has not used, since Bob will need it later on.
Since Bob always picks the bucket to charge the machine with at random, what is the expected amount of times he will have to charge it if he wants to paint all of the rooms? Bear in mind that Bob always chooses the first (and following) rooms optimally. That is to say, he will always pick a room in a way such that the expected number of total recharges over all rooms is minimized.
Please note that if there are $$$K$$$ buckets left in the machine, each of them has a probability of $$$\frac{1}{K}$$$ to be picked. Hence if there are $$$Q$$$ buckets of colour $$$3$$$, for instance, the probability of picking a bucket with that colour is $$$\frac{Q}{K}$$$.
The first line of input contains two integers: $$$N$$$ ($$$1\leq N \leq 10^5$$$) and $$$K$$$ ($$$1\leq K \leq N$$$), denoting the number of rooms and the number of different colours.
The second line shall contain $$$N$$$ integers, $$$c_i$$$ ($$$1 \leq i \leq N$$$ and $$$1 \leq c_i \leq K$$$), denoting the colour that room $$$i$$$ must be painted with.
Print an integer $$$X$$$ denoting the number of times Bob is expected to charge the machine, knowing that he picks the bucket randomly every single time and that he chooses the order of the rooms such that the final result will be minimized. Print X at a precision of $$$10^{-6}$$$.
6 3 2 1 3 3 2 3
12.50000000