### chokudai's blog

By chokudai, history, 3 years ago, We will hold AtCoder Beginner Contest 160.

We are looking forward to your participation! Comments (173)
 » 3 years ago, # | ← Rev. 2 →   So why was the discuss about AtCoder written here？amazing！
•  » » Because community of atcoder is just a subset of CodeForces community.
•  » » » thanks a lot,I understand this now.
•  » » » » I'm sorry about asking such strange question.
 » Hope to get a good result!
 » Another Contest in Home quarantine :D
 » C001_scrambled for first test case. I am participating here for the first time. It throws RE.Can somebody help with the reason??
•  » » Can you give link to submission?C001_scrambled should be sample test case, by the way.
 » 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
•  » » The key observation to C is that the distance from last to first house is $k-a[n-1]+a$
•  » » » can you link your solution ? thanks
•  » » » » 3 years ago, # ^ | ← Rev. 2 →
 » 3 years ago, # | ← Rev. 4 →   Edit: Please Ignore. I didn't realize the contest was still going on.
•  » » Dude the contest isn't over, don't discuss
•  » » » 3 years ago, # ^ | ← Rev. 2 →   [edited]
•  » » » » This is no pretext. You can be held accountable for using unfair means in the court of law.
 » 3 years ago, # | ← Rev. 2 →   Very First time I solved Problem E myself in single attempt,Nice Contest! thanks for good contest
•  » » 3 years ago, # ^ | ← Rev. 3 →   solution please?
•  » » » Contest isn't over...
•  » » » C is greedy, D is brute force and E is also greedy.Hope that helps!
•  » » » 3 years ago, # ^ | ← Rev. 2 →   You can do E using Priority Queues.
•  » » » » 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.
•  » » » » » Subtle
 » Anyone please explain solution to problem F.
•  » » 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.
•  » » 3 years ago, # ^ | ← Rev. 3 →   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$.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   Can you give a more elaborate prove or some idea of how we get that formula.
•  » » » I got your point but i didn't understand how could you derive formula for answer for given root?
•  » » » » 2 years ago, # ^ | ← Rev. 6 →   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.
•  » » » » » Ok thanks for explanation.
•  » » » Awesome explanation thanks
 » Can anyone explain C problem statement was not clear to me ?
•  » » 3 years ago, # ^ | ← Rev. 4 →   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. SpoilerYou 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.
•  » » » 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.
•  » » » » 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.
•  » » » » » 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.
•  » » » » Yes, but just adding that you have to consider it as a loop at point K.
•  » » » » » Yes I understood. Thank you.
 » How to solve F? I can't even get close to a bruteforce solution of O(n*n).
•  » » 3 years ago, # ^ | ← Rev. 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...
•  » » » $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.
•  » » » » 3 years ago, # ^ | ← Rev. 4 →   Modular inverse is O(logM). The correct formulation of my complexity should be O(N logM), where M is 10^9 + 7.
•  » » » » » 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
•  » » » » » » 3 years ago, # ^ | ← Rev. 2 →   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.
•  » » » » » » » 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)
•  » » » » » » » » Wow, this was a nice trick.
•  » » » » » » » 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]!$
•  » » » » » » » » 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)$
•  » » » » » » » » » Ok thanks, I got it. We are only doing inverses of $1!, 2!, \ldots n!$
•  » » » » » » » » » 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)!$
•  » » » » » » » » » I think you meant $i!^{-1} = (i+1)!^{-1}(i + 1)$
•  » » » » » » » » » gupta_samarth yes, of course you're right
•  » » » » » » » Why not? I think can be quite easy to code.My Submission
•  » » » » » » » » 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.
•  » » » 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
•  » » » » That's why we divide by the product of s[i]!, to avoid further permuting the already permuted subtrees.
•  » » » » » 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 =(
•  » » » » » » Yeah it's stsize[i]... I made a small mistake in the explanation. Thanks for pointing it out!
•  » » » » » » can you explain the rerooting solution thanks
•  » » » » » » » 2 years ago, # ^ | ← Rev. 2 →   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 = dp$, 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.
•  » » » » » 3 years ago, # ^ | ← Rev. 5 →   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]!} . \ ...)$
 » 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.
•  » » So we have to read the statement carefully, because the case which the order is not important usually uses sorting.
•  » » » Yes.
 » I am just going to leave this here.Problem F
•  » » At atcoder, it's kind of difficult to have new questions (at least in beginner contests)
•  » » » 3 years ago, # ^ | ← Rev. 2 →   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.
•  » » » » Certainly, you are right.
•  » » Can you explain DP formula there? I can't get it...
•  » » » 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.
•  » » » » can you provide code?
•  » » » » » 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 = iF = 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 - 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 - 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; dfs2(1); f(i,1,n+1)cout<
•  » » » 3 years ago, # ^ | ← Rev. 2 →   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$. 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.
•  » » Damn, makes me miss CSAcademy: this kind of short statement problem was like lots of their other good quality problems :'(
 » Why this doesnt work ? https://atcoder.jp/contests/abc160/submissions/11310758Insert all elements in a vector and sort.
•  » » 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.
•  » » 3 years ago, # ^ | ← Rev. 3 →   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
•  » » 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.
 » What is an idea in task F? I don't get it? How to count it?
•  » » Hint: Tree Dp
•  » » 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
 » Where will the editorials to the problems be posted ? Somewhere on Atcoder site or on codeforces ?
•  » » 3 years ago, # ^ | ← Rev. 2 →   A tab labelled "editorial" should show up on the AtCoder itself.
•  » » See any of the past contest. You will get it.
 » Man, the re-rooting in F was tough. :(
 » 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.
•  » » That's what I did, took me 40 mins.
 » can somebody tell me which topics are used in d and e
•  » » d: brute force e: sort, greedy
•  » » 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.
•  » » » can you explain e in more detail?
•  » » » can you explain E with dp solutions?In contest, I think dp too but I solved it greedy.
•  » » » » 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.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   for D: implemented using bfs code But still getting TLE
•  » » » » 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
•  » » » » » still getting TLE code
•  » » » » » » 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]]++; 
•  » » » » » » » Got it! Thanks
•  » » » » 3 years ago, # ^ | ← Rev. 3 →   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) )
•  » » » Can you explain your dp solution for E ?
•  » » » 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
•  » » » » Can you explain ur modification ?
•  » » » » » 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.
•  » » » 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].
•  » » 3 years ago, # ^ | ← Rev. 2 →   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.
 » 3 years ago, # | ← Rev. 4 →   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 :(
 » 3 years ago, # | ← Rev. 2 →   Can someone explain a O(n) solution for D? I think there exists a linear time solution.
