A rough sketch of my solution for A-E of CF Edu Round 168

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

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

$$$ p_i=\sum_{i=1}^n [s'_i=\text{'('}]-\sum_{i=1}^n [s'_i=\text{')'}]\\ r_n=0\\ r_i=\max(r_{i+1}-(-1)^{[s_{i+1}=\text{')'}]},0) $$$

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.

Comments (11)

Write comment?

123gjweq2

5 months ago, # |

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?

→ Reply

qwertylkjhg

5 months ago, # ^ |

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.

blaze

← Rev. 2 →

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?