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

By awoo, history, 21 month(s) ago, translation,

Hello Codeforces!

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 6 problems and 2 hours to solve them.

The problems were invented and prepared by Roman Roms Glazov, Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

Our friends at Harbour.Space also have a message for you:

Hi Codeforces!

The deadline to apply for our Master’s Scholarship in Bangkok is very soon!

Don't miss your chance and apply for our progressive Master’s programs in Data Science and Cyber Security in just 3 steps:

1. Submit your CV to see if you are an eligible candidate for the scholarship
2. If your profile matches the requirements, one of our admissions officers will get in touch with you
3. Apply for the program, pay the 125€ application fee, pass a series of interviews, and if you’re accepted, pack your bags to Bangkok!

And if you know someone who might be interested in Digital Marketing, High Tech Entrepreneurship, Interaction Design or FinTech, send them our way!

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 HIR180 6 106
2 neal 6 162
3 receed 6 172
4 Geothermal 6 174
5 cerberus97 6 179

Congratulations to the best hackers:

Rank Competitor Hack Count
1 Akulyat 24
2 hoke_t 20
3 dhxh 18:-1
4 vovanstrr 14
5 WNG 13:-1
255 successful hacks and 458 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A Dalgerok 0:01
B neal 0:04
C HIR180 0:08
D .__. 0:17
E gxnncrx1993 0:20
F Retired_MiFaFaOvO 0:07

UPD: Editorial is out

• +129

 » 21 month(s) ago, # |   +124 ![ ]()
 » 21 month(s) ago, # |   0 Best of luck to all those participating!!! Can't wait to see what problems there will be!!!
 » 21 month(s) ago, # |   -9 CODEFORCES IS THE BEST SITE FOR PRACTICE...
 » 21 month(s) ago, # |   +16 Why educational rounds have more greedy problems?
•  » » 21 month(s) ago, # ^ |   +9 because greed is good.https://www.youtube.com/watch?v=6bbzwJ0Sx48
•  » » » 21 month(s) ago, # ^ |   0 I was not expecting a video in the comment! LOL
•  » » 21 month(s) ago, # ^ |   0 sorry bro by mistake vote -ve ho gaya
•  » » » 21 month(s) ago, # ^ |   -7 You can still make positive.
 » 21 month(s) ago, # | ← Rev. 2 →   -20 Clashes with Mirror replay round of ICPC Gwalior regionals on Codechef
•  » » 21 month(s) ago, # ^ |   -20 If you have to do something else, just don't do the contest here instead of whining about it in the comments. There's no contest time that can satisfy everyone in every time zone.
•  » » » 21 month(s) ago, # ^ |   0 Would have considered that helpful, if u had replied before the contests started rather than now. Anyways peace out!
 » 21 month(s) ago, # |   +3 anyone please provide any good resource(book,blog,lecture) for understanding lazy-propagation i am unable to understand that.
•  » » 21 month(s) ago, # ^ |   +3
•  » » 21 month(s) ago, # ^ |   +1
•  » » » 21 month(s) ago, # ^ |   -9 thanks this seems really good
 » 21 month(s) ago, # |   +55 Who want to see my screencast(without comments)? Not sure I'm as cool as Um_nik tbh.
•  » » 21 month(s) ago, # ^ |   0 I want it!
•  » » 21 month(s) ago, # ^ |   0
 » 21 month(s) ago, # |   -16 Solve D — Rejudge WA 72 — Find that in your solution there can be cycle but it outputs a tree — Write a dfs checker — Forget to call dfs function to get 3 more WAs. LOL... Anyway D and E are easier this time(Assuming they passes or does not get hacked).
 » 21 month(s) ago, # |   +3 Can D solved something like interval handling using set?
•  » » 21 month(s) ago, # ^ |   0 I tried and got MLE on test 51 :(
•  » » » 21 month(s) ago, # ^ |   +6 :)
•  » » 21 month(s) ago, # ^ |   0 yes, it can.
•  » » » 21 month(s) ago, # ^ |   0 I thought of similar approach but stopped. Isn't your time complexity in worst case O(N^2) since you are also iterating the set of segments containing the i as starting point?
•  » » » » 21 month(s) ago, # ^ | ← Rev. 2 →   0 sort the segments depending on the endpoints. now for each segment i, all you need to iterate on is the segments j between i + 1 and n that satisfies the condition: start_point[i] <= start_point[j] <= end_point[i] which is the number of edges in the created graph
•  » » » » 21 month(s) ago, # ^ |   +14 when you have more than n-1 edges, just stop.
•  » » » 21 month(s) ago, # ^ |   +1 Okay, I get if(it.first > a[j].r) break; this makes it run faster.
 » 21 month(s) ago, # |   +2 For problem B, who solved using https://oeis.org/A140358
•  » » 21 month(s) ago, # ^ |   0 The link describes it as "Smallest positive integer k such that n = +-1+-2+-...+-k for some choice of +'s and -'s." What's the relation between this and problem B ?
•  » » » 21 month(s) ago, # ^ |   0 Find the absolute difference of a and b. Then when we add number to the smaller of a and b, we're just reducing the absolute difference by that number. Otherwise we're increasing it. The problem becomes: Find the smallest positive integer k such that the absolute difference = +-1+-2+-...+-k for some choice of +'s and -'s. Effectively the problem is solved using the link above.
 » 21 month(s) ago, # |   +1 WHAT IS TEST CASE 2 OF DIV2B
