### Edvard's blog

By Edvard, history, 2 years ago, translation, ,

Hello, Codeforces!

Educational Codeforces Round 11 will take place on 8 april 2016 at 18:00 MSK for the first and the second divisions.

<The changes in the last paragraph>

The round will be unrated for all users and it will be held with extented ACM ICPC rules. You will have two hours to solve six problems. After that you will have one day to hack any solution you want. You will have access to copy any solution and test it locally.

If you have ideas for some problems or maybe already prepared problems that you can't use in rounds or official competitions, you can write to me.

It seems that it is harder to invent interesting simple problems (like A and B) than difficult ones. So don't be afraid to suggest interesting simple or very simple tasks (of course the difficult tasks are also needed). Please send only the problems for which you know the solution with clear statement (the story is not required). And also please add one or two samples to make the problem statement more clear.

</The changes in the last paragraph>

The problemset was suggested by Codeforces users. The problem А was suggested by Ali Ibrahim New_Horizons. The problem B was suggested by Srikanth Bhat srikkbhat. Mohammad Amin Raeisi aminra sent the problem C. The problem D was suggested by Sadegh Mahdavi smahdavi4 a long ago. The problem E is the last (the fourth) problem suggested by Lewin Gan lewin. The problem F is the last (if I'm not wrong the third) problem suggested by Kamil Debowski Errichto.

Thanks a lot to them and all others who are sending the problems! At this point I've checked all the problems sent to me (except maybe for the problems sent in last week). I hope that I've replied to all of you. I have a list with all problems sent to me, so be sure I don't forget about your problem.

The problems F was prepared by Kamil Debowski Errichto. Other problems was prepared by me (Edvard Davtyan). Thanks to Maria Belova Delinur for checking the English statements. The problems was tested by users suggested them, respectively: Ali Ibrahim New_Horizons, Srikanth Bhat srikkbhat, Mohammad Amin Raeisi aminra, Sadegh Mahdavi smahdavi4, Lewin Gan lewin and Kamil Debowski Errichto. Thanks a lot to all of them!

I hope you will enjoy the problems! I'm considering the possibility to copy the problem E with larger constraints as problem G. What do you think about that?

Good luck and have fun!

P.S.: The bus from the problem B.

UPD: The contest is finished. Congrats to kezsulap and uwi with the win and halyavin with 93 hacks! The editorial is ready.

•
• +160
•

 » 2 years ago, # |   +12 After looking at bus, I thought problems will be about Scooby Doo!
 » 2 years ago, # |   +3 I hope you would all benefit and learn something new from my problem :D
 » 2 years ago, # |   +22 Well, I barely solved all problems the last time. I will unlikely have time to solve another one.
•  » » 2 years ago, # ^ |   -33 Is that a necessary condition for contest to be good to have sufficiently easy problems so that you can comfortably solve all of them :P?
•  » » 2 years ago, # ^ |   +6 Actually I think this time the contest will be a little easier than usual. The problem E can be solved for larger constraints, so it is not an another one, it is the same with larger constraints :-)
 » 2 years ago, # |   -27 I'm always thinking that educational round is prepared for my next rating-increasing round.
 » 2 years ago, # |   -11 Despite the fact that there are about 20 minutes left, I can't register to this contest. Is there any change in the registration rules?
•  » » 2 years ago, # ^ |   0 The problem was solved.
 » 2 years ago, # |   +6 How to solve E?
•  » » 2 years ago, # ^ | ← Rev. 2 →   +10 After a bit of observation (actually I just write every sequence for n = 2, m = 3), I get this recurrence: f(i) = f(i - 1) * (2m - 1) + miAnswer is f(n) + mn
•  » » » 2 years ago, # ^ |   0 Oh，how to find it? I can't understand it.
•  » » » » 2 years ago, # ^ |   0 why (2m-1) ??
 » 2 years ago, # |   +11 For E, wrote a bruteforce solution and looked at few answers for small values. Then found very simple relation when N increases. res = 2 * m for i in range(2, n + 1): res = res * (2 * m - 1) + m**(i - 1) 
•  » » 2 years ago, # ^ | ← Rev. 2 →   +8 Alternatively f[n] = (3 * m - 1) * f[n - 1] + (m - 2 * m^2) * f[n - 2]. Worst part, I calculated the coefficients but did not believe in them.
•  » » 2 years ago, # ^ | ← Rev. 6 →   +20 My solution
•  » » » 2 years ago, # ^ |   0 Nice! How to get the first formula and how to transform it into second?
•  » » » 2 years ago, # ^ |   +3 It is the author solution. I'll post the editorial soon.
•  » » » » 2 years ago, # ^ |   +2 can I find out whether declared the best crackers?
•  » » » » » 2 years ago, # ^ |   +15
•  » » 2 years ago, # ^ | ← Rev. 3 →   +8 How do you figure out that "simple relations"? :DI've also bruteforced for M = 2, OEIS'ed it, and found a similar formula.
•  » » » 2 years ago, # ^ |   0 When I fixed M = 5, increasing N seemed to multiply the result by 9, and looking at remainders showed powers of 5. For M = 7 multiplier was 13, so it is 2m - 1.
 » 2 years ago, # |   0 This was the first time I wrote CHT which works correctly on the samples :D BTW, how to solve E?
•  » » 2 years ago, # ^ |   +1 what is CHT?
•  » » » 2 years ago, # ^ |   +5 convex hull trick, maybe?
•  » » » 2 years ago, # ^ |   0 Yes, convex hull trick :)
•  » » » » 2 years ago, # ^ |   -6 F?
•  » » » » » 2 years ago, # ^ |   +5 Yes.
 » 2 years ago, # |   +28 If you want to try, attempt to find a simple closed form for E. You can then solve this if n,m <= 10^9 instead.
•  » » 2 years ago, # ^ |   0 One can just use fast power algorithm.
 » 2 years ago, # |   +5 In F I was getting WA on test 29 and then changed double to long double to get accepted :(
•  » » 2 years ago, # ^ |   +10 It was supposed to be solved with 64-bit integers.
•  » » » 2 years ago, # ^ |   0 Yeah, I put long long after getting accepted with long double. It's just my first time with CHT and I was trying to be fast so simply put double everywhere and then I saw I need it only when computing the intersections' X coordinates :)
 » 2 years ago, # |   -10 I got hacked on A for the stupidest reason ;_; What is the largest prime <= 10^9, because gcd with primes = 1, and I completely forgot that gcd with 1 is also 1, and that gcd of largest prime with itself is not 1 lol
•  » » 2 years ago, # ^ |   +22 What?
•  » » » 2 years ago, # ^ |   -10 I got hacked because the integer I inserted is the largest prime<=10^9 which was I think 99999931. But I should've inserted 1.
•  » » » » 2 years ago, # ^ |   +4 you can simply insert 1 .... because it is co-prime with any number
 » 2 years ago, # |   0 Could anyone explain me why this code gets TLe for problem D? 17241743
•  » » 2 years ago, # ^ |   -18 tl;dr
 » 2 years ago, # |   0 How to solve C in O(n)?
•  » » 2 years ago, # ^ | ← Rev. 6 →   +4 You can use two iterators — left and right border. You will have the best answer only if you changed zeroes such that after this action you get one long line. So you can move right iterator while countOfChangedElements <= k When countOfChangedElements is more than k you should move left iterator while countOfChangedElements > k On each iteration you should update an answer (if (curAnswer = r - l + 1) > maxAnswer you should update maxAnswer and maxL, maxR indexes, because you will also need to print a resulting array)
•  » » 2 years ago, # ^ |   0 Two Pointers.If you decide to convert segment [L , R] into all 1's , the operations required would be the count of 0 in range [L,R].We can then extend the right pointer until the count of 0 does not exceed K.
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 two pointers -- here is code 17242755
•  » » 2 years ago, # ^ |   0 I did it in nLogn should also pass
•  » » » 2 years ago, # ^ |   0 Thanks :D
•  » » » » 2 years ago, # ^ |   0 You're welcome :p
 » 2 years ago, # |   0 When the hacking stage will start ?
•  » » 2 years ago, # ^ |   +6 It has started.
 » 2 years ago, # |   0 How to solve D: Number of parallelograms http://codeforces.com/contest/660/problem/D ?
•  » » 2 years ago, # ^ | ← Rev. 2 →   +8 for every pair of points (xi, yi), (xj, yj) we find midpoint (xi + xj) / 2, (yi + yj) / 2. Now for all midpoints we make map cnt[(x, y)] — count of pair for which (x, y) — midpoint. Answer is sum (cnt[(x, y)] * (cnt[(x, y)] — 1)) / 2 for all (x, y) in map.
•  » » » 2 years ago, # ^ |   0 Can you explain further more ?
•  » » » » 2 years ago, # ^ |   +1 Hello,my version is almost similar, see here — function "par"The thought is, to do "vector addition" from all pair of points, and store them somewhere (in an array — "R" in my case). Here, we can sort it (or as Naduxa said, store it in the map) and find number of "pairs" which can make parallelogram. The pairs, which can do so are those pairs, which are "equal". So now, we know the number of those (from the sorted array /or/ map) and use Gauss's formula (given above) == N*(N-1)/2Hope it helped a little bit ^_^Good luck — feel free to ask additional questions :)
•  » » » » » 2 years ago, # ^ |   0 Can you please explain how to get the formula N*(N-1)/2? Thanks
•  » » » » » » 2 years ago, # ^ |   +3 The number of pairs out of N items is equal to the number of ways to choose 2 items out of N items. With knowledge of combinatorics, we get N(N-1)/2.There is an alternative way. Recall that 1+2+...+N equals N(N+1)/2. The first item has N-1 items to pair with. The second has N-2 items to pair with, for the first item has paired with it already. And so on, until the last item which has zero items to pair with; all of the previous items have already paired with it. Therefore, there are N(N-1)/2 pairs in total.