Educational Codeforces Round 52 [Rated for Div. 2]
By awoo, 6 years ago, translation, In English

On Oct/11/2018 17:50 (Moscow time) Educational Codeforces Round 52 (Rated for Div. 2) 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.

This round will be rated for the participants with rating lower than 2100. It will be held on extented ACM ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 7 problems and 2 hours to solve them.

The problems were invented and prepared by Roman Roms Glazov, Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov and me.

Good luck to all participants!

UPD 1: Our friends from Harbour.Space University are proposing you an unprecedented offer of free (and even with a scholarship!) robotics study in Barcelona! Read the details in the post by the link https://codeforces.me/blog/entry/62357

UPD 2: I'll be on the community Discord server shortly after the contest to discuss the problems.

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 isaf27 7 263
2 HanwhaEagles 7 340
3 Skywynne 6 251
4 CJYeong 6 273
5 -wawawa8 6 280

Congratulations to the best hackers:

Rank Competitor Hack Count
1 Laggy 63:-10
2 Doriath 38
3 BohdanPastuschak 38:-7
4 Kerman 36:-6
5 zoooma13 33:-2
860 successful hacks and 719 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A xiaowuc1 0:01
B xiaowuc1 0:03
C HanwhaEagles 0:07
D isaf27 0:33
E Kyouko 0:19
F mHuman 0:35
G tfg 0:44

UPD 3: Editorial is published

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

Comments Comments (108)
| Write comment?
»
6 years ago, # |
← Rev. 2   Vote: I like it -45 Vote: I do not like it

Educational aka KILL YOUR RATING contest in da house again!

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

    I think it's vice versa, you can really make comeback and get new high rating in Educational rounds.

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

awoo and his Educational rounds :D

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

The greatest hacker halyavin will hack us. Thank you for finding bugs:D

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

Thanks to MikeMirzayanov for such a great polygon.

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

I like Educational Round very much!

Thanks for Codeforces!

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

Will all problems be about robots?

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

    No, about math

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

      I just hope you're wrong... Though, sadly, I think you'll be right. I'd like to see a Segment Tree + DP problem, something with queries or string, or anything but math. It's like those kind of problems are out of fashion lately. Ugliness and boredom is what programmers are looking for apparently.

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

        is what programmers are looking for I guess programmers aren't looking for math. Just, they are finding only that type of problems.

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

wow, I took a look at cf rounds after a long time, and now it turns out that educational rounds are almost rated for me (I'm away just by 110 points)

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

Thank you friends from Harbour.Space University

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

i cant rally undasternd if or no is rated?

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

    You always ask this question it's ridiculous, stop it please.

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

Educational round! <3

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

delay

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

Sorry, we had some troubles with preparing the tasks, so the contest is postponed to 14:50 UTC.

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

    It's a good sign of problems' quality xD

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

The delay !!!

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

Good luck to everyone, have a nice contest!

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

OMG OMG OMG OMG OMG IS IT RATED ?? ? ? ? PICKMIKE DO NOT TELL LIE TO PEOPLE IT WON'T BE RATED!!! KEKEKKEKEKEKKEKEKEKEKKEKEK

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

    I want moooore dislikes

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

- :v

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

First contest. Wish everyone good luck and high ratings!

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

I'm from Viet Nam, Hello everyone, that is the first contest. Wish everyone good luck.

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

Empty contest xD

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

Excuse me, WTF?

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

Statements are so short, that they don't even exist!! Wow!

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

Where is the problemset??

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

WTH, where are the problems? LOL

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

Might be helpful to copy the upd in the post to the comments)

I'll be on the community Discord server shortly after the contest to discuss the problems.

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it -27 Vote: I do not like it

what a nice problem D is!

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

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

Hats Off! A well balanced contest :)

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

How to solve D?(My solution is bfs with lots of states, and will probably fail).

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

    I did bfs with state = (row, column, target_number, piece). This works because you process all states with distance 0, distance 1, distance 2, and so on, so if there is another state that arrives other states (already in the queue) you can update the min number of changes of that state.

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

What is F test case 4 ?

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

    I believe its a complicated version of this.

    10 2
1 2 3 2 1 6 7 7 7

    Answer should be 5

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

      Why the Answer is 5？

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

      I have draw this tree and the tree in test case 4. They are truly Homologous cases. But I cannot understand why the answer of this case is 5.

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

        You go 1 -> 4 -> 2 -> 5 -> 1 -> 8 -> 7 -> 9 -> 7 -> 10, covering all 5 leaves.

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

I coded problem D for more than 1 hour and I couldn't submit it for 30 seconds.

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

