### chokudai's blog

By chokudai, history, 9 months ago, ,

We will hold AtCoder Beginner Contest 133.

The point values will be 100-200-300-400-500-600.

We are looking forward to your participation!

• +36

 » 9 months ago, # |   +6 Thanks for organizing!I hope this will be my last (rated) ABC. :)
•  » » 9 months ago, # ^ |   +7 Good luck ! I hope that you continue to participate in future too and more importantly provide English Tutorial for the contest :D. It helps others a lot !
•  » » » 9 months ago, # ^ | ← Rev. 2 →   +8 Thanks, your comment meant a lot to me. And I'll try my best to have an English editorial for this contest out today.Edit: check out Geothermal's write-up here: https://codeforces.com/blog/entry/68231.
•  » » » » 9 months ago, # ^ |   +11 I have to say that i really enjoy your editorial and i am thankful for that.
•  » » 9 months ago, # ^ |   +3 Did ur dreams come true?
•  » » » 9 months ago, # ^ | ← Rev. 2 →   0 We'll see, haha, there are still a couple AGCs before the next ABC. Thanks for asking!
 » 9 months ago, # |   +11 How to solve F?
•  » » 9 months ago, # ^ |   +5 I solved it using Persistent Segment Tree.
•  » » » 9 months ago, # ^ |   0 Can you explain your solution more detailed, please?
•  » » » » 9 months ago, # ^ | ← Rev. 3 →   +3 You can have a look at https://atcoder.jp/contests/abc133/submissions/6297869 The basic idea is to keep track of sum of all edges having a particular colour and no of edges of that particular colour from root to all the vertices.
•  » » 9 months ago, # ^ |   +3 We essentially use LCA with square-root decomposition. A more detailed description of my solution is at https://codeforces.com/blog/entry/68231.
•  » » » 9 months ago, # ^ |   +5 I did F using LCA with Euler Tour+Segment Tree.Time Complexity — $O(n*log^2(n))$My Submission
•  » » » » 9 months ago, # ^ |   0 Can you explain your solution more detailed, please?
•  » » 9 months ago, # ^ |   +8 I solve by sqrt-decomposition of path (something like LCA).
•  » » 9 months ago, # ^ | ← Rev. 2 →   +10 We can also solve it using BIT maintaining the Eulerian order of the tree.Let $dis(u,v)$ be the sum of $d$ from $u$ to $v$ on the original tree. We have $Q(x,y,u,v) = dis(u,v) + \sum_{e \in path(u,v),color(e) = x} cst(e) + \sum_{e \in path(u,v),color(e) = x} 1$Thus, we can solve queries with the same $x$ together. Use two BITs to maintain $\sum_{e} cst(e)$ and $\sum_e 1$. Modify it before and clear it after printing answers to them.It works in $nlogn$ time.Actually, my solution is the fastest so far:D
•  » » » 9 months ago, # ^ | ← Rev. 2 →   +8 My idea was exactly same. I did it in Online mode.My in contest submission is slowest so far. :D
•  » » 9 months ago, # ^ |   0 I think it can be solved in $O(n\ log(n))$.like this My Submission
•  » » » 9 months ago, # ^ |   0 My solution works in logn time
•  » » 9 months ago, # ^ |   +8 I had an online solution with LCA, Eulerian tour and prefix sums. The idea seems to be similar to those of 11235813213455.Let's write down an Eulerian tour over edges (counting them with "+" when going down and with "-" when going up). We store prefix sums for all the edges ("large" array), and for edges of each specific color ("small" arrays). When answering the query, we split the path into two parts and consider only paths from LCA to each vertex. To find an answer, we need total path length and the contribution of the specific color. But it's just a sum on a segment (on "large" array or on one of the "small" arrays). Also, to find the bounds of the segment on a "small array", we can store which edges appear in this array and then perform a binary search.The code is here.This solution is $O(N\log N)$. It's neither the slowest, nor the fastest :)
 » 9 months ago, # |   0 How to solve E?I solved F with sqrt-decomposition but didn't find any ideas in E
