### awoo's blog

By awoo, history, 5 days ago, translation,

Idea: BledDest

Tutorial
Solution (BledDest)

1997B - Make Three Regions

Idea: BledDest

Tutorial
Solution (Neon)

1997C - Even Positions

Idea: BledDest

Tutorial

1997D - Maximize the Root

Idea: BledDest

Tutorial
Solution (Neon)

1997E - Level Up

Idea: BledDest

Tutorial
Solution 1 (awoo)
Solution 2 (awoo)

1997F - Chips on a Line

Idea: BledDest

Tutorial
Solution (BledDest)
• +83

 » 5 days ago, # |   +55 Problem D can be solved in $O(n)$ with just a basic DFS. The idea is to maximize the minimum in each subtree. Submission: 273547075
•  » » 5 days ago, # ^ |   0 .ComplaintFrame { display: inline-block; position: absolute; top: 0; right: -1.4em; } .ComplaintFrame a { text-decoration: none; color: #ff8c00; opacity: 0.5; } .ComplaintFrame a:hover { opacity: 1; } ._ComplaintFrame_popup p, ._ComplaintFrame_popup button { margin-top: 1rem; } ._ComplaintFrame_popup input[type=submit] { padding: 0.25rem 2rem; } ._ComplaintFrame_popup ul { margin-top: 1em !important; margin-bottom: 1em !important; } just what i do.
•  » » 4 days ago, # ^ | ← Rev. 2 →   0 Thanks for the great solution. Can you please explain, when node==0 , why we are not using this part? Partif (node != 0) { ll val = dp[node] - a[node]; if (val > 0) { dp[node] = a[node] + val/2LL; } } 
•  » » » 4 days ago, # ^ |   0 You only care about the final value in the node 0(1). So you maximize the minimum in node 0's subtree(excluding node 0) and then use the operation as much as the minimum allows.
•  » » » » 4 days ago, # ^ |   0 Thanks, Can you provide the intuition for your algo and how and why it works, I was on almost the same path for a few minutes in the contest but didn't connect much. Can you please explain>
•  » » » » » 4 days ago, # ^ | ← Rev. 2 →   +3 This was my thought process. I want to use the operation on node 1 as many times as possible. The number of times I will be able to do it is equal to the minimum value in the subtree(excluding node 1) of node 1. Now to extend the logic, the maximum number of times I will be able to do it is equal to the minimum value in subtrees of node 1's children. This logic naturally looks like dynamic programming.DP transitions: if the value of the current node is greater than the value of $dp[node]$, we don't change anything, otherwise we use the operation while $a[node] < dp[node]$, in math words $dp[node] = \lfloor\frac{a[node] + dp[node]} {2} \rfloor$.
•  » » » » » » 4 days ago, # ^ |   0 Thank you so much, mate.
•  » » » » » » 4 days ago, # ^ |   0 Thank you for your solution, I have difficulty understanding (a[node] + dp[node]) / 2 part.Is this because we try to evenly distribute values between a node and it's parent? So that we can ensure root node can get maximum value?
•  » » » » » » » 4 days ago, # ^ | ← Rev. 3 →   +1 Yeah, it is just a faster way of doing: while(a[node] < dp[node]) { a[node]++, dp[node]--; } since if you don't do anything, the value in the current node will become the minimum. $\lfloor \frac{a[node] + dp[node]}{2} \rfloor > a[node]$
•  » » » » » » 4 days ago, # ^ |   0 Can you please explain the dp state that you defined ??
•  » » » » » » » 4 days ago, # ^ |   0 $dp[node]$ means the minumum value in the subtree of $node$.
•  » » 4 days ago, # ^ |   +7 I created video editorial for D: Maximize the Root.
•  » » 4 days ago, # ^ |   0 Same solution without using additional dp array: https://mirror.codeforces.com/contest/1997/submission/273543097
•  » » 4 days ago, # ^ | ← Rev. 2 →   0 can u explain the format of input in d?i didnt get who is the parent,please explain by taking 1st test case,who is whose parents..
•  » » » 4 days ago, # ^ | ← Rev. 2 →   0 Input: 4 0 1 0 2 1 1 3Tree:Note: The given array is $p_2, p_3, p_4, ..., p_n$, in this case the array is $1, 1, 3$, that means that node 2's parent is node 1, node 3's parent is 1 and node 4's parent is node 3.
•  » » » » 4 days ago, # ^ |   0 oo got it,thanks
•  » » 4 days ago, # ^ | ← Rev. 2 →   0 Can anyone tell me what is wrong with this solution i got a overflow error even though everything is in long long 273894619
•  » » » 4 days ago, # ^ | ← Rev. 2 →   0 got it just put lazy < 2e9 then flag = 0 or else the lazy will propogate to high values 273916460
•  » » 4 days ago, # ^ |   0 You are correct. But you don't even need the memoization. A single pass down the tree suffices. Here's a slightly cleaned up version of my contest solution: 273914043
•  » » 4 days ago, # ^ |   0 Checkout my clean solution 273559093
 » 5 days ago, # | ← Rev. 2 →   0 Why did I time out $O(nlog^2n)$ on E.
