### Akikaze's blog

By Akikaze, 12 months ago,

We apologize for the huge gap from F to G.
In the meantime, you can join the Discord server of AC — a competitive programming forum — here.

## 1305A - Kuroni and the Gifts

Author: Ari
Development: Ari, dorijanlendvaj
Editorialist: Ari

Tutorial
Solution (Ari, C++)
Solution (Akikaze, Java 8)
Solution (Akikaze, Python 3)

## 1305B - Kuroni and Simple Strings

Author: xuanquang1999 (remixed by antontrygubO_o)
Development: Ari, Kuroni, xuanquang1999
Editorialist: antontrygubO_o

Tutorial
Solution (Ari, C++)
Solution (Akikaze, Java 8)
Solution (Akikaze, Python 3)

## 1305C - Kuroni and Impossible Calculation

Author: antontrygubO_o
Development: antontrygubO_o, dorijanlendvaj, Kuroni, Ari
Editorialist: antontrygubO_o

Tutorial
Solution (antontrygubO_o, C++)
Solution (Akikaze, Java 8)
Solution (Akikaze, Python 3)

## 1305D - Kuroni and the Celebration

Author: Akikaze
Development: Akikaze, dorijanlendvaj
Editorialist: Kuroni

Tutorial
Solution (Akikaze, C++)
Solution (Akikaze, Java 8)
Solution (Akikaze, Python 3)

## 1305E - Kuroni and the Score Distribution

Author: antontrygubO_o
Development: xuanquang1999
Editorialist: antontrygubO_o

Tutorial
Solution (xuanquang1999, C++)
Solution (Akikaze, Java 8)
Solution (Akikaze, Python 3)

## 1305F - Kuroni and the Punishment

Author: Kuroni
Development: Ari, 265918, Kuroni, dorijanlendvaj, xuanquang1999
Editorialist: Ari

Tutorial
Solution (Kuroni, C++)
Solution (Akikaze, Java 8)
Solution (Akikaze, PyPy 3)

## 1305G - Kuroni and Antihype

Author: antontrygubO_o
Development: antontrygubO_o, Kuroni
Editorialist: antontrygubO_o

