### rui_er's blog

By rui_er, history, 16 months ago,

1797A - Li Hua and Maze

Tutorial
Solution (rui_er)

1797B - Li Hua and Pattern

Tutorial
Solution (rui_er)

1797C - Li Hua and Chess

Tutorial
Solution (rui_er)

1797D - Li Hua and Tree

Tutorial
Solution (rui_er)

1797E - Li Hua and Array

Tutorial
Solution (rui_er)

1797F - Li Hua and Path

Tutorial
Solution (Celtic, centroid decomposition)
Solution (rui_er, reconstruction trees)
• +214

| Write comment?
 » 16 months ago, # |   +30 Super Fast Editorial
 » 16 months ago, # |   -266 problem descriptions were very bad. learn english.
•  » » 16 months ago, # ^ |   +107
•  » » 16 months ago, # ^ |   +57 I am not a native speaker either but to me the statements were clear and I understood them without a problem.
•  » » 16 months ago, # ^ |   0 So do I
•  » » 16 months ago, # ^ |   +8
 » 16 months ago, # | ← Rev. 2 →   +43 this contest is better than the previous one div2
 » 16 months ago, # |   +3 Fast Tutorial.
 » 16 months ago, # |   +8 Thanks for very fast editorial!
 » 16 months ago, # | ← Rev. 2 →   +11 I believe the diagrams in the editorial solution for A could have been much simpler, just block the TOP, BOTTOM, LEFT or RIGHT block depending on the position of either (x1, y1) or (x2, y2).
•  » » 16 months ago, # ^ |   +4 That would give away the solution...
•  » » » 16 months ago, # ^ |   +14 I meant the pictures given in the editorial solution. :)
•  » » » » 16 months ago, # ^ |   0 oh, lol
 » 16 months ago, # |   +21 Very good contest!
 » 16 months ago, # | ← Rev. 2 →   0 $n log^3$ with unordered_map constant got TL in E(((
•  » » 16 months ago, # ^ | ← Rev. 3 →   0 unordered_map can be "hacked" to be linear per operation
•  » » » 16 months ago, # ^ |   0 I know, but in fact, the number of different elements added was very small, O(logw), so it should still work fast enough, in O(1)
 » 16 months ago, # |   +18 orz contest. Problems are gold
•  » » 16 months ago, # ^ |   -90 seriously, were you guys paid to write these comments? what's good about this round? just mention one good problem
•  » » » 16 months ago, # ^ |   +45 E and F were Epic.Overall, the contest was well balanced and the statements were clear so yes it is a good contest
•  » » » » 16 months ago, # ^ | ← Rev. 2 →   -22 E and F were very standard problems, idk what you found epic about them, moreover you didn't solve them.The statements weren't clear at all(the coloring in B wasn't specific at the beginning, I found D hard to understand too), and very confusing. and A, B, C, D are pretty much on the same level, so I don't know what your definition of balanced is.
•  » » » » » 16 months ago, # ^ |   +45 Please, don't cry over each contest you don't do well in and start blaming authors, contest you find bad others find great, just try to learn from mistakes you make and you'll eventually improve.
•  » » » » » » 16 months ago, # ^ | ← Rev. 2 →   -56 who is crying? my rank was even better than yours. I am just saying that there was nothing spectacular about the round, as people claim.
•  » » » » » » » 16 months ago, # ^ |   +24 Ofc you are saying this from a fake account…
•  » » » » 16 months ago, # ^ |   0 I think E is interesting but F are too classical, but it's a good and educational round though.
•  » » » 16 months ago, # ^ |   +41 Yes we are. Maybe you should contact the authors and start making money?
 » 16 months ago, # |   -21 The idea in E is segment-tree-beats, isn't it? I guess it is a hard E for div 2.
•  » » 16 months ago, # ^ | ← Rev. 2 →   +18 Don't need segment-tree-beats, just 2 trees, 1 for lca and other to count number of changes to reach 1.My submission
 » 16 months ago, # | ← Rev. 3 →   +93 Thanks for good problems and lightning-fast Editorial!UPD: as well as fast rating-changing within less than 1 hour after the contest.
 » 16 months ago, # | ← Rev. 2 →   +10 Great contest!Even tho I only solved A -> D but I had lots of observations on E, F and I think they're absolutely worth upsolving. Waiting for more more rounds from you in the future!