•  » » 21 month(s) ago, # ^ | ← Rev. 2 →   0 Try for cases like 2 4 (Ans:3) or 5 14 (Ans:5)
•  » » » 21 month(s) ago, # ^ |   0 how is the answer for 2,4 equal to 2 ? could you explain it a little more
•  » » » » 21 month(s) ago, # ^ |   0 Sorry my mistake. Corrected.
•  » » » » » 21 month(s) ago, # ^ | ← Rev. 2 →   0 also for 5,14 case , i am getting 6 not 5 as the answer. first 5 + 1 = 6 //step 1 6+2 = 8 // 2 8 + 3 = 11 // 3 11 + 4 = 15 // 4 15 + 5 = 20 // 5 14 + 6 = 20 // 6 Is there a better way ?
•  » » » » » » 21 month(s) ago, # ^ |   0 5,14 to 5,15 to 5,17 to 8,17 to 12,17 to 17,17 I guess. This round was greedy AF smh
•  » » » » » » 21 month(s) ago, # ^ |   0 5 + (1 + 2 + 4 + 5) = 14 + 3
•  » » » 21 month(s) ago, # ^ |   0 Can you prove your answer 5 in 5 14
•  » » » » 21 month(s) ago, # ^ |   0 See above
 » 21 month(s) ago, # |   +47 Screencast if anyone's interested: https://youtu.be/g4Gcl0yAgDU
•  » » 21 month(s) ago, # ^ |   -10 Subscribed :)
•  » » 21 month(s) ago, # ^ |   +7 42 minutes ?!
•  » » 21 month(s) ago, # ^ |   +1 Wow! That's really cool. Hoping to get more of them
•  » » 21 month(s) ago, # ^ |   0 Subscribed!Simply amazing!!!
•  » » 21 month(s) ago, # ^ |   0 Can you explain how solve the problem B? I see that you are making some solution based on bits, But I could not get your solution...
•  » » » 21 month(s) ago, # ^ |   0 The bits were only used to test parity. https://codeforces.com/blog/entry/72268?#comment-565771 describes my solution well.
 » 21 month(s) ago, # |   +26 How to solve D? P.s. round was great, so interestring problems!
 » 21 month(s) ago, # |   +2 What was pretest 2 of B?I was first adding maximum possible n*(n + 1) /2 to the smallest number. Than answer = n + (difference between numbers) * 2;whats wrong in this approach?
•  » » 21 month(s) ago, # ^ | ← Rev. 2 →   0 input: 1 31 20output : 5
•  » » » 21 month(s) ago, # ^ | ← Rev. 2 →   0 Yes, getting 6 as output.
•  » » » » 21 month(s) ago, # ^ |   0 Sorry, the output should be 5
•  » » 21 month(s) ago, # ^ |   0 test this: 1 5 answer is 3 because: 1) 1 6 2) 3 6 3) 6 6
•  » » » 21 month(s) ago, # ^ |   0 Thanks for this case!So what was the approach to solving the problem?
•  » » » » 21 month(s) ago, # ^ | ← Rev. 2 →   +1 Sorry for my poor english, I cant explain this problem to you. The main idea that (a + b + tmp) mod 2 = 0 and (a + b + tmp) / 2 >= max(a, b), where tmp = 1 + 2 + 3 + .. + n. You can check my submission, I think it will help you. https://codeforces.com/contest/1278/submission/67230823
•  » » » » » 21 month(s) ago, # ^ |   0 Is there any chance of getting the second problem being hacked?
•  » » » » » » 21 month(s) ago, # ^ |   0 I think no.Educational rounds usually have strong sys tests
•  » » » » » » » 21 month(s) ago, # ^ | ← Rev. 2 →   0 Still, many solutions of problem D have been hacked!
•  » » » » » 21 month(s) ago, # ^ |   0 But you just did ++tmp it does't mean tmp = 1 + 2 + 3 + ... +n.i hope you understand.
•  » » » » » » 21 month(s) ago, # ^ |   0 tmp in my code its just a number that we will add next time, when we will need it. I increase a every time in cycle.
•  » » 21 month(s) ago, # ^ |   0 I did the same and it was wrong. Have you find mistake? please explain if yes...
 » 21 month(s) ago, # |   0 How do you guys solved C? I thought of a greedy approach but it didn't worked :(.
•  » » 21 month(s) ago, # ^ |   0 using 2 prefix sum arrays and then using maps
•  » » 21 month(s) ago, # ^ |   +1 Let us suppose you eat s1 strawberries and b1 blueberries in the left and s2 strawberries and b2 blueberries to the right. If total strawberries is s and b, then we want s — (s1 + s2) = b — (b1 + b2). Or, equivalently, (s — b) — (s1 — b1) = (s2 — b2). So, for given s1 and b1, you need search for minimum steps in the right to make difference equal to the above. You can maintain hashtable to store for every (s2 — b2) the minimum steps to reach it in the right. This will speed up the search...Complexity O(nlogn)
•  » » 21 month(s) ago, # ^ |   +1 What is wrong in the greedy approach?Cant I just eat up the jar which is closest to me?
•  » » 21 month(s) ago, # ^ | ← Rev. 3 →   +2 I reversed the problem; find the maximum possible of jars remaining such that the two types are equal in number. It is easy to see that such jars must form a prefix and a suffix of the given array.I thus separate the array into two halves ($A$ and $B$) and reverse the second half. I also treat strawberry as $+1$ and blueberry as $-1$. I then iterate through $A$ collecting prefix sums and storing it in a map (be sure to set $M[0] := 0$ before), thus for each prefix sum I now know the biggest prefix of $A$ with that sum.I then do similarly with $B$, except this time I treat strawberry as $-1$ and blueberry as $+1$, and I look up the prefix sums in the map. If the match exists, I add the two lengths and keep the biggest candidate seen. Finally, I restore the original answer by subtracting the maximum remainder from $2n$.Sample: 67283206
 » 21 month(s) ago, # |   +32 Eh, got stuck on E this time, had several approaches that worked on paper but didn't know how to translate them into code. So, how to solve E? :)