•  » » Answer is simply k-(maximum distance between two adjacent houses).code
•  » » » 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.
•  » » » » 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
•  » » » » » Oh that's problem C, not D =(.
•  » » » » » » 3 years ago, # ^ | ← Rev. 2 →   Damn forgive me. Actually he changed his comment
•  » » 3 years ago, # ^ | ← Rev. 4 →   https://atcoder.jp/contests/abc160/submissions/11292835 Runs in quadratic time for D. Can it be improved?
•  » » » why this solution has time complexity O(N)?I think that's O(N^2) with two for loop
 » 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?
 » Time to go to Codechef, #Quarantine
•  » » Hold rght there Sparky!!
 » 3 years ago, # | ← Rev. 2 →   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!
•  » » Why logN , it should be logM (M=1e9+5)
 » 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]++; } } 
•  » » 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.
•  » » » 3 years ago, # ^ | ← Rev. 3 →   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.
•  » » You mustn't count it twice
•  » » » 3 years ago, # ^ | ← Rev. 3 →   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.
 » 3 years ago, # | ← Rev. 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
•  » » 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
•  » » Thanks a lot. I finally understood solution to problem E after reading your explanation!
 » 3 years ago, # | ← Rev. 5 →   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.
•  » » Why do they divide?I don't understand it
•  » » 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!
•  » » » It is multinomial coefficient formula
 » How to solve D?
•  » » 3 years ago, # ^ | ← Rev. 2 →   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]$.
•  » » 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
 » So，How to slove the problem F？
 » so，how to solve the problem F？post
 » My linear solution for problem C:This code finds longest interval and subtracts from k. max = arr + (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);
 » Could anyone please link more problems like problem F (tree dp, rerooting)? Or could you please tell me where to find similar problems?
•  » » Found the following links which have relevant problems, thanks:
 » 3 years ago, # | ← Rev. 2 →   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
•  » » 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
•  » » » 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.
•  » » » 2 years ago, # ^ | ← Rev. 4 →   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.
•  » » » » You are right. I didn't notice it in the contest. Thanks!
 » 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.
•  » » You're using an unitialized value, c, and accessing the array with it: C[c-1]
•  » » » 2 years ago, # ^ | ← Rev. 2 →   My sample tests are running with it. They should also have a problem with c?Should I initialize c to some value?
•  » » The biggest N is 500000 but your array is A. I am not sure but I think this is the problem.
 » 2 years ago, # | ← Rev. 2 →   plz anyone explain the concept of problem-c?
•  » » 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.
•  » » Here is my linear solution if you want to take a look. https://atcoder.jp/contests/abc160/submissions/11318539
•  » » » Thanks brother.
•  » » » » You're welcome, brother.
 » can anyone explain question f?
•  » » i understood the question , no need
 » 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.
 » 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?
•  » » Check for overflow.You have declared sum as int try to change it to long long.
•  » » » Oh, I think I've seen accepted code with just integer sum but I was wrong. Thanks!
 » Any help for Task D. The editorial in AtCoder is in Japanese I think. And I am not able to understand that
•  » » For each vertex perform a BFS and calculate the distance to each other node and update their counts.
•  » » For International Readers: English editorial starts on page 7.for problem D: check editorial on page 10.
•  » » » Thanks a lot
 » Can someone explain how we reach the formula in the editorial of problem F? Thanks in advance!
•  » » 2 years ago, # ^ | ← Rev. 4 →   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
 » Supplementary editorial and sample codes for last 4 problems AtCoder ABC 160
 » 2 years ago, # | ← Rev. 4 →   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
 » 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???
 » can anyone tell about the problem b what is it asked?
 » can anyone please explain me what is the logic behind problem C. I can not understand the logic of this problem. Help someone.
•  » » 2 years ago, # ^ | ← Rev. 2 →   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.
 » 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 years ago, # | ← Rev. 2 →   E can be solved using ternary search as well.Link