Tutorial
Solution (Approach #1) (kefaa2, C++)
Solution (Approach #2) (Kuroni, C++)

## 1305H - Kuroni the Private Tutor

Author: zscoder
Development: zscoder, ngfam, Kuroni, antontrygubO_o
Editorialist: zscoder

Tutorial
Solution (zscoder, C++)

• +155

 » 12 months ago, # |   +34 Wow! Thanks for very fast editorial and nice tasks!
 » 12 months ago, # |   0 I tried to do D using centroids, is it good idea?
•  » » 12 months ago, # ^ | ← Rev. 2 →   +12 No. Tests 6-12 should've stopped you.(all of them are that same test but with different labels. Some people still passed with random shuffle; i guess only 7 of such tests weren't enough...)Edit: now 50 more were added for upsolving but it's still possible to pass by abusing the fact that codeforces rejudges a solution 1-2 times if it gets TLE. Example(worked on second try, copied from 72346371): 72366491
•  » » 12 months ago, # ^ |   0 If the idea is to always query a centroid with a neighbor then we can easily fail the solution with a star tree with the root is one of the "leafs". For every query, you will remove only one vertex.
•  » » 12 months ago, # ^ |   0 Yes,I solved D using it.
•  » » 12 months ago, # ^ | ← Rev. 2 →   0 Yes, here's what I did- Find the centroid- If it's the only remaining node, it's the answer- If it has only one child, you can report the answer in 1 query- Otherwise find it's 2 largest children, call them c1 and c2. Query their LCA, if the answer is the centroid, we know the root is not in sub-trees of c1 and c2, so block them and all their children. If the answer is c1 or c2, block all the sub-trees of children of the centroid other than the answer (c1 or c2) This way, we are removing at least two nodes per query, so it passes.My solution: https://codeforces.com/contest/1305/submission/72333569
•  » » » 12 months ago, # ^ |   +5 Nice solution! And any node having more than one edge can replace the centroid in your algorithm. (My English is poor TAT)
 » 12 months ago, # |   +56 OMG, such a nice contest. F is really nice random task, I'm really love it. Thx Kuroni for it.
•  » » 12 months ago, # ^ |   0 non random solution for F: 72347794
•  » » 12 months ago, # ^ | ← Rev. 4 →   +30 In this problem there is one more solution with random. First of all, we know that the answer $\le n$. Consider the right answer: $a_1 + \Delta_1, a_2 + \Delta_2, \ldots, a_n + \Delta_n$, s.t. $\sum\limits_{i=1}^{n}|\Delta_i| \le n \Rightarrow$ the number of different $\Delta$ is $O(\sqrt{n})$. Then the probability of picking two different $i, j$ with the same $\Delta$ $\left(i \neq j, \Delta_i = \Delta_j\right)$ is $\Omega(\sqrt{n})$. Consider such $i, j$. We know that $gcd(a_i + \Delta_i, a_j + \Delta_j) = gcd(a_i + \Delta_i, (a_i + \Delta_i) - (a_j + \Delta_j)) = gcd(a_i + \Delta_i, a_i - a_j) = g > 1$ then $g$ is one of divisors of $(a_i - a_j)$. Algorithm: iterate the following thing $C\sqrt{n}$ times: pick two different random $i, j$, factorize the value $(a_i - a_j)$ and try all primes in factorization to update the answer (this part is the same as the authors solution). Thanks to dorijanlendvaj for finding corner case. There is situation when the optimal solution has the following form: $\Delta_i = \Delta_j \Rightarrow a_i = a_j$, but then the number of different $a_i$ is less than or equal to the number of different $\Delta$, so $O(\sqrt{n})$, also we know that there is such $i$ that $\Delta_i = 0$, in that case we can check all of the $a_i$'s. So, total time $O(\sqrt{n}(n + FACTORIZE)), FACTORIZE = O(\sqrt[4]{MAXX})$ with Pollard.Code
•  » » » 12 months ago, # ^ |   0 Why do we consider only primes?
•  » » » » 12 months ago, # ^ |   0 Because $(a_i + \Delta_i)$ divisible by $pq \Rightarrow (a_i + \Delta_i)$ divisible by $p$,$p, q$ are different primes.
•  » » » » » 12 months ago, # ^ |   0 But how can I prove that $p$ need less operations than $pq$
•  » » » » » » 12 months ago, # ^ |   +3 If you can make some a_i to be divisible by $pq$ using C operations then you can using the same $C$ operations make $a_i$ to be divisible by $p$)
 » 12 months ago, # |   0 Can someone explain C more efficiently?
•  » » 12 months ago, # ^ | ← Rev. 6 →   +18 Because of modular substraction porperty and modular multiplication property we can state that (a - b) % m is equivalent to ((a % m) - (b % m)) % m (a * b) % m is equivalent to ((a % m) * (b % m)) % m We can consider (ai — aj) % m to be ((ai%m) — (aj%m)) % m. So we can convert all elements of the array from a1, a2, a3, .... , an to a1%m, a2%m, a3%m, .... , an%m. Which means there can be atmost m different values in array. If the number of elements n is greater than m, then there must be some value which is repeated more than once (pigeon hole principal). So there will be some pair (ai, aj) where both elements are the same, hence absolute difference of that pair will be 0. Resulting in a product 0.Lets's consider n = 4 and m = 3. 4 3 1 3 4 5 We can look at this array like: 1 0 1 2 Here we have a pair (1, 1) whose absolute difference is 0. No matter what the 4 elements are, there will always be atleast one such pair.If n < m, then we can just check all pairs (as m is small enough, 1≤m≤1000) and compute the product.
•  » » » 12 months ago, # ^ |   -8 But here (a*b)%m can be interpreted as ( |ai — bj| * |ax — by| ) % m, where ai, ax, bj, by are elements of the array. So thinking about a1%m, a2%m ... and coming to solution does not seem to be intuitive.
•  » » » 10 months ago, # ^ |   0 Amazing explanation man...!! Thanks a lot..
•  » » » 11 days ago, # ^ |   0 wow thank you !! such a good explanation.
•  » » 12 months ago, # ^ |   -10 in the first case it is very easy to solve problem like this: int sum = 1; for (int i = 1; i <= n; ++i) { for (int j = i + 1; j <= n; ++j) { sum *= abs(a[i] - a[j]); sum %= m; } } in the second one we have that remainders under division by m are : 0, 1 ... m. So, if the number of elements is bigger than m, we will have repetetive remainders under division by m. You also can read about Dirichlet's principle here : https://en.wikipedia.org/wiki/Dirichlet%27s_principle
•  » » » 12 months ago, # ^ |   0 What's the problem in having repetitive remainders? How can one conclude from that, the asked summation result will be divisible by m due to this fact?
•  » » » » 12 months ago, # ^ |   +2 two numbers have the same remainder a[i],a[j] .(a[i]%m=a[j]%m) then (a[i]-a[j])%m=0.and it's not sum, it's multiply then the answer is always 0.
•  » » » » » 12 months ago, # ^ | ← Rev. 3 →   +3 But in this problem we were concerned about the absolute differences of the elements of the array, not the values itself. I can understand that (|a1-a2|*|a1-a3|*…)%m = (|a1-a2|%m)*(|a1-a3|%m)… but the problem is according to the solution |a1-a2| % m = |a1%m-a2%m| (I don't know if it is true or not). If it is true then I can start thinking about what happens when a1%m, a2%m … has repetitive reminder or not. Because then clearly two element having same remainder gives 0, and 1 0 means the whole multiple is 0. So given solutions are about what happens ai%m = aj%m for some i,j. But my confusion is how do you even get there from the given problem statement?
•  » » » » » » 12 months ago, # ^ |   +2 |ai-aj|%m!=|(ai%m)-(aj%m)|suppose a=(4 9) and m=7|4-9|%7=5 , while |(4%7)-(9%7)|=2what I said is (ai%m)=(aj%m) so |ai-aj|=k*m (k>=0) then |ai-aj|%m=0when you see (m<=1000) so you can brute force for n<=m to take all |ai-aj| for all i,j (i!=j) O(n^2).otherwise (n>m) in worst case the first m elements have difference remainder {0,1,2,..,m-1} and the next element has a remainder is already exist so take these two elements that have the same remainder, the absolute difference is multiply of m then the remainder is 0.
•  » » » » » » » 12 months ago, # ^ |   +3 Ok I see, ai % m = aj % m means ai and aj are congruent. Very nicely explained , thanks.
•  » » » » » » » 12 months ago, # ^ |   0 In this problem it is not written that all the elements are different, the correct solution is based on this fact. Explain the error in my reasoning. Thanks.
•  » » » » » » » » 12 months ago, # ^ | ← Rev. 2 →   0 .
•  » » » » » » » » 12 months ago, # ^ |   0 yes they are not, but the worst case is when the numbers are different.
•  » » » » » » » » 12 months ago, # ^ |   0 If two numbers are same then simply their difference will be 0.
•  » » 12 months ago, # ^ |   0 if(n > m) , it always exists a pair(i,j) (i < j) such that ai and aj have same modular with m.If(n <= m) you can find the solution in O(m^2)
•  » » 10 months ago, # ^ | ← Rev. 2 →   0 For case1 it's easy but the second case can be proved by pigeonhole principle. Since there are n numbers and each number can have reminder from 0 to m-1. Hence by pigeonhole principle there will be at least one value of remainder (out of 0 — m-1) for which # of numbers having that reminder will be greater than or equal to ceil(n/m) which is greater than 2 for n>m.
 » 12 months ago, # |   +1 Is there a way to solve C in $O(n)$?
•  » » 12 months ago, # ^ |   -24 You can use segment tree to solve the problem in O(NlogN)
•  » » » 12 months ago, # ^ |   +31 How? I don't see how to do range add update and range product query.
•  » » 12 months ago, # ^ |   +6 Afaik there is a solution in $O(n \log^{2} n)$ solution here.
 » 12 months ago, # |   +9 C's editorial is basically the greatest plot twist for me in Competitive Programming till date
 » 12 months ago, # |   +31 Problem C is literally the most genious thing I've seen in my entire life. Dont even regret about my -120
•  » » 12 months ago, # ^ |   0 One more like this.
•  » » » 12 months ago, # ^ |   0 It's not like this, and the only common link between them is perhaps taking modulo with m. But the intentions of modulo are very different. But thank you for acquainting me with such a beautiful and educational problem. I think I gained some IQ points solving "Modulo Sum" :)
•  » » 12 months ago, # ^ |   0 Pigeonhole principle is very useful and very nice technique.
 » 12 months ago, # |   0 Nice ;)
 » 12 months ago, # |   0 Nice problem A code:)
 » 12 months ago, # |   +16 All model solutions are now available.I'll try implementing Java8/Py3 variants of G and H soon, but not before having a sleep first. ;)
•  » » 12 months ago, # ^ |   0 I see the editorial is still missing a Python solution on G, so here is a PyPy2 solution of G 72758499 similar to the 2nd editorial solution, but using a DSU with $O(1)$ lookup time and amortized $O(\text{log} n)$ merge. My time complexity is therefore $O(3^m + n \, \text{log} n)$ with $m = 18$.
 » 12 months ago, # |   0 Damn, author's solution to D is so elegant! My approach was to query about any edge that is not in the current graph, then remove all the vertices up to the lowest common ancestor, and if the LCA is on this edge — remove everyone on the path apart from the LCA itself. I got a TL for it:)
 » 12 months ago, # |   +46 I think it's been a while since there was a contest with Boruvka. F is a great random problem too. Thanks everyone for making such a great problemset and excellent contest ^^.
 » 12 months ago, # | ← Rev. 2 →   +3 How to hack 72367869? I only managed to hack looping until $n$ instead of $100$ with a stress tester with $n=5$($n \leq 4$ didn't find any countercases to looping until $n$); I made a test which breaks that with $n=6$ test $100$ of test $2$, but i couldn't find any pattern from that test which extends well to larger $n$.
 » 12 months ago, # |   0 Probably B and C could have been swaped
 » 12 months ago, # | ← Rev. 2 →   0 In problem F, could someone elaborate more on how we calculated the probability of the solution being optimal if we pick a random x and try the prime divisors of x, x+1, and x-1?
•  » » 12 months ago, # ^ |   +20 • The answer to the problem is at most n• There can't be more than n/2 elements which are affected by >1 operations (answer would be more than n/2 * 2 == n) ==>• ==> There can't be less than n/2 elements affected by 1 or less operations• n/2 is the half of n so the probability of [picking an element which needs to be affected by 0 or 1 operation] equals to 1/2• So we pick a random element x and we're 50% sure it will stay x or become x±1• If we repeat it k times, it's (1/2)^k probability. So the question is just about what's the value of k (authors recommend k = 20)
•  » » » 12 months ago, # ^ |   0 Got it. Thank you.
•  » » » 12 months ago, # ^ |   0 Isn't it at most n assuming d=2? ,I don't get it. Can you please explain it more precisely?
•  » » » » 12 months ago, # ^ |   0 With d==2 the answer is always not bigger than n (the worst case is when we have all the numbers odd so we have to add ±1 to each of them).If d>2 (let's say d==D1) and for d==D1 the optimal answer is bigger than n. Then it doesn't make sense to choose d==D1, cuz for d==2 it always gives us smaller answer.
 » 12 months ago, # |   +3 When you realise why the range of $m$ is only $1<=m<=1000$: why didn't the author just use $m==10**9+7$"You sneaky bas#ard" :P
•  » » 12 months ago, # ^ |   +24 I saw that $M\le 1000$ and assumed that $N\cdot M$ was intended ...
•  » » » 12 months ago, # ^ |   +14 What's $N.M$
•  » » » 12 months ago, # ^ |   0 Mind explaining your solution?
•  » » » 12 months ago, # ^ |   0 I wrote the same solution as you, But I got TLE on 10th pretests.It looks very strange because in your solution there are N * M modulo operations. while I have only N modulo operations.72379501Even adding #pragma optimizations didn't help.What is the magic?
•  » » » » 12 months ago, # ^ | ← Rev. 5 →   +8 (That's because it's wrong lol)Seems to work with long longs 72381297 (see inc, binpow).
•  » » » » » 12 months ago, # ^ |   0 yeah, stupid lol
 » 12 months ago, # |   0 There's a mistake in the editorial in problem B. It should be a(i+1) <= a(k) < b(l) <= b(q-i)
 » 12 months ago, # | ← Rev. 3 →   +43 I have a possibly correct solution to problem F, it looks like brute force but it passed system test.It runs as follows: Firstly, find out every prime number less than or equal to $10^6$. Then, arbitrary choose an $a_i$, factorize all the numbers between $[a_i-n,a_i+n]$.(Because after performing all the operations, $a_i$ will be in this range) In the end, use brute force to check all the prime numbers. The only thing we need to do is to break in time:  ll ans=n; for(int i=1;i<=num;i++) { ll p=prime[i]; ll res=0; for(int j=1;j<=n;j++) { res+=a[j]ans)break;// break in time } ans=min(ans,res); } printf("%lld\n",ans); Such a solution could pass system test, but I don't know whether it's correct or not.Could anyone prove its complexity, or hack my solution?72344820
•  » » 12 months ago, # ^ |   0 My solution is the same to you.
•  » » 12 months ago, # ^ | ← Rev. 2 →   +9 It seems really brute...but it works...Your "break in time" guarantees the low complexity,cause it's impossible to construct a simple that for lots of a[i],you have to sum many "min(a[j]%p,p-a[j]%p)" before you break.For example:when "min(a[j]%p,p-a[j]%p) == i" , "a[j]+i" or "a[j]-i" should be multiples of "p".So the numbers of possible "p" for every "i" is "log(a[j]+-i)" , equal to the numbers of factors of "a[j]+i" or "a[j]-i" , and you can't find a lot of "p" for a small "i".The upper boundary of complexity in total maybe "sigma(n/i * log(max a[j]))" , that is "O(nlnn*log(max a[j]))".[sorry for my poor English and ignorance of markdown QAQ]
•  » » » 12 months ago, # ^ |   0 You are so strong!!! And your English is not poor!!! %%%
•  » » 12 months ago, # ^ | ← Rev. 2 →   0 Even better, if you pick a random index $i$ and check prime factors of numbers between $[a_i - 2, a_i + 2]$, we do get AC.
•  » » » 12 months ago, # ^ | ← Rev. 2 →   0 Maybe I can hack you?data: 5 169999847(=17*9999991) 169999847 169999847 169999847 300469729580(=(17+2*3*5*7*11*13)*9999991+3) The answer is to choose $9999991$, but if you pick $5$ you will miss the correct answer.In this way there is a possibility of $0.2$ that your solution get the wrong answer.Update: hacked successfully.72392250
•  » » » » 12 months ago, # ^ |   0 Is it still hackable with big n?
•  » » » » » 12 months ago, # ^ |   0 Yes. We can use $4x\ 16999847$ and $x\ 300469729580$.
•  » » 12 months ago, # ^ |   0 I did that but instead of res > ans, I compressed repeated elements and did res >= n for the breaking condition and it passed in 200ms.
 » 12 months ago, # |   0 the submission for problem B:72330449()(((())))()()())))() the data can hack it.
•  » » 12 months ago, # ^ |   0 it had been hacked.By the way,why some people also can hack somebody after the contest?
 » 12 months ago, # | ← Rev. 2 →   -18 Problem D is it given that given tree is a binary tree ?? and what exactly is the definition of root of a tree ?? i'm not getting it if it's not binary then what is root for 7 vertex 1 2 1 3 1 4 1 5 1 6 1 7
•  » » 12 months ago, # ^ | ← Rev. 2 →   +1 In graphs, a tree is an undirected connected graph without any loop. But a rooted tree is a tree with one vertex defined as the root. This is the tree you may be familiar with. Converting a tree to rooted is to consider the distance between each vertex and the root, this will become the depth of each vertex. In Problem D, the root was hidden and you are to find it out. On the tree you cited above, when we ask the LCA (lowest common ancestor) for vertex 2 and 3, it will be vertex 2 when the root is 2, and vertex 1 when the root is 7.
 » 12 months ago, # |   0 Can someone clearly explain why in problem F we should take prime divisors of x, x-1 and x+1?
•  » » 12 months ago, # ^ |   +1 It was proven that in optimal answer there are a lot of numbers, which should be changed on at most one. So after changes, a particular number x will be either $x$-1, or $x$, or $x+1$. If the gcd of all number is not one, all number should have some common divisor, particularly, this one number should also be divisible by this number. We could do now bruteforce over all divisors of $x$-1, $x$ and $x+1$. But it is too slow, so lets consider only primes. It works because if we got $s$ steps for having gcd divisible by $z$, then we can do still those $s$ steps(or maybe less), making gcd divisible by some prime of $z$.
 » 12 months ago, # |   +3 In problem B, in the prove of claim, why we must have k>i and l
 » 12 months ago, # | ← Rev. 2 →   +6 Could someone pls explain, in D task, why is number of queries less than n/2?
•  » » 12 months ago, # ^ |   +3 Also, I'll be grateful if someone suggest another approach to solve it
•  » » » 12 months ago, # ^ | ← Rev. 3 →   +1 .
•  » » » » 12 months ago, # ^ |   0 " int(n / 2) * n" should be " int(n / 2) * 2"
•  » » » » » 12 months ago, # ^ | ← Rev. 2 →   0 .
•  » » » » 12 months ago, # ^ |   +3 Understood, thanks!
 » 12 months ago, # | ← Rev. 2 →   0 For D,I found the diameter of the graph and queried for the vertices that formed the diameter.Then I removed those 2(or 1) edges from the lca vertex that led to the diameter vertex.I did this until the both the edges of the diameter were the same and outputted that vertex.Where can this approach fail?
•  » » 12 months ago, # ^ |   0 I had an idea that sounds like exactly the same one. In my opinion, there are no reasons why it should fail.Unfortunately, my practice implementation (72378820) got TLE and it is somewhat messy+inefficient, especially its finding-a-diameter part... And also I lost motivation about making it work (because now I know a simpler way of solving the problem D).The idea of taking any two leaves is really awesome, significantly simpler in implementation.
•  » » » 12 months ago, # ^ |   0 Yup, there is nothing wrong with the idea indeed. I got AC.
•  » » 12 months ago, # ^ | ← Rev. 4 →   0 The idea is almost the same as in the editorial (since first and last nodes of the diameter are obviously both leaves) but in your submission 72400841 you have bug in detecting if node belongs to a path from lca to one of the outputed nodes.Try test 5 4 1 3 1 2 1 1 5 Where the root is 4 (vertex that isn't 1 and wasn't outputed by your code in first query).Basically the solution is making always only one query and think that the answer is the given lca. It's pretty surprising it has made it to the 13 test.
•  » » » 12 months ago, # ^ |   0 Thanks for pointing that out.I forgot to mark the LCA as visited before identifying which children contained the vertices of the diameter and thus the dfs moved back into the lca and messed up the code.I still didn't get an AC, TLE at #27 so I guess I'll implement the editorial's approach.
•  » » » » 12 months ago, # ^ | ← Rev. 4 →   -8 Well, you're getting TLE brecause of calling (redundant) reset() after each rdfs call which makes your solution $O(N^2)$ (probably too slow with python and huge I/O including many flushes).UPD: Idk why I got downvotes for this, 72563170 sanvi_kiit's code without the reset calls gets AC
 » 12 months ago, # |   0 You said that we can fix any string with 0 or 1 operation for problem B.This is an example that you can't fix it with 0 or 1 operations : (((()))())
•  » » 12 months ago, # ^ |   0 Oh no.I was wrong.so sorry!
 » 12 months ago, # |   -8 Hi! I am stuck at 13th tc of D. I am not sure what's wrong with my logic. Can anyone help me with this?72420055Thanks in advance!
•  » » 12 months ago, # ^ | ← Rev. 2 →   0 Sorry If the comment seemed casual,I am not sure how to debug it... but I'm really stuck at this and 13th tc is quite big so not able to find the mistake.My logic: Find two leaf nodes (say x , y) and find their lca. Now two cases : - if x == lca or y == lca we have our answer. break and print ans - else delete all the nodes in both subtrees that connect to lca of x and y(done in solve func) and set y = lca and use another leaf node for xContinue this until no leaf node is left and we will have our ans.My logic is somewhat the same as editorial hence I don't know what's wrong.
•  » » 12 months ago, # ^ |   0 The only place where you do leaves.insert() is before your main loop.But when you erase nodes from a tree, some non-leaf nodes become leaves.I think you should probably add them to 'leaves' somewhere inside the loop.
•  » » » 12 months ago, # ^ |   0 Apart from LCA I don't think any node is getting set as leaf node after deletion, because the subtrees are attached to LCA at end and not affecting any other node.
•  » » » » 12 months ago, # ^ |   0 Then, the LCA itself becomes a leaf :)
•  » » » 12 months ago, # ^ | ← Rev. 2 →   0 I think I found the mistake , it's when I am taking LCA in the query , I should take LCA only when it's a leaf otherwise the other leaf node has a chance of being in it's subtreeEdit : Got Ac 72535927Thanks for Help!
 » 12 months ago, # |   0 Thanks for the contest and nice editorial <3
 » 12 months ago, # |   0 Can anyone explain the solution of problem D 1305D - Kuroni and the Celebration ? Editorial is not clear to me.
•  » » 12 months ago, # ^ |   0 What exact part did you feel unclear?
•  » » » 12 months ago, # ^ |   0 If we make our query like this process, doesn't it cross the query limit that is [n/2]? I understand the solution of editorial but don't get the point why query limit is not exceeded?
•  » » » 12 months ago, # ^ |   +8 I have found the answer of my question... Now it is clear to me. Thank you Akikaze for your response :)
 » 12 months ago, # |   0 can anyone let me know the meaning of the verdict "cost limit exceed" in problem d
•  » » 12 months ago, # ^ | ← Rev. 3 →   0 You used too many queries (exceeded the $\lfloor \frac{n}{2} \rfloor$ limit).
 » 12 months ago, # |   0 In D, why int last variable is used in function void purge() ??
•  » » 12 months ago, # ^ |   0 "last" here serves as the previously traversing node, to avoid repetitive recursive call.
 » 12 months ago, # |   +10 G's solution can be proved constructively and I think it's a bit more intuitive that way. The key idea is that if we root the tree of invitations at the ${n+1}$-th node, each non-root person is invited by their parent. It provides a bijection between trees and valid sequences of invitations.When a person joins, the gain is equal to the parent edge weight minus the joining person's age. Since each person joins once, it suffices to maximize the weights of the edges in the tree.
 » 12 months ago, # |   0 can someone tell me how to solve E.or atleast that(i-1)/2 case.
•  » » 12 months ago, # ^ | ← Rev. 3 →   0 Adding a number i will increase the count of triplets by ( i -1)/2. Suppose we have elements 1 2 .. adding 3 will increase the count by (3-1)/2=1 because 1+2=3. Now we have 1 2 3, adding 4 to the elements increases the count by (4-1)/2=1 because we have 1+3=4. Generally we take the current most left and the most right elements and add them and we get the new added element and then we take the next most left and the next most right elements and repeat the process. As if we are using two pointers starting from the first index and last index and every time we increment the left pointer and decrement the right pointer, then the sum of the 2 current elements gives us i. having 1 2 3 4 5 6 and then adding 7 , we have 1+6 , 2+5 ,and 3+4 = 3 triplets = (7-1)/2. That's the number of current elements divided by 2 which is the number of elements ( assuming all elements to be 1 2 3 ... i-2 i-1 ) before adding the new element which is i, so the count increases by ( i -1) "the current number of elements before adding i to them" / 2 , because the sum of every two elements gives us i. If you still don't get it or want me to further explain the complete solution, feel free to ask.
 » 12 months ago, # |   0 https://codeforces.com/contest/1305/submission/72570404 this submission of mine os showing wrong ans on t20. the correct answer on B t20 says only one bracket needs to be removed . someone please explain
 » 12 months ago, # |   0 Can someone please explain the proof of the $F$ ? Why the probability is $1/2^m$ if we pick only m elements and factorise them ?
•  » » 12 months ago, # ^ |   0 HipHop's comment is a clear explanation you might want to read.
 » 12 months ago, # |   0 Can someone explain what the purge function is doing in the solution of DIV2 D and why we are doing it ? Thanks in advance !
•  » » 12 months ago, # ^ |   +1 After asking a query $(u, v)$ and receiving the LCA $w$, the purge functions went in and delete every node (and edge) in the path from $u$ and $v$ towards $w$. If there's any nodes being separated after that, they'll be purged along as well.
•  » » » 12 months ago, # ^ |   0 Thank you for your reply !. Can you elaborate "If there's any nodes being separated after that" a little please ?
 » 12 months ago, # |   0 Can anyone please explain E?
•  » » 12 months ago, # ^ | ← Rev. 2 →   0 Sorry for any grammar mistakesAssuming You Understood until (i-1)/2 case by the commenthttps://codeforces.com/blog/entry/74459?#comment-587005Let's Say the Number of special triples until now as S (let it be < M). If we add the new number there are two cases S will still be less than M (in this case we continue to add the new number). S will be greater than or equal to M. In the second case, we need to figure out the number which will only add M-S Special triples.If we use two pointers, First Pointer as 2*(M-S)+1 and second pointer as index of the last number added to the list. Every time we increment the left pointer and decrement the right pointer. The sum of the two elements will always give us a single number M-S times. So will use this number as the next number.At this point, we achieved the desired balance. I think After this how to handle the rest of the numbers is neatly explained by ending section of this problem editorial.My Code
 » 11 months ago, # | ← Rev. 2 →   0 For Problem F, I couldn't understand this part."When we apply the optimal sequence of operations there are at least n/2 elements which are affected by at most one operation."A proof would be really helpful.
 » 10 months ago, # |   0 Can anyone please explain problem H in more detail ?
 » 8 months ago, # |   0 https://codeforces.com/contest/1305/submission/84656279 What changes do i need in my code..please explain me
 » 6 weeks ago, # |   0 can anyone please explain problem B.
 » 3 weeks ago, # |   0 Can someone please post the solution for E? It doesn't load for me.