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

#	User	Rating
1	tourist	3947
2	ecnerwala	3654
3	jiangly	3627
4	jqdai0815	3620
5	orzdevinwang	3612
6	Benq	3586
7	Radewoosh	3582
8	Geothermal	3569
8	cnnfls_csy	3569
10	ksun48	3474

#	User	Contrib.
1	awoo	162
2	maomao90	160
3	adamant	156
4	maroonrk	153
4	atcoder_official	153
6	-is-this-fft-	148
6	SecondThread	148
8	Petr	147
9	nor	145
10	cry	144

0. Preface

It's midnight in China now, and I'm going to sleep. Detailed solution might be posted several hours later.

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

4 hours 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

4 hours 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?