I heard Alex really likes trees!
Given a tree, output "YES" if it produces oxygen, "NO" otherwise.
A tree.
—
Tests in subtasks are numbered from $$$1−20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.
Test $$$1-10$$$ are trees we found by going outside and touching grass. They produce oxygen.
Test $$$11-15$$$ are graph-theoretic trees. They do not produce oxygen. The first line contains $$$N$$$, the number of nodes. Nodes are indexed from $$$1$$$ to $$$N$$$. The next $$$N-1$$$ lines contain two integers $$$u$$$, $$$v$$$, representing an edge from node $$$u$$$ to node $$$v$$$.
Test $$$16-20$$$ are segment trees, written in C++ by various members of our problemsetting team. They do not produce oxygen.
"YES" if the tree produces oxygen, "NO" otherwise.
==
++== =-
++=*+===:= +=-
+*##***=-=*##*=====
+**%%#*#+*#%%%%%====
+++==++*+#%#**#%%#%%##*==-
***##++##+*%%+%%%#%%#+*++=
*####%%#**##%%%%%%#**==*=++=
+*#%%%%%%%%%%%%%%%#*##***===+##+=
+#+*+#%%%%%#**#%%%##+*#++==###*#*=-
+++*+=-==*-=+**%#+*+**+=###++*+=-:-
+#=*####*+**#*++**#=+%%#*:++====
*#######*+**=*%##%#*+-*#-:==
###*#*%##%*+*+%%%%##**++-+***#++--
*####+=#@%####%%%%%%**+===+#####%#-:-
+#*###*###%%***%%%@++*=#+-+#****+++*=-
+++*#%%%%%%#%%#%%@%%+--###+#**%#+-====-
++##%%%%%%#%%#*%%%%+#*%%*#%=+**=-
*+###%%%++%%%##%*####%%#*##+-+=-
%%%%%##*####+##%%%%%##*#*++++-=
#*#%%%#%*+#%%%%%#%%%%#+##%*#*+=-
**####%*=##%%%%##%%**+*#*#=#+=
*****#*++#%%%%+-%*+=*+=*+==+=
++++*+ #%##*#=#+=- =+=+ -=
*###*#+=+-- =
*###=+==:-
*##*=::-
+#-::
#-.
#-.
*:.
#=.
*-.
*-.
*=.
*=.
*-.
*=.
*-.
*-.
*-.
#*==
###*#+*=
#%#%-=+:=+
%##%%:--.--
++*%#--+-+=
##*%#=-=:-+
#*##=*=----
*##%*=%+*#=+=**
%##+*=+*###+-#=++
%%#=%+=*+*%**=--=
##++#++**%%*+=-==
%%*+###+*#%*%=+-
%%*###++%*+##--
%%%%#++=%%+=*=-
%%%##+=+%%*+=++
%%%%%+#+#%%+*#+
%%%%%*#+**#%#*#*%
%%%%**+*=+#+*#-+*
%%%%*%#*==#*=**+=
%%%#%#==+#*=+=*%
#%%%%##+**+=+=*#
*#%%%%#*-*%%===*#
%%%%##%-+%%++=%
%%##=%#==*#++=#
%%#%%%*++-=+*++
%@%%#%%#+=:**=%
%%%##%%**==**+%
%%#+#+%++-==++%
####*+%**+==+=+
#%%%%*==++*+++#
%%%##%%===+*=*%
%%%#*%#==*++=+%
*%%*%%#-=+=**+%
+###%%%*=+#+=*%
.-%#%#%%%*:=+*
.:#+#+**#-*+-.
-.##+=-.:=+%
.#*+=:..
:*+=*-.
%%#=*:.
%%#==:.
%%**--.
%#+=-:.
%%+=--.
%%#+-=-=
+%%+=:--
%+*#+*-+
%#**+*=+
#**##==
YES
5 1 3 1 4 3 5 2 3
NO
#include <bits/stdc++.h>
using namespace std;
int arr [1000000];
int va [1000000];
int lc [1000000];
int rc [1000000];
int curnod = 5;
int newnod(){
return ++curnod;
}
void construct(int cur, int l, int r){
if(l == r){
va[cur] = arr[l];
}else{
lc[cur] = newnod();
rc[cur] = newnod();
construct(lc[cur], l, (l+r)/2);
construct(rc[cur], (l+r)/2+1, r);
va[cur] = min(va[lc[cur]], va[rc[cur]]);
}
}
void change(int cur, int l, int r, int k, int u){
if(l <= k && k <= r){
if(l == r){
va[cur] = u;
}else{
change(lc[cur], l, (l+r)/2, k, u);
change(rc[cur], (l+r)/2+1, r, k, u);
va[cur] = min(va[lc[cur]], va[rc[cur]]);
}
}
}
int query(int cur, int l, int r, int fl, int fr){
if(fl <= l && r <= fr){
return va[cur];
}else if(r < fl || fr < l){
return 1000000000;
}else{
return min(query(lc[cur], l, (l+r)/2, fl, fr), query(rc[cur], (l+r)/2+1, r, fl, fr));
}
}
int main() {
int n, q;
cin >> n >> q;
for(int i = 1; i <= n; i++){
cin >> arr[i];
}
int root = newnod();
construct(root, 1, n);
for(int i = 0; i < q; i++){
int o;
cin >> o;
if(o == 1){
int k, u;
cin >> k >> u;
change(root, 1, n, k, u);
}else{
int l, r;
cin >> l >> r;
cout << query(root, 1, n, l, r) << endl;
}
}
}
NO
The first sample test case is a California Fan Palm. Although botanically speaking, palm trees are not true trees, this tree certainly undergoes photosynthesis and produces oxygen.
The second sample test case is a connected undirected acyclic graph; i.e., a graph-theoretic tree. It contains 5 nodes, numbered 1, 2, 3, 4, and 5. It has an edge connecting node 1 and node 3, node 1 and node 4, node 3 and node 5, and node 2 and node 3. This tree has only three leaves: nodes 2, 4, and 5, and the leaves do not have any chlorophyll. Thus, this tree does not produce oxygen.
The third sample test case is a segment tree, written in C++ by alexlikemath007. Although segment trees can combine segments together to perform range queries, they cannot combine water, carbon dioxide, and sunlight together to perform photosynthesis. Thus, this tree does not produce oxygen.
You are given an integer array $$$a$$$ of length $$$N$$$ and an integer $$$K$$$.
In one operation, you must pick two elements from $$$a$$$, remove them, and append their sum to $$$a$$$.
You have to make $$$Q$$$ of the following changes to the array: Given $$$i,j$$$, set $$$a_i$$$ to $$$j$$$.
After each change, output whether you can perform $$$ N-1$$$ operations without $$$a$$$ ever containing the value $$$K$$$, both before and after an operation.
The first line consists of an integer $$$t$$$ ($$$1 \le t \le 10^5$$$), the number of test cases.
The first line of each test case consists of three integers $$$N$$$ ($$$1 \le N \le 2 \cdot 10^5$$$), $$$K$$$ ($$$0 \le K \le 10^{12}$$$), and $$$Q$$$ ($$$1 \le Q \le 2 \cdot 10^5$$$).
The next line consists of $$$a_1, a_2, \dots ,a_n$$$ ($$$0 \le a_i \le 2 \cdot 10^5$$$).
The next $$$Q$$$ lines consist of two integers $$$i$$$ ($$$1 \le i \le N$$$), and $$$j$$$ ($$$0 \le j \le 2 \cdot 10^5$$$).
The sum of $$$N$$$ and the sum of $$$Q$$$ over all $$$t$$$ test cases does not exceed $$$2 \cdot 10^5$$$.
—
Tests in subtasks are numbered $$$1 - 20$$$ with samples skipped. Each test is worth $$$\frac{100}{20} = 5$$$ points.
Tests $$$1-2$$$ satisfy $$$N, a_i \le 5$$$.
Tests $$$3-5$$$ satisfy $$$N \le 10^4$$$.
Tests $$$6-20$$$ satisfy no additional constraints.
After each change, output "YES" if it is possible to perform exactly $$$N-1$$$ operations such that the array never contains the value $$$K$$$ at any point; otherwise, output "NO."
14 4 51 2 2 21 11 02 03 04 4
YESNONOYESNO
After change $$$1$$$, you can perform the operations $$$(1,2)$$$ to make $$$a=[2,2,3]$$$, $$$(2,3)$$$ to make $$$a=[2,5]$$$, and $$$(1,2)$$$ to make $$$a=[7]$$$.
After changes $$$2$$$ and $$$3$$$, there is no way to avoid $$$k=4$$$.
After change $$$4$$$, you can perform the operations $$$(1,2),(1,2),$$$ and $$$(1,2)$$$.
After change $$$5$$$, $$$k=4$$$ is already in $$$a$$$.
You have an array $$$a$$$ that has an initial length of $$$n$$$. Process the following queries:
- 1 x: Append $$$x$$$ to the end of the array.
- 2: Delete the last element of the array.
- 3: Reverse the array.
- 4: Clone the array and append the clone to the end of the array.
- 5: Query the sum of all elements in the array, modulo $$$998244353$$$.
The first line consists of an integer $$$n$$$ $$$(1 \le n \le 5 \cdot 10^5)$$$, the initial size of the array.
The second line consists of $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ $$$(0 \le a_i \le 10^9)$$$, the initial array.
The third line consists of an integer $$$q$$$ $$$(1 \le q \le 5 \cdot 10^5)$$$, the number of queries.
The next $$$q$$$ lines contain the queries as described above, subject to the following constraints:
- In queries of Type $$$1$$$, $$$0 \le x \le 10^9$$$.
- In queries of Type $$$2$$$, the array is not currently empty.
- It is guaranteed that there is at least one query of Type $$$5$$$.
—
Tests in subtasks are numbered from $$$1-20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.
Test $$$1$$$ has no queries of Types $$$1$$$, $$$2$$$, $$$3$$$, or $$$4$$$.
Tests $$$2-4$$$ have no queries of Type $$$4$$$.
Tests $$$5-7$$$ satisfy $$$n, q \le 10$$$.
Tests $$$8-9$$$ have no queries of Types $$$1$$$, $$$2$$$, or $$$3$$$.
Tests $$$10-11$$$ have no queries of Type $$$2$$$.
Tests $$$12-15$$$ have no queries of Type $$$3$$$.
Tests $$$16-20$$$ satisfy no additional constraints.
For each query of Type $$$5$$$, output one integer — the sum of all elements in the array, modulo $$$998244353$$$.
51 3 2 4 554231 35
28
Consider the sample test.
After query $$$\texttt{4}$$$, the array becomes $$$\{1, 3, 2, 4, 5, 1, 3, 2, 4, 5\}$$$.
After query $$$\texttt{2}$$$, the array becomes $$$\{1, 3, 2, 4, 5, 1, 3, 2, 4\}$$$.
After query $$$\texttt{3}$$$, the array becomes $$$\{4, 2, 3, 1, 5, 4, 2, 3, 1\}$$$.
After query $$$\texttt{1 3}$$$, the array becomes $$$\{4, 2, 3, 1, 5, 4, 2, 3, 1, 3\}$$$.
To answer query $$$\texttt{5}$$$, compute the sum $$$4 + 2 + 3 + 1 + 5 + 4 + 2 + 3 + 1 + 3 = 28$$$.
There are $$$n$$$ poles placed on a line, evenly spaced, with height $$$a_1,a_2,..,a_n$$$. Culver defines the steepness from pole $$$i$$$ to pole $$$j$$$ ($$$i\ne j$$$) being $$$$$$\left|\frac{a_i-a_j}{i-j}\right|$$$$$$ He wants to know the maximum and minimum possible steepness among all valid choices of pole $$$i$$$ and pole $$$j$$$.
Additionally, since Culver will occasionally replace a pole with another one possibly with a different length, he would like to know the new maximum and minimum steepness after each replacement. As Culver does not want to do the calculations himself, please help him.
The first line contains an integer $$$t$$$ ($$$1\le t\le 10^4$$$), the number of test cases.
The first line of each test case contains an integer $$$n$$$ ($$$2\le n\le 10^5$$$), the number of poles.
The next line of each test case contains $$$n$$$ integers $$$a_1,a_2,...,a_n$$$ ($$$1\le a_i\le 10^9$$$), the height of each pole.
The next line of each test case contains an integer $$$m$$$ ($$$1\le m\le 10^5$$$), the number of replacements.
The $$$k$$$-th line of the next $$$m$$$ lines contains two integers $$$x_k,y_k$$$ ($$$1\le x_k\le n$$$, $$$1\le y_k\le 10^9$$$), meaning that in the $$$k$$$-th replacement, Culver changes the height of pole $$$x_k$$$ to $$$y_k$$$ i.e. the value of $$$a_{x_k}$$$ becomes $$$y_k$$$.
It is guaranteed that both the sum of $$$n$$$ and the sum of $$$m$$$ over all test cases do not exceed $$$10^5$$$.
—
Tests in subtasks are numbered from $$$1-20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.
Test $$$1$$$ satisfies $$$n = 2$$$.
Tests $$$2-3$$$ satisfy $$$n \le 10$$$.
Test $$$4$$$ satisfies $$$m \le 10$$$.
Tests $$$5-20$$$ satisfy no additional constraints.
For each test, output $$$m+1$$$ lines.
The first line should contain two real numbers $$$max_0,min_0$$$, the maximum and minimum steepness at first.
Each line on the next $$$m$$$ lines contain two real numbers $$$max_k,min_k$$$, the maximum and minimum steepness after the $$$k$$$-th replacement.
Your answer is considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$.
Formally, let your answer be $$$a$$$, and the jury's answer be $$$b$$$. Your answer is accepted if and only if $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$$$.
451 3 4 5 232 12 35 661 1 1 1 1 161 12 23 34 45 56 646 9 4 244 62 101 13 521 131 12 21 5
3.000000 0.250000 3.000000 0.000000 3.000000 0.250000 2.000000 1.000000 0.000000 0.000000 0.000000 0.000000 1.000000 0.000000 2.000000 0.000000 3.000000 0.000000 4.000000 0.000000 1.000000 1.000000 5.000000 1.000000 5.000000 0.000000 6.000000 0.000000 9.000000 1.500000 9.000000 1.000000 0.000000 0.000000 0.000000 0.000000 1.000000 1.000000 3.000000 3.000000
In the first test case:
Initially, the heights of the poles are $$$1,3,4,5,2$$$ respectively. Then we can get the maximum steepness by choosing pole $$$4$$$ and pole $$$5$$$ which gives a steepness of $$$\left|\frac{5-2}{4-5}\right|=3$$$. We can get the minimum steepness by choosing pole $$$1$$$ and pole $$$5$$$ which gives a steepness of $$$\left|\frac{1-2}{1-5}\right|=0.25$$$.
After the first replacement, the height of the poles become $$$1,1,4,5,2$$$ respectively. Then we can get the maximum steepness by choosing pole $$$4$$$ and pole $$$5$$$ which gives a steepness of $$$\left|\frac{5-2}{4-5}\right|=3$$$. We can get the minimum steepness by choosing pole $$$1$$$ and pole $$$2$$$ which gives a steepness of $$$\left|\frac{1-1}{1-2}\right|=0$$$.
After the second replacement, the height of the poles become $$$1,3,4,5,2$$$ respectively. which is the same as the initial configuration of poles, so the maximum and minimum steepness are $$$3$$$ and $$$0.25$$$ respectively.
After the third replacement, the height of the poles become $$$1,3,4,5,6$$$ respectively. Then we can get the maximum steepness by choosing pole $$$1$$$ and pole $$$2$$$ which gives a steepness of $$$\left|\frac{1-3}{1-2}\right|=2$$$. We can get the minimum steepness by choosing pole $$$2$$$ and pole $$$3$$$ which gives a steepness of $$$\left|\frac{3-4}{2-3}\right|=1$$$.
You are thirsty, and the only thing you can drink is tea. Unfortunately, you hate tea because it is too bitter!
You initially have $$$t$$$ mL of tea and $$$w$$$ mL of fresh water. Because you are thirsty, you must drink exactly $$$s$$$ ($$$1 \le s \le t+w$$$) mL of tea. (You cannot drink fresh water.) You are also given an array $$$B_i$$$ ($$$1 \le i \le t+w$$$) denoting the bitterness you feel when you drink tea.
At any point in time, you can do one of two things:
- Drink tea. This increases your total bitterness by $$$B_t$$$, then decreases the amount of tea ($$$t$$$) by $$$1$$$ mL.
- Add fresh water. This decreases your amount of fresh water ($$$w$$$) by $$$1$$$ and increases the amount of tea ($$$t$$$) by $$$1$$$.
Find the minimum total bitterness you can have while drinking enough tea to not be thirsty.
Each test contains multiple test cases. The first line contains the number of test cases $$$n$$$ $$$(1 \leq n \leq 1000)$$$. The description of the test cases follows.
The first line of each test case contains three integers $$$t$$$, $$$w$$$, and $$$s$$$ $$$(1 \leq t + w \leq 2 \cdot 10^5, 1 \leq s \leq t+w)$$$.
The second line of input contains $$$t+w$$$ space-separated integers $$$B_1, B_2, ..., B_{t+w}$$$ $$$(1 \leq B_i \leq 10^3)$$$.
The sum of $$$t+w$$$ across all test cases is guaranteed to not exceed $$$2 \cdot 10^5$$$.
—
Tests in subtasks are numbered from $$$1$$$ — $$$20$$$ with samples skipped. Each subtask is worth $$$5$$$ points.
Tests $$$2$$$ — $$$3$$$ satisfy $$$t + w \leq 10$$$ for each test case.
Tests $$$4$$$ — $$$5$$$ satisfy $$$t + w \leq 200$$$ for each test case.
Tests $$$6$$$ — $$$8$$$ satisfy $$$t + w \leq 2 \cdot 10^3$$$ for each test case.
Tests $$$9$$$ — $$$20$$$ satisfy no additional constraints.
For each test case, output the minimum total bitterness you can have while drinking enough tea to not be thirsty.
65 0 51 2 3 4 55 5 31 2 3 4 5 6 7 8 9 105 5 310 9 8 7 6 5 4 3 2 11 5 61 100 100 100 100 1005 3 3100 100 100 100 100 100 100 15 3 3100 100 100 1 100 100 100 100
151266201102
In the first test case, you have no fresh water, so you must drink all of the tea and have a total bitterness of $$$5 + 4 + 3 + 2 + 1 = 15$$$.
In the second test case, it is optimal to not add any fresh water and only drink tea, for a total bitterness of $$$B_5 + B_4 + B_3 = 5 + 4 + 3 = 12$$$.
In the third test case, it is optimal to add all 5 mL of fresh water before drinking the tea, for a total bitterness of $$$B_{10} + B_9 + B_8 = 1 + 2 + 3 = 6$$$.
An optimal sequence of moves for the sixth test case is as follows:
- Drink tea, adding $$$B_5 = 100$$$ bitterness (total $$$100$$$) and reducing $$$t$$$ from 5 to 4
- Drink tea, adding $$$B_4 = 1$$$ bitterness (total $$$101$$$) and reducing $$$t$$$ from 4 to 3
- Add water, increasing $$$t$$$ from 3 to 4 and reducing $$$w$$$ from 3 to 2
- Drink tea, adding $$$B_4 = 1$$$ bitterness (total $$$102$$$) and reducing $$$t$$$ from 4 to 3
You are playing the game of checkers, there are $$$n$$$ enemies pieces on a 1D straight line, each time you have to jump over $$$k$$$ pieces of the enemy to eat the next $$$k+1$$$th piece. After that piece is eaten, you take it's place and that piece also vanishes. Given $$$T$$$ queries, each time given a separate $$$n$$$,$$$k$$$, and your piece's starting position, find the maximum number of pieces of the enemy that you can eat starting at the given starting position. The starting position is ordered such that the position is the number of enemy pieces to the left of your piece.
The first line contains one single integer $$$T$$$ ($$$1 \le T \le 10^5$$$).
On the next $$$T$$$ lines, each line contains three numbers $$$n$$$, $$$k$$$, $$$s$$$ ($$$1 \le n \le 10^{18}$$$, $$$0 \le k,s \le n$$$) - denoting the number of enemy pieces, jumping requirement, and the starting position in each of the queries.
—
Tests are numbered from $$$1-10$$$ and each test is worth $$$10$$$ points.
Tests $$$1-2$$$ satisfy $$$1 \le T \le 100, 1 \le n \le 500$$$.
Tests $$$3$$$ satisfy $$$k=1$$$.
Tests $$$4$$$ satisfy $$$k \lt =5$$$.
Tests $$$5$$$ satisfy $$$k \lt =10$$$.
Tests $$$6-10$$$ satisfy no additional constraints.
Output $$$k$$$ numbers, for each query what is the maximum number of pieces of the enemy that you can eat.
3 6 1 2 8 3 1 91 5 54
5 3 86
For the first testcase, the answer is 5 since a possible sequence to operate is:
xxuxxxx
uxnxxxx
nxnuxxx
nxnnxux
nunnxnx
nnnnxnu
Supposing that u is your piece, x is the enemy pieces, and n are blank spaces. In this scenario, it is provable that you can't eat all 6 pieces.
You are given a simple undirected graph with $$$n$$$ vertices numbered from $$$1$$$ to $$$n$$$ and $$$m$$$ weighted edges. The graph may be disconnected. The $$$i$$$-th edge joins vertices $$$u_i$$$ and $$$v_i$$$ and has weight $$$w_i$$$.
An increasing trip of length $$$k$$$ is an ordered sequence of $$$k+1$$$ vertices $$$(x_0,x_1,\ldots,x_k)$$$ such that:
- for every $$$0\le j \lt k$$$, vertices $$$x_j$$$ and $$$x_{j+1}$$$ are joined by an edge; and
- for every $$$0\le j \lt k-1$$$, the weight of the edge joining $$$x_j$$$ and $$$x_{j+1}$$$ is strictly smaller than the weight of the edge joining $$$x_{j+1}$$$ and $$$x_{j+2}$$$.
The same vertex may occur more than once in a trip. Two trips are considered different if their ordered vertex sequences are different. In particular, $$$(u,v)$$$ and $$$(v,u)$$$ are different trips.
Let $$$\ell$$$ be the maximum possible length of an increasing trip. Find $$$\ell$$$ and the number of increasing trips of length $$$\ell$$$, modulo $$$998244353$$$.
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2\le n\le 10^5$$$, $$$1\le m\le \min\left(\frac{n(n-1)}{2},2\cdot 10^5\right)$$$), the number of vertices and edges, respectively.
The $$$i$$$-th of the next $$$m$$$ lines contains three integers $$$u_i$$$, $$$v_i$$$, and $$$w_i$$$ ($$$1\le u_i \lt v_i\le n$$$, $$$1\le w_i\le 10^9$$$), describing an edge between vertices $$$u_i$$$ and $$$v_i$$$ with weight $$$w_i$$$.
It is guaranteed that $$$(u_i,v_i)\ne(u_j,v_j)$$$ for all distinct $$$i$$$ and $$$j$$$. Different edges may have equal weights.
—
Tests in subtasks are numbered from $$$1−20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.
Test $$$1$$$ satisfies $$$w_i=1$$$ for every $$$1\le i\le m$$$.
Tests $$$2$$$–$$$3$$$ satisfy $$$n\le 8$$$.
Tests $$$4$$$–$$$5$$$ satisfy $$$m=n-1$$$, $$$u_i=i$$$, and $$$v_i=i+1$$$ for every $$$1\le i\le m$$$.
Tests $$$6$$$–$$$7$$$ satisfy $$$m=n-1$$$, $$$u_i=1$$$, and $$$v_i=i+1$$$ for every $$$1\le i\le m$$$.
Tests $$$8$$$–$$$9$$$ satisfy $$$m=n-1$$$, $$$u_i\le i$$$, and $$$v_i=i+1$$$ for every $$$1\le i\le m$$$.
Tests $$$10$$$–$$$11$$$ satisfy $$$n\le 600$$$, and all edge weights are pairwise distinct.
Tests $$$12$$$–$$$14$$$ satisfy $$$n\le 600$$$.
Tests $$$15$$$–$$$17$$$ satisfy that all edge weights are pairwise distinct.
Tests $$$18$$$–$$$20$$$ have no additional constraints. "'
Output two integers $$$\ell$$$ and $$$c$$$, where $$$\ell$$$ is the length of the longest increasing trip and $$$c$$$ is the number of increasing trips of length $$$\ell$$$, modulo $$$998244353$$$.
4 51 2 12 3 13 4 11 4 12 4 2
2 4
6 61 2 31 3 72 3 54 5 95 6 84 6 2
3 2
In the first sample, the maximum length is $$$2$$$. The four longest increasing trips are $$$(1,2,4)$$$, $$$(1,4,2)$$$, $$$(3,2,4)$$$, and $$$(3,4,2)$$$. Each has edge-weight sequence $$$(1,2)$$$.
In the second sample, the maximum length is $$$3$$$. The two longest increasing trips are $$$(1,2,3,1)$$$ and $$$(4,6,5,4)$$$, with edge-weight sequences $$$(3,5,7)$$$ and $$$(2,8,9)$$$, respectively.
Please note the unusual memory limit for this problem.
You are given a pair of positive integers $$$A$$$ and $$$B$$$. Simplify $$$\frac{A}{B}$$$; find the unique pair of positive integers $$$a$$$ and $$$b$$$ such that $$$\frac{A}{B} = \frac{a}{b}$$$ and $$$\text{gcd}(a, b) = 1$$$.
The input contains two positive integers $$$A$$$ and $$$B$$$, separated by " / ".
—
Tests in subtasks are numbered from $$$1−20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.
Test $$$1$$$ satisfies $$$a, b \leq 10^3$$$, $$$A, B \leq 10^6$$$.
Test $$$2$$$ satisfies $$$a, b \leq 10^6$$$, $$$A, B \leq 10^{18}$$$.
Tests $$$3-5$$$ satisfy $$$a, b \leq 10^6$$$, $$$A, B \leq 10^{10^3}$$$.
Tests $$$6-7$$$ satisfy $$$a, b \leq 2$$$, $$$A, B \leq 10^{10^7}$$$.
Tests $$$8-12$$$ satisfy $$$a, b \leq 10^3$$$, $$$A, B \leq 10^{10^7}$$$.
Tests $$$13-20$$$ satisfy $$$a, b \leq 10^6$$$, $$$A, B \leq 10^{10^7}$$$.
Output two positive integers, $$$a$$$ and $$$b$$$, separated by " / ".
56 / 80
7 / 10
2358544209746913906612418916796916 / 5683441466720575133896324432207124
3229 / 7781
There are $$$n$$$ players, and these players all participate in a round-robin tournament (that is, each player plays every other player). The $$$i$$$th player has both a magic stat, $$$m_i$$$, and a strength stat, $$$s_i$$$.
For each $$$1 \le i \lt j \le n$$$, the $$$i$$$th and $$$j$$$th players will fight each other. The $$$i$$$th player's advantage over the $$$j$$$th player would be calculated as $$$\max(m_i - m_j, s_i - s_j)$$$. Conversely, the $$$j$$$th player's advantage over the $$$i$$$th player would be $$$\max(m_j - m_i, s_j - s_i)$$$. The winner is the player who has the greatest advantage.
The winning player gets a number of points equal to their advantage over their opponent. If both players have an identical advantage, they tie. Tying players get nothing.
Find the sum of all point totals across the whole tournament.
Each test contains multiple test cases. The first line contains the number of test cases, $$$t$$$ $$$(1 \le t \le 10^4)$$$. The description of the test cases follows.
For each test case: the first line contains a single integer $$$n$$$ $$$(2 \le n \le 10^5)$$$. The next $$$n$$$ lines contain 2 integers, $$$m_i$$$ and $$$s_i$$$ $$$(1 \le m_i, s_i \le 10^9)$$$.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5 \cdot 10^5$$$.
—
Tests in subtasks are numbered from $$$1−20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.
Tests $$$1-2$$$ satisfy $$$n \le 5000$$$.
Test $$$3$$$ satisfies $$$s_i = 1$$$.
Test $$$4$$$ satisfies $$$s_i \le 10$$$
Tests $$$5-20$$$ satisfy no additional constraints.
For each test case, output a single integer — the sum of the point totals of every player after the tournament has concluded.
233 74 47 355 38 49 16 412 2
633
In the first test case, when the 1st player battles the 2nd player, the 1st player wins and gains 3 points. When the 2nd player battles the 3rd player, the 3rd player wins and gains 3 points. When the 1st player battles the 3rd player, they both have the same advantage (3) so they tie. In total the players earned 3 + 3 = 6 points.
Joshi is trying to add numbers in non-traditional base systems. However, he is terrible at arithmetic, so he can only compute $$$x+y$$$ in base $$$p$$$ if no carries are required. Formally, if $$$x = \sum a_i k^i$$$ and $$$y = \sum b_i p^i$$$ for integer sequences $$$a$$$ and $$$b$$$ satisfying $$$0 \leq a_i, b_i \lt p$$$ for all $$$i$$$, then Joshi can compute $$$x+y$$$ if and only if $$$a_i + b_i \lt p$$$ for all $$$i$$$. For example, joshi can compute 67+33 in base 8, but not in base 10. You are given 4 integers: $$$p, a, b,$$$ and $$$k$$$. Compute the number of ordered pairs $$$(x, y)$$$ such that $$$0 \leq x, y \lt p^k$$$ and Joshi can compute $$$x+y$$$ in both base $$$p^a$$$ and base $$$p^b$$$. Give your answer modulo $$$10^9+7$$$.
Each test contains multiple test cases. The first line contains the number of test cases, $$$t$$$ $$$(1 \leq t \lt 10^5)$$$. The description of the test cases follows Every testcase contains 4 integers: $$$p, a, b,$$$ and $$$k$$$ ($$$1 \lt p \lt 10^9$$$, $$$1 \leq a \leq b \lt 10^5, 0 \lt = k \lt 10^{18}$$$) It is guaranteed that the sum of $$$a+b$$$ across all testcases doesn't exceed $$$2 \cdot 10^5$$$
—
Tests are numbered from $$$1-20$$$ and each test is worth $$$5$$$ points.
Tests $$$1-3$$$ satisfy $$$r \lt 2 \cdot 10^5$$$.
Tests $$$4-7$$$ satisfy $$$a = b$$$.
Tests $$$8-20$$$ satisfy no additional constraints.
Print the number of ordered pairs $$$(x, y)$$$ such that $$$0 \leq x, y \lt p^r$$$ and $$$(x, y)$$$ is both $$$p^a$$$ good and $$$p^b$$$ good, given modulo $$$10^9+7$$$
72 2 3 02 2 3 12 2 3 22 2 3 35 2 2 43 3 4 97 11 13 1000
14103010562527556200467115580
You are given an $$$n \times n$$$ grid, initially all white. You will repeatedly color cells black or white. After each update, output whether the black cells are vertically symmetric. That is, you can draw a vertical line which reflects all the black cells onto each other. Formally, a grid is vertically symmetric if there exists some $$$k$$$ such that for every $$$1 \le r, c \le n$$$, the cell on row $$$r$$$ and column $$$c$$$ is black if and only if the cell on row $$$r$$$ and column $$$k - c$$$$$$^{\text{∗}}$$$ is black.
$$$^{\text{∗}}$$$cells with $$$k - c \lt 1$$$ and $$$k - c \gt n$$$ are considered white cells for the purposes of this check.
Each test contains multiple test cases. The first line contains the number of test cases, $$$t$$$ $$$(1 \le t \le 10^4)$$$. The description of the test cases follows.
For each test case: the first line contains 2 integers, $$$n$$$ $$$(1 \le n \le 10000)$$$, the size of the grid, and $$$q$$$ $$$(1 \le q \le 10^6)$$$, the number of queries. The next $$$q$$$ lines will contain 2 integers, $$$r_i$$$ and $$$c_i$$$ $$$(1 \le r_i, c_i \le n)$$$, indicating the row and column of the cell whose color should be flipped. If the cell was white, then it will be turned black, and if it was black, it will be turned white.
It is guaranteed that the sum of $$$q$$$ over all test cases does not exceed $$$10^6$$$.
—
Tests in subtasks are numbered from $$$1−20$$$ with samples skipped. Each test is worth $$$5$$$ points.
Test $$$1-2$$$ satisfies $$$n \le 100$$$.
Tests $$$3-6$$$ guarantee that all queries will turn cells from white to black. That is, there are no cells which are affected more than once by any queries in a test case.
Tests $$$7-20$$$ satisfy no additional constraints.
After each query, output '"YES"' (without quotes) if the black cells are vertically symmetric, and '"NO"' (without quotes) otherwise.
You can output '"YES"' and '"NO"' in any case (for example, strings '"yES"', '"yes"' and '"Yes"' will be recognized as a positive response).
24 41 22 12 32 45 81 11 21 31 41 31 22 11 4
YESNOYESNOYESYESYESYESNOYESNOYES
At the TEA Manufacturing Sector Composed Of Developers & Engineers, we specialize in brewing high-quality tea. Today, famous tea critic John Tea has come to try our tea. However, from past experience, we know our tea is far too strong for most customers, including John Tea.
Thus, we must dilute the tea with water. For a regular customer, we could give them some water and have them pour the water into the tea until they like it, but John Tea has a very fine tea palate, and such inaccurate methods will not work.
The concentration of a tea + water solution is the ratio of the volume of tea to the total volume of the solution. We have measured John Tea's desired concentration to be $$$C \cdot 10^{-9}$$$, and he will only accept the tea if the concentration is within $$$10^{-9}$$$ of the desired concentration.
Unfortunately, our patent-pending state-of-the-art tea dilution machine has not been invented yet, so we'll have to dilute the tea the old-fashioned way. We have a small $$$A$$$-liter jug (Jug A), a large $$$B$$$-liter jug (Jug B), faucets dispensing water and tea, a drain, and a robot which can pour liquids and follow simple commands.
The following is a list of commands which we can give to the robot, and what they will do.
- FILL A W: Fill Jug A to the brim with water.
- FILL A T: Fill Jug A to the brim with tea.
- FILL B W: Fill Jug B to the brim with water.
- FILL B T: Fill Jug B to the brim with tea.
- POUR A B: Pour liquid from Jug A to Jug B until Jug A empties or Jug B becomes full.
- POUR B A: Pour liquid from Jug B to Jug A until Jug B empties or Jug A becomes full.
- DUMP A: Dump the contents of Jug A into the drain.
- DUMP B: Dump the contents of Jug B into the drain.
- SUBMIT A: Submit the contents of Jug A to John Tea. No more commands should follow.
- SUBMIT B: Submit the contents of Jug B to John Tea. No more commands should follow.
After each command, the jugs are stirred to ensure uniform concentration. In degenerate cases (such as when a jug is already full when a POUR command is given), nothing happens. You will receive a Wrong Answer verdict if you perform any commands after a SUBMIT command, submit an empty jug, submit tea with an unacceptable concentration, or fail to submit a jug.
Currently both jugs are empty, and the robot is awaiting your commands.
Construct a sequence of up to $$$10^5$$$ commands for the robot to submit acceptable tea to John Tea.
The input consists of $$$3$$$ space separated integers, $$$A$$$, $$$B$$$, $$$C$$$. $$$(1 \leq A \lt B \leq 1000)$$$, $$$(0 \leq C \leq 10^9)$$$. $$$A$$$ and $$$B$$$ are the capacities of the jugs in liters, and $$$C \cdot 10^{-9}$$$ is the desired concentration.
—
Tests in subtasks are numbered from $$$1−20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.
Test $$$1$$$ satisfies $$$C = 0$$$.
Test $$$2$$$ satisfies $$$C = 10^9$$$.
Tests $$$3-4$$$ satisfy $$$A = 1$$$, $$$B = 1000$$$, and $$$C$$$ is a multiple of $$$10^6$$$.
Tests $$$5-6$$$ satisfy $$$A = 1$$$ and $$$B = 2$$$.
Tests $$$7-8$$$ satisfy $$$A = 1$$$ and $$$B = 3$$$.
Tests $$$9-10$$$ satisfy $$$A = 2$$$ and $$$B = 3$$$.
Tests $$$11-14$$$ satisfy $$$A, B \leq 10$$$
Tests $$$15-20$$$ satisfy no additional constraints.
On the first line, output $$$K$$$, the number of commands. $$$(0 \leq K \leq 10^5)$$$
On the next $$$K$$$ lines, output a command.
1 2 500000000
5 FILL A T POUR A B FILL A W POUR A B SUBMIT B
1 3 111111111
9 FILL B W POUR B A FILL B T DUMP A POUR B A DUMP B POUR A B FILL B W SUBMIT B
—
We have created a tea pouring simulator™ in C++ to simulate the robot executing a list of commands.
It is available here: https://ide.usaco.guide/P-L2eGkO-X6DZQX8KeV.
The simulator reads from standard input. The standard input should contain the test input ($$$A$$$, $$$B$$$, and $$$C$$$), followed by the test output (your construction; $$$K$$$ and your list of $$$K$$$ commands). The simulator will output "Accepted" if your sequence of commands satisfies the problem constraints and submits acceptable tea to John Tea, and "Wrong Answer" otherwise.
Bessie is running through an obstacle course! There are $$$N$$$ platforms, initially at height $$$h_i$$$ ($$$h_i$$$ is even so they will cross at an integer time). Each platform moves either up or down one meter per second. To jump from a platform of height $$$x$$$ to a platform of height $$$y$$$, it takes Bessie $$$\lvert x-y \rvert$$$ energy and $$$0$$$ time. Bessie can also wait at any platform.
Bessie wants to move through the course with minimal energy. Find the minimum energy that must be expended for Bessie to complete the course (travel from the first platform to the last platform).
First line contains $$$N (N \leq 10^5)$$$.
Next $$$N$$$ lines contain $$$1$$$ integer and $$$1$$$ uppercase letter each line: $$$h_i (\lvert h_i \rvert \leq 10^9), h_i$$$ is always even and a letter c denoting whether the platform is moving up or down where U denotes up and D denotes down.
—
Tests in subtasks are numbered from $$$1-20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.
Tests $$$1-2$$$ satisfy that $$$N \leq 20$$$.
Tests $$$3-6$$$ satisfy that $$$N \leq 1000$$$.
Tests $$$7-8$$$ satisfy that all platforms move in the same direction.
Tests $$$9-20$$$ satisfy no additional constraints.
Output one line, the minimum energy to go through the course.
536 U14 D0 D16 U14 D
54
You are going to a stone skipping contest. The lake can be represented as a number line, with the shore being all negative integers, and the lake occupying all the nonnegative integers.
You may stand at any integer position on the shore and throw your stone with any integer power. If you throw with power $$$p$$$, the stone will move $$$p$$$ meters before bouncing. When the stone bounces, if it has power $$$p$$$, it will bounce again with power $$$\lfloor p/2 \rfloor$$$, and if the stone has power $$$0$$$, it will sink. Contest regulations state the stone must sink at position $$$N$$$ $$$(1 \le N \le 10^{18})$$$, and the score of the throw is the sum of $$$a_x$$$ for each position $$$x$$$ the stone bounces, for an zero-index array $$$a$$$ of length $$$N$$$.
The array $$$a$$$ initially begins at all $$$0$$$s, but there are $$$Q$$$ $$$(1 \le Q \le 10^5)$$$ modifications which change $$$a_x = y$$$ where $$$0 \le x \lt N$$$ and $$$0 \le y \le 10^{15}$$$. Compute the maximum score after each modification.
The first line contains two positive integers: $$$N$$$ $$$(1 \le N \le 10^{18})$$$, the final sink position, and $$$Q$$$ $$$(1 \le Q \le 10^5)$$$, the number of modifications.
The next $$$Q$$$ lines contain two integers each: $$$x$$$ $$$(0 \le x \lt N)$$$, the position of the change, and $$$y$$$ $$$(0 \le y \le 10^{15})$$$, the modified value.
—
Tests in subtasks are numbered from $$$1−20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.
Tests $$$1-2$$$ satisfy $$$N \leq 1000$$$, $$$Q \leq 1000$$$.
Tests $$$3-5$$$ satisfy $$$N \leq 10^6$$$, $$$Q \leq 2000$$$.
Tests $$$6-9$$$ satisfy $$$Q \leq 2000$$$.
Tests $$$10-20$$$ satisfy no additional constraints.
Output $$$Q$$$ integers—the maximum score after each modification.
10 69 36 55 1000 47 66 0
3 8 8 12 12 9
Problem Idea: achen
Problem Preparation: TheRowletOwlet
Occurrences: Advanced E
You are given a tree with $$$n$$$ nodes, where each node has a strength of $$$a_i$$$.
You are asked to perform $$$q$$$ surgeries on the tree. Each surgery has an intensity of $$$k$$$. A surgery can be successfully performed if and only if it is possible to remove a (possibly empty) set of edges from the tree such that the strength of every resulting connected component is exactly $$$k$$$.
The strength of a connected component is defined as the sum of the strengths of all nodes within it.
For each of the $$$q$$$ surgeries, determine whether it can be performed. Note that the queries are independent; the tree is completely restored to its original state after evaluating each query.
The first line contains one integer, $$$n \text{ } (1 \leq n \leq 10^6)$$$ — the number of nodes in the tree.
The next line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n \text{ }(0 \leq a_i \leq 10^{12})$$$ — the strength of each node on the tree.
Each of the next $$$n - 1$$$ lines contains two integers, $$$u \text{ } (1 \leq u \leq n)$$$ and $$$v \text{ }(1 \leq v \leq n)$$$, representing an edge connecting node $$$u$$$ and node $$$v$$$.
The next line contains one integer, $$$q \text{ } (1 \leq q \leq 10^6)$$$ — the number of surgeries you need to perform.
Each of the next $$$q$$$ lines contains one integer, $$$k \text{ } (0 \leq k \leq 10^{18})$$$ — the intensity of the surgery.
—
Tests $$$1$$$ — $$$4$$$ satisfy $$$n, q \leq 2000$$$.
Tests $$$5$$$ — $$$10$$$ satisfy $$$a_i \geq 1$$$.
Tests $$$11$$$ — $$$20$$$ satisfy no additional constraints.
For each surgery, output YES if it can be performed, and NO otherwise.
32 0 01 21 311
NO
80 4 2 2 4 0 4 41 21 33 41 51 66 76 8641052028
YES NO NO YES NO NO
For the first sample, the total strength of the tree is $$$2$$$.
- $$$k = 1$$$ (NO): It is impossible to cut the tree into any components of strength $$$1$$$.
For the second sample, the total strength of the tree is $$$20$$$.
- $$$k = 4$$$ (YES): Remove edges $$$(1,3)$$$, $$$(1,5)$$$, $$$(1,6)$$$, and $$$(6,8)$$$. The resulting components are $$$\{1, 2\}$$$, $$$\{3, 4\}$$$, $$$\{5\}$$$, $$$\{6, 7\}$$$, and $$$\{8\}$$$, each summing to exactly $$$4$$$. Note that $$$0$$$-weight nodes (like $$$1$$$ and $$$6$$$) must merge with other nodes.
- $$$k = 10$$$ (NO): $$$10$$$ divides $$$20$$$, but it is structurally impossible to cut the tree into components of exactly $$$10$$$.
- $$$k = 20$$$ (YES): Remove $$$0$$$ edges. The entire tree already sums to $$$20$$$.
- $$$k \in \{2, 5, 8\}$$$ (NO): $$$8$$$ does not divide $$$20$$$. For $$$2$$$ and $$$5$$$, it is impossible to split individual nodes that already have a strength of $$$4$$$.
Ruby and Aqua are playing Mario! Unfortunately, Aqua has fallen into one of the pipes. Since Aqua is a liquid, he is now flowing through it. As Ruby and Aqua's personal plumber, you have to rescue him!
The pipe is the infinite vertical strip between the lines $$$x=0$$$ and $$$x=W$$$. It is open at the top and bottom, and water flows from top to bottom.
Ruby installs $$$Q$$$ filters, one after another. Installation $$$i$$$ is described by four integers $$$a_i$$$, $$$b_i$$$, $$$c_i$$$, and $$$d_i$$$.
- If $$$d_i=0$$$, Ruby starts at $$$(0,a_i)$$$ and draws toward $$$(W,b_i)$$$.
- If $$$d_i=1$$$, Ruby starts at $$$(W,a_i)$$$ and draws toward $$$(0,b_i)$$$.
Ruby stops drawing as soon as the new filter reaches the opposite wall or first touches a previously installed filter.
Filters have zero thickness, but a contact forms a sealed junction: water cannot slip between two filters at their common point. A portion of filter $$$i$$$ whose horizontal projection has length $$$\Delta x$$$ lets at most $$$c_i\Delta x$$$ units of water pass. Notice that $$$\Delta x$$$ is horizontal length in the $$$x$$$-direction, not Euclidean length.
More formally, after all installations, split every filter at all contact points. The filters divide the pipe into chambers. Water can move freely inside a chamber, but for a filter of horizontal length $$$\Delta x$$$, only $$$c_i \Delta x$$$ water can pass through the filter.
Find the maximum amount of water that can flow through the pipe per unit of time.
The first line contains an integer $$$T$$$ ($$$1 \le T \le 10$$$) — the number of test cases.
The description of each test case begins with two integers $$$W$$$ and $$$Q$$$ ($$$1 \le W \le 10^9$$$, $$$1 \le Q \le 10^5$$$) — the width of the pipe and the number of installations.
Each of the next $$$Q$$$ lines contains four integers $$$a_i$$$, $$$b_i$$$, $$$c_i$$$, and $$$d_i$$$ ($$$-10^9 \le a_i,b_i \le 10^9$$$, $$$1 \le c_i \le 10^9$$$, $$$d_i\in\{0,1\}$$$), describing one installation.
It is guaranteed that the sum of $$$Q$$$ over all test cases does not exceed $$$10^5$$$.
For the following guarantees, define the intended left and right heights $$$(L_i,R_i)$$$ by $$$$$$ (L_i,R_i)= \begin{cases} (a_i,b_i), & d_i=0,\\ (b_i,a_i), & d_i=1. \end{cases} $$$$$$
Within each test case, the values $$$L_1,\ldots,L_Q$$$ are pairwise distinct, and the values $$$R_1,\ldots,R_Q$$$ are pairwise distinct. Furthermore, no three lines through $$$(0,L_i)$$$ and $$$(W,R_i)$$$ pass through one common point strictly inside the pipe. Consequently, every new filter either reaches the opposite wall or touches the interior of exactly one existing filter piece.
—
Tests in subtasks are numbered from $$$1 - 20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.
Tests $$$1-2$$$ satisfy that the sum of $$$Q$$$ over all test cases is at most $$$200$$$.
Tests $$$3-4$$$ satisfy that the sum of $$$Q$$$ over all test cases is at most $$$5000$$$.
Tests $$$5-10$$$ satisfy $$$d_i=0$$$ for every installation in every test case.
Tests $$$11-20$$$ satisfy no additional constraints.
For each test case, print one real number — the maximum amount of water that can flow through the pipe per unit of time.
Your answer is accepted if its absolute or relative error does not exceed $$$10^{-6}$$$.
110 20 0 3 01 -2 1 0
23.333333333333333
110 30 0 5 010 -10 1 015 -5 2 1
16.250000000000000
Filter $$$2$$$ reaches filter $$$1$$$ at $$$x=10/3$$$, so its dashed continuation is not installed.
$$$20$$$ units of water can cross the right part of filter $$$1$$$, while another $$$10/3$$$ units can pass through filter $$$2$$$ and then filter $$$1$$$. The answer is $$$20+10/3=70/3$$$.