chokudai's blog

By chokudai, history, 6 months ago,

We will hold AtCoder Beginner Contest 160.

We are looking forward to your participation!

• +97

 » 6 months ago, # | ← Rev. 2 →   -22 So why was the discuss about AtCoder written here？amazing！
•  » » 6 months ago, # ^ |   +4 Because community of atcoder is just a subset of CodeForces community.
•  » » » 6 months ago, # ^ |   0 thanks a lot,I understand this now.
•  » » » » 6 months ago, # ^ |   +1 I'm sorry about asking such strange question.
 » 6 months ago, # |   +2 Hope to get a good result!
 » 6 months ago, # |   +7 Another Contest in Home quarantine :D
 » 6 months ago, # |   +1 C001_scrambled for first test case. I am participating here for the first time. It throws RE.Can somebody help with the reason??
•  » » 6 months ago, # ^ |   0 Can you give link to submission?C001_scrambled should be sample test case, by the way.
 » 6 months ago, # |   +6 Either this is not one of my good days of programming or I don't know, i ussually do ABCD and now i can't do C
•  » » 6 months ago, # ^ |   0 The key observation to C is that the distance from last to first house is $k-a[n-1]+a[0]$
•  » » » 6 months ago, # ^ |   0 can you link your solution ? thanks
•  » » » » 6 months ago, # ^ | ← Rev. 2 →   0
 » 6 months ago, # | ← Rev. 3 →   -47 How to solve F, any hints ?
•  » » 6 months ago, # ^ |   +25 Dude the contest isn't over, don't discuss
•  » » » 6 months ago, # ^ | ← Rev. 2 →   -31 [edited]
•  » » » » 6 months ago, # ^ |   +7 This is no pretext. You can be held accountable for using unfair means in the court of law.
 » 6 months ago, # | ← Rev. 2 →   +10 Very First time I solved Problem E myself in single attempt,Nice Contest! thanks for good contest
•  » » 6 months ago, # ^ | ← Rev. 2 →   -27 how did you solve? can you give topic's name of c,d,e...please?
•  » » » 6 months ago, # ^ |   +8 Contest isn't over...
•  » » » 6 months ago, # ^ |   +7 C is greedy, D is brute force and E is also greedy.Hope that helps!
•  » » » 6 months ago, # ^ | ← Rev. 2 →   0 You can do E using Priority Queues.
•  » » » » 6 months ago, # ^ |   +9 I'm always amazed how low-rated people seem to give the name of the data structure they used rather than any substantial insight to the solution.
•  » » » » » 6 months ago, # ^ |   0 Subtle
 » 6 months ago, # |   +20 Anyone please explain solution to problem F.
•  » » 6 months ago, # ^ |   +8 The base of the idea is like this.Let's suppose there are two edges connecting node (x,y) and node (x,z) and the node x is root. And let's define the number of the nodes belonging to the y-rooted subtree(subtree whose root node is y), as A, and the number of the nodes belonging to the z-rooted subtree, as B.Now we can count the number of the ways in which writing 1 on vertex y(or z) and writing each of the numbers 2 ~ A(or B) on the nodes of the y(or z)-rooted subtree. Let's define this number as C, D each.In short, the number of ways writing A numbers on the nodes of y-rooted tree is C, and the number of ways writing B numbers on the nodes of z-rooted tree is D.In this case, the number of ways writing (A+B+1) numbers on y-rooted tree, z-rooted tree, and the node x is C*D*(A+B)!/A!/B!(It contains combination).Sorry for many definition.
•  » » 6 months ago, # ^ | ← Rev. 3 →   +26 First: answer for given root is: $\frac{n!}{s_1s_2\ldots s_n}$, where $s_i$ is size of subtree rooted at $i$. Why? Because a permutation is valid iff value at any node is less than any other value in its subtree, probability of this holding for specific node $i$ is $\frac{1}{s_i}$ and those are all independent.Now run dfs from one fixed root and calculate for each vertex size of its subtree. For any vertex $v$ except for the root let's consider two parts of the tree splits to when edge between $v$ and its parent. If the root is inside $v$ subtree size of upper subtree with size $n - s_i$ will be included in calculating the result, otherwise lower subtree with $s_i$ will. Thus for each such node we want to multiply all answers in its subtree by $\frac{1}{n - s_i}$. The latter is equivalent to multiplying all values by $\frac{1}{n - s_i}$, and those in $v$ subtrees by $n - s_i$. To perform sequence of operations: multiply all values in a subtree by $x$, and at the end extract value from each node we can just: whenever we multiply all values in a subtree multiply the value at its root only, and at the end use basic dfs to calculate for each vertex product of values on path from root to this vertex.EDIT: to be precise: the formula I described includes dividing by size of root's subtree, while the solution divides by all except for the root. Thus we need to divide answer for all vertices $n$.
•  » » » 6 months ago, # ^ | ← Rev. 2 →   +7 Can you give a more elaborate prove or some idea of how we get that formula.
•  » » » 6 months ago, # ^ |   0 I got your point but i didn't understand how could you derive formula for answer for given root?
•  » » » » 5 months ago, # ^ | ← Rev. 6 →   0 The basic idea is : for any tree the number of possible arrangements are (n-1)! (as we have to keep the node with smallest value at root of this tree) but since for any subtree of this tree(lets say u) there are not sizeu! but dpu possible arrangements so the answer(i.e. (n-1)!) has to be divided by sizeu! and multiplied by by dpu. Thus we get the above formula dpv = (vsize-1)!*k where k is product of dpu/(sizeu!) for all u such that u is a child of v. It is slightly similar to how we calculate the number of arrangements in a list of numbers with duplicates.
•  » » » » » 5 months ago, # ^ |   0 Ok thanks for explanation.
•  » » » 6 months ago, # ^ |   +6 Awesome explanation thanks
 » 6 months ago, # |   +3 Can anyone explain C problem statement was not clear to me ?
