Educational Codeforces Round 23
By BledDest, history, 8 years ago, translation, In English

Hello Codeforces!

On June 15, 18:05 MSK Educational Codeforces Round 23 will start.

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.

The round will be unrated for all users and will be held on extented ACM ICPC rules. After the end of the contest you will have one day 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 prepared by Mikhail awoo Piklyaev, Vladimir vovuh Petrov and me. Huge thanks to Alexey Perforator Ripinen, Alexey ashmelev Shmelev and Maxim HellKitsune Finutin for testing!

Good luck to all participants!

UPD. I am pleased to announce the 2nd Hello Barcelona Programming Bootcamp in collaboration with Moscow Workshops ACM ICPC, which will be hosted by our partner Harbour.Space University together with Moscow Workshops ACM ICPC, ITMO University, Moscow Physics and Technology University, Saint Petersburg State University and Codeforces!

LEARN MORE

UPD: The editorial is published.

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

Comments Comments (85)
| Write comment?
»
8 years ago, # |
  Vote: I like it +35 Vote: I do not like it

WOW !! Editorial has been published before the contest.

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

    Sorry, we fixed it now.

    Anyway, it was a link to the ER22 editorial, so it would not help anyone with this round.

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

Please correct the time of the contest

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

Today is Champions Trophy Semifinal INDIA vs BANGLADESH ....Timing issue

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

servers are getting really slow. Hope the contest won't be delayed

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

    The contest will surely delay, it is tradition.

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

      Hey, it's a tradition for usual rounds but not for ERs! Previous 5 rounds started at the time they were scheduled.

      Though I really don't like current condition of servers too.

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

        Of course. The round won't be delayed but the solutions will be failed to judge.

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

Judgement failed??

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

What is Judgement Failed?

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

Me too! Don't worry. Round will be unrated. xD

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

Are pretests too weak? I am submitting crap and they all are getting "accepted" as of now.

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

Large amount of hacks on A and B is coming...

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

I think problem F could be solved using segment tree if the interval was smaller... Can it be solved using a lazy-constructed segment tree? (we create nodes as we need them)

Thanks! :)

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

    the answer is always l[i] or r[i] + 1 for some i , so just coordinate compress these points and then use normal segtree.

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

    I think we can compress the value of L and R and then build a segment tree with the new value (1 — 200000) and then use lazy-constructed segment tree as you said.

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

    Sparse Segment Tree gives MLE on test 15 :( But shouldn't that pass the ML? It creates ~ 64 nodes per update. Each node has one long long and one short.

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

      I think when we pushdown lazy tag it will expand more nodes so not just 64 nodes per update ,I guess

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

How to solve F and C?

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

    C was a binary search :)

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

    the sum of the digits can't be large, so there's not many numbers x such that the check x - digitsum(x) >  = s is interesting. Check them all and add the rest in O(1), I checked only the interval [s..min(s+200,n)].

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

    It can be proved that if a > b then a — sum_of_digits(a) >= b — sum_of_digits(b) so we can do binary search to find the smallest n that n — sum_of_digits(n) >= s

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

    All numbers from s+9*18+1 to n are really big. So you can check numbers from s to s+9*18 and add max(0, n — s+9*18)

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

    C is really a brute force problem.

    It was supposed to be A.

    Just iterate through s+1 to max(n, s+160) and find where
    this condition met -> (s+i) — sum_of_digit(s+i) >= s.
    then just print (n — (s + i) + 1).
    if not met then just print 0.

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

      Thanks, finally understood it after 3 years.

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

Any idea for D? I thought something on basis of RMQ and adding one element at a time to the array. But it is TLE easily.

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

How solve D? :'v

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

can we get AC with a NlogN solution in problem D ?

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

Why i cant double click on submissions to hack it???

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

Can't wait until tomorrow to see the verdict. Please try to hack my C. I haven't used binary search or dp. code

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

    brute force is enough for C. Dont worry!!

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

How to solve D with O(N) complexity?

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

    here you go.

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

    For each element, let the number of subarrays in which it is the min be cnt_min[i] and the number of subarrays in which it is the max be cnt_max[i]. Answer is sum of arr[i]*(cnt_max[i]-cnt_min[i]).

    To find cnt_max[i], for each index i, find the closest indices to its left and right such that value there is > arr[i]. This can be done in cumulative O(n) time using stack. Similar for cnt_min[i].
    Take care of duplicate values.

    Code

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

    The basic idea is for each i find Nmx[i] — the number of subarrays that will have a[i] number as maximum. Then do final_answer += Nmx[i] * a[i]. Similarly find Nmn[i] — number of subarrays in which a[i] will be the minimum number, and do final_answer -= Nmn[i] * a[i].

    Nmx can be found in O(N) time. To find Nmx[i], you have to find Rmx[i] and Lmx[i] such that a[i] is maximum among all numbers in the segment [Lmx[i], Rmx[i]]. Rmx and Lmx arrays can be obtained with a forward sweep and a reverse sweep of the original array.

    Similarly find Nmn array.

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

