shiny_shine's blog

A rough sketch of my solution for A-E of CF Edu Round 168
By shiny_shine, 4 months ago, In English

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.

  • Vote: I like it
  • +17
  • Vote: I do not like it

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It results in TLE .

    → Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Instead of merge-sort-tree you can use persistent segment tree, but it will TLE as well.

    → Reply
  • »
    »
    4 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      → Reply
      • »
        »
        »
        »
        4 months ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Here is the submission: 273585156

        I don't know anything about persistent segment trees sorry. The constant factor might be making a difference.

        → Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    lol, i thought exactly the same thing, but i knew it will tle

    → Reply
»
4 months ago, # |
  Vote: I like it -14 Vote: I do not like it

thnx . if possible please make such blog for every contest . it helps to understand the mindset of problem solving

→ Reply
»
4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

thank you!

→ Reply
»
4 months ago, # |
  Vote: I like it +6 Vote: I do not like it

I approached D using Binary search & dfs.

→ Reply