•  » » 6 months ago, # ^ | ← Rev. 4 →   +7 You have N cities around this lake and you can traverse it clockwise or anti-clockwise. You have to pass through every city and total distance travelled is sum of distances between every two cities in your path.In second sample, one city is in position 0 degrees ("north of the lake") and the last is in position 15. If you walked anti-clockwise (array is circular, remember), you could go from the 0-th city to the 2-th in 5 degress, because $(0 - 15) \ mod \ 20 = 5$.Solution. СпойлерYou can always ignore one path between two adjacent cities. Let's say you want to ignore $i$ to $i+1$, then you can do path $i \to 0$, $0 \to n-1$ and $n-1 \to i+1$.So basically you can just put all distances of adjacent cities in an array (including anti-clockwise distance from 0 to n-1, sort and then take the sum of the n-1 first ones.
•  » » » 6 months ago, # ^ |   0 Does this means the given array is the co-ordinates of the i-th house if we plot on x-axis? Correct me if I am wrong.
•  » » » » 6 months ago, # ^ |   0 Nope. The array gives yous the distance in terms of the perimeter of the circle.Think of this sample: 20 3 0 5 15 First house if in the top-most point of the circle, second house if 5 meters away (clockwise), then third house is 15 meters away (clockwise).Total perimeter is 20. So if you're in the first house and you travel 5 meters anti-clockwise, you get to the third house.
•  » » » » » 6 months ago, # ^ |   0 Thank you. Problem statement was very confusing to me. Even there explanation for sample was not very clear to me. And at last I was suffocated by number of submissions.
•  » » » » 6 months ago, # ^ |   0 Yes, but just adding that you have to consider it as a loop at point K.
•  » » » » » 6 months ago, # ^ |   +1 Yes I understood. Thank you.
 » 6 months ago, # |   0 How to solve F? I can't even get close to a bruteforce solution of O(n*n).