•  » » 16 months ago, # ^ |   0 ya E has a beautiful observation. i also try to upsolve
•  » » 11 months ago, # ^ |   0 Can you explain use of DSU according to tutorial in the solution?
 » 16 months ago, # |   0 Great contest and fast editorial!
 » 16 months ago, # |   0 going to expert possibly:))))
 » 16 months ago, # | ← Rev. 2 →   0 the link for the solution of F using RT is broken it is showing "you are not allowed to view the requested page"
•  » » 16 months ago, # ^ | ← Rev. 3 →   +4 Oops, it seems that you can't view the submission. How can I share the submissions correctly?I'll fix them soon.UPD: fixed.
•  » » » 16 months ago, # ^ |   0 Could you elaborate on how to calculate C in problem F in the RT solution ? Thanks in advance.
•  » » » » 16 months ago, # ^ |   +19 Oh sorry, I forgot about this message.You first calculate the dfs number ($\operatorname{dfn}$) and subtree size ($\operatorname{sz}$) of every vertex on the max-RT. Then $u$ is in subtree of $v$ on the max-RT if and only if $\operatorname{dfn}(v)\le\operatorname{dfn}(u)\le\operatorname{dfn}(v)+\operatorname{sz}(v)-1$.Then, you dfs on the min-RT. Entering a vertex $u$, you have all ancestors of $u$ marked in the fenwick tree. You can use the dfs number and size on max-RT to calculate how many ancestors of $u$ on min-RT is in the subtree of $u$ on max-RT.
 » 16 months ago, # |   0 https://mirror.codeforces.com/contest/1797/submission/201352138 WHat is wrong in this for B
 » 16 months ago, # |   +1 editorial faster than my code's time complexity
 » 16 months ago, # |   0 Beautiful Contest, I like all the questions. Especially the C and D questions although easy to get solution tricky to implement!!
 » 16 months ago, # |   -8 i am newbie can anyone tell why solution of problem a fail my approach to a was first i check for x1 and x2 at corners if they are at corners means that they only move two steps so we block only two steps if they not at corners but at first row or first column or nyh row or mth col they move only three steps then we need to block only three steps if they not at corners and also not at 1 or nthrow or mthcol then they must in between something in between so we move 4 steps so i check both this conditions for (x1,x2) and (y1,y2) and tale min of both of them so my pretest was pass during contest but fail on system test can anyone pls tell where my codes fails here is my code 201316107
•  » » 16 months ago, # ^ | ← Rev. 2 →   0 1 100 1000 100 100 50 50//ans should be 3,but output is 4
 » 16 months ago, # |   +5 Today I wrote the forbidden complexity in E, O(N log(W) sqrt(N)) !!I didn't thought such atrocity could pass System test but it did.Now I know that with seg tree I can do in O(N log^2 N)
 » 16 months ago, # |   0 Such a great contest, well done, authors
 » 16 months ago, # |   0 Nice problems，fast Editorial and fast ranting update.
 » 16 months ago, # |   0 I think there is another solution in C which is maybe easier. Consider (x, y) as the answer we need to find. If we query (a, b), we will get max(abs(x — a), abs(y — b)) as answer. We can ask (1, 1) (get k1) and (2, 1) (get k2) and we have 2 cases. If k1 = k2 then y — 1 must equal to k1 cause if it not then k1 = abs(x — 1), k2 = abs(x — 2) => k1 != k2. If k1 != k2 then abs(x — 1) = k1, abs(x — 2) = k2 and we can calculate x. The final query will be (1, y) if you can find y or (x, 1) if you can find x.
•  » » 16 months ago, # ^ |   0 three-point localization wwwthe problem can be harder if the 3 points are given and u need to calc the position
 » 16 months ago, # |   +1 I think C can be done in 2 queries, by querying (1, 1) and (n, 1) and then solving a system of equations.