•  » » 9 months ago, # ^ |   +19
•  » » 9 months ago, # ^ | ← Rev. 5 →   +8 For E you could use multiplication principle. Start with the root. We have k choices here. Now the first child will have k — 1 choices, second will have k — 2 and so on. But while calling dfs for children keep track of how many siblings of the node you traversed. Because for node x all its siblings wont have an effect on children of x. Just work it out you will get it. One more thing for depths greater than 3 the dependency on the node higher than current nodes by 2 will not be there.
•  » » 9 months ago, # ^ |   +1 Root the tree arbitarily. If you are at the root. You can assign the color for the root in K ways and its children in (K-1)P(degree[root]) ways. For the other vertices you can assign the colors for its children in (K-2)P(degree[vertex]-1) ways.
 » 9 months ago, # |   +1 How to solve Problem D??
•  » » 9 months ago, # ^ | ← Rev. 2 →   +14 It was a system of linear equation. We had equations in the format. x1+x2=a1 x2 +x3=a2 . . . xn + x1=an But if you add and subtract first n-1 terms alternately. You will always get x1-xn = alternate sum of n-1 terms. Using this and last equation we can get x1 and now x2 and x3 and so on till xn can be ascertained
•  » » 9 months ago, # ^ |   +6 Let's denote the water in dams from 1 to $n$ as $x_1,x_2...x_n$ and the water on each mountain as $y_1,y_2...y_n$.Then the equations read as $x_1=(y_1+y_2)/2$, $x_2=(y_2+y_3)/2$, . . . $x_n=(y_n+y_1)/2$ Now see that $x_1-x_2+x_3-x_4+...x_n=y_1$ From $y_1$ we can successively find $y_2,y_3$ so on by substituting in the original equations.
 » 9 months ago, # | ← Rev. 2 →   +9 Two things. Since in the last few ABCs some people have volunteered for editorials it would be nice if you can add the link of such editorials in the announcement. Was E a case of coincidence?
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 E was a problem from codejam semifinals(2008) but with slight reduction in constraints http://www.manchik.co.uk/problem/32010/2
 » 9 months ago, # |   0 I got C wrong, Test case 16, stride_zero_01. I dont get it. Can somebody tell me what is wrong? Thanksresult
•  » » 9 months ago, # ^ | ← Rev. 3 →   0 2 2020 Your answer is 2, but the correct answer should be 0.I guess that you can't just swap l and r after l %= 2019 and r %= 2019.
•  » » 9 months ago, # ^ |   +2 Swapping l and r if l > r is incorrect. 6 2024 is a countercase: your solution prints 30; the correct answer is 0.Adding 2019 to r in this case should fix the error.
•  » » 9 months ago, # ^ |   +2 Modulos is circular. After taking modulo of l and r with 2019, if r > l then also answer can be zero. For ex. lets take l = 2 and r = 29 and taking mod with 5 , then after taking modulo with 5 , r = 4 and l = 2 , but here answer will be 0 as r became 4 after 3 or 4 round of modulo circle.
•  » » 9 months ago, # ^ |   +2 Your code gives 2 as output for l=1 and r=2023, ans should be 0(i=1,j=2019) The problem is SpoilerYou should check whether floor(l/2019) and floor(r/2019) are same or not. If they aren't, answer is 0 because a number between l and r is divisible by 2019.
•  » » » 9 months ago, # ^ |   0 This testdata is better than others, my submission code can accept 2 2020, 6 2024. But cannot accept this data.MY CODE ON ATCODER
•  » » » » 9 months ago, # ^ |   0 This is because my code turned into 1 and 4, and this causes error to my code
•  » » 9 months ago, # ^ |   0 It is enough to have all 2019 modulos of 2019 number. After it you can calculate minimum product of all modulos. In loop from l to r you calculate current module, when you size of modulos reaches 2019 you break from loop. Then you can calculate minimum product.
•  » » 9 months ago, # ^ |   0 I have a simple solution. If the distance between l and r is greater than 2019 then it will certainly contain a factor of 2019 and hence the answer will be zero. Otherwise we can calculate by brute force.
 » 9 months ago, # |   0 How to solve Problem F??
