### kenechi's blog

By kenechi, history, 6 weeks ago,

Note :- The contest ended on 8 Aug

Here are the problems :-

Problem 1
Problem 2
Problem 3
Problem 4
Problem 5

It would be a great help if anyone could provide ideas about solving problem 3 and problem 5. Please share problems similar to problem 5 if anyone has seen such kind of problem before. Thanks

• +11

 » 6 weeks ago, # |   0 vector>th; vectorchild; map,int>ed; #define ll long long int mod =(int)1e9+7; map,ll>hw; ll as = 0; void dfs(int u,int p=-1){ ll ans = 0; for(auto x:th[u]){ if(x==p)continue; dfs(x,u); ans+=child[x]; } child[u] = ans+1; if(p!=-1){ int wh = ed[make_pair(p,u)]; if(wh<=0){ as= 1LL*(as%mod + 1LL*(1LL*(1LL*(wh+mod)%mod*(child[u]%mod))%mod+mod)%mod); as%=mod; }else hw[make_pair(p,u)] = 1LL*((1LL*wh%mod*(1LL*child[u]%mod))%mod+mod)%mod; } } int Solution::solve(int a, vector > &b, int k) { th = vector>(a+1); ed.clear(); hw.clear(); as=0; for(int i=0;i(a+1,0); ll sum =0 ;dfs(1); vectorv; for(auto x:hw){ v.push_back(x.second); // cout<
•  » » 6 weeks ago, # ^ |   0 Your logic is correct, I did the same, here's my code. Spoiler#include using namespace std; using ll = long long; #define endl '\n' map, ll> mp, cnt; const int mxn = 1e5 + 1; std::vector edg[mxn], visi(mxn, 0), sz(mxn, 0), par(mxn, -1); int dfs(int u, int p){ visi[u] = 1; par[u] = p; int ssz = 1; for(auto x : edg[u]){ if(x==p) continue; ssz += dfs(x, u); } return sz[u] = ssz; } signed main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);z ll n;cin>>n; for(int i = 0; i < n - 1; ++i){ int x, y, z;cin>>x>>y>>z; mp[{x, y}] = z; mp[{y, x}] = z; edg[x].push_back(y); edg[y].push_back(x); } dfs(1, 0); int c;cin>>c; vector ans; for(int i = 2; i<=n; ++i){ ll val = mp[{i, par[i]}]; ans.push_back(val*sz[i]); } sort(ans.begin(), ans.end()); while(c--){ ans.pop_back(); } ll sm = 0; for(auto x : ans){ sm += x; } cout<
 » 6 weeks ago, # |   0 Where was this contest held ?
•  » » 6 weeks ago, # ^ |   +1
 » 6 weeks ago, # |   +8 If possible post a text version, it is hurting my eyes when I try to read it
 » 6 weeks ago, # |   0 can u also post the given test cases for problem 5.
 » 6 weeks ago, # |   +4 Does anyone know how the 5th problem will be solved?
 » 6 weeks ago, # |   0 Please post solutions/editorials of 3rd and 5th question.
