By pikmike, history, 6 weeks 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 Ne0n25 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 SweetPrinces 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 wxhtxdy 0:07

UPD: Editorial is out

• +129

 » 6 weeks ago, # |   +124 ![ ]()
 » 6 weeks ago, # |   0 Best of luck to all those participating!!! Can't wait to see what problems there will be!!!
 » 6 weeks ago, # |   -9 CODEFORCES IS THE BEST SITE FOR PRACTICE...
 » 6 weeks ago, # |   +16 Why educational rounds have more greedy problems?
•  » » 6 weeks ago, # ^ |   +9 because greed is good.https://www.youtube.com/watch?v=6bbzwJ0Sx48
•  » » » 6 weeks ago, # ^ |   0 I was not expecting a video in the comment! LOL
•  » » 6 weeks ago, # ^ |   0 sorry bro by mistake vote -ve ho gaya
•  » » » 6 weeks ago, # ^ |   -7 You can still make positive.
 » 6 weeks ago, # | ← Rev. 2 →   -20 Clashes with Mirror replay round of ICPC Gwalior regionals on Codechef
•  » » 6 weeks 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.
•  » » » 6 weeks ago, # ^ |   0 Would have considered that helpful, if u had replied before the contests started rather than now. Anyways peace out!
 » 6 weeks ago, # |   +3 anyone please provide any good resource(book,blog,lecture) for understanding lazy-propagation i am unable to understand that.
•  » » 6 weeks ago, # ^ |   +3
•  » » 6 weeks ago, # ^ |   +1
•  » » » 6 weeks ago, # ^ |   -9 thanks this seems really good
 » 6 weeks ago, # |   +55 Who want to see my screencast(without comments)? Not sure I'm as cool as Um_nik tbh.
•  » » 6 weeks ago, # ^ |   0 I want it!
•  » » 6 weeks ago, # ^ |   0
 » 6 weeks 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).
 » 6 weeks ago, # |   +3 Can D solved something like interval handling using set?
•  » » 6 weeks ago, # ^ |   0 I tried and got MLE on test 51 :(
•  » » » 6 weeks ago, # ^ |   +6 :)
•  » » 6 weeks ago, # ^ |   0 yes, it can.
•  » » » 6 weeks 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?
•  » » » » 6 weeks 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
•  » » » » 6 weeks ago, # ^ |   +14 when you have more than n-1 edges, just stop.
•  » » » 6 weeks ago, # ^ |   +1 Okay, I get if(it.first > a[j].r) break; this makes it run faster.
 » 6 weeks ago, # |   +2 For problem B, who solved using https://oeis.org/A140358
•  » » 6 weeks 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 ?
•  » » » 6 weeks 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.
 » 6 weeks ago, # |   +1 WHAT IS TEST CASE 2 OF DIV2B
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   0 Try for cases like 2 4 (Ans:3) or 5 14 (Ans:5)
•  » » » 6 weeks ago, # ^ |   0 how is the answer for 2,4 equal to 2 ? could you explain it a little more
•  » » » » 6 weeks ago, # ^ |   0 Sorry my mistake. Corrected.
•  » » » » » 6 weeks 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 ?
•  » » » » » » 6 weeks 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
•  » » » » » » 6 weeks ago, # ^ |   0 5 + (1 + 2 + 4 + 5) = 14 + 3
•  » » » 6 weeks ago, # ^ |   0 Can you prove your answer 5 in 5 14
•  » » » » 6 weeks ago, # ^ |   0 See above
 » 6 weeks ago, # |   +47 Screencast if anyone's interested: https://youtu.be/g4Gcl0yAgDU
•  » » 6 weeks ago, # ^ |   -10 Subscribed :)
•  » » 6 weeks ago, # ^ |   +7 42 minutes ?!
•  » » 6 weeks ago, # ^ |   +1 Wow! That's really cool. Hoping to get more of them
•  » » 6 weeks ago, # ^ |   0 Subscribed!Simply amazing!!!
•  » » 6 weeks 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...
•  » » » 6 weeks ago, # ^ |   0 The bits were only used to test parity. https://codeforces.com/blog/entry/72268?#comment-565771 describes my solution well.
 » 6 weeks ago, # |   +26 How to solve D? P.s. round was great, so interestring problems!
 » 6 weeks 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?
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   0 input: 1 31 20output : 5
•  » » » 6 weeks ago, # ^ | ← Rev. 2 →   0 Yes, getting 6 as output.
•  » » » » 6 weeks ago, # ^ |   0 Sorry, the output should be 5
•  » » 6 weeks ago, # ^ |   0 test this: 1 5 answer is 3 because: 1) 1 6 2) 3 6 3) 6 6
•  » » » 6 weeks ago, # ^ |   0 Thanks for this case!So what was the approach to solving the problem?
•  » » » » 6 weeks 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
•  » » » » » 6 weeks ago, # ^ |   0 Is there any chance of getting the second problem being hacked?
•  » » » » » » 6 weeks ago, # ^ |   0 I think no.Educational rounds usually have strong sys tests
•  » » » » » » » 6 weeks ago, # ^ | ← Rev. 2 →   0 Still, many solutions of problem D have been hacked!
•  » » » » » 6 weeks ago, # ^ |   0 But you just did ++tmp it does't mean tmp = 1 + 2 + 3 + ... +n.i hope you understand.
•  » » » » » » 6 weeks 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.
•  » » 6 weeks ago, # ^ |   0 I did the same and it was wrong. Have you find mistake? please explain if yes...
 » 6 weeks ago, # |   0 How do you guys solved C? I thought of a greedy approach but it didn't worked :(.