•  » » 6 months ago, # ^ | ← Rev. 2 →   +2 The O(N^2) solution is as follows:Root the tree at k. Now, we observe that this problem bijects to listing nodes in order such that all parents appear before their children. Let the number of ways to order nodes in the subtree of v be s[v]. We observe that through combinatorics, s[v] is the product of s[i] for all i that are children of v, multiplied by (stsize[v] — 1)!, divided by the product of s[i]!. The part with the factorials corresponds to the number of ways to order the different subtrees relative to each other. Thus, this can be solved in O(N) per root if we precompute the factorials and the multiplicative inverses.To speed up to O(N logN), a further idea is needed. (Hint: consider how to reroot the tree.)Edit: divide by the product of stsize[i], not s[i]. I'm a bit of an idiot...
•  » » » 6 months ago, # ^ |   0 $O(n log n)$? Why. It can be quite easily in $O(n)$. I guess your $O(n log n)$ uses some data structure like HLD, which is way more harder to implement than simple DFS.
•  » » » » 6 months ago, # ^ | ← Rev. 4 →   0 Modular inverse is O(logM). The correct formulation of my complexity should be O(N logM), where M is 10^9 + 7.
•  » » » » » 6 months ago, # ^ |   0 OK I forgot about this xD. My solution also works in $O(n log mod)$. We can of course precompute inverses of all numbers from $1$ to $n$ in linear time, so for "theoretical complexity" we can say it can be solved $O(n)$, but who would bother implementing it during the contest
•  » » » » » » 6 months ago, # ^ | ← Rev. 2 →   0 How does one compute inverse of numbers in linear time? I've never seen such an algorithm.Edit: apparently it's extended euclid and some dynamic programming idea. Yeah, I can see why no one would want to code it in contest time.
•  » » » » » » » 6 months ago, # ^ |   +3 That's one way, another is: if you want to compute inverse of $n$ numbers what you can do is: calculate their product, its inverse, products of numbers of each prefix and suffix. Inverse of one value is: inverse of product times product of all other, but all other is one suffix and one prefix so it's enough to calculate: inverse of product times suffix beginning one element after times prefix ending one element earlier.It works in $O(n + \log m)$(of course if you need such tricks to make your solution pass it means either model solution has better complexity, or time limit is insanely tight)
•  » » » » » » » » 6 months ago, # ^ |   0 Wow, this was a nice trick.
•  » » » » » » » 6 months ago, # ^ |   0 I'm not sure how precomputing the inverses would help. We will possibly need to compute the inverse mod $M$ of $n!$, so with the dp approach we might need to compute all inverses from $1$ to $M-1$. (in above, $s[i]$ is a subtree size, $O(n)$, and we are dividing by $s[i]!$
•  » » » » » » » » 6 months ago, # ^ |   0 No. First we compute $n! \mod m$ which is simply product of $n$ numbers modulo $m$ which takes linear time, then calculate inverse of this one particular number which takes $O(\log m)$
•  » » » » » » » » » 6 months ago, # ^ |   0 Ok thanks, I got it. We are only doing inverses of $1!, 2!, \ldots n!$
•  » » » » » » » » » 6 months ago, # ^ |   0 If we want to calculate inverses of all factorials we can simplify this trick a little bit. Calculate $n!$, its inverse and iterate over $i$ from $n$ to $1$ and use identity $i!^{-1} = (i+1)^{-1}(i + 1)!$
•  » » » » » » » » » 6 months ago, # ^ |   +10 I think you meant $i!^{-1} = (i+1)!^{-1}(i + 1)$
•  » » » » » » » » » 6 months ago, # ^ |   0 gupta_samarth yes, of course you're right
•  » » » » » » » 6 months ago, # ^ |   0 Why not? I think can be quite easy to code.My Submission
•  » » » » » » » » 6 months ago, # ^ |   0 This formula at first seems totally out of the blue, but if you do remember/understand it, than OK, it can be easy to code.
•  » » » 6 months ago, # ^ |   0 Could you please explain in a bit more detail s[v] is the product of s[i] for all i that are children of v, multiplied by (stsize[v] — 1)!, divided by the product of s[i]! ?I understand that $(stsize[v] — 1)!$ will give us permutations of relative subtrees, but doesn't it also count permutation of relative subtrees of different depths? Wouldn't that count bad permutations?Thanks
•  » » » » 6 months ago, # ^ |   0 That's why we divide by the product of s[i]!, to avoid further permuting the already permuted subtrees.
•  » » » » » 6 months ago, # ^ |   0 So shouldn't it be divide by product of stsize[i]!? Still, I can't see how that works ;_;. I understand the solution and I managed to code the rerooting thing and get AC, but I don't understand the DP recurrence =(
•  » » » » » » 6 months ago, # ^ |   +1 Yeah it's stsize[i]... I made a small mistake in the explanation. Thanks for pointing it out!
•  » » » » » » 6 months ago, # ^ |   0 can you explain the rerooting solution thanks
•  » » » » » » » 6 months ago, # ^ | ← Rev. 2 →   +7 Yea sure.You calculate $dp$ for one root (let's say 1). Then you do a DFS and each time you're going from node $u$ to node $v$, you want to reroot this tree, making $v$ its new root. So think like you're basically "rotating" this tree.So at first, you'll know that $ans[1] = dp[1]$, because you calculated $dp$ rooted at 1.So what changes? To calculate $dp[u]$, we use size of subtree rooted on $u$ and the size of all subtrees of its childs.So now $v$ is no longer a child of $u$, then $dp[u]$ will have to get rid of all of it's dependencies of $v$. Since $dp[u] = (size[u]-1)! * (\frac{dp[v1]}{size[v1]!} . \frac{dp[v2]}{size[v2]!} . \ ...)$Then we have to multiply $dp[u]$ by $size[v]!$.Additionally, $size[u]$ will change because $v$ is not a child of $u$ anymore, so $size[u] = size[u] - size[v]$. But that means that our $dp$ changes too, so you'll have to divide $dp[u]$ by $(size[u] - 1)!$, recalculate $size[u]$ and multiply it again by $(size[u] - 1)!$These changes apply to $dp[v]$ too! Now $u$ is a child of $v$, so $size[v]$ increases by (the old) $size[u]$ and you have to recalculate $dp[v]$.This makes MUCH more sense if you draw it on your notebook.After recalculating $dp[u]$ and $dp[v]$, $ans[v] = dp[v]$, you call dfs recursively to child $v$ (now it's as if you didn't do any rerooting and you had just calculated everything rooted at $v$).After the recursive calls end (you're back at node $u$, you restore $dp[u]$, $dp[v]$, $size[u]$ and $size[v]$. You can do this part in a smart way or just use some auxiliary variables.
•  » » » » » 6 months ago, # ^ | ← Rev. 5 →   +4 OOOOO! Maybe I got it!Out of $size[v]!$ possible permutations for a child v of u, we have $dp[v]$ good ones. That means that there's a $\frac{dp[v]}{size[v]!}$ probability for a permutation to be good.So let $vi$ be the $i$-th child of $u$.So out of a total of $(size[u]-1)!$ possible permutations for ALL children of $u$, we have a probability of $\frac{dp[v1]}{size[v1]!}$ of it being a good permutation from subtree of child 1, $\frac{dp[v2]}{size[v2]!}$ of it being a good permutation from subtree of child 2 and so on.So $dp[u] = (size[u]-1)! * (\frac{dp[v1]}{size[v1]!} . \frac{dp[v2]}{size[v2]!} . \ ...)$
 » 6 months ago, # |   0 I tried to implement E with given ordering of the apples, noticed a minute before end that it would be more wise to reorder them by deliciousness.
•  » » 6 months ago, # ^ |   0 So we have to read the statement carefully, because the case which the order is not important usually uses sorting.
•  » » » 6 months ago, # ^ |   +5 Yes.
 » 6 months ago, # |   +39 I am just going to leave this here.Problem F