•  » » 21 month(s) ago, # ^ |   +31 Suppose you can build answer for any subtree of the current tree. Answer for subtree is a list of segments. We will say that the last segment in this list is the root.Then you have a tree, you built answers for every children. If there are no children, you can return a single segment {0,1}. Otherwise you do something that is drawn on the picture. Real segments mean a last (root) segment and the area near it means other segments in this subtree. a, b, c are children of d and a', b', c', d' are other segments in that subtrees. In this picture we build a tree d. You can see that there are no intersections between the children, but all the children root's are intersected with d.If you take the biggest (by count of segments in it) child as a base, you can add other children to this child and in total it will take nlogn time.
•  » » » 21 month(s) ago, # ^ |   +16 Seems that O(N) is possible too: Encode single idx-th segment as a (linked) list of 2 events: (idx, 1) and (idx, 0) (1 — segment opens, 0 — segment closes). '+' will denote two linked list concatenation (done in O(1)). (N segments are represented as linked list of length 2*N) Root given tree at some node, say 1. Answer for subtree rooted at root_idx will always start with (root_idx, 1). Answer for leaf: solve(leaf_idx) = [(leaf_idx, 1), (leaf_idx, 0)] Answer for non-leaf: suppose we calculate answer for node d with children a, b, c. Denote solve(a)=[(a, 1)]+otherA, solve(b)=[(b,1)]+otherB, solve(c)=[(c, 1)]+otherC. Then solve(d)=[(d, 1), (a, 1), (b,1), (c, 1), (d, 0)] + otherC + otherB + otherA Restore l_i, r_i by traversing solve(1) Overall complexity: O(N)
•  » » » » 21 month(s) ago, # ^ |   +13 Wow, that's nice. The idea is almost the same as mine one, but works much faster.
 » 21 month(s) ago, # |   +1 Anyone solve C using binary search???
•  » » 21 month(s) ago, # ^ |   0 I tried with binary search but i got Wrong answer on test 2
•  » » » 21 month(s) ago, # ^ | ← Rev. 2 →   +3 same here, but now I realise that binary search will not work on some cases
•  » » 21 month(s) ago, # ^ | ← Rev. 2 →   0 Actually I managed to do that, you just need to build prefix differences (num2 — num1) & suffix differences, then sort the suffix ones and find a pair where suffix difference = -prefix difference using binary search.
•  » » » 21 month(s) ago, # ^ |   0 Could you please explain the process in detail ?
•  » » » » 21 month(s) ago, # ^ | ← Rev. 2 →   0 The idea is as follows: 1. For all prefixes of the array containing from 0 to n elements inclusive we compute the difference between #of 1-s and 2-s (doesn't matter in which order). Going from the smaller to bigger ones, this is done in linear time. 2. Do the same thing for all suffixes from size 0 to n inclusive. Store the difference together with the size of the suffix 3. Sort the suffix differences from smaller difference to larger (if the differences match, put the one where the the length is bigger first) 4. For each of the prefixes, do a binary search in the sorted suffix differences array. We search for -prefix_differences[]. From all the suffixes with matching difference, select the largest (remember that due to our comparator being clever this requires almost no modifications). 5. Out of all the pairs select the one where 2 * n — prefix_length — suffix_length is smallest. This is the answer.
•  » » » » » 21 month(s) ago, # ^ |   0 Thanks .
 » 21 month(s) ago, # |   +1 How to solve B?