•  » » 6 weeks ago, # ^ |   0 using 2 prefix sum arrays and then using maps
•  » » 6 weeks 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)
•  » » 6 weeks ago, # ^ |   +1 What is wrong in the greedy approach?Cant I just eat up the jar which is closest to me?
•  » » 6 weeks 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
 » 6 weeks 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? :)
•  » » 6 weeks 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.
•  » » » 6 weeks 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)
•  » » » » 6 weeks ago, # ^ |   +13 Wow, that's nice. The idea is almost the same as mine one, but works much faster.
 » 6 weeks ago, # |   +1 Anyone solve C using binary search???
•  » » 6 weeks ago, # ^ |   0 I tried with binary search but i got Wrong answer on test 2
•  » » » 6 weeks ago, # ^ | ← Rev. 2 →   +3 same here, but now I realise that binary search will not work on some cases
•  » » 6 weeks 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.
•  » » » 6 weeks ago, # ^ |   0 Could you please explain the process in detail ?
•  » » » » 6 weeks 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.
•  » » » » » 6 weeks ago, # ^ |   0 Thanks .
 » 6 weeks ago, # |   +1 How to solve B?
•  » » 6 weeks 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)
•  » » » 6 weeks ago, # ^ |   0 Thank you dude
•  » » » 6 weeks ago, # ^ |   0 What is the logic behind that?
•  » » 6 weeks 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..
•  » » » 6 weeks 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
•  » » » » 6 weeks ago, # ^ |   0 We haven't proved yet .We have proved necessary condition but not sufficient ,
•  » » » » » 6 weeks 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 ?
•  » » » 6 weeks ago, # ^ |   0 tmwilliamlin168 Care to explain?
•  » » » » 6 weeks 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.
•  » » » 6 weeks 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$
•  » » » 6 weeks 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
 » 6 weeks ago, # |   0 How to solve C?
•  » » 6 weeks 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.
 » 6 weeks ago, # |   +52 This was the most difficult B I've ever seen.
 » 6 weeks ago, # |   0 That moment when you find the bug in the last second I'm so unlucky
•  » » 6 weeks ago, # ^ |   +6 That moment when C is easier than B :sad:
•  » » » 6 weeks 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) :)
•  » » » » 6 weeks ago, # ^ |   0 Only if how to solve meant that the question was easy :(
 » 6 weeks 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
•  » » 6 weeks ago, # ^ |   +1 Did you cover the case when you eat up no jar from the left side or right side?
•  » » 6 weeks 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.
•  » » » 6 weeks ago, # ^ |   0 Could you give me a test that explain your idea?
•  » » » » 6 weeks 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.
•  » » » 6 weeks ago, # ^ |   0 In which test case my solution is wrong?? https://codeforces.com/contest/1278/submission/67240467
•  » » » 6 weeks 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
 » 6 weeks 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.
•  » » 6 weeks ago, # ^ |   +2 you don't cover the case when you eat no jar from the left or right
•  » » 6 weeks ago, # ^ |   0 You may have missed some corner cases..
 » 6 weeks ago, # |   +24 How to solve F?
