intrusiv's blog

By intrusiv, 9 months ago,

Author: valeriu

Solution
Code (valeriu)
Rate Problem

Author: valeriu

Solution
Code (valeriu)
Rate Problem

Author: tibinyte

Solution
Code (tibinyte)
Rate Problem

Author: tibinyte

Solution
Code (tibinyte)
Rate Problem

Author: tibinyte

Solution
Code (tibinyte)
Rate Problem

F — Field Should Not Be Empty

Author: tibinyte

Solution
Code (tibinyte)
Rate Problem
• +90

 » 9 months ago, # | ← Rev. 3 →   +33 why the name of problem C is Adam lying face when it is Largest subsequence? or am i stupidupd. fixed, thanks
•  » » 9 months ago, # ^ |   +5 the same with problem A
 » 9 months ago, # | ← Rev. 4 →   +42 Problem names of A, B and C are wrong: A — Indirect Sort vs 1905A - Constructive Problems B — Beginner's Zelda vs 1905B - Begginer's Zelda C — Adam Lying Face vs 1905C - Largest Subsequence upd: Thanks for fixing it :)
•  » » 9 months ago, # ^ |   0 In problem C my method has utilised O(n) complexity and yet it is giving tle at last test(9). please look upon this..237829405
•  » » » 9 months ago, # ^ |   0 v.insert(...) runs in O(n) time. I can offer deeper feedback if you rewrite your code in a more readable style
•  » » » » 9 months ago, # ^ |   0 yah,i realised that btw thanks...my codes are horrible lol
 » 9 months ago, # |   -25 Problem C did not mention whether the string had to be sorted in ascending or descending order. I got a wrong answer on test case 2 (21th test case dcbbaa) as i considered sorting in descending order too. Please look into this issue.
 » 9 months ago, # |   -38 gray round, that says it all...
•  » » 9 months ago, # ^ |   +19 dude, Link
•  » » » 9 months ago, # ^ |   +29 omg gray comment...
•  » » » » 9 months ago, # ^ |   0 people when there is no alts
•  » » 9 months ago, # ^ |   +29 ratism?
 » 9 months ago, # |   0 Can someone please explain C. for finding the number of operations we will subtract the length of the largest prefix of equal values of the subset from its length. Didn't understand this.
•  » » 9 months ago, # ^ |   +7 If the largest subsequence is zzzba for example, the number of operations would be 2.Total length is 5 and the largest prefix of equal values would be zzzThis is because after two operations, the largest subsequence will be zzz and further operations will be no-op.
 » 9 months ago, # |   +50 In E you can also notice that for a subtree of fixed size the sum of LCAs for all the verices in this subtree is some linear function of $v$: $f(v) = kv + b$, where $v$ is root of the subtree. Then it is easy to solve the problem for arbitrary $v$, thus getting a linear function. Since there's at most $O(\log (n)^2)$ different subtrees you can easily solve the problem using recursion with memoization.This is my implementation: 237520087