•  » » 21 month(s) ago, # ^ | ← Rev. 2 →   0 Get the absolute difference. Keep increasing the sum and count from 1. If the sum equals the difference print the count. else keep adding to sum till both diff and sum are odd or even. Print count Try in cpp and try to decode the logic. Thank me later! ;) T.c O(1e5)
•  » » » 21 month(s) ago, # ^ |   0 Thank you dude
•  » » » 21 month(s) ago, # ^ |   0 What is the logic behind that?
•  » » 21 month(s) ago, # ^ | ← Rev. 2 →   +21 My answer for B. A and BLet the numbers be $a$ and $b$. After the operations, we end up with another number that is $c$ where $c\ge \max(a, b)$. Now the operations are adding $1, 2, 3 ...$ so after $n$ operations we have $\frac{n\cdot(n+1)}{2}$ as total increment in $a$ and $b$, distributed among them in some way.Now this total increment is also equal to $c-a + c-b = 2\cdot c -a-b$. Thus we have $\frac{n\cdot(n+1)}{2} = 2\cdot c-a-b$. Increment can also be written as $|a-b|+2(c - \max(a,b))$. From here we get the two required conditions. We loop over $n$ to get first $n$ that satisfies: $\frac{n(n+1)}{2} \ge |a-b|$ $\frac{n(n+1)}{2} - |a-b|$ should be divisible by $2$ Now since we need increment $\frac{n(n+1)}{2} \ge \max(a,b)$ so at the max $n^2 = 10^9$, so the time complexity is $\sqrt{\max(a, b)}$.My submission: 67218512Btw I was watching William Lin's screencast, I have no idea what he has done. People have done it very quickly!EDIT: Just realised, no need to loop over so many values, since we know $\frac{n(n+1)}{2} \ge \max(a, b)$. Thanks to @aniervs. That will give constant complexity..
•  » » » 21 month(s) ago, # ^ | ← Rev. 3 →   +1 dude thanx from bottom of heart here i made only small change in your logic to keep it simple and it works like 1. total increment = n*(n+1)/2 2.suppose number at which a and b both land will be cso (c-a)+(c-b)=n*(n+1)/2 here c>=max(a,b) two cases arise (say)x=n*(n+1)/2+a+b1.x%2==0&&x>=2*max(a,b)iterate until above reach and print xbelow is my solution https://codeforces.com/contest/1278/submission/67251204
•  » » » » 21 month(s) ago, # ^ |   0 We haven't proved yet .We have proved necessary condition but not sufficient ,
•  » » » » » 21 month(s) ago, # ^ |   0 I mean how to prove that with that n , we can add to a and b and they will be equal in the end ?
•  » » » 21 month(s) ago, # ^ |   0 tmwilliamlin168 Care to explain?
•  » » » » 21 month(s) ago, # ^ |   0 I did the same thing, looping over the first n such that a >= b (assuming a < b at first) and that a and b will have the same parity.
•  » » » 21 month(s) ago, # ^ |   +4 let's say $n$ is the value that $a$ and $b$ reach at the end, and there were $k$ operations. Then, $2n=a+b+\frac{k(k+1)}{2}$. Multplying by $2$, we get $4n=2a+2b+k(k+1)$. Let's say $a <= b$, then $4n>=4b$, so $2a+2b+k(k+1)>=4b$, we get $k(k+1)>=2b-2a$, then $(k+1)^2>=2b-2a$, so $k >= (2b-2a)^{1/2}-1$. But $2a+2b+k(k+1)$ is a multiple of $4$, so we can iterate $k$ by the first four values grater than or equal to $(2b-2a)^{1/2}-1$
•  » » » 21 month(s) ago, # ^ | ← Rev. 2 →   0 Thank you. I cleared c and when c >= max (a, b) and 2c — a — b == n*(n + 1) / 2 found the answer. Here my submission: 67275338
 » 21 month(s) ago, # |   0 How to solve C?
•  » » 21 month(s) ago, # ^ |   0 I took 2's as -1 and maintained prefix sum of array from left to center at each position and the same for the right of center.Then I stored first occurence of distinct prefix sum's to the left and right in different tables.Now just iterate over tables and check if an element in left table has a negative counterpart in the right one, if it does, then the gap is one of the possible answers.
 » 21 month(s) ago, # |   +52 This was the most difficult B I've ever seen.
 » 21 month(s) ago, # |   0 That moment when you find the bug in the last second I'm so unlucky
•  » » 21 month(s) ago, # ^ |   +6 That moment when C is easier than B :sad:
•  » » » 21 month(s) ago, # ^ |   0 Not really? You find the index of first triangle number larger than abs(b — a) that has the same parity as abs(b — a) :) Because you can increment the smaller number one by 1+2+3+...+n EXCEPT for (triangle number — abs(b — a)) / 2 (which is an integer) :)
•  » » » » 21 month(s) ago, # ^ |   0 Only if how to solve meant that the question was easy :(
 » 21 month(s) ago, # |   0 I think C can be solved using binary search (searching for the the minimum number of jars ) but why i got WA on test 2 ???? ooooohhhh
•  » » 21 month(s) ago, # ^ |   +1 Did you cover the case when you eat up no jar from the left side or right side?
•  » » 21 month(s) ago, # ^ |   +21 I don't think C is possible with bianry search, since (number of jar to use)->(whether the goal is possible) function is not monotonic.
•  » » » 21 month(s) ago, # ^ |   0 Could you give me a test that explain your idea?
•  » » » » 21 month(s) ago, # ^ |   0 I do not think binary search is possible too because if an interval size satisfies the criteria of the question, bigger interval may violate it...I haven't generated the precise test case but consider the below transition:Binary search at len = x tells interval Lx,Rx is one of the feasible intervals: So interval is like : ..... 1 (1 2 2 1 1 2 2) 1 .... So just expanding the interval to the right or to the left or towards both sides changes the feasibility of interval to remain as answer.
•  » » » 21 month(s) ago, # ^ |   0 In which test case my solution is wrong?? https://codeforces.com/contest/1278/submission/67240467
•  » » » 21 month(s) ago, # ^ |   +1 i solved it using binary search,what i did is make two vectors (vector of pairs {value,index}) for left(1 to n) and right part(n+1 to 2*n) where each element of both arrays stores the contribution they give to the "difference".(if s=no. of strawberrys and b=no. of blackberrys then difference is abs(s-b) ).sort both vectors. Now apply binary search such that left_i + right_j = difference. Also check for left_i=diff and right_j=diff separately. This is my code : https://codeforces.com/contest/1278/submission/67254126
 » 21 month(s) ago, # |   0 For $C$ what is wrong with this approach:- Iterate from $2n$ to $n + 1$, If $a[i] == 1$ then $val = val + 1$ else $val = val - 1$, Push these values in an HashTable, $HashTable[val].pushback(index)$. Now iterate from 1 to n, keep a variable (let say) $val = 0$. If $a[i] == 1$ then $val = val + 1$ else $val = val - 1$, then find the smallest index corresponding to value $-val$ in HashTable(if present), and update the answer.