•  » » 6 months ago, # ^ |   0 At atcoder, it's kind of difficult to have new questions (at least in beginner contests)
•  » » » 6 months ago, # ^ | ← Rev. 2 →   +3 You can debate that a problem of this caliber (not an easy problem btw) shouldn't be repeated. However I can understand that the problem looks like it can get repeated accidentally just thought I'd mention it.
•  » » » » 6 months ago, # ^ |   0 Certainly, you are right.
•  » » 6 months ago, # ^ |   0 Can you explain DP formula there? I can't get it...
•  » » » 6 months ago, # ^ |   +6 I didn't read the editorial however here is my solution.I am also too lazy to write any formulas but here is my solution.Let's assume that the tree is rooted so i need to calculate the number of topological sortings for this tree beginning at node 1 now let's assume that node $X$ has 1 child then $dp[X] = dp[child]$ i.e just append $X$ on the topological sorting of it's child. However in case $X$ has 2 children this means I have 2 arrays and I want to find the number of ways to merge them into one array such that the order of each array still stands meaning the $i-th$ number comes before the $(i+1)-th$ number array-wise, this can be done using stars and bars. this way I can merge any topological sorting with the current topolgical sorting of all previous children.After calculating $dp[X]$ for each node we calculate $dp2[X]$ for each node which is the answer for all the tree excluding the subtree rooted at $X$ this part should be pretty standard. then merge $dp[X]$ with $dp2[X]$ using stars and bars.
•  » » » » 6 months ago, # ^ |   0 can you provide code?
•  » » » » » 6 months ago, # ^ |   0 Sure#pragma GCC optimize ("O3") #pragma GCC optimize ("unroll-loops") #include "bits/stdc++.h" using namespace std; #define pb push_back #define F first #define S second #define f(i,a,b) for(int i = a; i < b; i++) #define endl '\n' using ll = long long; using db = long double; using ii = pair; const int N = 2e5 + 5, LG = 19, MOD = 1e9 + 7; const int SQ =225; const long double EPS = 1e-7; vector adj[N]; int n; int dpD[N]; int dpU[N]; int sz[N]; int F[N + N]; int iF[N + N]; int fast(int b, int e){ int res = 1; for(;e;e >>= 1, b = 1ll * b * b % MOD) if(e & 1) res = 1ll * res * b % MOD; return res; } int C(int n, int k){ if(k > n)return 0; return 1ll * F[n] * iF[k] % MOD * iF[n-k] % MOD; } int StarsAndBars(int ArraySize, int AddSize){ return C(ArraySize + AddSize, AddSize); } void init() { F[0] = iF[0] = 1; f(i,1,N + N){ F[i] = 1ll * i * F[i-1] % MOD; iF[i] = fast(F[i], MOD - 2); } } vector prefix[N], suffix[N]; vector prefixSz[N], suffixSz[N]; void dfs(int node, int par){ dpD[node] = 1; if(node != par) adj[node].erase(find(adj[node].begin(), adj[node].end(), par)); for(auto child : adj[node]){ dfs(child, node); dpD[node] = 1ll * dpD[node] * dpD[child] % MOD * StarsAndBars(sz[node], sz[child]) % MOD; sz[node] += sz[child]; prefix[node].pb(dpD[node]); prefixSz[node].pb(sz[node]); } reverse(adj[node].begin(), adj[node].end()); int curSz = 0; int curDp = 1; for(auto child : adj[node]){ curDp = 1ll * curDp * dpD[child] % MOD * StarsAndBars(curSz,sz[child]) % MOD; curSz += sz[child]; suffix[node].pb(curDp); suffixSz[node].pb(curSz); } reverse(suffix[node].begin(), suffix[node].end()); reverse(suffixSz[node].begin(), suffixSz[node].end()); reverse(adj[node].begin(), adj[node].end()); sz[node]++; } int ans[N]; void dfs2(int node){ for(int i = 0; i < adj[node].size(); i++){ int curDp = dpU[node]; int curSZ = sz[1] - sz[node]; if(i != 0){ curDp = 1ll * curDp * prefix[node][i-1] % MOD * StarsAndBars(curSZ, prefixSz[node][i-1]) % MOD; curSZ += prefixSz[node][i-1]; } if(i + 1 != adj[node].size()){ curDp = 1ll * curDp * suffix[node][i+1] % MOD * StarsAndBars(curSZ, suffixSz[node][i+1]) % MOD; curSZ += suffixSz[node][i+1]; } dpU[adj[node][i]] = curDp; dfs2(adj[node][i]); } ///merge dpU[node] and dpD[node] ans[node] = 1ll * dpU[node] * dpD[node] % MOD * StarsAndBars(sz[node]-1, sz[1] - sz[node])%MOD; } int32_t main(){ #ifdef ONLINE_JUDGE ios_base::sync_with_stdio(0); cin.tie(0); #endif init(); cin >> n; f(i,1,n){ int u, v; cin >> u >> v; adj[u].pb(v); adj[v].pb(u); } dfs(1, 1); dpU[1] = 1; dfs2(1); f(i,1,n+1)cout<
•  » » » 6 months ago, # ^ | ← Rev. 2 →   +3 Suppose you have a rooted tree with $1$ as the root. Let $dp[x]$ equal the number of ways to distribute $|x|$ consecutive values on the subtree rooted at $x$, with the lowest value assigned to $x$. Then for leaves this equals 1, and we want $dp[1]$. If node $r$ has $k$ children $n_1,\ldots,n_k$, then think about first putting the lowest value at $r$, and then distributing the remaining $|r|-1$ values on the subtrees. A way to do this is to distribute values on each individual subtrees, and then "interleaving" these distributions. So you get the product $dp[n_1]dp[n_2]\cdots dp[n_k]$ times multinomial coefficient $C(|r|-1,[|n_1|,|n_2|,\ldots,|n_k|])$, where the multinomial coefficient gives the number of ways to interleave the distributions from different subtrees.Then for other roots, use re-rooting.
•  » » 6 months ago, # ^ |   +5 Damn, makes me miss CSAcademy: this kind of short statement problem was like lots of their other good quality problems :'(
 » 6 months ago, # |   0 Why this doesnt work ? https://atcoder.jp/contests/abc160/submissions/11310758Insert all elements in a vector and sort.