•  » » 5 days ago, # ^ | ← Rev. 2 →   -45 I'm wondering a similar thing. Why do $O(n\cdot\log^4(n))$ solutions time out but $O(n \sqrt{n})$ solutions pass?$log^4(200000) \approx 790$ and $\sqrt{200000} \approx 447$. They really aren't that different. Plus, $\log$ is a tiny thing compared to square root.
•  » » » 5 days ago, # ^ |   +32 You took the logarithm in base 10, $log^4_2{200000} \approx 96161$.
•  » » » » 5 days ago, # ^ |   -11 Ah yes, thanks for pointing that out. It looks like google defaults to $\log_{10}$. No wonder why $O(n \cdot \log^4 (n))$ solutions don't pass lol
•  » » » 5 days ago, # ^ | ← Rev. 2 →   0 log is base 2, not 10.log(200000)=17.6,
•  » » » 5 days ago, # ^ |   0 because $log^4(2 * 10^5) ≈ 10^4$
•  » » » 5 days ago, # ^ |   +62 it's because of iq
 » 5 days ago, # | ← Rev. 2 →   -12 I fsted D and E :(I hope there will be strong pretests next time.
 » 5 days ago, # |   +1 I enjoyed all of the problems I saw in the contestA was easy but still is a good problem for Div 2 A.My only complaint is that for problem B, it wasn't really emphasized that there was one connected component at the start. It was there in text but the diagram had more than one component. Ideally that part would have been in bold. For problem C, I misread the problem (which was completely my fault) and thought that the data corruption affected both random even and odd characters. If anyone has a solution to that problem I'd be interested. The greedy doesn't work as it is possible that by adding a closing bracket at your current position you stop the bracket sequence from becoming a regular bracket sequence. (Funnily enough, I actually the working code for this problem as a part of my attempt at a solution for the problem where random even and odd characters are corrupted.)Problem D was a classic tree DP problem that I almost solved but ran out of time because of how much time I wasted on problem B and C. Very nice and educational contest even though I completely under-performed.
•  » » 5 days ago, # ^ |   0 D was binary search not DP i thought.
•  » » » 5 days ago, # ^ |   +1 You can solve it with both. To me DP was more intuitive but the intended solution was binary search.
 » 5 days ago, # |   -11 B was basically an IQ problem