•  » » 9 months ago, # ^ |   +30 Used the same idea, except the only candidates for subtree sizes are $\left\lfloor \frac{n}{2^x} \right\rfloor$ and $\left\lceil \frac{n}{2^x} \right\rceil$.So this actually gives $O(\log n)$ per test case (assuming you merge in constant time).
•  » » » 9 months ago, # ^ | ← Rev. 2 →   -16 $O(\log n^2)$ = $O(2\log n)$ = $O(\log n)$
•  » » » » 9 months ago, # ^ |   +14 What I've written was $O(\log (n)^2) = O((\log (n))^2)$, and you can't simplify the way you did. Maybe I should've written $O((\log (n))^2)$ in the first place, but nevertheless.
•  » » » » » 9 months ago, # ^ | ← Rev. 3 →   +14 oh, I see. but isn't number of different subtrees actually $O(2\log n)$ ?
•  » » » » » » 9 months ago, # ^ | ← Rev. 2 →   +9 According to ToniB that is true, but I don't have the proof yet, so I'm not too keen on believing this. Actually, I might've found counterexamples, but I'm not too sure.UPD. Tried to test out different values of $n$, and found that it is, indeed, true, and my counterexamples were wrong.
•  » » » 9 months ago, # ^ |   +10 Actually, if it really is the bound, then my solution also checks at most $O(\log (n))$ different subtrees per test case.However, I don't really know how to formally prove that it is really the case. Can you share your proof?
•  » » » » 9 months ago, # ^ | ← Rev. 4 →   +11 for any $n$: $\left\lfloor\frac{n}{2}\right\rfloor$ , $\left\lceil\frac{n}{2}\right\rceil$, $\left\lfloor\frac{n + 1}{2}\right\rfloor$ and $\left\lceil\frac{n+1}{2}\right\rceil$ have at most 2 unique values, and they are also some $x$ and $x + 1$so for every depth of the tree we have at most 2 unique ranges.so max number of different subtrees is $O(2\log n)$
•  » » » » 9 months ago, # ^ | ← Rev. 2 →   +19 For any $L \leq n \leq R$ you can see $\left\lfloor \frac{L}{2} \right\rfloor \leq \left\lfloor \frac{n}{2} \right\rfloor \leq \left\lceil \frac{n}{2} \right\rceil \leq \left\lceil \frac{R}{2} \right\rceil$.Now you prove by induction. Suppose $\left\lfloor \frac{n}{2^x} \right\rfloor \leq k \leq \left\lceil \frac{n}{2^x} \right\rceil$ where $k$ is a subtree size on $x$-th layer from the top. Using the inequality above, you get $\left\lfloor \frac{\left\lfloor \frac{n}{2^x} \right\rfloor}{2} \right\rfloor \leq \left\lfloor \frac{k}{2} \right\rfloor \leq \left\lceil \frac{k}{2} \right\rceil \leq \left\lceil \frac{\left\lceil \frac{n}{2^x} \right\rceil}{2} \right\rceil$which simplifies to $\left\lfloor \frac{n}{2^{x+1}} \right\rfloor \leq \left\lfloor \frac{k}{2} \right\rfloor \leq \left\lceil \frac{k}{2} \right\rceil \leq \left\lceil \frac{n}{2^{x+1}} \right\rceil$Since these are the only possible sizes of subtrees in the next layer, the next step will also hold. Base case is trivial.UPD: or just what ibrahimwq said, looks simpler.
•  » » 9 months ago, # ^ |   +3 Can you explain more clearly how to construct this formula: f(v) = kv + b Thank you!
•  » » » 9 months ago, # ^ | ← Rev. 3 →   +13 Well, firstly, suppose we have some subtree of size $n$, and by induction for trees of size smaller than $n$ we already know their linear functions. Then what is the answer for this subtree (LCA is some vertex of this subtree)? LCA(S) = $v$ only in subsets, for which there is at least 1 leaf from the left son, at least 1 leaf from the right son, and there are no leafs besides this subtree (or LCA would be some ancestor of v). For a tree of size $n$ left son has the size $\lceil \frac{n}{2} \rceil$, and right son has the size $\lfloor \frac{n}{2} \rfloor$. Then there are $(2^{\lceil \frac{n}{2} \rceil} - 1)(2^{\lfloor \frac{n}{2} \rfloor} - 1)$ subsets for which LCA is $v$.Now we need to calculate the answer for the case when LCA is equal to some vertex in the left or the right son. Because by induction we already know what formula of the answer for the left and right son is, we have $f_l(v)=k_l v + b_l$, $f_r(v) = k_r v + b_r$. Then the answer for the left son is $f_l(2v)$, and $f_r(2v+1)$ for the right son. Composition of linear functions is also a linear function (given $f(v)=av+b, g(v)=pv+q,$ we have $f(g(v)) = a(pv+q)+b = (ap)v + (aq+b)$)Combining everything together, the answer for the subtree is $f(v) = (2^{\lceil \frac{n}{2} \rceil} - 1)(2^{\lfloor \frac{n}{2} \rfloor} - 1) v + f_l(2v) + f_r(2v+1).$UPD: base for this induction is linear function for subtree of size 1: $f(v) = v$
 » 9 months ago, # |   0 can someone help me in trying to check which testcase my code if failing for problem C :( 237528783