How to solve E? I could feel the use of tries but I couldn't come up with a good idea.

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

    Read this tutorial to learn how to solve similar problems involving XOR using trie.

    In this problem, maintain a trie in which numbers are inserted/removed in the decreasing order of bits in their binary representation. Now, for the query part, just traverse along the path specified by P and consider all cases in which you can get XOR < L.
    eg. if next bit of P is 0 and next bit of L is 1, you can add all the numbers along the 0-edge to the answer and then move along the 1-edge (because for all numbers inserted in subtree of 0-edge, their XOR with P will be < L).

    You can see all the cases in my code. Code

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

Constraints in the problem E are so good that an O(Q^2) solution gets AC (it's not that the tests are weak: I can't make it run for more than ~1.5 seconds).

Was it intended?

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

    Hacked.

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

      What test did you use? I thought about adding 50000 numbers than query 50000 times.

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

        That's exactly what I did.

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

          That's weird. I didn't try this hack because it worked less than <1.5 seconds using custom invocation (and even a little bit less locally with actual input reading/printing the answer).

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

      Cool. What's the idea of your test case? I tried to do something like adding different numbers K times and than making N — K queries (choosing K to maximize the run time), but it didn't work.

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

        I just took K = 50000.

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

      What about this one?

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

The editorial is published.

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

This was another great educational round from your part, I liked the problems a lot, keep up the good work.

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

Why my MEX queries does not work? Here's my code:

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

It seems like that several past educational rounds are full of data structure problems XD

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

    They are :c We really try to balance out problemsets but everytime it ends up with lots of ds problems.

    I guess that it is actually fine in context of ERs because education in competitive programming is mostly about learning algos and data structures. Still somehow I am not pleased with the quality of contests...

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

For B. Makes And The Product I don't know why my logic won't work

27820072

Basically I am counting the frequencies of smallest 3 distinct elements. For example 1 1 1 2 2 3 3 3 3

So the frequency is 1 -> 3, 2-> 2, 3->4 Call them k1,k2,k3 for smallest numbers a1,a2,a3

If k1>=3, it means the constituents of my minimum product all come from a1...So it is k1 choose 3

else if k1==2, then i just choose one of a2, which gives k2 ways.

else if k1==1 and k2>=2, then number of ways is k2 choose 2

else if k1==1 and k2==1, then i have to choose one a3, k3 choose 1 way of doing that.

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

    overflow.(btw, you declared n as long long and answer as int lol)

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

      I have used long long but still someone has hacked mine. code

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

        if(x != y and x != z) should be if (x != y and y != z)

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

    Your logic works, but the result of k1 choose 3 doesn't fit in an int type, you should use long long int.

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

214 successful hacks!! Great!

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

    As usual :D

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

      There is just too few tests for such tricky problems. Authors often use Educational Rounds as an excuse to be a bit lazy.

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

        Which problem was the tricky one?

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

        Well, most of the hacks are made on easier problems. We can't add too many tests for them as it can lead to big server load. I won't deny that we don't try that hard to make tests as strong as possible but it isn't easy to cover all the cases with 10-15 tests.

        There is just about couple of dozens successful hacks for D-F. I suppose that is fine, isn't it?

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

          Server load is definitely a concern. Do you know how bad it is in practice? May be we can afford more tests from B onward?

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

            I'm not sure. As far as I can guess from usual rounds, ~30 tests for task with ~20 submits per minute is about the limit (considering submissions for all problems, not only this one).

            Though it's hard to determine submissions rate before the contest. Adding more tests is always risky.

            I suppose that we can try pushing this limit a bit by rearranging tests. I don't think that A can have more tests than it currently does but for B it's possible, I think. We will try to increase this number in next round.

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

              Use multitests

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

                Great point! Why didn't we even consider it previously? Thanks, next round will definitely include multitest in problems B or C then.

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

                  Because everyone hates multitest? You don't feel progress while fixing bugs and yet still getting WA2.

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

                  It's not a problem to make a couple of somewhat hard testcases of 1 test and place it right after samples...

                  Does everyone really hate it that much?

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

Can anyone explain me D&C solution for D? Because solution with stacks looks awful. I was thinking D&C on contest but couldnt solve it. Edit: got it. This solution helped me: http://codeforces.net/contest/817/submission/27832753

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

Would you please update the Python2 version for the judging system?

This submission is said to be runtime error for python 2.7.3 while it works perfectly on my macbook with python 2.7.11.

http://codeforces.net/contest/817/submission/27881187

→ Reply