•  » » 6 months ago, # ^ |   +9 Because coloring all the colorless apples red, before coloring any of them green is not always optimal.Ex.: 2 1 2 2 2 2 2 1 1 10 10 The answer is 22, but your code gives 21.
•  » » 6 months ago, # ^ | ← Rev. 3 →   +6 I didn't go through your whole code, but here is what I did. First sort A, B, C array in descending order. Make a new array(Let it be F) by taking the first X and first Y of B. Sort the new array F in descending order. Now try replacing the smallest element of F by the largest element of C. Do it until Del(Ci) — Del(Fj) > 0.(Why? Because If we replace now, our sum will decrease). Here is my simple implementation: Submission
•  » » 6 months ago, # ^ |   +1 When you use a colorless apple you must decide which color it has to become based on which color has the worst apple who was being eaten before coloring this one(because that's the one you want to discard). If you mix all the apples you don't get to choose by this criteria and fail to reach maximum value.
 » 6 months ago, # |   0 What is an idea in task F? I don't get it? How to count it?
•  » » 6 months ago, # ^ |   0 Hint: Tree Dp
•  » » 6 months ago, # ^ |   0 Think, of a node N with two children X,YYou already know the size of the subtree on each child, and the number of ways you can label it.Since N is a parent of X,Y N should get the lowest number. And among the remaining you've to choose which are going to each child and multiply by the ways to label on each child.That will give you the solution for a particular root, use re-rooting after
 » 6 months ago, # |   0 Where will the editorials to the problems be posted ? Somewhere on Atcoder site or on codeforces ?
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 A tab labelled "editorial" should show up on the AtCoder itself.
•  » » 6 months ago, # ^ |   +1 See any of the past contest. You will get it.
 » 6 months ago, # |   +16 Man, the re-rooting in F was tough. :(
 » 6 months ago, # |   0 For problem F, I think I can use dp to get the answer for $numberofways(root)$, for an assignment starting with "1" at some fixed root. The expression has a multinomial coefficient so worst case has a $\log n$ factor, for a total of $O(n\log n)$. Then I think the answer for a node adjacent to root can be obtained from the above answer, by changing some individual factors. It seems the total number of such changes as I change from node to node will equal the sum of degrees, so the answer should stay $O(n\log n)$. Can someone who solved it tell me if this is a good approach because I feel like it would take too long to implement.
•  » » 6 months ago, # ^ |   +3 That's what I did, took me 40 mins.
 » 6 months ago, # |   0 can somebody tell me which topics are used in d and e
•  » » 6 months ago, # ^ |   0 d: brute force e: sort, greedy
•  » » 6 months ago, # ^ |   0 The key observation in D is that we cannot use Floyd-Warshal because it gives TLE, and then we implement BFS wich works better $O(n^2)$E is dynamic programming.
•  » » » 6 months ago, # ^ |   0 can you explain e in more detail?
•  » » » 6 months ago, # ^ |   0 can you explain E with dp solutions?In contest, I think dp too but I solved it greedy.
•  » » » » 6 months ago, # ^ |   0 I did read the problem now once again... and noticed that I still got it wrong."You are going to eat X red apples and Y green apples." I took this as in first place we eat x+y red/green apples, then we eat anoter c ones, from which we can choose to color them red/green as long as there are some of them left.
•  » » » 6 months ago, # ^ | ← Rev. 2 →   0 for D: implemented using bfs code But still getting TLE
•  » » » » 6 months ago, # ^ |   0 You should not use a vis[] array. Instead, push nodes to the queue whenever relax, ie whenever you found a new min distance to that node.for example see code
•  » » » » » 6 months ago, # ^ |   0 still getting TLE code
•  » » » » » » 6 months ago, # ^ |   0 Ah, ok, it is the way you count the distances for every k. That makes it $O(n^3)$Note that the max distance between two nodes is n, so you can make and array of that size and run once throug the two-dimensional array. Basically you do then ans[dist[i][j]]++; 
•  » » » » » » » 6 months ago, # ^ |   0 Got it! Thanks
•  » » » » 6 months ago, # ^ | ← Rev. 3 →   0 You can use Dijkstra's algorithm for sparse graphs : https://cp-algorithms.com/graph/dijkstra_sparse.htmlbasically using normal dijkstra, using priority queue / set to extract min node. Complexity will be O(V^2log(V) + EVlog(V) )
•  » » » 6 months ago, # ^ |   +1 Can you explain your dp solution for E ?
•  » » » 6 months ago, # ^ |   +2 For D, we can use Floyd Warshal with a little modification. https://atcoder.jp/contests/abc160/submissions/11317101 E can be done with a greedy approach. https://atcoder.jp/contests/abc160/submissions/11318492
•  » » » » 6 months ago, # ^ |   0 Can you explain ur modification ?
•  » » » » » 6 months ago, # ^ |   +1 What Floyd Warshal does in every iteration is that it picks a vertex and for all pairs of points,it updates the shortest distance between them passing through the iteration point and thus after all iteration, the adjacency matrix will have the min distance between i,j. In our problem,we only have one other edge i.e x,y so, instead of taking iterations over all points, we only consider them through that edge and the main path. Thus,we only have 2 loops and one statement inside them instead of the third loop. I hope this helped.
•  » » » 5 months ago, # ^ |   0 I don't think you need bfs also. Just use the idea of floyd warshall algorithm and prove that the shorter path will only consists of the X and Y vertices only. So instead of iterating k from 1 to n , you just use k as X and Y only. mat[i][j]=mat[i][x]+mat[x][y]+mat[y][j] if mat[i][x]+mat[x][y]+mat[y][j] < mat[i][j].
•  » » 6 months ago, # ^ | ← Rev. 2 →   +7 Nothing! simple observation.my_D (without any Bfs/Dfs) just simple HashMap you can use array too to store. for any (i,j) pair distance(k) will be k=min(abs(i-x)+abs(y-j)+1,abs(i-j)); just store it and finalyy print it.my_E just sort and pick TopMax x+y having constrain that you can't pick more than x from red and more than y from green apples respectively.
 » 6 months ago, # | ← Rev. 4 →   +10 Brief Solutions: Simple check ---- O(1) The answer will 1000*(n/500)+5*((n%500)/5) ---- O(1) For every starting position i, the distance will be a[n-1]-a[i]+(i-1>=0?(k-a[n-1])+a[i-1]:0). Then take the minimum for all i — O(n) Form a graph, and then run bfs starting from each node. Then count the nodes at a distance k for every k. Since, every pair (i, j) appears twice, divide the answer by 2. Perhaps there exists a O(n) someone can explain. — O(n^2) First sort set A, B, C. Greedily take top x apples from set A, top y apples from set B and then atmost top (x+y) apples from set C. Sort them and take the top (x+y). — O(AlogA+BlogB+cLogC+(x+y)log(x+y)) I couldn't solve myself :(
 » 6 months ago, # | ← Rev. 2 →   +3 Can someone explain a O(n) solution for D? I think there exists a linear time solution.
