Everule's blog

By Everule, history, 3 weeks ago, In English,

I'm trying to solve atcoder ABC167F. https://atcoder.jp/contests/abc167/tasks/abc167_f .

I started by questioning what conditions decide whether a concatenation is valid. We start by defining sum of a bracketed sequence, which is count('(')-count(')'). I then found the sum of every string, and the smallest sum of a prefix of the string. They are denoted by $$$sum$$$ and $$$mnprefix$$$ in my code. If my current string is valid which is equivalent to $$$mnprefix\ge 0$$$ and has a sum of $$$x$$$, then a concatenation is valid if and only if $$$x+mnprefix\ge 0$$$ and our new sequnce has a sum of $$$x+sum$$$. Let's say we have two strings $$$a$$$ and $$$b$$$. Let $$$a.sum$$$ denote the sum of $$$a$$$ and the rest of the notation is deductible.

Let's say $$$a$$$ comes before $$$b$$$. Then the two conditions that need to be valid are $$$x\ge a.mnprefix$$$ and $$$x\ge b.mnprefix-a.sum$$$. So we want $$$\max(a.mnprefix, b.mnprefix-a.sum)\le \max(b.mnprefix, a.mnprefix - b.sum)$$$ for $$$a$$$ to be chosen before $$$b$$$. However my proof has one flaw, which is that it doesn't account for transitivity. I don't know how to prove another string $$$c$$$ will not affect my result, and how do I know my comparator function is transitive, as each string doesn't have an exact value, and the comparator values are differing according to the string being compared to.

If my solution is correct, can someone tell me if I have made an error in my implementation.

My code

Edit : nvm, I was using abs(mnprefix) in my calculation but not in my code.

Read more »

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

By Everule, 2 months ago, In English,

https://atcoder.jp/contests/abc160/tasks/abc160_f //Question link

https://atcoder.jp/contests/abc160/submissions/11324766 //My TLE submission

I need help in understanding how to reroot the tree in O(n) I think I have understood how to reroot the tree but I cannot understand how to do it for every node. For example

dp.resize(n,mp(-1,0)); //dp[u]=(the actual answer, size of subtree) 

The following code seems to correctly calculate the answer for the root node and it's first edge. But how do I reroot the tree in such a way that it goes to all edges and calculates the answer in O(n)?

Read more »

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