•  » » 16 months ago, # ^ |   +5 Consider this: Board size $9 \times 9$ Distance from $(1, 1)$ is $4$ Distance from $(9, 1)$ is $4$ Where is the king?
•  » » » 16 months ago, # ^ |   0 (5, 1) ? maybe im missing something
•  » » » » 16 months ago, # ^ | ← Rev. 2 →   0 It could also be $(5, 2)$, $(5, 3)$, $(5, 4)$ or $(5, 5)$
•  » » » » » 16 months ago, # ^ |   0 I think im misunderstanding something about the problem. If distance from (1, 1) is 4 , how can you reach (5, 5) from (1, 1) in 4 steps?
•  » » » » » » 16 months ago, # ^ |   0 King also moves diagonally
•  » » 16 months ago, # ^ | ← Rev. 2 →   0 10 10? 1 1 1? 10 18! 2 1 or ! 2 2 ?
•  » » » 16 months ago, # ^ |   0 How can it be ! 2 2, if distance from (1, 1) is 1?
•  » » » » 16 months ago, # ^ |   0 King can move diagonally so 2,2 to 1,1 is 1
 » 16 months ago, # |   +21 Probably the stupidest mistake ever in C.I printed the string "! n m" instead of "!" and the values of n and m... SpoilerThis is the first time I solved A and B so fast that I'm rated as top 300, but C got me stuck till the end because of this stupid mistake.....
 » 16 months ago, # |   +20 Thank you rui_er for excellent problems and fast editorial. I enjoyed the problems very much.
 » 16 months ago, # | ← Rev. 2 →   0 https://mirror.codeforces.com/contest/1797/submission/201344789 Can someone please tell me my mistake for Problem C.
•  » » 16 months ago, # ^ |   0 flush the output ( cout.flush(); ) after printing anything
•  » » » 16 months ago, # ^ |   0 endl flushes automatically
•  » » » » 16 months ago, # ^ |   0 ohh, i dont know about that
•  » » 16 months ago, # ^ |   0 in the first test case for n=3, m=4, r=2, c=2 you will get a=1, b=2, c=1 in your code and y=1 and x=-1while printing x and y you are printing -1(x) so you are getting wrong output format just dry run your code you will get it.
 » 16 months ago, # |   +26 Can someone explain the idea behind the Centroid-Decomposition solution in task F?
•  » » 16 months ago, # ^ | ← Rev. 3 →   +11 Consider the operation of adding vertices. If we know the initial answer and array $f_n$ meaning the number of paths in which one end is $i$ and the other is the minimum, we can easily calculate the increase of the answer because the adding vertex must be the maximum. And we have $f_{n+j}=f_{k_j}+1$ in the $j$-th operation.Then we consider how to calculate the initial answer and array $f_i$.We can use Centroid-Decomposition. Denote $u$ as the current centroid. We can calculate the paths passing the vertex $u$. If we calculate the maximum and minimum from each vertex to the root, each vertex can be represented as a triple $(i,max_i,min_i)$. Then the answer passing $u$ is a two-dimension counting points problem. It can be solved in $O(n\log n)$. We need to do it again for each subtree because two vertices in the same subtree can't contribute to the answer.Total time complexity $O(n\log^2 n)$.
•  » » » 16 months ago, # ^ |   +12 Thank you very much!
•  » » » 16 months ago, # ^ |   +9 What is the "two-dimension counting points problem" that we got here?
 » 16 months ago, # |   +1 My approach to Problem C: Find the distance from $(1,1)$ (let it be $k$), now the king must be on the following two segments: from $(1,k+1)$ to $(k+1,k+1)$ from $(k+1,1)$ to $(k+1,k+1)$ Now take the intersection point of the two segments, i.e., $(k+1,k+1)$. Find the distance from $(k+1,k+1)$ (let it be $d$). You will have two possible options only: $(k+1-d,k+1)$ (let it be point $p1$) or $(k+1,k+1-d)$ (let it be point $p2$). In the third query find the distance from $p1$, if it's $0$ then print $p1$ else the king was on $p2$. Note : When $k+1$ exceeds either $n$ or $m$, then make the $x$ or $y$ coordinate to $n$ or $m$ (in the $2nd$ step). The approach/idea will remain the same.
 » 16 months ago, # |   0 Nice problems
 » 16 months ago, # | ← Rev. 2 →   0 Could someone tell why I'm getting "wrong output format illegal query (test case 1)" in this code?https://mirror.codeforces.com/contest/1797/submission/201367288
•  » » 16 months ago, # ^ |   0 because the board has size n*m (n rows and m columns). You ask the question "? m 1". But there may be no line m, for example if n = 3,n = 5. (You are asking the question "? 5 1" and there are only 3 lines.)
•  » » » 16 months ago, # ^ |   0 Thanks,I interchanged n and m I'm so dumb
 » 16 months ago, # |   0 Submission Can somebody check why this is giving idleness limit exceeded on test 2. I have used endl and cout.fflush to flush the output. Thanks!