•  » » 6 months ago, # ^ |   0 Answer is simply k-(maximum distance between two adjacent houses).code
•  » » » 6 months ago, # ^ |   0 Why is tha true? I pondered for like 10 minutes to try and find an O(n) solution and just gave up and coded N BFS searches haha.
•  » » » » 6 months ago, # ^ |   0 You see it's a circle and to travel all the houses you are basically not gonna traverse an arc of the circle.Being greedy you want that arc to be of maximum length, that is why we subtract maximum arc length.Hope that helps
•  » » » » » 6 months ago, # ^ |   0 Oh that's problem C, not D =(.
•  » » » » » » 6 months ago, # ^ | ← Rev. 2 →   0 Damn forgive me. Actually he changed his comment
•  » » 6 months ago, # ^ | ← Rev. 4 →   0 https://atcoder.jp/contests/abc160/submissions/11292835 Runs in quadratic time for D. Can it be improved?
•  » » » 6 months ago, # ^ |   +1 why this solution has time complexity O(N)?I think that's O(N^2) with two for loop
 » 6 months ago, # |   0 For E I first considered the approach: Put all colored apples in a vector and sort by their value (and maintain their type as the second value in this pair). Also put colorless apples in a priority queue. Then for each apple in this vector, if its value is better than the biggest one in the priority queue and you can still get apples of this type, get it, otherwise get the top of the priority queue.But this idea could be hacked using the following input: 2 2 2 2 2 10 2 9 1 5 1 Because array would be like 10 9 2 1 and red apple with value 2 would be replaced with colorless apple with value 5.So then I considered getting best colored ones (in that case 10 and 9) while colorless weren't worth it and then replacing what's left with colorless from smallest to biggest value (in this case, 5 would replace blue apple with value 1), but this approach failed =(.So what's wrong with this last idea?
 » 6 months ago, # |   0 Time to go to Codechef, #Quarantine
•  » » 6 months ago, # ^ |   +2 Hold rght there Sparky!!
 » 6 months ago, # | ← Rev. 2 →   0 The editorial says there there is an O(N) solution for F.However, if I am not mistaken, the computation of multiplicative inverse is needed, which is O(logN). Thus, shouldn't it be O(N logN) overall?Edit: oops, I meant logM. Thanks to ahshafi for pointing out my mistake!
•  » » 6 months ago, # ^ |   0 Why logN , it should be logM (M=1e9+5)
 » 6 months ago, # |   0 Why this approach doesn't work for D ( I got 5 WA ) for (int i = 1; i <= n; i++) { for (int j = i + 1; j <= n; j++) { int distance_direct_path = j - i, distance_bridge_path = abs(x - i) + abs(y - j) + 1; ans[min(distance_bridge_path, distance_direct_path)]++; if (distance_direct_path == distance_bridge_path) ans[distance_direct_path]++; } } 
•  » » 6 months ago, # ^ |   0 You are double counting when you check whether distance_direct_path is equal to distance_bridge_path. They are the same pair, and thus should only be counted once.
•  » » » 6 months ago, # ^ | ← Rev. 3 →   0 You are right I got accepted but I dont understand isn't when distance_direct_path == distance_bridge_path in this case we have 2 differents shortest paths from i to j, so we need to count them both ?EDIT:My bad the answer is the number of pairs and not the number of paths.
•  » » 6 months ago, # ^ |   0 You mustn't count it twice
•  » » » 6 months ago, # ^ | ← Rev. 3 →   0 Why we have 2 differents shortest paths, one direct path and the other path using the extra edge, so we need to count them both ? EDIT:My bad the answer is the number of pairs and not the number of paths.
 » 6 months ago, # | ← Rev. 2 →   +2 Brief solnA : Do it.B : Greedy.C : perimeter — longest interval length.D : There might be more efficient ways, but for this problem size of input ($n = 2,000$) is small enough to run $n$ BFS and just add everything. This gives $O(n^2)$ algorithm.E : Take $X$ best red and $Y$ best green. Now, from these, we can replace some of these to colorless ones to get better result. while we can improve (smallest in bag < largest colorless out of bag), we improve greedily. If we look at colorless one from biggest to smallest, we can easily maintain with priority queue. Code is easier than explaining. https://atcoder.jp/contests/abc160/submissions/11286026F : We root the tree at 1 and solve for 1. Note that what we compute is actually number of permutations which does not violate order of tree. Consider some statement like this. If a subtree rooted at node 5 has (5, 6, 7, 8, 9), in the final permutation, 5 must be the first of subsequence (5, 6, 7, 8, 9) where order of 6,7,8,9 does not matter. If we throw any permutation at random, we have 1/5 chance sufficing this criterion. Observe that sufficing one statement does not change probability of sufficing another, so we compute answer for 1.By DFS, we can compute $f(a, b)$ where $a$ is parent of $b$, $f(a, b)$ = number of nodes in subtree rooted at $b$. With this notation, we can write the answer above as $n!$ divided by some product of $f$s. When we change root to something adjacent of current node, note that exactly 2 edge changes it's 'direction'. We can compute all values in $O(n)$ dfs calls, but I implemented $f$ function with map so my solution is $O(n \log n)$. https://atcoder.jp/contests/abc160/submissions/11298787