•  » » 6 weeks 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.
•  » » » 6 weeks 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.
•  » » » » 6 weeks ago, # ^ |   +1 Off topic note: does anyone know how to fix the inline latex not rendering correctly? :P
•  » » » » » 6 weeks 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]$
•  » » » » 6 weeks 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
•  » » » » » 6 weeks 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.
•  » » » » » » 6 weeks ago, # ^ |   0 THX！How stupid of me for forgetting this is a "programming" competition lol
•  » » » » 6 weeks 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.
•  » » » » » 6 weeks 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.
•  » » » » 6 weeks ago, # ^ |   +3 Can you tell why can we raise i to the power k?
•  » » » » » 6 weeks ago, # ^ |   +3 Yes, it is actually from the definition of expected value. Informally, expected value of $f(x)$ is equal to: Unable to parse markup [type=CF_MATHJAX] Unable to parse markup [type=CF_MATHJAX]In this case, $f(x) = x^k$, and the probability terms end up equaling the coefficients in my above comment.
•  » » » » 6 weeks ago, # ^ |   0 Your solution was much better than the MGF one!
•  » » » 6 weeks 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?
•  » » » » 6 weeks ago, # ^ |   +1 Yes, I can explain derivative implementation details :). Unable to parse markup [type=CF_MATHJAX]We remove constant Unable to parse markup [type=CF_MATHJAX] and account for it at the end. Now we do derivative and multiply by $x$. Unable to parse markup [type=CF_MATHJAX]Now, the second repetition. Unable to parse markup [type=CF_MATHJAX] Unable to parse markup [type=CF_MATHJAX]We notice all terms are of form Unable to parse markup [type=CF_MATHJAX] for some coefficient $C$ and some power $i$. We create an array $a$ of size $k+1$ with indices Unable to parse markup [type=CF_MATHJAX] 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 Unable to parse markup [type=CF_MATHJAX].
•  » » 6 weeks 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).
•  » » » 6 weeks ago, # ^ | ← Rev. 2 →   +38 F can be done in Unable to parse markup [type=CF_MATHJAX] using FFT.Unable to parse markup [type=CF_MATHJAX], where Unable to parse markup [type=CF_MATHJAX] is indicator variable for the Unable to parse markup [type=CF_MATHJAX] try. Unable to parse markup [type=CF_MATHJAX] Unable to parse markup [type=CF_MATHJAX]Now, the Inner expected value can be calculated as : Unable to parse markup [type=CF_MATHJAX]So, cleaning, we get : Unable to parse markup [type=CF_MATHJAX]The inner sum part for each $i$ can be calculated over all $i$ using NTT, and so overall Unable to parse markup [type=CF_MATHJAX] My Submission
•  » » 6 weeks ago, # ^ |   +60
 » 6 weeks ago, # |   0 Does anyone have proof that the answer for problem $F$ is polynomial of degree $k + 1$?
•  » » 6 weeks 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.
•  » » 6 weeks 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.
 » 6 weeks 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.
 » 6 weeks 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 
 » 6 weeks 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?
 » 6 weeks ago, # |   +6 when's the editorial coming?
•  » » 6 weeks ago, # ^ |   0 After ends the hacking phase , hope so.
 » 6 weeks ago, # | ← Rev. 2 →   0 While everyone is discussing C/D/E/F, newbie is thinking how to solve B :(
 » 6 weeks ago, # |   +3 I think proof of B had similar idea as this question: https://atcoder.jp/contests/abc147/tasks/abc147_f
 » 6 weeks 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)$.
 » 6 weeks ago, # |   +11 whats the hack for D? and also is it a wa hack or a tle one?
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   0 41 42 53 86 7The answer should be NO.
 » 6 weeks ago, # |   0 who can help me???67258839
•  » » 6 weeks ago, # ^ |   +3 problem C
•  » » » 6 weeks 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.
•  » » » » 6 weeks ago, # ^ |   +2 Can you give me a counterexample?thank you
•  » » » » » 6 weeks 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.
•  » » » » » » 6 weeks ago, # ^ |   +3 all right, i find my misstake if(i <= n && k-i <= n) accpeted ,thank you
 » 6 weeks ago, # |   +37 When will system test start?
 » 6 weeks ago, # |   +13 When system tests?-
 » 6 weeks ago, # |   0 someone can tell me why ( ans*(ans+1) — abs(a-b) )%2 == 0 in problem B ?
•  » » 6 weeks 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!
•  » » » 6 weeks ago, # ^ |   0 ok, i got it. Thank for your help ^^^
 » 6 weeks 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. :(
•  » » 6 weeks 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.
•  » » 6 weeks 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.
•  » » 6 weeks 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.
•  » » » 6 weeks ago, # ^ |   +5 Thanks,That was very helpful ^_^
 » 6 weeks ago, # |   +37 When the ratings will be updated?
 » 6 weeks ago, # |   0 Can anyone share their approach to solve D?
•  » » 6 weeks 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
•  » » » 6 weeks ago, # ^ |   0 Shouldn't you have Min[p] = v[l] in your build function at line 111?
•  » » » » 6 weeks 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. ioustreamh mentioned very simple idea for implementation as well in comment
•  » » 6 weeks ago, # ^ |   +14 Get all the edges until it's less that n :) 67240718
 » 6 weeks ago, # |   +6 when editorial will be published ?
 » 6 weeks 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!
•  » » 6 weeks ago, # ^ |   0 I think so using prefix and suffix sums and jumping pointers.
•  » » 6 weeks 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)$.
•  » » 6 weeks 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?
 » 6 weeks ago, # |   +7 ............When the ratings will be updated?
•  » » 6 weeks ago, # ^ |   0 Its updated now.
 » 6 weeks ago, # |   0 Auto comment: topic has been updated by PikMike (previous revision, new revision, compare).
 » 6 weeks ago, # |   -18 when will the parsing be published? (if anyone has a discard please)
 » 6 weeks ago, # |   0 Auto comment: topic has been updated by PikMike (previous revision, new revision, compare).
 » 6 weeks ago, # |   0 Why does this solution 67308922 fails on case #434 on test 2?
 » 6 weeks ago, # |   0 Where can i get solutions for Codeforces round 78 Div. 2?
 » 5 weeks 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!
 » 5 weeks ago, # |   0 Need Help! Can anyone please explain how to approach problem 3 im newbie don't know how to approach this problem ??