DIV2A-DZY Loves Chessboard
Just output the chessboard like this:
WBWBWBWB...
BWBWBWBW...
WBWBWBWB...
...
Don't forget to left '-' as it is. The time complexity is O(nm).
check the C++ code here.
DIV2B-DZY Loves Chemistry
It's easy to find that answer is equal to
Unable to parse markup [type=CF_TEX]
, where v is the number of connected components.check the C++ code here.
DIV1A-DZY Loves Physics
If there is a connected induced subgraph containing more than 2 nodes with the maximum density. The density of every connected induced subgraph of it that contains only one edge can be represented as
Unable to parse markup [type=CF_TEX]
, whereUnable to parse markup [type=CF_TEX]
are the values of the two nodes linked by the edge. The density of the bigger connected induced subgraph is at mostUnable to parse markup [type=CF_TEX]
.If
Unable to parse markup [type=CF_TEX]
, and for every edge,Unable to parse markup [type=CF_TEX]
. Then we'll haveUnable to parse markup [type=CF_TEX]
, andUnable to parse markup [type=CF_TEX]
, andUnable to parse markup [type=CF_TEX]
, it leads to contradiction.So just check every single node, and every 2 nodes linked by an edge.
The time complexity is O(n + m).
check the C++ code here.
DIV1B-DZY Loves FFT
Firstly, you should notice that A, B are given randomly.
Then there're many ways to solve this problem, I just introduce one of them.
This algorithm can get
Unable to parse markup [type=CF_TEX]
one by one. Firstly, choose an s. Then check ifUnable to parse markup [type=CF_TEX]
equals toUnable to parse markup [type=CF_TEX]
. If none of is the answer, just calculateUnable to parse markup [type=CF_TEX]
by brute force.The excepted time complexity to calculate
Unable to parse markup [type=CF_TEX]
is aroundUnable to parse markup [type=CF_TEX]
where
Unable to parse markup [type=CF_TEX]
.Just choose an s to make the formula as small as possible. The worst excepted number of operations is around tens of million.
check the C++ code here.
DIV1C-DZY Loves Colors
The only thing you need to notice is that if there are many continuous units with the same uppermost color, just merge them in one big unit. Every time painting continuous units, such big units will only increase by at most 3. Then you can use STL set to solve it. But anyway, a segment tree is useful enough, check the C++ solution here.
The time complexity is 
.
DIV1D-DZY Loves Strings
We can solve a subproblem in which all the query strings are characters only first. The problem becomes calculating the shortest substring containing two given characters.
If character ch appears more than T times in S, use brute force with time complexity
Unable to parse markup [type=CF_TEX]
to calculate all the queries containing ch. Obviously, there are at mostUnable to parse markup [type=CF_TEX]
such ch in S.Otherwise, we consider two sorted sequences, just merge them with time complexity O(T)(Both of the two characters appear at most T times). Being merging, you can get the answer.
So the complexity is
Unable to parse markup [type=CF_TEX]
. We can chooseUnable to parse markup [type=CF_TEX]
, then the complexity isUnable to parse markup [type=CF_TEX]
.And short substring is almost the same with characters.
Check the C++ code here.
DIV1E-DZY Loves Planting
Firstly, use binary search. We need to determine whether the answer can be bigger than L. Then, every pair
Unable to parse markup [type=CF_TEX]
must contain at least one edge which length is bigger than L. It's a problem like bipartite graph matching, and we can use maxflow algorithm to solve it.We create 2 nodes for every node i of the original tree. We call one of the nodes
Unable to parse markup [type=CF_TEX]
, and the otherUnable to parse markup [type=CF_TEX]
. And we need a source s and a terminal t. Link s to everyUnable to parse markup [type=CF_TEX]
with upper bound 1, and linkUnable to parse markup [type=CF_TEX]
to t with upper bound xi. Then if the path between node a and node b contains an edge with value larger than L, linkUnable to parse markup [type=CF_TEX]
andUnable to parse markup [type=CF_TEX]
with upper bound 1. This means they can match. Every time we build such graph, we must check O(N2) pairs of nodes, so number of edges of the network is O(N2).We can make it better. Consider the process of \texttt{Divide and Conquer} of a tree, This algorithm can either based on node or edge. And The one based on edge is simpler in this problem. Now, there are two subtrees
Unable to parse markup [type=CF_TEX]
,Unable to parse markup [type=CF_TEX]
on two sides, we record the maximum edge from every node i to the current edge we split, we call itUnable to parse markup [type=CF_TEX]
.Suppose
Unable to parse markup [type=CF_TEX]
is inUnable to parse markup [type=CF_TEX]
andUnable to parse markup [type=CF_TEX]
is inUnable to parse markup [type=CF_TEX]
(it is almost the same in contrast). We create two new nodesUnable to parse markup [type=CF_TEX]
,Unable to parse markup [type=CF_TEX]
in the network to represent the two subtrees. Add edgesUnable to parse markup [type=CF_TEX]
(i is inUnable to parse markup [type=CF_TEX]
) and edgesUnable to parse markup [type=CF_TEX]
(i is inUnable to parse markup [type=CF_TEX]
). If i is inUnable to parse markup [type=CF_TEX]
andUnable to parse markup [type=CF_TEX]
, we add an edgeUnable to parse markup [type=CF_TEX]
. If j is inUnable to parse markup [type=CF_TEX]
andUnable to parse markup [type=CF_TEX]
, we add an edgeUnable to parse markup [type=CF_TEX]
.Then use maxflow algorithm. The number of nodes in the network is O(N) and the number of edges in the network is
Unable to parse markup [type=CF_TEX]
. So the total complexity isUnable to parse markup [type=CF_TEX]
with really small constant.Check the C++ code here.
This is what I supposed DIV1-E will be. And thank subscriber for coming up with a really good algorithm with time complexity
Unable to parse markup [type=CF_TEX]
7025382. And maybe others have the same idea. This is my mistake, and I feel sorry for not noticing that, I'm too naive, and not good at solving problems. Please forgive me.
