UPD: The full version is here.
1. Strong Password
It's obvious that the best insertion method is to find two same adjacent characters and add a difference to it, and that increases the time by $$$3$$$.
If there isn't a pair like that, we can simply add a character different to the back of the string, to increase the time by $$$2$$$.
2. Make Three Regions
Since there is at most $$$1$$$ connected component in the input graph, and there are only $$$2$$$ rows, so a legal construction only acts like this:
.0.
x.x
or you can flip it by the x-axis.
3. Even Positions
Define $$$n$$$ is size of $$$s$$$, $$$s'$$$ is $$$s$$$ after restoration, and
Then, for all integers $$$i$$$ in range $$$[1,n]$$$, $$$p_i$$$ shouldn't less than $$$r_i$$$.
So, just greedily construct $$$s'$$$ by checking each $$$r_i$$$ in time.
4. Maximize the root
The overall strategy is able to be called "maximize the minimum". Apply depth-first search on the tree, and when you finish all "maximize the minimum" for vertex $$$x$$$'s childs, if $$$a_x$$$ is lower than all $$$a_i$$$ where $$$i$$$ is in $$$x$$$'s subtree and $$$x\neq i$$$, then set $$$a_x$$$ to the floor average of $$$a_x$$$ and $$$\min(a_i)$$$. Otherwise, don't perform operations.
Answer is $$$a_1+\min_{i=2}^n a_i$$$.
5. Level Up
Observed that for each $$$i$$$, there exists a constant $$$c_i$$$ that $$$i$$$-th monster always fight with Monocarp when $$$k\ge c_i$$$.
Apply binary search with a BIT to find $$$c_i$$$, which has a time complexity of $$$O(n\log^2 (2\times 10^5))$$$, then we can answer each query in constant time.
For E: there's a type of segment tree that stores the sorted array segment in its nodes and you can use it to find elements $$$ \le x$$$ in $$$O(\log^2(n))$$$ time. I was thinking of using that type of segment tree along with iterating through possible $$$k$$$ values and binary searching to find when the $$$k$$$ values change. This would make for a time complexity of $$$O(n \cdot \log^4(n))$$$. Did anyone try this idea, and did it TLE?
It results in TLE .
whew, thank God I didn't implement that.
Instead of merge-sort-tree you can use persistent segment tree, but it will TLE as well.
I solved it exactly that way but you can kick out the binary search by "walking" on the segment tree for $$$O(n \cdot log^3_2{n})$$$. By the way a segment tree that stores the sorted interval in each node is called merge sort tree.
I see, thanks. I'm assuming it didn't TLE, right?
Do you know the time complexity of a persistent segment tree? Would that also be an $$$O(n \cdot \log^3(n))$$$ solution? If so, do you know why one TLE's and the other passes?
Here is the submission: 273585156
I don't know anything about persistent segment trees sorry. The constant factor might be making a difference.
lol, i thought exactly the same thing, but i knew it will tle
thnx . if possible please make such blog for every contest . it helps to understand the mindset of problem solving
thank you!
I approached D using Binary search & dfs.