•  » » 5 days ago, # ^ |   +2 Why are you so obsessed with iq? You also literally solved it in the contest.
•  » » » 5 days ago, # ^ |   0 I am not so obsessed with IQ. It is just an interest of mine.B being an IQ problem doesn't really have to do with whether or not I solved it. It is an IQ problem because you clearly can't train for such problems. I bet you can't even find a similar problem on codeforces.Anyway, it seems like most div. 2 A-C are IQish problems. To me, it just felt like this B was a full-on IQ problem. I bet you could put that problem on an IQ test and no one would bat an eye.
•  » » » » 5 days ago, # ^ |   0 Isn't your whole point that you can never reach red because your iq isn't high enough. Or am I mistaken? So if you can solve so called "IQ problems" than why can't you reach red?Also I think that your claim that you can't train for such problems is clearly ridiculous. Many GMs were stuck at Newbie for months and couldn't solve div.2 A-C. Has their IQ changed?
•  » » » » » 5 days ago, # ^ |   -11 Well, to be fair, it was an easier IQ problem. There are harder IQ problems out there, like that one B2 from a few contests ago. Though I'd classify that B2 as an IQish problem, not a full-on IQ problem. I was just letting the authors know that they made (whether on accident or on purpose) an IQ problem.The sad thing is that the IQish problems don't seem to go away completely as you search for higher-rated problems. There is no feeling like going to a problem's editorial and seeing that it was an IQ/IQish problem all along. Of course, there are worse feelings, like getting sent to hell probably, but there is no feeling quite like failing to solve an IQ problem. Also I think that your claim that you can't train for such problems is clearly ridiculous. Many GMs were stuck at Newbie for months and couldn't solve div.2 A-C. Has their IQ changed? Probably, because most of them started codeforces when they were like 12. On average, cognitive ability increases substantially from 12-25, but it mostly stops increasing by age 18. Show me the profile of one of these users, though. I'd be happy to be proven wrong.
•  » » » » » » 4 days ago, # ^ |   0 According to Emory School of Medicine, "IQ is an abbreviation for Intelligence Quotient. “Intelligence,” as measured by IQ tests is rather narrowly defined. An IQ is intended as a predictor of the level of abilities a child will need to be successful in school. In the general population this score becomes relatively stable after about four years of age." So no, IQ doesn't generally change when you're an adolescent. Here are two profiles that I think have inspiring rating graphs. Bakry adamant his username fits his rating graph quite well in my opinion
•  » » » » » » » 4 days ago, # ^ |   0 What they mean by that is that individuals' IQ scores generally stabilize by the age of 4. This means that, if a person scores 115 at age 4 (this is in reference to other 4-year-olds), they will likely score around 115 at age 34 (this is in reference to people around the age of 34). It doesn't mean that cognitive ability doesn't increase past 4. Of course a 34 year old is gonna be smarter than a 4 year old, on average.With that being said, I think that both of those users you have mentioned started way before they were 18. So they had lower cognitive ability when they started than they do now.
•  » » » » 4 days ago, # ^ |   0 These are called "ad-hoc problems."
•  » » 5 days ago, # ^ |   +11 You are overusing the term IQ problem.
 » 5 days ago, # |   +5 The given grid contains at most 1 connected regionmissed the above statement in B, because my mind covered with the pictures in the statement , assumed there can be multiple components, because of which much time got wasted
•  » » 5 days ago, # ^ |   +1 Exactly bro
 » 5 days ago, # |   0 Amazing Contest! but I think there is a problem, rating changes applied to all participants even those whose rating greater than 2100 this could be a mistake maybe.
 » 5 days ago, # | ← Rev. 2 →   +1 The B Question was not correctly framed.The ambiguity in the sentences were high.
 » 5 days ago, # | ← Rev. 3 →   +3 Alternative approach to problem E. I observed that, if we do not fight against monster i for some k = x, then we will not fight against it for k < x either. So I found the max k for each monster that would make them run away from the fight, and for each input if x <= res[i] then we do not fight with them. My proof was prayers, so anyone is welcome to either prove it right or wrong. The rest is straight forward: We will do binary search for each monster. Let's take some fixed k. If we will not fight with monster i, then we have already fought with at least k*a[i] monsters out if first i-1. If that's the case then we should look for a greater k. Now we must be able to check how many of them we did not fight, meaning how many of them had res[j] >= k for j < i. We can do it with simple sum segment tree, keeping how many monsters had k = x in the leaf nodes. The reason I cannot prove the first paragraph is that, when we check k < x, it's true that we will have more frequent level-ups, however it's also true that we will skip more monsters, so if we create an equation, both sides would be decreasing.Accepted solution: 273561881