•  » » 21 month(s) ago, # ^ |   +2 you don't cover the case when you eat no jar from the left or right
•  » » 21 month(s) ago, # ^ |   0 You may have missed some corner cases..
 » 21 month(s) ago, # |   +24 How to solve F?
•  » » 21 month(s) ago, # ^ |   +37 Essentially, the problem is this (My solution requires some knowledge about calculus and probability) Given a binomial distribution $B(n, \frac{1}{m})$, we want $E(X^k)$.Consider moment generating function $M(t) = E(e^{tX})$. Then, k-th moment, which is $E(X^k)$, can be achieved as $\frac{d^k}{dt^k} M(t)$ evaluated at $t = 0$. (one can prove this by taylor expansion)Also, a mathematical fact — $M(t) = (pe^t + 1 - p)^n$ for $B(n, p)$. Considering all this, try actually computing some derivatives. You can notice some pattern. By this pattern, we can get some $k$ degree polynomial about $n$ and $p = \frac{1}{m}$. The actual computation was quite messy, but the pattern was clearly noticable. The only task left is to implement this function and evaluate with rational numbers as given.
•  » » » 21 month(s) ago, # ^ | ← Rev. 4 →   +26 My approach is similar, but more intuitive IMO, if you have never seen the $M(t)=E(e^{tX})$ before.We want: $\sum_{i=0}^ni^k\binom{n}{i}\left(\frac{1}{m}\right)^i\left(\frac{m-1}{m}\right)^{n-i}$Notice, it is similar to our familiar binomial expansion: $\left(\left(\frac{1}{m}\right)x+\left(\frac{m-1}{m}\right)\right)^n$ $=\sum_{i=0}^nx^i\binom{n}{i}\left(\frac{1}{m}\right)^i\left(\frac{m-1}{m}\right)^{n-i}$We want to create the term $i^k$ in the front, and then plug in $x=1$ to get our answer. How do we create the $i^k$? We, can do derivative with respect to $x$ :). Like this: $\frac{d}{dx}\left(\left(\left(\frac{1}{m}\right)x+\left(\frac{m-1}{m}\right)\right)^n\right)$ $=\sum_{i=0}^nix^{i-1}\binom{n}{i}\left(\frac{1}{m}\right)^i\left(\frac{m-1}{m}\right)^{n-i}$Now, multiply $x$ and repeat! Do it $k$ times total to get the term $i^k$. Calculating the $k$ derivatives takes $O(k^2)$ time.
•  » » » » 21 month(s) ago, # ^ |   +1 Off topic note: does anyone know how to fix the inline latex not rendering correctly? :P
•  » » » » » 21 month(s) ago, # ^ |   0 Try to put \displaystyle in the beginning of a formula.$\displaystyle\sum_{i=0}^n\left[i^k\binom{n}{i}\left(\frac{1}{m}\right)^i\left(\frac{m-1}{m}\right)^{n-i}\right]$
•  » » » » 21 month(s) ago, # ^ |   0 I don't get what the "multiply x and repeat" mean. It's easy for me to understand that after k times derivatice, the right of this equation is just what we want. But how to deal with the left part of this equation? I tried to multiply x and derivative the left part but found nothing. Would you like to explain it in details? Thx
•  » » » » » 21 month(s) ago, # ^ | ← Rev. 2 →   +3 The right side of equation starts with term $x^i$. After derivative it becomes $ix^{i-1}$. Then we multiply by $x$ to get $ix^i$. Then another derivative to get $i^2x^{i-1}$. Then multiply by $x$ again, etc. It is straight forward to see how this process can generate term $i^k$. Now, for left side, we must also do the derivative and multiply by $x$ repetition. For this, one strategy is to keep an array of size $k+1$ of coefficients of terms $\left(\left(\frac{1}{m}\right)x+\frac{m-1}{m}\right)^{n-i}x^i$ for $i=0,\ldots,k$, perform $k$ updates on this. This is the approach I used in submission above.
•  » » » » » » 21 month(s) ago, # ^ |   0 THX！How stupid of me for forgetting this is a "programming" competition lol
•  » » » » 21 month(s) ago, # ^ |   0 Couldn't we just calculate the original expression in the top without using any derivatives as only thing to care about there is the nci terms other than that all terms can be easily calculated.
•  » » » » » 21 month(s) ago, # ^ |   +3 Ah, sorry, the sum is supposed to be to $n$, not $k$ (which is the reason why we can't calculate the sum directly). I have fixed the post now.
•  » » » » 21 month(s) ago, # ^ |   +3 Can you tell why can we raise i to the power k?
•  » » » » » 21 month(s) ago, # ^ |   +3 Yes, it is actually from the definition of expected value. Informally, expected value of $f(x)$ is equal to: $\sum f(x)\cdot\left(probability\_of\_x\_jokers\right)$ $=\sum f(x)\cdot\left(\frac{ways\_to\_get\_x\_jokers}{total\_ways\_to\_get\_any\_amount\_of\_jokers}\right)$In this case, $f(x) = x^k$, and the probability terms end up equaling the coefficients in my above comment.
•  » » » » 21 month(s) ago, # ^ |   0 Your solution was much better than the MGF one!
•  » » » 21 month(s) ago, # ^ |   0 Is there some pattern tbh? I am facing a lot of difficulty as to how to calculate those messy derviatives, how did you write the recursion for the same?
•  » » » » 21 month(s) ago, # ^ |   +1 Yes, I can explain derivative implementation details :). $\frac{d}{dx}\left(\left(\frac{1}{m}\cdot x+\frac{m-1}{m}\right)^n\right) =\left(\frac{1}{m}\right)^n\frac{d}{dx}\left(\left(x+m-1\right)^n\right)$We remove constant $\left(\frac{1}{m}\right)^n$ and account for it at the end. Now we do derivative and multiply by $x$. $\frac{d}{dx}\left(\left(x+m-1\right)^n\right)\cdot x =(n)(x+m-1)^{n-1}x$Now, the second repetition. $\frac{d}{dx}\left((n)(x+m-1)^{n-1}x\right)\cdot x$ $=(n-1)(n)(x+m-1)^{n-2}x^2+(n)(x+m-1)^{n-1}x$We notice all terms are of form $C\cdot(x+m-1)^{n-i}\cdot x^i$ for some coefficient $C$ and some power $i$. We create an array $a$ of size $k+1$ with indices $i=0,...,k$ such that $a[i]$ stores coefficient of above term. Now we can apply derivatives and multiplication of $x$ on this array. We can see this operation results in relation $a[i]=(n-i)\cdot a[i-1]+i\cdot a[i]$.
•  » » 21 month(s) ago, # ^ |   +59 Let's rewrite $x^k$ as the number of tuples $(x_1, x_2, \dots, x_k)$ such that $1 \le x_i \le n$ and for every $i$, the $x_i$-th shuffle of the deck resulted in a joker. Then the expected value of $x^k$ is the expected number of such tuples.For each tuple, we need to determine the probability that it belongs to the set of tuples. If the number of distinct elements in a tuple is $y$, then this probability is $\frac{1}{m^y}$. Then for each $y$ calculate the number of tuples of size $k$ with exactly $y$ distinct elements; this can be done with dynamic programming — let $dp_{i, j}$ be the number of tuples of size $i$ with $j$ distinct elements; during each transition we either add a new element (there are $n - j$ ways to do it) or add a previously added element (there are $j$ ways to do it).
•  » » » 21 month(s) ago, # ^ | ← Rev. 2 →   +38 F can be done in $O(K \log K)$ using FFT.$\mathbb{E}(X^K)=\mathbb{E}((x_1+x_2+...+x_n)^K)$, where $x_i$ is indicator variable for the $i^{th}$ try.$= \mathbb{E}(\sum_{y_1+y_2+..+y_n=K} {K \choose {y_1,y_2,...,y_n}} \cdot x_1^{y_1} \cdot x_2^{y_2}...\cdot x_n^{y_n} )$$= K! \cdot \mathbb{E}(\sum_{y_1+y_2+..+y_n=K} \frac{x_1^{y_1}}{y_1!} \cdot \frac{x_2^{y_2}}{y_2!} ... \cdot \frac{x_n^{y_n}}{y_n!})$Now, the Inner expected value can be calculated as :$\sum_{i=1}^{min(N,K)} \binom{N}{i} (\frac{1}{M})^{i} \cdot \sum_{j=0}^{i} \binom{i}{j} \cdot (-1)^{i-j} \cdot \frac{j^K}{K!}$ So, cleaning, we get :$\sum_{i=1}^{min(N,K)} \frac{N!}{(N-i)!} \sum_{j=0}^{i} \frac{-1^{(i-j)}}{(i-j)!} \cdot \frac{j^K}{j!}$The inner sum part for each $i$ can be calculated over all $i$ using NTT, and so overall $O(K \cdot \log K )$ My Submission
•  » » 21 month(s) ago, # ^ |   +60
 » 21 month(s) ago, # |   0 Does anyone have proof that the answer for problem $F$ is polynomial of degree $k + 1$?