•  » » 6 months ago, # ^ |   0 I think there is another O(n^2) solution not using BFS in problem D. We can figure out the shortest path from vertex A to vertex B (A
•  » » 6 months ago, # ^ |   0 Thanks a lot. I finally understood solution to problem E after reading your explanation!
 » 6 months ago, # | ← Rev. 5 →   +4 So here's how I solved F(got AC just after contest has ended) :(Let as solve for a specific node x as root which has p children:Let it's children be x1,x2,x3...,xp respectively. Let their subtree sizes be s1,s2,....sp respectively.Obviously we have to distribute s1 numbers to subtree rooted at x1, s2 numbers to subtree rooted at x2,..... , sp numbers to subtree rooted at xp.Thus we have the following recursive solution: solve(x)=solve(x1)*solve(x2)*....*solve(xp)* (NUMBER OF WAYS TO DISTRIBUTE n-1 NUMBERS TO SETS OF s1,s2,....,sp).The last value is a simple combinatorics problem which is equal to (n-1)!/(s1! * s2! *....sp!).The factorials can be precomputed and thus we can get the value for a particular root in O(n * log(n) ) time. (log term for doing modular inverse of factorials).The values for remaining nodes can be found by re-rooting technique.
•  » » 6 months ago, # ^ |   0 Why do they divide?I don't understand it
•  » » 6 months ago, # ^ |   0 Your solution seems much simpler than others.Could you please again explain it with more details?specially the this part.(n-1)!/(s1! * s2! *....sp!
•  » » » 6 months ago, # ^ |   +2 It is multinomial coefficient formula
 » 6 months ago, # |   0 How to solve D?
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 You can build graph and run one BFS for each node and get minimum distances (this is possible because $N \leq 2*10^{3}$ so you can do $O(N^{2})$. Then brute force each pair (i, j) and sum $1$ to k-th answer, where $k = dist[i][j]$.
•  » » 6 months ago, # ^ |   +1 You can calculate the distance for every pair of nodes in the graph with N BFS (for every node). After that, you will have a matrix dist of distances, where position [i][j] represents the distance from i to j. Then, you just count the number of times the k-th distance appears above the main diagonal of the matrix. vector counter(n); for(int i=0; i
 » 6 months ago, # |   +3 So，How to slove the problem F？
 » 6 months ago, # |   0 so，how to solve the problem F？post
 » 6 months ago, # |   0 My linear solution for problem C:This code finds longest interval and subtracts from k. max = arr[0] + (k - arr[n - 1]); for(int i = 0; i < n - 1; i++){ max = max < arr[i + 1] - arr[i] ? arr[i + 1] - arr[i] : max; } printf("%lld", k - max);
 » 6 months ago, # |   +9 Could anyone please link more problems like problem F (tree dp, rerooting)? Or could you please tell me where to find similar problems?
•  » » 6 months ago, # ^ |   +5 Found the following links which have relevant problems, thanks:
 » 6 months ago, # | ← Rev. 2 →   +3 Problem D can be solved in $O(N)$.Hint: use difference array and prefix sum. SpoilerFor each vertex, all the distances from other vertexes to it can be separated into several arithmetic sequences. Each arithmetic sequence adds $1$ to an interval of the answer array.My Submission
•  » » 6 months ago, # ^ |   -6 Oh, I only got an $O(n^2)$ solution using an algorithm like bucket sort. I didn't think about using difference array and prefix sum:(Perhaps my algorithm is easier to code, but its efficiency is very low...My code is below: #include using namespace std; const int maxN=2005;int n,x,y,s[maxN][maxN],ans[maxN],t[maxN*maxN]; int main() {cin>>n>>x>>y; for (int i=1;i
•  » » » 6 months ago, # ^ |   0 I think this should the intended solution. Actually I coded exactly this $O(n^2)$ solution in contest. Here I'm just discussing a better solution after contest.
•  » » » 6 months ago, # ^ | ← Rev. 4 →   0 A slight modification can bring down space usage. We can avoid using the 2d array s by directly incrementing corresponding index in t.Maximum distance is only N-1, not N^2. So, T's size can just be linear instead of quadratic.
•  » » » » 6 months ago, # ^ |   0 You are right. I didn't notice it in the contest. Thanks!
 » 6 months ago, # |   0 https://atcoder.jp/contests/abc160/submissions/11326931This is my submission for problem C ,can anybody tell me why i am getting a runtime error on the testcases. I am new to programming ,please help.
•  » » 6 months ago, # ^ |   0 You're using an unitialized value, c, and accessing the array with it: C[c-1]
•  » » » 6 months ago, # ^ | ← Rev. 2 →   0 My sample tests are running with it. They should also have a problem with c?Should I initialize c to some value?
•  » » 6 months ago, # ^ |   0 The biggest N is 500000 but your array is A[20000]. I am not sure but I think this is the problem.
 » 6 months ago, # | ← Rev. 2 →   0 plz anyone explain the concept of problem-c?
•  » » 6 months ago, # ^ |   0 Imagine that there are houses on one side of a circular road. Let's call those houses A, B, C, D, E, F, G. You want to traverse all of the houses. You can traverse clockwise or anti-clockwise and the problem wants you to calculate the distance of the shortest path. You can start from any house it doesn't matter. Don't forget that this road is circular so house A comes after house G.
•  » » 6 months ago, # ^ |   0 Here is my linear solution if you want to take a look. https://atcoder.jp/contests/abc160/submissions/11318539
•  » » » 6 months ago, # ^ |   0 Thanks brother.
•  » » » » 6 months ago, # ^ |   0 You're welcome, brother.
 » 6 months ago, # |   0 can anyone explain question f?
•  » » 6 months ago, # ^ |   0 i understood the question , no need
 » 6 months ago, # |   -14 Just stay at your home and start coding, better for you & your family and your society, it may be a chance for you to increase your problem solving skillsI HOPE EVERYONE TO HAVE SAFE LIFE.
 » 6 months ago, # |   +3 I don't know why this approach doesn't work for E. ( I got 6 WA )Here is my solution: https://atcoder.jp/contests/abc160/submissions/11367454Is there anyone who save me?
•  » » 6 months ago, # ^ |   +3 Check for overflow.You have declared sum as int try to change it to long long.
•  » » » 6 months ago, # ^ |   +3 Oh, I think I've seen accepted code with just integer sum but I was wrong. Thanks!
 » 6 months ago, # |   +3 Any help for Task D. The editorial in AtCoder is in Japanese I think. And I am not able to understand that
•  » » 6 months ago, # ^ |   +3 For each vertex perform a BFS and calculate the distance to each other node and update their counts.
•  » » 6 months ago, # ^ |   +3 For International Readers: English editorial starts on page 7.for problem D: check editorial on page 10.
•  » » » 6 months ago, # ^ |   +3 Thanks a lot
 » 6 months ago, # |   +3 Can someone explain how we reach the formula in the editorial of problem F? Thanks in advance!
•  » » 6 months ago, # ^ | ← Rev. 4 →   +3 Let $size[u]$ be the size of the subtree rooted at node $u$. Consider you're starting the process in node $u$. Then the number of answers for $u$ is the number of possible permutations of size $size[u]$ such that a child never comes before its parent in this permutation. Why is that? Because if we start at $u$. We write $1$ on it, then we go to its children, write first number between $2$ and $size[u]$ that hasn't been written yet and so on. So a child's number will never be smaller than its parents in this permutation.Now to get to the $dp$ formula, read this: https://codeforces.com/blog/entry/75262?#comment-594252
 » 6 months ago, # |   +3 Supplementary editorial and sample codes for last 4 problems AtCoder ABC 160
 » 6 months ago, # | ← Rev. 4 →   +3 There is another solution to E! I'll introduce another variable,N,and assume N,A,B,C,X,Y all have magnitude 1e5,to show time complexities. Brute Force(the big idea)Brute force the nomber of white apples you color red.Then,sort all remaining white&green apples in order and pick Y of them.Use prefixsums to optimize.Time Complexity:O(n^2 long n).Not so good. Optimization 0Use a multiset to maintain all remaining white apples,but that's still O(n^2 log n)... Optimization 1We can actually use 2 multisets:A and B.A contains the best Y apples,while B contains the remainder.We also keep a sum of the top Y apples.When we're deleting an apple with deliciousness of i(coloring it to red),there're 3 cases: Case 1.i is not in A Remove i from B.No changes in sum. Case 2.i is in A and in B(that only happens when there are a lot of occurrences of apples with deliciousness i) Remove i from B too.No changes in sum. Case 3. Remove i from A.Put the best element in B to A.The sum will change and delta is easy to calculate.Complexity:O(n log n)!Yeah!Here's my code
 » 6 months ago, # |   0 for problem d the editorial provided has this formula min{|j −i|, |X −i|+ 1+|j −Y |, |Y − i| + 1 + |j − X|}. for the computing the shortest distance between vertex i and j. even if we don't use the second part of the formula which is "|Y − i| + 1 + |j − X|" the computed ans will always be the shortest path between the vertex i,j. i used similar concept and got accepted. can anyone explain me why the second part of the formula is not used or maybe the test cases provided would be too weak???
 » 6 months ago, # |   0 can anyone tell about the problem b what is it asked?
 » 6 months ago, # |   0 can anyone please explain me what is the logic behind problem C. I can not understand the logic of this problem. Help someone.
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 The problem 'Find the minimum distance that needs to be traveled' is equal to subtract the maximum distance between two adjacent houses from K. You shoud think about how to calculate the distance between the first house and last one.
 » 3 months ago, # |   0 Can anyone tell me how can we solve C if i can go in both direction in the same time? or if anyone have a link for a problem with a similar idea.in other words i can go to the left two cities then go to the right for all cities i believe it's obvious that this would give a shorter distance sometimes? or am i wrong?
 » 2 months ago, # | ← Rev. 2 →   0 E can be solved using ternary search as well.Link