Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке: https://t.me/codeforces_official. ×

Автор PikMike, 2 месяца назад, По-русски,

Привет, Codeforces!

В 11.10.2018 17:50 (Московское время) состоится Educational Codeforces Round 52 (рейтинговый для Див. 2). Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.

Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ACM ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.

Вам будет предложено 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.

Задачи вместе со мной придумывали и готовили Роман Ajosteen Глазов, Адилбек adedalic Далабаев, Владимир Vovuh Петров и Иван BledDest Андросов.

Удачи в раунде! Успешных решений!

UPD 1: Наши партнёры из университета Harbour.Space попросили донести до участников раунда беспрецедентное предложение о бесплатном обучении в Барселоне (плюс стипендия!) по направлению робототехника. Подразумевается магистерская программа в Harbour.Space University. Все подробности в посте https://codeforces.com/blog/entry/62357.

UPD 2: Жду всех желающих в местном Discord сервере сразу после контеста для обсуждения задач.

Поздравляем победителей:

Место Участник Задач решено Штраф
1 isaf27 7 263
2 HanwhaEagles 7 340
3 Seraphimon 6 251
4 CJYeong 6 273
5 -vjudge- 6 280

Поздравляем лучших взломщиков:

Место Участник Число взломов
1 Laggy 63:-10
2 Doriath 38
3 BohdanPastuschak 38:-7
4 Kerman 36:-6
5 zoooma13 33:-2
Было сделано 860 успешных и 719 неудачных взломов.

И, наконец, поздравляем людей, отправивших первое полное решение по задаче:

Задача Участник Штраф
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: Разбор опубликован

 
 
 
 
  • Проголосовать: нравится  
  • +135
  • Проголосовать: не нравится  

»
2 месяца назад, # |
Rev. 2   Проголосовать: нравится -45 Проголосовать: не нравится

Educational aka KILL YOUR RATING contest in da house again!

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится +17 Проголосовать: не нравится

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

»
2 месяца назад, # |
Rev. 4   Проголосовать: нравится +2 Проголосовать: не нравится

PikMike and his Educational rounds :D

»
2 месяца назад, # |
  Проголосовать: нравится +33 Проголосовать: не нравится

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

»
2 месяца назад, # |
Rev. 6   Проголосовать: нравится +85 Проголосовать: не нравится

я еблан

»
2 месяца назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

Thanks to MikeMirzayanov for such a great polygon.

»
2 месяца назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

I like Educational Round very much!

Thanks for Codeforces!

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Will all problems be about robots?

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    No, about math

    • »
      »
      »
      2 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      +1

    • »
      »
      »
      2 месяца назад, # ^ |
        Проголосовать: нравится -34 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        2 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 месяца назад, # |
  Проголосовать: нравится -31 Проголосовать: не нравится

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)

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I will serious in this test!

»
2 месяца назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Thank you friends from Harbour.Space University

»
2 месяца назад, # |
  Проголосовать: нравится -20 Проголосовать: не нравится

i cant rally undasternd if or no is rated?

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Educational round! <3

»
2 месяца назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

ого пикмайк желтый))0)

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

delay

»
2 месяца назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

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

»
2 месяца назад, # |
  Проголосовать: нравится +112 Проголосовать: не нравится

The delay !!!

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Good luck to everyone, have a nice contest!

»
2 месяца назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

ща будет пяцот комментов, что раунд перенесли

»
2 месяца назад, # |
  Проголосовать: нравится -44 Проголосовать: не нравится

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

»
2 месяца назад, # |
  Проголосовать: нравится -18 Проголосовать: не нравится

delayed :(

»
2 месяца назад, # |
  Проголосовать: нравится -66 Проголосовать: не нравится

- :v

»
2 месяца назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

First contest. Wish everyone good luck and high ratings!

»
2 месяца назад, # |
Rev. 2   Проголосовать: нравится +12 Проголосовать: не нравится

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

»
2 месяца назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

Empty contest xD

»
2 месяца назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Excuse me, WTF?

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What is happening to the contest?

»
2 месяца назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

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

»
2 месяца назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Where is the problemset??

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

WTH, where are the problems? LOL

»
2 месяца назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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.

»
2 месяца назад, # |
Rev. 2   Проголосовать: нравится -27 Проголосовать: не нравится

what a nice problem D is!

»
2 месяца назад, # |
  Проголосовать: нравится +84 Проголосовать: не нравится

»
2 месяца назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

Hats Off! A well balanced contest :)

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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.

»
2 месяца назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

What is F test case 4 ?

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 месяца назад, # |
Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

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

»
2 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

Can someone help? 44139210

»
2 месяца назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

What is the 3rd test case for Problem C ?

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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

»
2 месяца назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Me

    • »
      »
      »
      2 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        2 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          2 месяца назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          That makes sense Thanks:)

        • »
          »
          »
          »
          »
          2 месяца назад, # ^ |
            Проголосовать: нравится +3 Проголосовать: не нравится

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

    • »
      »
      »
      2 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      How?

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Dijkstra is overkill, BFS is enough

»
2 месяца назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

dude, cool contest! thanks a lot

»
2 месяца назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

How to solve problem D

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 месяца назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

How to solve F?

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится +29 Проголосовать: не нравится

    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.

    • »
      »
      »
      2 месяца назад, # ^ |
        Проголосовать: нравится +26 Проголосовать: не нравится

      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

      • »
        »
        »
        »
        2 месяца назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        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

  • »
    »
    2 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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

»
2 месяца назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

what's the hack for c ? I solved it with binary search and just got hacked

»
2 месяца назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

whats the logic for E?

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve C ?

  • »
    »
    2 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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)

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    2 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    same here

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

  • »
    »
    2 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    deleted.

    • »
      »
      »
      2 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

»
2 месяца назад, # |
Rev. 4   Проголосовать: нравится -14 Проголосовать: не нравится

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.

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    i was solving this by same approach ..... i dont know what was i doing as i was using 4*m^2 and now i realized this is due to pressure..lol

»
2 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Nevermind.

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve E?

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    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.

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In PROBLEM C: my solution is failing for 6th test case by 1; Can anybody help me in debugging??

Submission

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

great problems :) thanks :D

»
2 месяца назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

How to solve D?

  • »
    »
    2 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    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

»
2 месяца назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Possible Case of Cheating! PikMike

»
2 месяца назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

If i hack someone will it improve my rank

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
2 месяца назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

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

»
2 месяца назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Is there going to be an editorial? :)

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can we get rating in this race?

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Please some one explain problem C..

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Sorry halyavin

»
2 месяца назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

editorial?

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

EDITORIAL ???