Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

Recent actions
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 36 hours ago 0 Can anyone provide information? Pls
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 36 hours ago 0 I received a notice of violation from the Codeforces system. https://codeforces.com/contest/1901/problem/D for my solution in this problem. But I didn't do anything wrong. How appropriate is this?
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 2 days ago 0 or you can always choose x = max + 1
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 3 days ago 0 Thanks for your help! Didn't know about CF Stress. I got it why my answer was wrong.
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 3 days ago 0 Thanks
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 3 days ago 0 Take a look at Ticket 17158 from CF Stress for a counter example.
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 3 days ago 0 Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 3 days ago Created or updated the text
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 3 days ago 0 Can anyone tell why my D is wrong my approach was to choose the index with maximum value in the beginning and then choose the smallest value which can be reached from that index and also 2 cases which start from beginning and start from end. This is my solution 234114731
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 3 days ago 0 In problem D, you are under-estimating the actual amount of damage monsters will take. How are you sure that would yield a correct answer?
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 3 days ago 0 To solve this on contest you just need to notice that in this problem your operation is choosing subarray and decreasing all values in it by $1$.
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 3 days ago 0 The task B is:you have an array $a_1,a_2,\ldots,a_n$. One operation use choose $[l,r]$ and decrease all $a_i$ by $1$ ($l \le i \le r)$.This is basic problem. Answer is $\sum\limits_{i=1}^{n+1} \frac{|a_i - a_{i-1}|}{2}$, where $a_0 = a_{n+1} = 0$.
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 3 days ago 0 Those are not the only cases. For example, in an array with 5 elements (1-indexed), if you start at index 3, you can also go 3->4->2->5->1. At any moment in time, if there are 2 indexes that you've not visited adjacent to indexes that you have visited, you can go in either one of the 2, that's why it's important to account for all possible ways. But yes, in the solution, you're basically assuming the worst case scenario, that is, if the index is to the left of the starting element you're assuming it first went to the right and only then came left so that by the time it reaches that index, the power will be the minimum. The same goes for when the index is to the right of the starting index, only in reverse.
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 3 days ago +18 Rating Updated! :)
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 3 days ago 0 so basically if we choose index 'i' so there are two possiblites that either go to the right of till end and the the other half and another one like go to left of i to the start and then go for the other half ?
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 3 days ago 0 me who builded a segment tree on D for no appearant reason
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 3 days ago +2 Please Update the Rating !
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 3 days ago +5 Please post the editorial.
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 3 days ago +5 update the rating !
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 3 days ago +5 Update the rating!
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 3 days ago +3 Update the rating!
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 3 days ago +13 When will we get the editorials and ratings change BledDest/awoo? Thank you.
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 3 days ago +5 I hope so. I should become green (Im trusting carrot).
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 3 days ago +5 Has this contest become unrated? It is showing as unrated in ratings graph.
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 3 days ago +3 will the rate updated before the upcoming codeton contest
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 3 days ago 0 sometimes it takes a couple of hours
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 3 days ago 0 thx
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 3 days ago 0 just wait for a few days and it will change.
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 3 days ago 0 I participated this contest but my rating didn't change. Why?
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago 0 A simple logic for the problem c : if max_element of array is even then we add 1 to array otherwise add 0 234215511
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago 0 this round is rated or unrated idk. I think this round unrated because rate not given soooo longgg
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago 0 I Have completed 1 problem successfully still didn’t get any rate.It's showing unrated.why so!!
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago 0 One of the best edu rounds.
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago 0 Thanks LightBrand99 for the explanation. For problem B could you please guide through your thought process (ie, how you came up with the above solution)? my thought process - couldn't solve with thisEach isolated hill (asc and desc sequence) can be accounted separately (this is straight forward which is just height of hill (above the line of connection to another hill)). Only connecting of hill needs to be handled for hill to hill relation. But I couldn't think how to get min no of operation to account for the connections
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago 0 If you start at index 4 with power 7 you than kill the index 5 with power 6 and the index 6 with power 5, now you don't have enough power left to kill the monster at index 4. Remember, since the monster killed is chosen randomly between the 2 options possible (or 1 if there are no 2 possible options), you have to account for the worst case scenario. Sure, power 7 would've worked if you killed index 3 first, then the indexes >4 and than the indexes <3, but that's only one case, we have to account for all possible cases.
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago 0 Check out this test: 8 1 11 1 1 12 1 1 1 Here, if we choose the monster with 12 health we need x = 17, but if we choose to start from the monster with health 11 we only need x = 16.We can't choose the monster with 12 and have x = 16 because we kill that monster and all monster to the right and our power decreases to 12, we kill the monster to the left of it with 12 and we get to 11, we kill the left monster again and we are down to 10, this is less than what we need to kill the monster with 11 health.
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago 0 In problem D, for test case 2, 1, 5, 6, 4, 3 why spell of 7 is not the minimum because if we start with index 4(value = 6) and damage = 7, then index = 3 getting damage 6, then index 5 getting damage 5, index 6 getting damage 4 and index 2 and 1 getting damage 3 and 2 respectively. Can anyone suggest where I am doing wrong?
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago +2 Waiting for editorial
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago 0 The system test finished and my tricky solution 234102255 for problem E is still alive. Can anyone provide a hack test or it is actually true ?
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago 0 oh i get it now! thanks you. so hard to understand it for me
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago 0 Thanks for the test case! It makes sense as to why we have to consider every possible index now.
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago 0 "Firstly, Vasya chooses an index i of some monster (1≤i≤n) and the initial power of the spell x"the first monster can be chosen. If you choose the 6-hp monster, you will certainly kill all with 8 spell power.
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago +1 I am curious about the input size n (5 times of 10^5 but not usual 1 or 2) in problem E, is it intended? I kept getting MLE and RTE during the contest and, it turns out RTE is stack overflow (I should have thought it through), while I only left two local variables in the usual tree-DP recursive function. After exact those two local variables out of the recursion stack, it is an Accepted code. It seems that the stack size setting for Java in CF is a small number of MB, while I never thought it would be an issue, at least not in tree-DP. (BTW I used 128MB in local dev-environment setting.)But thanks to this problem, now I have got a snippet of code to do tree-DP-traversal without recursion. =)
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago +113 In this round，Im_dik from Chongqing Nankai Secondary School defeated the famous Legendary Grandmaster Um_nik. It's so fun!
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago 0 That greedy solution you are talking about? Probem B is: we have array $a_1,a_2,\ldots,a_n$. Find minimum number of following operations we have to do to make array all zeroes. Operation is take a subsegment $[l,r]$ and decrease all values by $1$.It's easy to proof that if we use our operation on segment $[l,r]$ and can use it on segment $[l', r'] (l' < l, r < r')$ we should use it on segment $[l', r']$.
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago +1 What if there are multiple monsters with highest health?Also try this case 7 3 1 4 2 2 2 2 If you start with 3, the minimum power is 8 If you start with 4, the minimum power is 9
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago 0 In D, won't it be smart to always choose the monster with the highest health at the beginning? I'm unable to come up with a counter-example as to when this won't work
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago 0 Wow, good job;
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago 0 But what happen if 8 damage onto 2? Or it doesn't the worst case what's the worst case mean? Thankyou
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago +1 Take a look at Ticket 17155 from CF Stress for a counter example.
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago 0 Any counter Test for this solution of C https://codeforces.com/contest/1901/submission/234171914
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago -8 solve() { ll n ; cin >> n; ll a[n+4]; ll mx = 0; ll mn = 1e18; for(ll i = 1; i <= n ; i++){ cin >> a[i]; mx = max(a[i],mx); mn = min(a[i],mn); } ll cnt = 0; vectorv; for(ll j = 1 ; j <= 35 ; j++){ if(abs(mx-mn) == 1){ if((mx>0 && mn > 0) && (mx%2 == 0) ){ v.push_back(1); //cout << "f"< 0 && mn > 0) && (mx%2 == 1)){ v.push_back(0); cnt++; break; } //else continue; } if((mx-mn) == 0 ){ break; } mx = 0; mn = 1e18; for(ll i = 1; i <= n ; i++){ a[i] = (a[i]/(ll)2); mx = max(a[i],mx); mn = min(a[i],mn); } v.push_back(0); cnt++; } if(cnt > n){ cout << cnt <
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago 0 For first move, you will need a[1]-1 moves always you can always move to A[i] from A[i-1] if A[i]<=A[i-1] without TeleportingBut if A[i]>A[i-1] you need to Teleport A[i]-A[i-1] timesAns can be $A[1]-1+\sum_{i=2}^{n} max(A[i]-A[i-1],0)$
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago 0 me newbie who take more then 1 hour for B and a was easy
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago 0 In problem E,what is the highest node in the tree?And what do we return as the answer?
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago 0 I just realized that source count must always be equal to the destination count, due to the way they are calculated, so yeah, you can count either one and it should be the answer.
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago 0 Big Uss.
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago 0 Just always choose min value.
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago +1 For C: it's useful to realize that to minimize the difference after division you only need to consider adding either $0$ or $1$.Specifically, if $a < b$, then: If $a$ is odd, and $b$ is even, you must add $1$. If $a$ is even, and $b$ is odd, you must add $0$. If $a$ and $b$ have the same parity you can add either $0$ or $1$.
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago +1 Think about the problem in binary. You are performing $m$ operations, where at each operation, you add a value $x_k$ ($0 ≤ k < m$) to all $a_i$ and then shift right, discarding the least-significant bit for each number.Here is one useful insight: if you have a solution of the form: add $x_0$, shift, add $x_1$, shift, ..., add $x_{m-1}$, shift; then there is an equivalent solution of the form: add $s$, shift, add $0$, shift, add $0$, shift, ...; where $s = x_0 + 2x_1 + 4x_2 + \dots + 2^{m-1}x_{m-1}$; i.e., the number of shift operations stays the same, but you add everything in the first operation.So a different way to formulate the problem is: pick integers $s$ and $n$ so that $shift(a_i + s, n) = shift(a_j + s, n)$ for all pairs $i, j$, and $n$ is minimal.Now if you have $a_i ≤ a_j ≤ a_k$, then $shift(a_i + s, n) = shift(a_j + s, n) = shift(a_k + s, n)$ iff. $shift(a_i + s, n) = shift(a_k + s, n)$, so you only need to consider the minimum and maximum values of $a$.
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago 0 I solved Problem A with 13 time's try.!
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago +8 why does coincidence of the smallest and the largest number ensure that all the numbers in between coincide too?
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago 0 Use CLIST!
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago 0 Without a single hope for something good, I solved problem C on the 18th attempt
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago +12 For B: you don't need to consider source counts at all. It suffices to count how many times the token must be teleported to each square, which is $max(c_i - c_{i - 1}, 0)$ for the $i$-th square ($i > 1$) and $max(c_i - 1, 0)$ for $i = 1$ (since the token starts at square 1 for free).So the solution is basically $\sum_{i=1}^n \max(c_i - c_{i-1}, 0)$ if you define $c_0 = 1$.
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago +14 I often see very common terms like tree, permutation, subarray, subsequence etc. defined. Gave me the notion that defining these terms was the standard.Although I don't need it, I like it better than without.
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago 0 Thanks
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago +5 What I think is that people below 1500 rating think too greedy that today's C will be easier for them but the people above 1600 try to think in a more generic way that's why they were not able to come up with the logic that answer will only depend on the highest and lowest element.We should try to balance both things I guess to perform the best.I also was not able to solve C but solved D in just 15 mins, sadly :(
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago 0 It's not easy to know which terms are "well-known" and which are not, especially if you aren't a native english speaker. There will always who doesn't know some term. That's why the clarificiations -system and google exist.
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago 0 for test n = 7 a = {5, 5, 5, 4, 4, 4, 4} your solution return 11 but right answer is 10
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago 0 messed up on C a lot
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago 0 could smbd prove greedy solution for B, pls?
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago 0 For me, it was D > B > C > A. C came intuitively to me and I found D much harder.
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago 0 In problem D, can anyone explain why I'm getting WA on test 6:submission
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago 0 Thanks Sir
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago +3 I solved B with two sets
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago +6 If x = min or x = max, the difference between max and min decrease by the floor of half. This is easy to observe mathematically. For other choices, it is possible for the difference to decrease by either the floor or the ceiling of half, depending on the parity of the original min, original max, and your chosen x. This requires a little more case work for a mathematical proof, but one can intuitively deduce that the difference can't possibly be reduced further than the floor of half, so it is optimal to stick with that.
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago 0 bruh
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago +10 B: When a teleportation happens, there is a source and destination. My approach was to count how many source teleportations are required and how many destination teleportations are required.For each $i$ in which $c_i > c_{i - 1}$, there must have been $(c_i - c_{i - 1})$ teleportations with destination $c_i$. Add that to the destination count.For each $i$ in which $c_i < c_{i - 1}$, there must have been $(c_{i - 1} - c_i)$ teleportations with source $c_{i - 1}$. Add that to the source count.Furthermore, add $c_1 - 1$ to the destination count, and also add $c_n - 1$ to the source count. Return the maximum between source and destination counts.C:Consider when there are two distinct values $a$ and $b$. No matter which value of $x$ you pick, the difference between $a$ and $b$ reduces to either $\left\lfloor\frac{b - a}{2}\right\rfloor$ or $\left\lfloor\frac{b - a}{2}\right\rfloor + 1$. The former is optimal and can be achieved by simply choosing either $a$ or $b$ as your $x$.If you have more than two distinct elements, all you need to do is ensure that the smallest and biggest values coincide, and this guarantees that all other values will coincide too. Simply find the difference between the largest and smallest elements, and then return the number of bits in the binary representation for this difference.
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago 0 You are right. Fixed this.
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago 0 When x=0 and y=1 you get infinite loop which allocates large amount of memory
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago 0 What I was actually trying to say is that you confused D with E and C with D
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago 0 Check in official standings. Those submissions were made after contest
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago 0 Problem C:234129053can someone please explain why I am getting memory limit exceeded for this code ?
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago 0 But D solved more than 255 people? Am I wrong?
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago 0 There should be tasks that separates div2 and new div1 participants. The last two were just for latter ones
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago 0 E
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago 0 Bro, I'm your fan
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago 0 Solve count
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago 0 B>D>C
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago 0 What are that numbers?
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago +3 Thank you for problem F! It was really satisfying to solve.
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago +6 These terms should be defined in the statement imo. Also, authors can use more familiar terms, like "degree", which should also be defined
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago -18 " very balanced round in recent months "Problem D: 1987Problem E: 255Its decreasing by 10. Ideally it should decrease by 2 on each step to be balanced.
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago 0 Since there is no yet editorial: how to solve F?
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago 0 B: I noticed a pattern from the provided input->output examples that the result is just the sum of the difference between each element and the element before it but only if the element before it has a higher value, plus the final element — 1.C: Just always pick the minimum element in the array as x. Always. The number of times it takes for all elements in the array to equal each other is equal to the number of times it takes for the maximum element to get to the minimum element with the given equation.So, I did just that. Stored the minimum element and the maximum element, and then made a while loop that does the operation with a counter.
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago 0 thanks
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago +1 Really interesting tasks and one of the most balanced round for last months. I will be glad to see next rounds from the authors!
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago 0 WOW but it seems your code is semi-complicated while the solution is each time x = max_number + 1because, (x+x+1)/2 = x while (x+x+2)/2 = x+1 so what ever happened all numbers will not exceed max_number and make the min_number be equal to max_number you can check my submission 234086134
 On awoo → Educational Codeforces Round 158 [Rated for Div. 2], 4 days ago 0 I just tested with some cases by choosing min and it seems to be correct, plus there was just about only less than a minute left (and I couldn't make it in time as in my comment).