•  » » 16 months ago, # ^ |   0
•  » » » 16 months ago, # ^ |   0 By the way, if you use endl, you can not prescribe flush since it is already included in endl
 » 16 months ago, # |   -16 Test 3 of the D is the worst ivention of humanity. But the xontest was really fun and i enjoyed solving it. I especially liked D. Also E feels a bit unbalanced for a div2.
 » 16 months ago, # |   0 I tried submitting my solution for C but it's continuously prompting ""wrong output format illegal query (test case 2)" on the first test case Link to my submission -> 201341675
•  » » 16 months ago, # ^ |   0 Got it! was just exceeding the upper limit for query. Will take care next time.
•  » » » 16 months ago, # ^ |   0 what does it means? I am having the same issue please help.
•  » » 16 months ago, # ^ |   0 When the field is, for example, 8 by 5, and the first response to the request is "? 1 1" this is 7. The next query according to your algorithm will be "? 8 8" although this cell is located outside the field, therefore the error
•  » » » 16 months ago, # ^ | ← Rev. 2 →   0 Thanks mate got it and sorted it out! I dealt with it by making a case for "if $query + 1$ exceeds n or m we know $query + 1$ is definitely the other co-ordinate." and I will just make another query to find the other element. in the example of 8 5 we ask "? 1 1" --> 7 then since 8>5 we know 1st co-ordinate is 8 then the next query "? 8 1" --> something and "! 8 (something + 1)"
 » 16 months ago, # |   0 for problem E, rather than using a segment tree to solve everything, you can just use a sparse table to get the LCA of the range, and then get the minimum depth (depth = how far away is the number from 1) and the sum of depth using a seg tree. This leads to an O(w log w + n log n log w + m log w) sol (w log w for the sieve, n log n log w for sparse table build + seg tree updates, and m log w sparse table query). This could technically be sped up to O(w log log w + n log n log w + m log log w) but doesn't really matter. Here's the code (its a bit messy but still most understandable then the tutorial's solution in my opinion): 201387841Hope this helps!
•  » » 15 months ago, # ^ | ← Rev. 4 →   0 You are not recalculating the lca after type 1 queries, the lca can change for certain (l,r) after a type 1 query involving some part of (l,r), you have only calculated for the initial values. Can you explain, please
•  » » » 15 months ago, # ^ |   0 Instead of calculating the lca, we can find the depth of the lca. If the depth of one of the nodes in a range is less than the initial lca depth of the range, we know that that is the new lca. This is because if the depth is higher then the initial lca of the range, the lca will not change because the lca is still one of the node's ancestors, but if the depth is lower than the initial lca, the lca is no longer on of the node's ancestors, but now the node is one of the lca's ancestors, meaning this node is the new lca. This basically means that the depth of the current lca will be the min of the depth of the original lca and the depth of the current numbers in the range of (l, r).
 » 16 months ago, # |   0 Can anyone finds the runtime error in this code? Thank you!1797D
 » 16 months ago, # | ← Rev. 2 →   -38 ****
 » 16 months ago, # |   0 Can someone help me about prblm e.. here is my solution.. https://paste.ubuntu.com/p/w9TBJNmBp5/
 » 16 months ago, # |   0 First interactive that i could solve. The problem statements were very clear looking forward for more such rounds
 » 16 months ago, # |   +6 Implementation based round that only exists to confuse with tricks and shortcuts. A round befitting of Chinese authors. The problems were god awful that only wants people to think how to implement, not how to solve.
 » 16 months ago, # |   0 oh，I think my mind is we
 » 16 months ago, # |   0 I have a different solution to problem E, does not require any dsu, just some logic + vectors + segtree.
 » 16 months ago, # |   0 Problem E can also be solved using just a segment tree(struct tournament in a code) with sum on an interval. For each query operation we know that the answer must be one of the numbers which the leftmost element in an interval can turn into using some number of operations. For each element we will store that set of numbers and maintain the number of operations for each number in a segment tree. Also for each number we will store the set of indexes that can become that number using some number of operations. We can answer each query by binary searching on the set of numbers which the leftmost element can turn into. If we are currently answering a query and need to know if each element in an interval can become a given number, we need to check if all numbers in a given interval can turn into it(can be done using lower_bound() on a set and a segment tree) and calculate the sum of operations with the before mentioned segment tree. When updating an interval, we can update the elements one by one as mentioned in the editorial, and decrease the number of operations for all numbers that the current element can turn into by one. The tricky part of understanding this idea is how this segment tree works(ordering of the leaves is somewhat similar to how we order nodes in HLD) and how to maintain it.Code: 201457307
 » 16 months ago, # | ← Rev. 2 →   0 Can Problem E be optimized to $\mathcal{O}(q \log n)$ by maintaining the max and min dfn?
 » 16 months ago, # |   0 I think the problem descriptions were clear!
 » 16 months ago, # | ← Rev. 2 →   0 rui_er is there really a solution for problem E without $\Omega(n\log w)$ ?