•  » » 9 months ago, # ^ |   0 No body can reply this?
•  » » » 9 months ago, # ^ |   0 Actually, you can find the solution of this problem by click the url below solution
•  » » » » 9 months ago, # ^ |   0 Thx
 » 9 months ago, # |   0 Can some explain F in simple words i know about sqrt decomposition but was unable to come up with the solution
 » 9 months ago, # |   0 Can anyone explain the logic behind E.
•  » » 9 months ago, # ^ | ← Rev. 5 →   +5 I will try to phase it so that everyone can understand. We will use multiplication principle of counting. Step number one consider any node(preferably 1) as root. We can color it in k ways. Now if I consider its children they cannot be colored in the same color as its parent(as a matter of fact no child can be colored with the same color as its parent). Now for any node, if it has sibling(same parent), it will have a distance of 2 from its sibling. So if a parent can be colored in $m$ ways, its first child can be colored in at least $m - 1$ ways(I will come to why more), second child at least $(m - 2)$, third $(m - 3)$ ways and so on. If you consider a set of nodes with same parent, the nodes among themselves cannot be colored with same color because they have a distance of 2 within them but their children, will have distance 3 from the other sibling hence, will be independent. To understand, this point consider following connections:1 21 32 4Here 2 and 3 children of 1 cannot have same color but 3 can have same color as 4 which is 2's child. So how to consider this in multiplication principle? Simple when you call dfs on unvisited children keep track of how many new nodes you found, if you found $c$ new nodes, then if you call the dfs on the $(c + 1)^{th}$ new node, you send that information onto it as a function parameter in a variable $siblingExplored$, so that when you call the child of the node it can get the correct multiplication factor. Let's run our example on an example. n = 5, k = 4 edges: 1 21 33 44 51 can be colored in 4 ways.2 can be colored in remaining 3 ways.3 can be colored in 2 ways(different from 1 and 2)now when we explored 3 we said can be colored in 2 ways, that doesn't mean 4 will be colored in only 1 way, but since we explored 1 child node of parent node 1, we went onto 3, we noted that 2 affects one but we sent that information(of having explored 1 sibling before) onto 3, so the multiplication factor of 4 remained 2 because 2 no longer affects it. And for nodes with height greater than 2 we will not reduce the multiplication factor by 1. Why because even though the number of possible colors are decreasing by 1 but at the same time, the dependecy on parent 3 levels up is also vanishing. codevll g[MAX]; bool vis[MAX]; ll ans = 1; void dfs(ll cur, ll k, ll d, ll ck, ll nbv) { vis[cur] = true; if(d > 2) k++; // cout << cur << ' ' << k << endl; ans = (ans * k) % mod; if(k) { bool p = true; ll nv = 0; for(auto x : g[cur]) { if(!vis[x]) { dfs(x, k - 1 + nbv, d + 1, ck, nv); nv++; k--; } } } } Parameter ck is useless ignore it
 » 9 months ago, # |   0 Hi! Can someone please share their approach and solution to problems C and D — I got stuck at a step in both of them. Also would be great if editorials can be provided for all problems, would help in upsolving. Thanks!
•  » » 9 months ago, # ^ |   0 Here is one written by Geothermal : https://codeforces.com/blog/entry/68231
 » 9 months ago, # |   0 can anyone solve problem B without brute force or use any nice property. Thanks...
 » 9 months ago, # |   +1 Official editorials are available here
 » 7 months ago, # |   0 Problem F: I used lca to range min query (using sparse table) inorder to find the distance between any two vertices in O(1). I ran DFS from any arbitrary source node, and storing the number of colors I can use for every node (color[i] = total_unassigned_color + number_of_vertices_that_have_been_visited and whose distance is > 2)I am getting TLE for most of the cases, i understand the the reason. But I'm also getting Wrong answer for two test cases and Run Time Error for two test cases. Can any one explain me what is going on?here is Link of my submissionhttps://atcoder.jp/contests/abc133/submissions/7205633