Edvard's blog

Educational Codeforces Round 11
By Edvard, history, 9 years ago, translation, In English

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 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.

  • Vote: I like it
  • +160
  • Vote: I do not like it

Comments Comments (51)
| Write comment?
»
9 years ago, # |
  Vote: I like it +12 Vote: I do not like it

After looking at bus, I thought problems will be about Scooby Doo!

→ Reply
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I hope you would all benefit and learn something new from my problem :D

→ Reply
»
9 years ago, # |
  Vote: I like it +22 Vote: I do not like it

Well, I barely solved all problems the last time. I will unlikely have time to solve another one.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it -33 Vote: I do not like it

    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?

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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 :-)

    → Reply
»
9 years ago, # |
  Vote: I like it -27 Vote: I do not like it

I'm always thinking that educational round is prepared for my next rating-increasing round.

→ Reply
»
9 years ago, # |
  Vote: I like it +6 Vote: I do not like it

How to solve E?

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +10 Vote: I do not like it

    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

    → Reply
»
9 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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)
→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    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.

    → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 6   Vote: I like it +20 Vote: I do not like it

    My solution

    → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 3   Vote: I like it +8 Vote: I do not like it

    How do you figure out that "simple relations"? :D
    I've also bruteforced for M = 2, OEIS'ed it, and found a similar formula.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This was the first time I wrote CHT which works correctly on the samples :D BTW, how to solve E?

→ Reply
»
9 years ago, # |
  Vote: I like it +28 Vote: I do not like it

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.

→ Reply
»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

In F I was getting WA on test 29 and then changed double to long double to get accepted :(

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    It was supposed to be solved with 64-bit integers.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 :)

      → Reply
»
9 years ago, # |
  Vote: I like it -10 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

    What?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it -10 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

        you can simply insert 1 .... because it is co-prime with any number

        → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Could anyone explain me why this code gets TLe for problem D? 17241743

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C in O(n)?

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 6   Vote: I like it +4 Vote: I do not like it

    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)

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I did it in nLogn should also pass

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

When the hacking stage will start ?

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D: Number of parallelograms http://codeforces.me/contest/660/problem/D ?

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you explain further more ?

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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)/2

        Hope it helped a little bit ^_^

        Good luck — feel free to ask additional questions :)

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Can you please explain how to get the formula N*(N-1)/2? Thanks

          → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

            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.

            → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

weak test cases on A ?

→ Reply