•  » » 5 days ago, # ^ | ← Rev. 2 →   0 A proof in plain language:Consider two ks, k_0
•  » » 5 days ago, # ^ | ← Rev. 2 →   0 Another way to do this with a similar approach is store store an ordered multiset of all res[j] for j < i and find the order of key k.
•  » » 4 days ago, # ^ | ← Rev. 2 →   0 Proof for the first paragraph:Proposition to be proved is $(\forall i \exists ans[i]$ such that $query(i, x) \leftrightarrow ans[i] < x)$. Assume that $i$ is the minimum index for which the statement does not hold. Hence $\exists k$ such that $query(i, k) \wedge \neg query(i, k + 1)$. Therefore $card(j < i, ans[j] = k) \geq a[i] + 1$. We define $t := max(j < i, ans[j] = k)$. $(k*a[t] \leq \Sigma_{k' = 0}^{k - 1} card(j < t, ans[j] = k') \wedge k*a[t] + a[t] > \Sigma_{k' = 0}^k card(j < t, ans[j] = k'))$ which means that $a[t] > a[i] \wedge \neg query(t, k)\Rightarrow \neg query(i, k)$. Thus we achieve proof by contradiction.
•  » » 3 days ago, # ^ |   0 My post contest solution with explanatory comments. Your explanation helped. Thanks <3https://mirror.codeforces.com/contest/1997/submission/273966239
 » 5 days ago, # |   0 In Problem F, can anyone explains me this line how this would be the most optimal:this is just checking that the minimum number of Fibonacci numbers used to represent an integer is equal to m .
 » 5 days ago, # | ← Rev. 3 →   +1 I had a solution for problem E that's a bit simpler conceptually. (Doesn't require the harmonious series observation or changing the timeframe from i to k)It's based on the following observation:If a monster is fought when k=k_0, it will be fought when k is larger.Given above, we can walk from position 1 to n, and maintain the number of monster fought for each k. For every new monster, based on observation, we only need to increase the count by 1 for a suffix. That can be done with BIT or your favorite range query data structures.Now we still need to decide what's the smallest k for each position, or the which suffix should we operate on.Again based on the observation, this can be found by binary search. When checking whether we will fight that monster for k, we make a query to our BIT to calculate the current level for k.The overall complexity is still O(nlog^2n).
•  » » 5 days ago, # ^ |   0 You can also query the BIT directly(find first) and the complexity will be $O(n \log n)$.
•  » » » 5 days ago, # ^ |   0 how to find pref[x] / x < a in log(n) with point updates?
•  » » » » 4 days ago, # ^ | ← Rev. 2 →   +3 On each segment store the rightmost value. Apply updates lazily. If the binary search condition is false for rightmost, then it is false for the entire segment. Find the first element by crawling the tree.
•  » » » 5 days ago, # ^ | ← Rev. 2 →   0 Hmm can you explain more? Thanks!IMO one log is from binary search and another is from BIT, it's not clear to me how we can drop one of the two? I figured out how to do it... Basically you look at 1, 10, 100, 1000... and combine finding sum and checking the binary search condition.
 » 5 days ago, # |   0 A simpler implementation of C without stack/vector. 273589519i thought of brackets reducing in pair of 2 and guessed by looking at pretest. although i am not very clear why this works and it would be great if someone could explain it.
 » 5 days ago, # |   +3 Problem C can be solved in constant time and space with the formula len(s)/2 + 2*s.count(‘(‘) for an input string s, just have counter for open parenthesis and update as the input comes in.If anyone has a good proof, I would be interested in seeing it.
 » 5 days ago, # | ← Rev. 2 →   0 i'm really curious and wanna know the linear $O(n + m)$ of mine passes in ~$500ms$ but at the same time the binary search solutions having time complexity of $O(n\log_2 n + m\log_2 n)$ pass in ~$200ms$.
 » 5 days ago, # |   0 Solution For C SpoilerI can't explain much about the solution. I just observed some pattern and code it up and worked. void solve(int T) { int n;cin>>n;string s;cin>>s; int temp = 0; int ans = 0; for(int i=0;i
 » 4 days ago, # |   0 Can someone please explain why my question D doesn't work? I am just using basic DFS, and trying to find what the maximum value can I add to vertex 1. Submission: https://mirror.codeforces.com/contest/1997/submission/273756060
 » 4 days ago, # |   0 can someone please explain the B problem, i really dont understand from either tutorial and vid soln