•  » » 21 month(s) ago, # ^ |   +16 Yes, as I wrote in the comment right above your comment, I tried computing some derivatives and could get $k$ degree polynomial. We start with $(pe^t + (1-p))^n$, and we differentiate it $k$ times. Also notice that since we are dealing with $t = 0$, $e^t$ term left in the solution will be evaluated to 1.
•  » » 21 month(s) ago, # ^ |   +5 Note that we only need to find the expected value of $X^k$, where $X$ is a binomially distributed random variable with parameter $1/m$. For binomially distributed random variables, we know that the $E[D_r(X)] = \frac{n!}{(n-r)!} \cdot p^r$, where $D_r(x)$ is the falling factorial function with degree $r$. Also, we know that $x^k = \sum_{i=0}^{i=k} S(k, i) D_i(x)$, where $S(k, i)$ is the Stirling number of the second kind. Now the answer can be computed using a dp to compute $S(k, i)$ and then by taking the expected value of the identity above.
 » 21 month(s) ago, # | ← Rev. 3 →   +11 I think n is too large in D/E. It's essential to solve problems like these using dfs approach, but you probably can't do it because stack size is not that large.I've got StackOverflowError in this submission 67239760 and accepted the same code but with bfs instead of dfs 67244701.
 » 21 month(s) ago, # |   0 C can be solved with greedy approach in o(n) time. for right and left create a list X that each element is accumulated difference of the two types. input = 1 1 2 1 2 1 becomes>> right = [1 2 1] left = [2 1 1] X_right = [-1 0 -1] X_left = [1 0 -1] all numbers in X are between -5*10^4 and 5*10^4. then using X create a list ( or hashmap ) that is first occurrence of any number in X. first_right = { -1:1 , 0:0} first_left = {-1:3 , 0:0 , 1:1} with this we decide how much of the total difference are we gonna cover from left or right.(greedy part) for example. 4 reds 2 blues so difference is -2. right: 0 and left:-2 >> firstright[ 0] + firstleft[-2] >> n/a right:-1 and left:-1 >> firstright[-1] + firstleft[-1] >> 1 + 3 = 4 right:-2 and left: 0 >> firstright[-2] + firstleft[ 0] >> n/a 
 » 21 month(s) ago, # |   +28 I just browsed through some of the profiles and many of them says : William Lin fan-clubAnybody can shed some light on it for me?
 » 21 month(s) ago, # |   +6 when's the editorial coming?