•  » » 9 months ago, # ^ |   +5 In the last for loop, you have to iterate over lar.size() not n.
•  » » » 9 months ago, # ^ |   +4 sweet. i so fking dumb. cant even see shit. thanks
 » 9 months ago, # |   +4 The author's solution F is too long, it seems it could have been written simpler. https://mirror.codeforces.com/contest/1905/submission/237540164
•  » » 9 months ago, # ^ |   0 SegmentTree W
•  » » 9 months ago, # ^ |   0 Another simple solution with just regular segtrees https://mirror.codeforces.com/contest/1905/submission/238286775
 » 9 months ago, # |   +2 Problem B from graph :p,though not related to graph related algos :)
 » 9 months ago, # | ← Rev. 2 →   0 We can rather think of B in this ways:No matter what path we choose, we only reduce the total no. of leaf nodes by 2. And it is obvious that we will only choose a path having 2 leaf nodes. So, if initially the total no. of leaf nodes is x. After 1 operation, it will be x-2. So, how many times you subtract 2 from x? ceil(x/2)You can use this site to visualize the trees and confirm yourself for better understanding: https://csacademy.com/app/graph_editor/
 » 9 months ago, # |   0 can any one tell me the intuition of D?
•  » » 9 months ago, # ^ | ← Rev. 2 →   +42 I might have had a different intuition than the Editorial, but i can try. For simplicity, let $pm(i)$ denote $\text{mex}({p_1, p_2, ..., p_i})$, that is the mex of a prefix of $p$ of length $i$. Lets assume $p_n=0$. What's the answer? $n$. Because every mex of a prefix will be equal to $0$ except the prefix containing the entire permutation.Now, what happens when $p_{n-1}=0$?If you try a few cases you will see that the answer in this case is $p_n + n$. If $p_n=1$ then the answer must be $1 + n$. Because $pm(i)=0$ for all $i •  » » » 9 months ago, # ^ | ← Rev. 2 → 0 How do you find the last element smaller than$p_i$? Edit: Oh, that's why VectorViking has a monotonic stack. We read the array of$p_i$from left to right, and at every$p_i$, we pop all elements bigger than$p_i$before pushing$p_i$. Thank you very much! •  » » » » 9 months ago, # ^ | +1 and anyway in general if you wanna keep track of nextLarger, nextSmaller or prevLarger, prevSmaller you use monotonic stack •  » » » 9 months ago, # ^ | +1 It's actually the same as the editorial's solution, just changes the order to calculate ans. But your way is more easy to understand, and then we can clearly see that each number would push on and pop out in the stack for at most once, thus the time complexity is O(n). •  » » » 9 months ago, # ^ | 0 Your maths skill are very good in my case I don't even know why 2 is greater then 1 •  » » » 9 months ago, # ^ | +5 I guess there are some typos after the sentence will then be equal to our new value Those$p_j$here should be$p_i$•  » » » 9 months ago, # ^ | ← Rev. 2 → 0 I tried implementing this solution but idk where is my error. I get the following verdict: 45478th numbers differ — expected: '31', found: '0' even though at the end of my code I output something like$max+n$, where$max$is always$max\geq 0$. Here is my code •  » » » » 9 months ago, # ^ | +5 When n=1 you don't read the whole input •  » » » 9 months ago, # ^ | ← Rev. 3 → 0 pretty good explanation and the code was clean and easy to understand , got the idea clearly Thanks bro!! •  » » » 12 days ago, # ^ | ← Rev. 3 → 0 Do you have any intuition that zero start from head? (0, p1, p2, p3, ...)My intuition is zero start from head, and i think of it for a day. But i can not find the solution like monotonic stack which can calculate the sum in O(1).EDIT: Or how do you come up with the intuition that zero start end but not front?EDIT2: I probably found out why zero can only be put on right.consider zero move right like 0 1 2 3 -> 3 0 1 2 I can use two pointer from left two right to found out where the integer start add. However, the number of right hand sid of number we found is not fixed, the number in the sequence may still become bigger. To detect this, I need O(N). For example:number : 0 1 4 5 2 3 6 7 -> 7 6 3 2 0 1 4 5sum : ___1 2 2 2 3 6 7 8 -> 0 0 0 0 1 4 5 8On the other hand, let zero start from right can avoid this problem. Because when I move some number from left to right we can use a monotonic stack to keep the changing of number.The different is that whether you need to traverse the array to check the current number or not. •  » » 9 months ago, # ^ | ← Rev. 2 → +3 Let's solve the following example: 2 3 6 7 0 1 4 5We first place 0 at the end: 1 4 5 2 3 6 7 0What's the cost? It's 8 ( =n ), because everything before 0 adds +0, and at the end there is always +n (we used all numbers from 0 to n-1).Now we rotate the sequence to the left. 1st iteration: 4 5 2 3 6 7 0 1 (cost is 1 + 8) 2nd iteration: 5 2 3 6 7 0 1 4 (cost is 1 + 4 + 8) 3rd iteration: 2 3 6 7 0 1 4 5 (cost is 1 + 4 + 5 + 8) 4th iteration: 3 6 7 0 1 4 5 2 (cost is 1 + 3 * 2 + 8) Why is that? Because now 2 is at the end and we can use it for places where we used 4 and 5 (they are bigger). It's enough to maintain a monotonic stack while iterating, so the solution is linear.You can see my solution at: 237547878. Hope this helps! •  » » » 9 months ago, # ^ | 0 Why is the cost of the 4th iteration not$1 + 2 \times 2 + 8$? •  » » » » 9 months ago, # ^ | 0 Because the cost is computed as the sum of mex, for each iteration: 0th: 0 0 0 0 0 0 0 8 1st: 0 0 0 0 0 0 1 8 2nd: 0 0 0 0 0 1 4 8 3rd: 0 0 0 0 1 4 5 8 4th: 0 0 0 1 2 2 2 8 As you can see, when we "rotated" 2 from the start of the sequence to the end, it became the new smallest non-negative integer ( mex ) instead of 4 and 5. The third 2 comes from the rotation itself. •  » » » » » 9 months ago, # ^ | 0 Thank you!  » 9 months ago, # | 0 Can someone please explain D. I'm not able to understand the tutorial. Thanks! •  » » 9 months ago, # ^ | ← Rev. 3 → +12 These were my ideas during the contest. I hope it helps! Idea 1We are working on cyclic shifts so we can concatenate the given permutation to itself. Now a cyclic shift can be represented by a contiguous subsequence of length n. Idea 2For any permutation$mex([a_1, a_2, \dots, a_i]) = min([a_{i+1}, a_{i+2}, \dots, a_n])$Idea 3Let's apply the contribution to the sum technique. For every element in the permutation we want to find it's contribution to$\sum_{i=1}^{n} mex([a_1, a_2, \dots, a_i]$. Consider that$a_j = min([a_i, a_{i+1}, \dots, a_j])$, where$i$is minimal i. e.$a_j > min([a_{i-1}, a_i, \dots, a_j])$, the$j^{th}$element contributes to interval$[i, j)$with$a_j$. Idea 4The data structure part (not the best): For every$j$we can calculate$i$using a monotonic stack and for updating the contribution we can use any data structure that supports range update and range query: for every$j$we add$a_j$to interval$[i, j)$and for every$k \geq n$we calculate the sum from interval$[k - n + 1, k]$. I used a segment tree because: In this sad world full of imperfections, ugly segment trees exist. •  » » » 9 months ago, # ^ | 0 lol •  » » » 9 months ago, # ^ | 0 can you explain why you do a[i]++ in your code ? Thanks a lot.  » 9 months ago, # | 0 In problem B solution. I think there should be ceil(K/2) instead of ceil(K+1/2) •  » » 9 months ago, # ^ | 0 does it matter? •  » » 9 months ago, # ^ | +1 I've written about floor((X+1)/2), which is practically ceil(X/2) :) •  » » » 9 months ago, # ^ | +17 If you want to write the floor function properly, you can use$\left\lfloor\frac{K+1}{2}\right\rfloor$(\left\lfloor\frac{K+1}{2}\right\rfloor) instead of$[\frac{K+1}{2}]$.  » 9 months ago, # | -17 unbalanced round  » 9 months ago, # | ← Rev. 2 → 0 Can anyone tell why I am getting a runtime error on this submission(C)- 237514134 •  » » 9 months ago, # ^ | ← Rev. 2 → 0 Type cast d.size()-1 to (int)d.size()-1, now u are getting wrong answer •  » » » 9 months ago, # ^ | 0 It worked, thanks, but can you tell what exactly is causing the problem? •  » » » » 9 months ago, # ^ | 0 Bcoz size() returns an unsigned int, so if used in the loop condition might cause undefined behaviour •  » » » » » 9 months ago, # ^ | 0 Ohh alright thanks!  » 9 months ago, # | ← Rev. 3 → +3 This is the proof that D worst time is O(n)I will use the accounting method (the second method of amortized analysis)The operations of the algorithm to solve problem D: merge frequencies into one => cost = n (by removing all frequencies of elements greater than v[i], then incrementing the frequency of v[i] by them) increment frequency of v[i] => cost = 1 decrement frequency v[i] => cost = 1 So, the upper bound of the algorithm is O(n^2) It is correct, but not tightNote two important things:1- we have only n operations2- we cannot remove frequency of any element unless it was incremented beforeCan't we just make the cost of increment to be 2 instead of 1? one for incrementing and one as a credit to be the cost of the future remove operation so we can assume the cost of merge operation to be 0, and the increment operation to be 2hence, the total cost$<= \sum_i^n 2 <= 2n$Which is O(n)  » 9 months ago, # | ← Rev. 2 → 0 Can someone pls see why my code for problem C fails for 1043rd numbers on test case 2 ? 237554366 •  » » 9 months ago, # ^ | +5 I think the following line is causing an issue SpoilerAfter checking the next letter, you simply set last1 to last2. But you forget the possibility that last2 could be smaller than last1.So the correct code is last1 = max(last1, last2) •  » » 9 months ago, # ^ | +5 Found a test case that your solution will fail Test case1 6 zzcaza  •  » » » 9 months ago, # ^ | ← Rev. 2 → 0 thanks a lot.. It got an AC :)  » 9 months ago, # | 0 this contest was great  » 9 months ago, # | 0 in C I don't know what is s = '' + s for and what is the name of title I should study for this. •  » » 9 months ago, # ^ | 0 just to for from 1 to n if you dont have that its from 0 •  » » » 9 months ago, # ^ | 0 thanks  » 9 months ago, # | 0 Do you know there is a good problem about MEX in luogu, too?Link  » 9 months ago, # | 0 Hi! Friends :) •  » » 9 months ago, # ^ | 0 Hi! lol  » 9 months ago, # | 0 here is my code for problem C,i cant understand why it doesnt work.here is mine.#237576156 •  » » 9 months ago, # ^ | 0 •  » » » 9 months ago, # ^ | 0 czddeneeeemigec may have conut 7 but it return 8  » 9 months ago, # | 0 i think problem F is easier than D for someone like me :(  » 9 months ago, # | 0 Video Editorial For Problem A,B,C,D.  » 9 months ago, # | 0 can anyone explain the editorial solution of E  » 9 months ago, # | 0 The problem D. The second cycle may be from 1 to n .  » 9 months ago, # | 0 "Thus, we can easily check if the string is sortable". How that's literally the point of an editorial plus for number of operations you're not explaining why which kind of defeats the whole purpose of an editorial.  » 9 months ago, # | 0 Is there a simpler O(n) solution for F ? •  » » 9 months ago, # ^ | 0 https://mirror.codeforces.com/contest/1905/submission/237719024 this solution is O(N). I've used hashmap to store the pair of swaps, so that should be O(N) too.  » 9 months ago, # | 0 Here comes a$O(\log N)$solution for problem E. We still focus on the fact that, for each depth there are at most 2 different interval lengths, and let's assume they are$(2k,2k+1)$, which will become$(k, k+1)$a layer deeper. For the case$(2k-1, 2k)$we do it in a similar way. We can count the number and the sum of ids of both kinds of intervals, e.g. there are$cnt_0$intervals of length$2k$, and the sum of their ids is$sum_0$. The same for$cnt_1, sum_1$with intervals of length$2k+1$.If we already know these values of$(2k, 2k+1)$, we can calculate those for$(k, k+1)$.Then, we count the number of leaves of a segment-tree with a$(k,k+1)$-length interval root, e.g. there are$lf _0$leaves in a segment-tree with a$k$-length interval root, and$lf _1$for$k+1$.We can calculate these values of$(2k, 2k+1)$from$(k, k+1)$.At last, the contribution of this depth is$sum _0*(2 ^{lf _0}-1)*(2 ^{lf_0}-1) + sum _1*(2^{lf_0}-1)*(2^{lf_1}-1)$.The time complexity is$O(\log N)$. You can see my submission for more details.  » 9 months ago, # | +8 I solve D with Treap algorithm. •  » » 9 months ago, # ^ | +8 can you please explain how did you do it? •  » » » 9 months ago, # ^ | +8 Just replace your segment tree with Treap))) •  » » » » 9 months ago, # ^ | +8 Thank you! I think it was a nice idea. It's much more easier than author's solution! •  » » » » » 9 months ago, # ^ | +8 What is author's solution? •  » » » » » » 9 months ago, # ^ | +8 He used deque. •  » » » » » » » 9 months ago, # ^ | +5 What is deque? •  » » » » » » » » 9 months ago, # ^ | +5 It's a treap but you can use only first and last element. •  » » » » » » » » » 9 months ago, # ^ | ← Rev. 2 → 0 thank you, petarda •  » » » » » » » » » 9 months ago, # ^ | ← Rev. 2 → 0 you are welcome, traktor.  » 9 months ago, # | -6 Thats enough of internet today  » 9 months ago, # | ← Rev. 2 → 0 Can someone please help me figure out the error for C in my submission 237655544? It fails on the 2124th test case, test 3. •  » » 9 months ago, # ^ | ← Rev. 2 → 0 This is so weird. I rewrite your code in Python3 and it passed. 237667769Update: Found the issueSince you are storing index in v1, so you should use vector instead of vector.See 237668463 for more details. •  » » » 9 months ago, # ^ | 0 Thanks a lot  » 9 months ago, # | ← Rev. 2 → 0 can any one tell me the intuition of E?I'm not able to understand the editorial.  » 9 months ago, # | 0 Will using set instead of deque in D exceed the time limit ? I used a set to maintain which numbers present in the current prefix mex array are grater than p1 and with a time complexity of O(nlogn) my code is giving tle on submissionhttps://mirror.codeforces.com/contest/1905/submission/237714597 •  » » 7 months ago, # ^ | 0 wdym? it got AC •  » » » 7 months ago, # ^ | 0 yeah that was the corrected submission here's the one using a set https://mirror.codeforces.com/contest/1905/submission/237711310  » 9 months ago, # | 0 cool  » 9 months ago, # | ← Rev. 2 → 0 I solved F without segment tree, here is my solution: 1) There is only 2 * n possible good swaps same as normal solution: n solutions of type(i, pi) and n solutions of type: can actually make some other numbers good 2) We calculate the solution for first type in O(n) time by precalculating for every i: are all elements before i-th index smaller than i in boolean array? So when we swap a[i] and a[a[i]] we need to "only" check did they become good solutions now(for pi = i we just check if it is good in our boolean array because if it is after swap it will be added to answer, but we also need to check is pi = ppi(if we have situation: 1 2 3 5 4, after swaping 5 and 4 we also make 5 in good spot) and similarly check will it increase solution.Yes, after doing this operation some more indexes might become good, but it will be checked in second case :) 3) Second case: which indexes can become good after swaping some 2 elements? Only those that have 1 pair inversed on left and right of them. We can find for every element can it become good and those 2 numbers in O(nlogn). After doing it, we just sort those pairs of indexes and for every pair (i,j) that makes x indexes good we add x to solution without swaps. Note: in this part we also check will (i, j) also get i or j in their good position and do same checks as in previous part. Solution:237847430  » 9 months ago, # | ← Rev. 3 → +8 Very late to this, but I also found another solution for problem F that avoids segment trees or sets: 238072983If we think of the permutation$p$as a function$(i\mapsto p_i)$, then an index$x$is good if and only if$p_x=x$and no arc$i\rightarrow p_i$jumps across it (where having the arc jump over$x$means$i
 » 9 months ago, # |   0 Hey guys, can please someone help me out here ? In problem D, why are we running the last for loop in the code for n-1 one times and why not n times ? if we run it for n times, then we will end up with the original configuration only right so the answer should not change. Just curious to know why.
