By BledDest, history, 8 days 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 PikMike Piklyaev, Vladimir 0n25 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  
  • +154
  • Vote: I do not like it  

»
8 days ago, # |
  Vote: I like it +35 Vote: I do not like it

WOW !! Editorial has been published before the contest.

  • »
    »
    8 days 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.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Please correct the time of the contest

»
7 days ago, # |
  Vote: I like it -59 Vote: I do not like it

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

»
7 days ago, # |
  Vote: I like it -12 Vote: I do not like it

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

  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The contest will surely delay, it is tradition.

    • »
      »
      »
      7 days 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.

      • »
        »
        »
        »
        7 days 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.

»
7 days ago, # |
  Vote: I like it +64 Vote: I do not like it

Judgement failed??

»
7 days ago, # |
  Vote: I like it +1 Vote: I do not like it

What is Judgement Failed?

»
7 days ago, # |
  Vote: I like it +54 Vote: I do not like it

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

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

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 days 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! :)

  • »
    »
    7 days 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.

  • »
    »
    7 days 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.

  • »
    »
    7 days 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.

    • »
      »
      »
      3 days 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

»
7 days ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve F and C?

  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    C was a binary search :)

  • »
    »
    7 days 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)].

  • »
    »
    7 days 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

  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In C

    n=10 s=9 ans=1 n=11 s=9 ans=2 . . n=19 s=9 ans=10 .. .. .. .. n=100 s=99 ans=1 . n=101 s=99 ans=2 .. .. so on

  • »
    »
    7 days 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)

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

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How solve D? :'v

»
7 days ago, # |
  Vote: I like it +10 Vote: I do not like it

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

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 days 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

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D with O(N) complexity?

  • »
    »
    7 days ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    here you go.

  • »
    »
    7 days 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

  • »
    »
    7 days 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.

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

  • »
    »
    7 days 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

»
7 days 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?

  • »
    »
    7 days ago, # ^ |
      Vote: I like it +65 Vote: I do not like it

    Hacked.

    • »
      »
      »
      7 days 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.

      • »
        »
        »
        »
        7 days ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        That's exactly what I did.

        Code
        • »
          »
          »
          »
          »
          7 days 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).

    • »
      »
      »
      7 days 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.

    • »
      »
      »
      7 days ago, # ^ |
      Rev. 3   Vote: I like it +30 Vote: I do not like it

      What about this one?

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

The editorial is published.

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

»
7 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I am not getting problem A ,I mean why does not (x2-x1)%x==0 and (y2-y1)%y==0 work?Please explain.

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Plus you need to check ((x2 — x1) / x + (y2 — y1) / y ) % 2 == 0 because there are no rules that move only x or y.

    • »
      »
      »
      6 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      but also number of moves in x and y-axis can't be given by (x2 — x1) / x, (y2 — y1) / y because in 0 0 0 6 and x=2,y=3,no of moves in x axis is not(0-0)/2 .

»
6 days ago, # |
  Vote: I like it -8 Vote: I do not like it

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

Solution
»
6 days 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

  • »
    »
    6 days 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...

»
6 days 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.

  • »
    »
    6 days 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)

  • »
    »
    6 days 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.

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

214 successful hacks!! Great!

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    As usual :D

    • »
      »
      »
      6 days ago, # ^ |
        Vote: I like it +15 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.

      • »
        »
        »
        »
        6 days ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        Which problem was the tricky one?

      • »
        »
        »
        »
        6 days ago, # ^ |
          Vote: I like it +15 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?

        • »
          »
          »
          »
          »
          5 days 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?

          • »
            »
            »
            »
            »
            »
            4 days 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.

            • »
              »
              »
              »
              »
              »
              »
              4 days ago, # ^ |
                Vote: I like it +21 Vote: I do not like it

              Use multitests

              • »
                »
                »
                »
                »
                »
                »
                »
                4 days 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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 days 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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 days 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?

»
6 days 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.com/contest/817/submission/27832753

»
4 days 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.com/contest/817/submission/27881187