•  » » 21 month(s) ago, # ^ |   0 After ends the hacking phase , hope so.
 » 21 month(s) ago, # | ← Rev. 2 →   0 While everyone is discussing C/D/E/F, newbie is thinking how to solve B :(
 » 21 month(s) ago, # |   +3 I think proof of B had similar idea as this question: https://atcoder.jp/contests/abc147/tasks/abc147_f
 » 21 month(s) ago, # | ← Rev. 4 →   +13 The way I solved B was like this :Let $P_n$ be a set of distinct natural numbers from $1$ up to $n$. And let $sum[i] = \frac{i*(i+1)}{2}$, which is sum of all natural numbers from $1$ to $i$. Choose two disjoint subsets $A$ and $B$ of $P_n$ such that $A \cup B = P_n$ and the difference between the sum of elements of $A$ and $B$ be $d$. You have to choose $A$ and $B$ is such a way that $d$ is equal to the difference between $a$, and $b$, and then add the subset having smaller sum with $max(a,b)$ and the other one with $min(a,b)$ to make $a$ and $b$ equal. Now the problem is to choose such a $P_i$ such that $i$ is minimum and $d = abs(a-b)$. Notice that if I choose $P_i$ such that $sum[i]$ is even, then the set of all possible $d$ made from $P_i$ contains all non negative even numbers up to $sum[i]$. The reason is, if you choose $A$ such that the sum of elements of $A$ is $x$, and then put all the other numbers of $P_i$ inside $B$, then sum of elements of $B$ and $A$ shall be $sum[i] - x$, and $x$ respectively. So, $d = sum[i] - x -x = sum[i] - 2x$. So, $d$ is even. And obviously $1 \leq x \leq sum[i]$, so we get all the non negative even numbers up to $sum[i]$. Similarly, if $sum[i]$ is odd, all $d$s are odd. So, the solution is to find minimum value of $i$ such that $sum[i] \geq abs(a-b)$.
 » 21 month(s) ago, # |   +11 whats the hack for D? and also is it a wa hack or a tle one?
•  » » 21 month(s) ago, # ^ | ← Rev. 2 →   0 41 42 53 86 7The answer should be NO.
 » 21 month(s) ago, # |   0 who can help me???67258839
•  » » 21 month(s) ago, # ^ |   +3 problem C
•  » » » 21 month(s) ago, # ^ |   +5 I think your mistake is, you are adding 1 to $ans2[i]$ and $ans1[i]$ when you get 1, and adding -1 when you get 2. But, you need to check frequency of 1 and 2 first. If the frequency of 1 is greater, then you increment $ans[i]$ if 1 is found, and otherwise increment decrease $ans[i]$ by 1. I did the same mistake first.
•  » » » » 21 month(s) ago, # ^ |   +2 Can you give me a counterexample?thank you
•  » » » » » 21 month(s) ago, # ^ |   +6 I suggest you to use map. You are running the loop from 0 to $2*n$ and $2*n$ can be $2*10^5$ at most, but your array size is less than that. And also your nested loop may cause TLE.
•  » » » » » » 21 month(s) ago, # ^ |   +3 all right, i find my misstake if(i <= n && k-i <= n) accpeted ,thank you
 » 21 month(s) ago, # |   +37 When will system test start?
 » 21 month(s) ago, # |   +13 When system tests?-
 » 21 month(s) ago, # |   0 someone can tell me why ( ans*(ans+1) — abs(a-b) )%2 == 0 in problem B ?