•  » » 9 months ago, # ^ | ← Rev. 4 →   0 If you have determined that the solution has stabilized, meaning that further iterations do not significantly change the result, there is no need to continue the loop for the full n iterations. This phenomenon is often referred to as convergence, and it is common in iterative algorithms. Stopping the iterations early can lead to faster execution times and more efficient resource utilization.
•  » » » 9 months ago, # ^ |   0 Thanks!
 » 8 months ago, # |   0 why am I getting TLE on this submission 238664593 but not on this one 238664527?
 » 8 months ago, # |   0 1905EE can be considered in another way by first observing how to use O(logN) time to keep deduct segment tree size pair (size is for range) (k, k + 1) to segment tree size pair (k / 2, k / 2 + 1), then define $F_k(x)$ as sum for a segment tree with range having size $k$ and root node as $x$.Then a transition can be: $F_k(x) = (2^{lsz} - 1) (2^{rsz} - 1) * x + F_{lsz}(2x) + F_{rsz}(2x + 1)$, where $lsz$ and $rsz$ are the size of range of the subtrees. Then, notice $F_k(x)$ will be an affine transformation in $\mathbb Z \to \mathbb Z$ (or $\mathbb R \to \mathbb R$). Considering $2x, 2x+1$ are both affine, and affine transformation is closed under adding, multiplying by a scalar (forms a vector space), and also closed under composition ($C(Ax + b) + d = ACx+ Cb + d$, so the result $F_k(x)$ is still an affine transformation. So by induction $F_k(x)$ is affine for all $k \in \mathbb N$.
 » 8 months ago, # |   0 I think the answer for problem A for n,m>=2 will always be 2 for minimum number of cities. Then why is our answers the maximum of n,m?
 » 8 months ago, # |   0 Problem A reminds me of the folklore problem grid infection (try it if you haven't seen it before!) which is very nice.Given $n \times n$ grid, some squares are initially infected. In each subsequent step in time, any square which has two or more infected neighbors also becomes infected. Squares that are infected stay infected forever. What's the minimum number of squares that need to be infected at the start for the infection to eventually spread to every square in the $n \times n$ grid?
 » 8 months ago, # |   0 I got TLE on problem D by using the lazy segment tree O(nlogn),maybe due to the big factor.Then I use the monotone stack to solve problem D in O(n) time and finally got AC.It`s such a really tough experience,but I enjoy it hahahaha! :(
 » 7 months ago, # |   0 i do not understand test case on problem C 15 czddeneeeemigec output:6 please help me
 » 2 months ago, # |   0 An easy implimentaion of problen C is given: https://mirror.codeforces.com/contest/1905/submission/268933428 , it can also be improved.
 » 4 weeks ago, # | ← Rev. 8 →   0 F can be solved quite simply and without a segment tree. The condition for an index being good is equivalent to p[1...X] is a permutation of elements 1...X p[x]=x. Therefore we can iterate through all prefixes of p noticing that there is either zero or one swaps that improves the answer. These can be found through casework: Case 1: the index x is already good (zero swaps will improve the answer) Case 2: p[x]=x and p[1...x] is missing exactly one element-> in this case notice there must be one element greater than x, the swap is then swap it for the missing element Case 3: p[x]>x and we are missing only x -> swap p[x] and x Case 4: Otherwise -> no swaps will improve the answerOur answer is the most improving swap (makes the most elements good) + the number of indices already good. If all indices are good, it can be shown that the optimal answer is to swap the two last elements.Wait! What if a swap makes an index no longer good! We can show that this will never happen. Notice that all our swaps swap a larger element that occurs earlier in the array with a smaller one that occurs later. Using this fact let us use casework (that fact is sufficient but this is easier to understand): Case 1: ...a...b...x -> ...b...a...x : obviously in this swap x will remain good because the order of elements before has no effect on whether they form a permutation 1...x Case 2: ...x...a...b -> ...x...a...b : our condition does not care about elements after x nor their order Case 3: ...a...x...b -> ...b...x...a : b ...x...a... : x ...a...x... : a
 » 11 days ago, # |   0 Problem C was good,required a great depth of thought to avoid wrong subs.