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 C137. The problem B was suggested by Srikanth Bhat bharsi. Mohammad Amin Raeisi Smaug 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 C137, Srikanth Bhat bharsi, Mohammad Amin Raeisi Smaug, 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 tribute_to_Ukraine_2022 and uwi with the win and halyavin with 93 hacks! The editorial is ready.
After looking at bus, I thought problems will be about Scooby Doo!
I hope you would all benefit and learn something new from my problem :D
Well, I barely solved all problems the last time. I will unlikely have time to solve another one.
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?
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 :-)
I'm always thinking that educational round is prepared for my next rating-increasing round.
How to solve E?
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) + mi
Answer is f(n) + mn
Oh，how to find it? I can't understand it.
why (2m-1) ??
For E, wrote a bruteforce solution and looked at few answers for small values. Then found very simple relation when N increases.
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.
Nice! How to get the first formula and how to transform it into second?
It is the author solution. I'll post the editorial soon.
can I find out whether declared the best crackers?
How do you figure out that "simple relations"? :D
I've also bruteforced for M = 2, OEIS'ed it, and found a similar formula.
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.
This was the first time I wrote CHT which works correctly on the samples :D BTW, how to solve E?
what is CHT?
convex hull trick, maybe?
Yes, convex hull trick :)
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.
One can just use fast power algorithm.
In F I was getting WA on test 29 and then changed double to long double to get accepted :(
It was supposed to be solved with 64-bit integers.
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 :)
I got hacked on A for the stupidest reason ;_;
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.
you can simply insert 1 .... because it is co-prime with any number
Could anyone explain me why this code gets TLe for problem D? 17241743
How to solve C in O(n)?
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
countOfChangedElementsis more than
kyou should move left iterator while
countOfChangedElements > k
On each iteration you should update an answer (if
(curAnswer = r - l + 1) > maxAnsweryou should update
maxL, maxRindexes, because you will also need to print a resulting array)
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.
I did it in nLogn should also pass
You're welcome :p
When the hacking stage will start ?
It has started.
How to solve D: Number of parallelograms http://codeforces.com/contest/660/problem/D ?
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.
Can you explain further more ?
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)/2
Hope it helped a little bit ^_^
Good luck — feel free to ask additional questions :)
Can you please explain how to get the formula N*(N-1)/2? Thanks
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.
weak test cases on A ?