Took me way too long to notice that a semi-naive solution fits time limit in G (44152174) :(.

F and G were very nice problems, but it's kind of silly that the hardest problem was D

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

Couldn't debug my solution for C throughout the round and lost interest halfway :( RIP rating

Can someone help? 44139210

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

What is the 3rd test case for Problem C ?

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

    I had a wa on 3d test because my solution idea was wrong the answer is not the amount of cubes divided by k because each slice is not necessarily the same amount of cubes and anyway i just got hacked :( so sad

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

Is there anyone who solved D in djkstra's algorithm?

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

    Me

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

      I didn't know that djkstra's can be coded with multiset XD I only used priority queue before what is faster?

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

        Priority queue of course. How could it be slower when it implements a strict subset of the functions that a multiset implements :Dd

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

          That makes sense Thanks:)

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

          Well, it depends. With priority queue implementations, usually you insert a node into the queue whenever you find a better cost for that node, which can happen O(E) times, therefore your priority queue with have O(E) size. With a set implementation, when you find successfully relax a node, you look it up and update it (which you can't do in a normal priority queue). Therefore, your set will have O(V) size and usually V < E in problems. I agree many times priority queue will be faster (I personally implement with priority queue as well), but the issue isn't as simple as "it implements a strict subset of the functions, therefore it is faster". The very fact that it is not as powerful means there's certain things you might want to do, but you can not (things that would speed up your solution).

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

      How?

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

    Dijkstra is overkill, BFS is enough

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

dude, cool contest! thanks a lot

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

How to solve problem D

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

Can anyone hack me?Please hack me!HACK ME PLS,PLS,PLS

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

How to solve F?

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

    In addition to the directed tree, we add an edge from each leaf to its kth parent (or the root if there is no kth parent). Now we want to find a path which maximizes the number of different leaves on it, which can be done with SCC + DP.

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

      Or for every leaf node find the node which smallest depth achievable by jumping to leaf to leaf and increase the value of that node(initial all nodes value 0). After we will do dp with our value of nodes.
      dp[nd] = max(dp[childs of nd]) + value[nd]
      Btw we will do first part by segment tree+binary lifting.
      Here is my code: 44154622

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

        Or we can use DSU to maintain SCC's with each connected component storing the number of leafs present in them. Then the problem will reduce to finding a path in a tree from root to leaf, having maximum value. It is quite simple to implement this. Here is my code : 44159892

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

    When you running dfs,for each node maintain two value bk(can back) and dbk(dont come back),the answer is bk[1]+dbk[1].

    44179107 this code is short

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

.

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

    I hacked few people with this test:

    5 6

    3 3 3 3 3

    Answer: 0

    Your code outputs: 1

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

whats the logic for E?

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

How to solve C ?

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

    heights of tower = th[1...n]

    max(th[i]) = mx

    min(th[i]) = mn

    Let array B of size (mx-mn) , B[1....(mx-mn)] , where B[i] = number of cubes at height[i+mn]

    now problem reduces to find the minimum number of contiguous subsegments of array B such that sum of each segment is less or equal to k.

    O(max(n,(mx-mn)

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

My solution for C got hacked but when I submitted the same solution again it's getting accepted.Can someone explain me why this happened?

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

    same here

    edit: after I resubmitted the same solution it got accepted and got hacked again lol

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

    deleted.

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

      Not true. Tests are added to the testset during the hacking phase, but it doesn't rebuild the problem packages instantly. You can expect the test to get added to the testset in like half an hour or so.

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

        Do you know the hack for it? My binary search got hacked.

        → Reply
»
6 years ago, # |
← Rev. 4   Vote: I like it -14 Vote: I do not like it

long double g=ceil((1+sqrt(1+(8*m)))/2.0);
if(m==0)
cout<<n<<" "<<n;
else
cout<<max((long long)0,n-(2*m))<<" "<<n-(long long)g;

I solved B using maths ,where g is the minimum number of nodes which can contain g edges and strongly connected. We know in strongly connect graph n(n-1)=total no. of edges. So by solving quadratic equation I got the value of g,and I considered it's upper bound. I hope it's correct.

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

Nevermind.

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

How to solve E?

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

    The problem turns into:

    You have 2 strings of same size (ignore the middle position if the size is odd) and you can swap prefixes of some given sizes. Find the number of equivalent groups.

    First, note that you can swap the intervals between the swap sizes independently. This means you can just count the number of equivalence classes in each group and multiply them to find the total number of equivalence classes.

    If you have a group of size S, you have A^S classes with both sides being equal and (A^2S — A^S) / 2 classes with both sides being different. After this, you just need to multiply A^(number of characters outside of groups) because they never change.

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

How to solve D?

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

    Hey natofp, I just solved it with dijkstra's algorithm. Try to minimize (moves, replacements) (sort by moves and then replacements)

    Then you can keep track of the state [3][node][level].

    The idea is that you can hit multiple nodes from reaching a to a+1. Therefore, we denote 1, 2, ... n as a separate dimension called [level] (the target points or breakpoints we travel through) We can just update level when the node we are on matches the next "level" in the path we need to hit.

    And then for the inidividual nodes along the way we have another dimension [node] which is just the current node we are on.

    And the [3] is just knight,rook, or bishop.

    As an implementation details, by n I actually mean the total amount of nodes so n = 100. If you do this way you have to convert numbers values to row/col and vice versa.

    My code: https://pastebin.com/ghseX4WT

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

Possible Case of Cheating! awoo

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

If i hack someone will it improve my rank

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

Is it possible to solve C in a fast way if we expand the restriction of 1 <= ai <= 2e5? I'm sure most who solved made observation that vertical was easier than horizontal (because the cuts were horizontal lines), but what about 1 <= ai <= 2e9, is there a good solution for it if we are forced to solve horizontally?

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

    Discretizate ai and then use segment tree

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

    Yeah, my solution was actually horizontal (still O(N log N) cause i gotta sort).

    https://codeforces.me/contest/1065/submission/44166753

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

      Thanks, this is what I was looking for.

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

      My solution was horizontal as well, without the extra log factor because I didn't sort, but for some stupid reason I kept getting WA, so I decided to rage quit the contest and went play some Hollow Knight.

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

      By "expand"the restriction I mean make it bigger, so im asking for a solution where ai <= 2e9 instead (where this method wouldn't work, as I also used this idea)

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

Educational round and halyavin hasn't made a single hack yet? That's weird :P

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

Is there going to be an editorial? :)

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

Why for educational rounds system testing takes very long to start ?

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

    This round had a 12h hacking phase after which the system testing started.

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

Can we get rating in this race?

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

    This round is rated for all users below 2100.

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

editorial?

→ Reply