•  » » 6 weeks ago, # ^ | ← Rev. 6 →   +10 Tagging kal013 as he was the only one who solved third question, I referred generating function blog written by zscoder but I could only Calculate for specific n and small n(around 1000). I could not solve for each i from 1 to n, in the 3rd question,as it's very complex maths and also not available on oeis, so it might be some sieve related calculation Also tagging sudobug,nagpaljatin1411 please help me here for 5th question.
•  » » » 6 weeks ago, # ^ |   +3 My 5th Question Approach:- Since all the leaf nodes were at same level, so we needed to see for how many seconds continuously a node would drop fruits(call it Ans of Node) [As there was no such case where it'd not drop fruits continuously]. While in a dfs, for a node, I calculated the [Sum] of fruits it recieved, and the [Max] number of fruit it recieved from all it'd children nodes. The Ans of a Node was [Max]-min([Sum]-[Max],it's capacity). You had to return Ans of Node[1] + the Depth of Leaf Nodes - 1.
•  » » » » 6 weeks ago, # ^ |   0 The Ans of a Node was [Max]-min([Sum]-[Max],it's capacity). You had to return Ans of Node[1] + the Depth of Leaf Nodes - 1. I am unable to understand this can you pls explain.
•  » » » » » 6 weeks ago, # ^ |   0 I'd explain by an example, You have a Node say i (which is not a leaf node) with it's children's Ans being 5, 8, 15 respectively. Now you know, that atleast for 15 seconds, Node i would constantly drop fruits, which leaves you with 13(15+8+5-15) fruits after 15 seconds. Now if your capacity is something less than 13, say 9, then fruits would fall for 9 more seconds (the 4 would fall directly to ground), else it'd fall for 13 more seconds. It doesn't matter, when the 4 fruits fall to the ground. Note that Ans of Leaf Nodes is equal to the Number of fruits they have i.e. A[i].Now for the Actual Answer which you had to return, The 1st Fruit from Leaf Node takes 'Depth-1' time to reach the Node-1, Now if Root was leaf Node, then Ans would have been Ans of Node-1, and if it's not, then the answer is Ans of Node-1 +depth-1.
•  » » » » » » 6 weeks ago, # ^ |   0 thanks ,i got it
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   +5 My $O(Nlog^2 N)$ solution for problem 3:N here is the maximum limit for which all answers have to be found.Let $f(n,g)$ be ways of choosing permutations such that each cycle length is a multiple of g. Let $h(n,g)$ be ways such that gcd of the cycle lengths = $g$. The final answer is the $\sum_{g=1}^{n} g * h(n, g)$ for any $n$ ( $h(n, g) = 0$ if $g$ does not divide $n$).Now we have the following relation: $\sum_{k=1}^{\frac{n}{g}} h(n,k*g) = f(n,g)$If we are able to calculate $f(n,g)$ over all pairs ${g, n}$ such that $g | n$, then we can calculate $h(n, g)$ in $O(N log ^ 2 N)$, by noting that for each ${g, n}$: $h(n, k*g)$ is $0$ if $k*g$ does not divide n or $k$ is not a divisor of $\frac{n}{g}$.So by iterating only over factors of $\frac{n}{g}$, we can see that for each $g$, number of steps taken will be $\sum_{i=1}^{\frac{N}{g}} numberOfFactors(i) = O(\frac{N}{g} log \frac{N}{g})$Summing this over all g, we get the desired complexity.Now to calculate $f(n,g)$, choose size of cycle containing $n$. If the size is $k*g$ then ways = $\binom{n - 1}{kg -1} * (kg -1)! * f( n - kg, g) = (n - 1)! * (\frac{f(n - kg, g)} {(n - kg)!})$$f(n, g) = \sum_{k = 1}^{\frac{n}{g}} (n - 1)! * (\frac{f(n - kg, g)} {(n - kg)!})$This can be computed in $O(N log^2N)$ by using the previous trick or in $O(N log N)$ by maintaining a running sum of $\frac{f(n - k*g, g)}{(n - k *g)!}$
•  » » 6 weeks ago, # ^ |   0 zeus_orz zeus_iitg please help us with 3rd and 5th question.
•  » » 6 weeks ago, # ^ |   +5 For the 3rd problem, evilbuggy described a solution that solves for a fixed $N$ (not for all $N$ from $1$ to $N$) in $\mathcal{O}(N \log n \cdot \mathtt{div} N)$. textConsider the tuple (c_1, c_2, ... c_n) (also known as cycle structure) corresponding to a given permutation where c_i denotes number of cycles of length i in the permutation.Number of permutations which have given cycle structure (c_1, c_2, ... c_n) is equal to n!/((1^c_1 * c_1!)(2^c_2 * c_2!) .... (n^c_n * c_n!)) (Well known problem)The generating function of this is equal to f(t_1, t_2, ... t_n) = e^{t_1 x + (t_2 x^2)/2 + (t_3 x^3)/3 + (t_4 x^4)/4 + .....) (Again a well known problem)Number of permutations whose cycle lengths are divisible by k is equal to coefficient of x^n in f(0, 0, ... t_k, 0, 0, ...t_2k, ...) (Substitute 1 at t_k, t_2k, ....)Then it's just mobius shit after thisI guess the time complexity is O(n log(n) tou(n)) where tou(n) is number of divisors of n img
 » 6 weeks ago, # |   0 Where is the ranklist?
 » 5 weeks ago, # |   0 for the 1st question can't we solve the question greedily using bfs instead of dfs where for each edge we calculate the effective weight depending on the number of adjacent nodes that its child has.