•  » » 21 month(s) ago, # ^ |   0 Imagine two numbers a and b. a=1 and b=5. The difference between both is 4. So we need a summation that is bigger than 4 like 1+2+3 which is equal to 3 steps. lets take the all the summation and add it to B so now the B becomes 11 and the difference is now 10. If you took the 2 from the summation and deleted it from B and added it to A, the difference will become 6 as you subtracted 2 from B and added it to A. do the same for the 3 and now the difference become 0. So overall, it has double the effect. 1+2+3=6 that summation accepts the difference between A and B to be:6,4,2,0. To sum up the idea, the summation result and the difference between A and B should be both either even or odd! I hope this helped!
•  » » » 21 month(s) ago, # ^ |   0 ok, i got it. Thank for your help ^^^
 » 21 month(s) ago, # | ← Rev. 2 →   0 Can somebody help me with the fact that — "What is the best way to approach a mathematical problem?"(Like Problem B in this contest).I usually try to make some test cases and from that cases try to form a general formula.But most of the times,i get WA in test case 4-5. :(
•  » » 21 month(s) ago, # ^ |   0 Whenever you solve a problem(or maybe you fail to) always try to understand the mathematical solution behind it. It will add up to your knowledge and may help you next time. This is a never-ending process, you have to learn something new, every time.
•  » » 21 month(s) ago, # ^ |   0 I think that each individual develops their own mathematical intuition for different types of problem and I am sorry to say that there is no shortcut to approach such problems, except one, practicing and up-solving lots and lots of math problems.
•  » » 21 month(s) ago, # ^ | ← Rev. 2 →   +6 1 — Solve codeforces under 1000-dif-math problem This is best way to get a better view of math problems(also all A&B problem)[I had the same problem solving math problems] and how to think better. As you done(became master solving this kind of problems easily), Start solving under 1500-dif and so on.2 — Study number theory.3 — Every step in thinking on a problem ask yourself what to do now? this gives your mind a really nice view about the problem.4 — Don't ignore some dumb ideas on a problem (sometimes this dumb ideas are the solution)5 — Search for the pattern not for a single testcase you wrote, think more open (for example : in problem B, it was better to write down all the differences that adding 1 to n can make. (I also did this & got Acc on B)Hope it was helpful.
•  » » » 21 month(s) ago, # ^ |   +5 Thanks,That was very helpful ^_^
 » 21 month(s) ago, # |   +37 When the ratings will be updated?
 » 21 month(s) ago, # |   0 Can anyone share their approach to solve D?
•  » » 21 month(s) ago, # ^ | ← Rev. 2 →   +9 basic idea is sort the range in increasing order of l. now consider a range at index i {l,r} find all the range that start b/w (l,r) and end after r then there will be intersection b/w segment without completely inside of another.now how can we do that optimally, maintain a segment tree such that v[i]=range[i].r after sorting. we can find the range of index of segment for which segment start b/w (l,r) using lower_bound. now we can update using segment tree, if max of v[i] is less than r for an interval in segment tree then we won't go into that node, otherwise there can be atleast one segment for which it start b/w (l,r) and end after r.In worst case there could nc2 edges but we don't need to go beyond n-1 edges. once there are n edges in graph it will no longer remain tree. so we can use dsu to maintain whether we got the cycle or not.to find a node in segment tree such that there will be intersection b/w segments, its complexity will be O(logn) using segment tree. we need to add atmost n-1 edges so combined complexity will be O(nlogn) and we need to maintain dsu for cycle check that can be O(nlogn) so overall complexity will be O(nlogn) Here is my Submission
•  » » » 21 month(s) ago, # ^ |   0 Shouldn't you have Min[p] = v[l] in your build function at line 111?
•  » » » » 21 month(s) ago, # ^ |   +5 Oh yeah, my mistake I missed that in build function but reason it didn't made any effect on verdict because Min[i] will always be zero and the condition I applied (Min[i]>r) will never be true.I think my solution is pretty complex. Mohammad_Amin mentioned very simple idea for implementation as well in comment
•  » » 21 month(s) ago, # ^ |   +14 Get all the edges until it's less that n :) 67240718
 » 21 month(s) ago, # |   +6 when editorial will be published ?
 » 21 month(s) ago, # |   0 Can C be done in worst case O(n) time without using hashmap? I managed to do it in O(nlog n) using map, but I am curious about linear time!
•  » » 21 month(s) ago, # ^ |   0 I think so using prefix and suffix sums and jumping pointers.
•  » » 21 month(s) ago, # ^ |   +2 Instead of using a map to query the nearest index in the right half with required difference in strawberries and blackberries, we can maintain an array with size $2n$ initialized to -1. This works since difference ranges between $-n$ and $+n$. This will run in $O(n)$.
•  » » 21 month(s) ago, # ^ |   0 Well yes, we can surely do that, but is there some general method to find if there exists a subarray whose sum is a given value, in linear time?
 » 21 month(s) ago, # |   +7 ............When the ratings will be updated?
•  » » 21 month(s) ago, # ^ |   0 Its updated now.
 » 21 month(s) ago, # |   0 Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
 » 21 month(s) ago, # |   -18 when will the parsing be published? (if anyone has a discard please)
 » 21 month(s) ago, # |   0 Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
 » 21 month(s) ago, # |   0 Why does this solution 67308922 fails on case #434 on test 2?
 » 21 month(s) ago, # |   0 Where can i get solutions for Codeforces round 78 Div. 2?
 » 21 month(s) ago, # |   0 67469642 Could someone please explain to me which part of my code is causing the "heap use after free" error shown in the diagnostics section? (I understand my code is in no way a solution to the problem it was submitted for, I would just like to know what is causing the error before I try to convert what I have into a solution)Thank you!
 » 21 month(s) ago, # |   0 Need Help! Can anyone please explain how to approach problem 3 im newbie don't know how to approach this problem ??