•  » » 4 days ago, # ^ |   0 There are only two layouts in which blocking a cell creates 3 regions. Try brute forcing every cell and you will notice that only two layouts can be added to the answer.
•  » » » 4 days ago, # ^ |   0 oh f yeah, thanks
 » 4 days ago, # |   0
 » 4 days ago, # |   0 For problem E can someone explain this part : int nxt = x + k - 1 >= int(alive.size()) ? n : *alive.find_by_order(x + k - 1);
 » 4 days ago, # |   0 I just realised B says at most 1 connected component and here I was thinking of using articulation points and all lol
 » 4 days ago, # |   +11 E can be solved in $O(nlogn)$ using the "binary search on fenwick tree" approach. You can see 273651754.
•  » » 4 days ago, # ^ | ← Rev. 3 →   0 Another solution for E is a parallel binary search or divide and conquer approach also in O(n * log(n)). My solution: 273896973
 » 4 days ago, # |   0 Can anyone tell me why my submission for D overflows the stack? As far as I can tell, I only visit each node once.
 » 4 days ago, # |   0 Problem E can be solved in $O(n \log n)$. I've written a blog for it.
 » 4 days ago, # |   0 Can anybody explain how to find k-th element, greater than x with fenwick? :)
•  » » 35 hours ago, # ^ |   +3 Process the queries offline. Sort queries by decreasing x.Make an array of [value, index] pairs in the original array. Sort that by decreasing value. Maintain a pointer for the array of [value, index] pairs, initially starting at 0 Now to solve the query [x, k] in log^2(n) time:while the pointer is pointing at a value greater than x,update the fenwick tree at index from 0 to 1 Binary search for the correct position
•  » » » 8 hours ago, # ^ | ← Rev. 2 →   0 Do you know any log(n) solution with Fenwick? :( Trick with binsearch is classic. In this case complexity is O(n log^3(n)), not O(n log^2(n)) (task E)
 » 4 days ago, # |   0 HelloCan someone help me find the error in my submission : 273811843 it showed runtime error in test 6.
 » 4 days ago, # | ← Rev. 4 →   0 Maybe my solution for Problem D is the most simply one with only 30 lines. Just use dfs(p) to refer how many can be offered by all p's children. This solution is very fast Code
•  » » 4 days ago, # ^ | ← Rev. 2 →   0 Bro used one liner condition to handle so that it looks pretty short, however it doesn't count as "most simply one"., as it is nothing more than greedy approach most people have known.
 » 4 days ago, # |   0 I solved problem D with a basic dfs traversal.https://mirror.codeforces.com/contest/1997/submission/273877479
 » 4 days ago, # |   0 I have a doubt in F. Can you please explain where am I wrong. After placing all chips on the line after doing some operations we always end up with 1 or 2 chips finally. So, cost is always 1 or 2.. Proof - Because lets say i>2 have a even number of chips at i. Lets say 4, now by op 1 it becomes 1 3 1 Op-2 — 0 2 2 Op-2 — 1 1 1 Op-2 — 0 0 2 Like this every even pile can be reduced to 2. And every odd pile to 1. After this, to ones at diff pos can be combined into 1 or 2. 10001 goes to 110111 after few 1st operations. Again this can be combined and made into 1 or 2.So, how can there be a solution for m>2
 » 4 days ago, # |   +3 E and F is so dificult, i had no idea for this ;-;
 » 4 days ago, # |   0 Can anyone tell me what is wrong with this solution for problem D, i got a overflow error even though everything is in long long 273894619
 » 3 days ago, # |   0 I have one doubt regarding Problem E. In this problem when i used segmented tree my solution exceeded the time limit in test case 12 but when i did the same with fenwick tree it passed . Can anyone tell me the reason behind it? although the updation and query time complexity for both the data structure is same ,that is O(logN).273965828 Fenwick Tree , 273964980 Segmented tree.
•  » » 35 hours ago, # ^ | ← Rev. 2 →   +5 fenwick tree has a better constant factor than segment tree.
 » 3 days ago, # |   0 Problem D can also be solved in O(n)` by using basic Divide and Conquer. Submission: 274014881
 » 43 hours ago, # |   0 Thank you for such well detailed E problem solution BledDest.