•  » » 16 months ago, # ^ |   0 We thought some of the testers (like LXH-cat) wrote the solution with a single $\log$.
•  » » » 15 months ago, # ^ |   0 I guess so.
 » 16 months ago, # |   0 Hi. Can someone please help me out by letting me know why my submission 202689621 for $E$ fails?My basic idea is to maintain a single segment tree where every node is a pair of integers. First entry is their LCA and second is the minimum number of operations. While merging segments in $build$ and $query$, I have just climbed up starting from LCAs of both the segments. This process wasn't required in $update$ because we are doing point updates in which the node takes value of its ancestor which is just one level above it (its parent). So LCA of every segment containing it either changes just by one level or doesn't change at all.Thank you.
•  » » 16 months ago, # ^ |   +3 Take a look at Ticket 16840 from CF Stress for a counter example.
•  » » » 16 months ago, # ^ |   0 Thanks a lot mate! I forgot to take care of the set iterator after deleting element from it.
 » 15 months ago, # |   0 Can anyone tell me Why this gives the wrong output? 205025905 But when I change the insert process of set -ve it works? 205025843 . What stl problem is creating?
 » 10 months ago, # |   0 Problem D- Li Hua and Tree Can someone what's wrong in this implementation? Code#include using namespace std; #define LSOne(x) (x&(-x)) typedef long long int ll; typedef long double ld; ll t = 1; const ll M = 998244353; ll mod_add(ll a, ll b){ return ((a%M) + (b %M))%M; } ll mod_minus(ll a , ll b){ return ((a%M) - (b %M) + M)%M; } ll mod_mul(ll a, ll b){ return ((a%M)*(b%M))%M; } ll power(ll a, ll b){ ll ans = 1; while(b > 0){ if(b % 2 == 1){ ans = mod_mul(ans , a); } a = mod_mul(a , a); b = b/2; } return ans; } ll mod_inverse(ll a){ return power(a, M-2); } ll mod_divide(ll a, ll b){ return mod_mul(a , mod_inverse(b)); } const ll MAX = 1e18; ll lcm(ll a , ll b){ return (a*b)/__gcd(a,b); } const ll N = 1e5 + 10; ll n , m ; ll a[N]; ll sz[N], p[N], res[N]; bool comp(ll a, ll b){ return ((sz[a]> nadj(N, set(comp)); set adj[N]; void dfs(ll s){ sz[s] = 1; for(auto &x: adj[s]){ p[x] = s; adj[x].erase(adj[x].find(s)); dfs(x); sz[s] += sz[x]; } } void dfs2(ll s){ res[s] = a[s]; for(auto &x: nadj[s]){ dfs2(x); res[s] += res[x]; } } void solve(){ cin>>n>>m; for(ll i = 1;i<=n;i++){ cin>>a[i]; } for(ll i = 1; i>u>>v; adj[u].insert(v); adj[v].insert(u); } dfs(1); for(ll i = 1;i<=n;i++){ if(adj[i].size() > 0){ nadj[i].insert(adj[i].begin(),adj[i].end()); } } dfs2(1); for(ll i = 1; i<=m;i++){ ll type,x;cin>>type>>x; if(type == 1){ cout<>t; while(t--){ solve(); } } 
 » 5 months ago, # |   0 why My solution on problem B fails on test case 5 Here is my solution please explain me why?? my solution link is : https://mirror.codeforces.com/contest/1797/submission/250240610
 » 3 months ago, # |   0 For problem B, the image in the description about the rotation to 180 degrees, regarding the test case 2, doesn't seem right.