Автор awoo, история, 4 года назад, По-русски

Привет, Codeforces!

В 02.03.2021 17:45 (Московское время) состоится Educational Codeforces Round 105 (рейтинговый для Див. 2).

Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.

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

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

Задачи вместе со мной придумывали и готовили Роман Roms Глазов, Адилбек adedalic Далабаев, Владимир vovuh Петров, Иван BledDest Андросов и Максим Neon Мещеряков. Также большое спасибо Михаилу MikeMirzayanov Мирзаянову за системы Polygon и Codeforces.

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

Также от наших друзей и партнёров из Harbour.Space есть сообщение для вас:

Codeforces and Harbour.Space

И снова отличные новости, Codeforces!

Мы особенно рады возможности чаще делиться своими стипендиями!

На этот раз, мы и OneRagtime снова открываем двери в увлекательный мир информационных технологий.

В партнерстве с OneRagtime мы предлагаем полную стипендию на магистратуру компьютерных наук в Harbour.Space, во время которого вы будете проходить стажировку на позиции full stack разработчика в OneRagtime!

О стипендии:

Работа в одном из самых интересных технологических городов Европы
Размер стипендии до 31 500 евро.
Компенсация за стажировку в OneRagtime (800 евро в месяц)
Возможность работать в OneRagtime на полную ставку по окончанию обучения

Преимущества работы в OneRagtime:

  • Международная команда
  • Постоянное развитие навыком
  • Умопомрачительная атмосфера
  • Погружение в европейскую технологическую экосистему
  • Применение новых технологий в венчурном инвестировании
  • Работа в самых интересных технологических городах Европы

Codeforces and Harbour.Space

Ранее мы сотрудничали с другими компаниями, такими как OneRagtime, Hansgrohe, Cohera и Remy Robotics, чтобы воплотить мечту молодых талантов по всему миру и помочь им построить свою карьеру. Мы уже заполнили несколько позиций в сотрудничестве с OneRagtime, в том числе:

  • Разработчик Full Stack в OneRagtime награжден Алехандро Мартинес из Мексики
  • Дизайнер UI / UX из OneRagtime награжден Давидом Петриашвили из Грузии

Мы всегда рады видеть членов сообщества Codeforces, которые присоединяются к семье Harbour.Space. Подайте заявку сейчас, чтобы получить шанс учиться у лучших в этой области и начать свою карьеру!

Следите за новостями в LinkedIn, чтобы не упустить новые возможности. А так же загляните в наш Instagram, где мы делимся событиями студенческой жизни и историями успеха наших учеников.

Удачи в вашем раунде и до встречи в следующий раз!

Harbour.Space University

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

Место Участник Задач решено Штраф
1 antontrygubO_o 6 251
1 Pyqe 6 251
3 244mhq 6 260
4 tute7627 6 272
5 Um_nik 6 288

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

Место Участник Число взломов
1 noimi 11
2 neal 7
3 Origenes 6
4 Kregor 5:-2
5 chilliagon 5:-4
Было сделано 94 успешных и 293 неудачных взломов.

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

Задача Участник Штраф
A noimi 0:01
B noimi 0:04
C wygzgyw 0:15
D conan1412yang99 0:16
E thenymphsofdelphi 0:15
F rainboy 0:35

UPD: Разбор опубликован

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

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

Good luck on the contest everyone!(if you are participating that is)

hmm

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

Lets hope people(like me) losing rating in Global round can gain positive delta in this round :)

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

Опечатка:

О стипендии:

➡ Работа в одном из самых интересных технологических городов Европы

➡ Размер стипендии до 31 500 евро.

➡ Компенсация за стажировку в OneRagtime (800 евро в месяц)

➡ Возможность работать в OneRagtime на полную ставку по окончанию ($$$->$$$ окончании) обучения

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

[DELETED]

»
4 года назад, # |
  Проголосовать: нравится -63 Проголосовать: не нравится

My chance to become specialist :-P

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

Such a long announcement

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

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

It would be very cool too see in future video editorial from the authors!

P.S Sorry for bad English.

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

Hope for green.

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

Is there any points system associated with educational rounds and how do successful/unsuccessful hacks affect the points system (if there is one), ranking and the rating?

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

    The person whose solution you back will get deduction of points as his solution will be marked as wrong. You will not gain any point for successful hacking and neither loose any point for unsuccessful hacking .

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

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

Let's just hope that problem A isn't 2 lines of code while problem B requires 3 dimensional dynamic programming and you need to precalculate all the stock market crashes in the next 5 months.

»
4 года назад, # |
  Проголосовать: нравится -30 Проголосовать: не нравится

I hope there are no adhoc/constructive/geometry/very mathy problems.

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

I wish higher problems had higher points :(

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

.

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

I have participated in 50 contests! Will i be CM before my 100th contest?

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

My Last brain cell during contest :/

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

Ahh life's too stressed ....wake up 12 in the noon pass the time learning algos till 7...then CP till 11 and then Counter Strike till 3 am ,sleep at 4:30 and repeat. I guess i messed up this lockdown .

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

I wish I can do well in this round!

»
4 года назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

Delayed by 10 minutes!

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

Well, it's delayed. Here we go again)

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

delayed by 10 minutes..duh

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

Delayed by 10 minutes :(

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

.

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

Delayed by 10 mins.Hope the contest to remain rated

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

Contest has been delayed so I'm here because I don't know what to do with my life for the next 10 mins.

»
4 года назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

What ever the reason of delay is, I hope the contest doesn't become unrated again.

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

.

»
4 года назад, # |
  Проголосовать: нравится -15 Проголосовать: не нравится

I just pray it don't go unrated.:(

»
4 года назад, # |
  Проголосовать: нравится -61 Проголосовать: не нравится

why they extend time , it affects mindset of some coders ,what do u think guys ?

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

oh,a delayed contest may lead somthing unlucky and I hope the contest will go well.

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

10 more minutes of TWICE it is :D

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

I this 10 min I realize how useless I am ....

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

I this 10 min I realize how useless I am..

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

Hope to become cyan.

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

This type of Div 2 B demotivates me very much

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

Sadist is what you call the person who authored problem B.

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

bruteForces

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

I really hated this B because I tried to solve it the wrong way I guess

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

Some one please tell me about process of B i was trying since 1.5 h but i can't find a answer. Please help me to find out the answer

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

    It's almost same as A, just bruteforce the 4 corners (2^4), and check if 4 numbers are not negative and less than n — 1.

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

      why should all be less than n-1 ?

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

        Because you already know the 2 corners for each row/column so you have n-2 remaining cells.

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

          just a thought.

          "2 corners for each row/column so you have n-2 remaining cells"

          If above is the reason for

          "check if 4 numbers are not negative and less than n — 1"

          in your first comment, It's more clear in the first glance if you say

          "less than or equal n-2" instead of "less than n-1"

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

      I dont think A and B are almost the same

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

      What do you think about this for B

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

Can someone tell how to solve B

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

Gap between B and C was very huge , fucked up in the contest literally fucked up !!

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

    It's actually hard to achieve...

    And It seems that E is easier than D (aftering having a look... XD

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

      Yes it is! Regret not looking at it during the contest while spent 1+ hour on D and got nothing :(

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

        This round seems more educational. :(

        Less dp problems, more implementation problems...

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

ImplementationForces

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

UPD:

AC code
»
4 года назад, # |
  Проголосовать: нравится +46 Проголосовать: не нравится

Really bad problems

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

For question D: https://codeforces.net/contest/1494/submission/108942229

Input

3
2 5 7
5 1 7
7 7 4

Participant's output

5
2 1 4 5 7 
4
1 4
2 4
3 5
4 5

Checker comment

wrong answer LCA of 1 and 3 is 4 and c[4]=5, but a[1][3]=7

I think the graph will be

5

4 3

1 2

So LCA of 1 and 3 is 5 but checker says it is 3. I don't understand why ? is there anything wrong with my output format ?

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

In problem B, you only need to check 4 corners, which is totally 16 situation, and just brute force all of them, If you use if else... if else..... you will probably get WA till the end.

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

My impression when i see the accepted on B after 1.44 hour continuous trying xD .. I am getting negative delta but still happy xD

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

    You can just check the minimum number of blocks that should be black in the border columns. You can check my submission for more clarity.

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

I hope to become a potato now.

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

Is the solution to C a two pointers?

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

    Either two pointers or binary search (I think the latter is easier).

    The main idea is to split the line on $$$0$$$ to get two independent problems. After that, suppose we are pushing blocks to the left (solve the part with negative coordinates). We should push them so the last block we pushed coincides with some special position. We can iterate on this position, calculate the number of blocks we push with, for example, lower_bound, and then calculate the number of special positions in the resulting segment of blocks with another lower_bound.

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

      Thanks a lot! I think the binary search is easier to implement. I spent 1h 50min on C, and I just realized one variable was misswritten. Got AC with the two pointers idea :/

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

      Oops !!! I was trying to coincide the first block with some special position and got around 10 WA on pretest 2 :(

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

        Could you tell me any test case, why matching the first block to some special position leads to non optimal solution.

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

          I think there is nothing wrong in putting the first block in the special position. But it was difficult for me to track how many blocks will be one after another from the first block which I realised after the contest. I think both approaches are correct.

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

Hey,is there any reason why we had to use complicated language like supervisor etc for Probelm-D? Stating it simply in graph theoretic terms like "There exists a rooted tree, each node has has a number and a value. The value of each node is strictly greater than the value of each of its children. You are given the number of leaf nodes and the value of the lca node of each pair of leaf nodes. Construct any such possible tree". I was so confused for so long thinking the given values for each pair was the minimum of direct supervisors.

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

    Most problem setters have majored in literature and they don't want us to forget that fact. (EDIT: Just kiddin)

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

VerboseForces

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

In D, I did the following: if two vertices' common salary is the maximum overall, it means that the root of their tree must have that salary. Thus, we can start with an initial set of leaf nodes, and split them into two sets according to which ones have the max common salary or not. Then create a new root node and recursively process the two sets.

Is that approach incorrect? I can't find a counter example :(

Here's my submission: https://codeforces.net/contest/1494/submission/108943905

Thanks.

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

    One vertex can have more than 2 sons. Test:

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

      Could u please help me in finding the error in my logic as well?

      I claim — "That every distinct value written in the 2D array is a new node in the tree"

      Let's say, that for some val, which is connected to nodes $$$a0,a1...ak$$$, we will create a new node and make top_most_parent[a0], top_most_parent[a1],... top_most_parent[ak]=node.

      The idea is motivated from the idea of LCA itself, which is, that the $$$LCA(a,b)=parent(topMostParent[a])=parent(topMostParent[b])$$$

      It seems, that Ashishgup also implemented the same idea. I don't know what went wrong.

      Link to my code

      Link to Ashisgup's code

      Thanks in advance!

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

        I havent look at the code, but there csn be many nodes with same value.

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

          Do you mean to say, that for some value val, instead of having just one new node, we might have more than one new nodes?

          I think in that case also, we can create just one single node

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

          I understand my mistake now. Thanks for helping !

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

        Well yeah, there can be many nodes with the same value. Test:

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

Screencast with commentary (the quality will get better when YouTube will process it)

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

Solution: https://codeforces.net/contest/1494/submission/108942229

Input

3
2 5 7
5 1 7
7 7 4

Participant's output

5
2 1 4 5 7 
4
1 4
2 4
3 5
4 5

Checker comment

wrong answer LCA of 1 and 3 is 4 and c[4]=5, but a[1][3]=7

LCA of 1 and 3 should be 5 but checker says that it is 4. Is there anything wrong ? Is my output format is wrong ?

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

I solved A and B in a similar manner (brute force). For A, I iterated from 000 to 111 (Binary) and checked every possible string b. For B, I iterated from 0000 to 1111 (Binary) and checked all possible black intersections.

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

    Thanks for reminding bitmask idea, I brute forced using recursive functions which was more messy to code.

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

it was a bit different. did anyone else get stuck in B?

»
4 года назад, # |
  Проголосовать: нравится -28 Проголосовать: не нравится

:'(

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

i thought i should output number of edges in problem D :(.

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

Why sometimes "out of bound" gives WA and sometimes RE for the same compiler on codeforeces?

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

I think the last educational round was very easy than this one.

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

what's the wrong with my idea of problem A.. My idea was in a greedy fashion. every balanced parenthesis start with ( and ends with ")". so I checked s[0] and converted all of with "(". then I checked s[n-1] and converted all of them with ")". then, there is only one character(A or B or C) in S. at first, I convert that with ")". after that with "(". then, checked the validity for this two options. But wrong answer. my submission may you help me ?

»
4 года назад, # |
  Проголосовать: нравится -17 Проголосовать: не нравится

GraphForces

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

I know it might be out of context but I wanted to say this for a while.

I think the point system in educational round(also div-3) is a bit unfair. All of the problems are assigned 1 point even though they are in increasing difficulty. For instance if somebody has solved problem A and C but not problem B (unlikely but still happen sometimes) then his ranking would be similar to someone who has solved A and B but not C. Even though the first person was able to solve a tougher problem(theoretically and practically) he is still in the same position as the second person which seems unfair to me.

A problem with higher difficulty should have more points, For instance the score distribution in Edu and div-3 contests should be 1,2,3,4,... so on. What's the problem with this score distribution? Maybe I'm missing something.

Open to criticism :)

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

    (unlikely but still happen sometimes)

    It's more likely than you think

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

    If the first person couldn't solved the easier problem then apparently it wasn't an easy one for him. If he could solve the easier problem he should have solved it, since he already know the rules before the contest. Even though the first person was able to solve a tougher problem(theoretically and practically) he is still in the same position as the second person which seems unfair to me

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

    ICPC

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

    It is classic ICPC format

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

sent by mistake

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

For Div 2B,

Can anyone please help me with the testcase where my code fails? 108917717

I am unable to understand the issue with my code.

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

.

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

many of the solutions of F can be hacked with the case

6 7
1 2
1 3
1 4
1 5
4 5
4 6
5 6

there seems other hack case for other participants which couldn't hack with this case too. Is the testcases prepared for the system test strong enough??

»
4 года назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

Seems like todays winner is not alone check his submissions.

standings

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

One of shorter solutions for B obtained by factoring out symmetries: 108950466 -(Perl). Idea was to squeeze all posible corner cases. I.e. consecutive n 0 is impossible, and it is symmetric to 0 n in reversed direction.

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

Can someone tell me case number 78 in test case 2 for problem C? Here is the link to my submission that fails at 78th test so can't figure out why. Thanks!

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

    Same

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

    Hi, i got the same wa, and found that case (isn't the 78th, but breaks the code)

    1

    4 5

    1 2 4 6

    4 5 7 15 17

    Correct answer it's 3.

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

      can you help me out with case 126 of TC 2 in problem C. Here is my link to submission

      My Approach:

      Divided the problem into two parts (1. positive 2. Negative). solve the negative part in the same way as positive. positive part ( made 2 array for positon to be kept/ special position(sp) and original position our block(p) ) 1. I made a suffix array of already set blocks.

      1. Traversed through the sp(i = 0 to i < len(sp)) and lowerbounded on p with sp[i] those whose position is <= sp[i] , say found the val at j(index in p).

      2. lowerbounded on sp with sp[i] — j (which would give us the maximum contiguous block such that some or all of them are on special position having end at sp[i]), say found at k.

      3. the no of blocks satisfying the condition = k-i+1+bolcks that are alredy on the special position after this position(suf[i+1]).

      4. found maximum for all all indexs

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

        The idea it's okay. But your code has a little a bug:

        ll j = lower_bound(p.begin(), p.end(), sp[i]) — p.begin();

        if(p[j] > sp[i]) j--;

        if sp[i] it's bigger than maxValue on P, then your code will access to an unkown position. Same for negative one.

        You can fix it by put this before the iteration:

        p.pb(INF); n.pb(INF);

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

          ohhh, I thought of that secenario but for some reason i always thought it would be handled automatically.

          thank you , For clearing my doubt.

          Will keep this in my mind next time.

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

      Thanks!

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

How to overcome pain in ass when you keep getting WA on test 2 after implementing for almost 2 hours ?

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

Today I waste 1.5h to solved problem B but still I can't solved it. that's make me ☹

»
4 года назад, # |
  Проголосовать: нравится -16 Проголосовать: не нравится

Realy bad contest ,, its just about hard implementation not about problem solving. also late editorial .

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

    I think that's why it is educational. A lot of "how to get that parts right...". Not so much "lets have fun".

»
4 года назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

SIMULATION-FORCES

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

2021-02-08-1

»
4 года назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

In B, I am trying every possible move by recursion

can anyone point out what's wrong in it ?

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

Please share some memes I can laugh at; to ease the pain.

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

Competitive compensation for the internship at OneRagtime (€800 / month)

A non-intern student can earn twice that amount while doing less work. What a joke! (assuming internship = 40 hours/week, location = Paris|Barcelona)

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

    In which country/city? Tell me, I am interested to relocate

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

      In most western EU countries, Germany, France, Ireland... you can check the minimum wage across these nations which is compulsory as long as the word 'intern' doesn't apply.

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

        Well, for a western country or a big city, the 800 Euro sum doesn't seem like something big. In my city though, it's three times the average salary

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

          The same for my home country (enough for 1 year of living if you live in the village) but what I am trying to criticize here is the fact that they are exploiting student labor. An intern is practically just a student but the pay gap is huge because it is compulsory in their curriculum even though the work is similar.

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

How many of you think that awoo was better as the coordinator for edu rounds.

PS I thought pikmike !=awoo

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

What is the expected solution to problem F?

I thought about the following one, but it recieved WA on test 19:

  1. If the graph contain 2 or 0 odd degree nodes, just find an Eulerian Path.

  2. Otherwise, I claimed that: It is not possible to start a shift on node U, go to neighbor V and dont return to U immediately. Suppose that we went to node V and didnt return to U immediately. This means we didnt deleted the edge (U, V) so we must delet it later. Then, we will traverse a path that goes back to U, using the shift, implying that there will be edges on this path that will survive, leading to a contradiction, because we would never destroy all the edges of the graph.

Then, it follows that: After some "Eulerian Path" that ends on a node U, the remaining graph must be a star centered on U. Is this solution incorrect? (There are some cases regarding to the part of the code that finds the possible star, but is all coded here: https://codeforces.net/contest/1494/submission/108965452)

»
4 года назад, # |
  Проголосовать: нравится -15 Проголосовать: не нравится

I'm very vegetable.

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

When we got editorial?

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

Please upload the editorial..!!

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

Will this round be unrated now?

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

NEED EDITORIAL. PLEASE UPLOAD THE EDITORIAL.

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

How to solve problem A. Iam new to this please help

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

    So given a string, we need to check if it will be a regular bracket sequence,

    We can only use '(' and ')' to replace the characters of the string, it is also mentioned that all the A's should be replaced with the same bracket, all the B's should be replaced with the same bracket, and also all the C's should be replaced with the same bracket, this narrows down the problem much more, for any bracketed sequence to be a regular bracket sequence it needs to start with '(' and end with ')', this can only happen when the first and the last characters of the string are different so that all the occurrences of the first character can be replaced with '(' and all the occurrences of the last characters can be replaced with ')'. If this is not the case then it is not possible. So for now replace all the characters of the string as given above, after this there exist 2 cases:

    1. All the characters of the string are converted to brackets i.e., the string contains only 2 unique elements. Here just write a function to check for a regular bracketed sequence. and pass your string into it
    2. The string contains 3 unique characters thus there are characters that have not been replaced with brackets. Here first replace all occurrences of the unreplaced character with '(' and pass it into a regular bracketed sequence checker, if it returns false, replace it with ')' instead and pass the string into the regular bracketed sequence checker.

    well, that is it :) my method is a bit lengthy and brute force-y haha but it gets the job done, comment if you did not understand anything.

    Solution my code in python, ignore the staring wrappers and functions the solution is from the checker function.

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

When will the ratings be out? :)

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

Is this round unrated? For the first time I got 4k rank and now my rating doesnt change ;(

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

It was rated for div 2 but why it is showing unrated to me?

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

Can someone help me figure out why is the first pretest failing for me for Problem D. https://codeforces.net/contest/1494/submission/108949724 . The tree i have built doesn't seem to have LCA as 4. It should be 5.

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

Someone, please tell me why is this code failing for B 108907428

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

.

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

Are the system tests over?

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

How to solve D? Please if someone knows explain it! Thanks in advance xD!

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

    Put pairs of points with the same point weight in a vector and enumerate the point weight from smallest to largest. Maintain a merge set, and for point pair (i,j), get the ancestors x and y of them. if they are the same then skip. If one of them has the same point weight as the currently enumerated point weight, then connect the other point to that point. Otherwise, a new point is created and both x and y are connected to the new point.

    You can see ny code at https://codeforces.net/contest/1494/submission/108925449

    Sorry that I'm Chinese and I use DeepL to translate. Never mind the mistakes in my words.

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

Wating for rating changes & tutorial...

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

When will the editorial be out?

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

WAITING FOR RATING CHANGE .....2 HOURS LATER........ WAITING FOR RATING CHANGE .....2 DAYS LATER......... WAITING FOR RATING CHANGE .....2000 YEARS LATER..... WATING FOR RATING CHANGE

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

Guys, please give editorial if not rating changes !

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

Edit: Nevermind, ratings updated!

»
4 года назад, # |
  Проголосовать: нравится -32 Проголосовать: не нравится

Time to downvote the article to get attention.

»
4 года назад, # |
  Проголосовать: нравится -12 Проголосовать: не нравится

E was easier than B.

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

Me : getting positive delta and waiting for the rating changes

Mike : It's time for another test

Me : What's that ?

Mike : Patience Test

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

Why edu rounds take too much time updating rating even after hacking phase?

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

Literally me when edu rounds rating changes appear :)

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

I think I have a short greedy solution for problem B (as it passes system tests).

This is my solution: The variables na, nb, nc, nd (in my code) represent the number of black cells left after taking away the black cells that also belong to other sides. So, if there is a side with n black cells, I reduce each of the two variables that represent adjacent sides by 1. If there is a side with n-1 black cells, it means there is one or two sides that share with it a black cell. I greedily reduce only one side — the side that has more black cells left. I return "YES" only if none of the variables has become negative.

Has anybody done the same? Was this intended to work? Link to my solution: https://codeforces.net/contest/1494/submission/109001204 109001204

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

    Yeah, mine solution is the same as yours and it passed the system test too.

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

    I have done the same.

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

    Same here, tho I made the picking of the side to add 1 black cell to for a side with n-1 black cells a little complicated. And i wasn't also sure if it works starting from any random side, so i looped, the algo to run 4 times starting from all sides then checking the one that works.

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

when will ratings get updated??

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

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

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).

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

For editorial try this

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

If the rating change system is slow, you could release it as a problem for the next Div 1 contest and get 1000 better algorithms.

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

At last!!

Editorial is ready: https://codeforces.net/blog/entry/88344

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

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).

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

Is it rated?

-- The contest seems to be under-rated.

The round hadn't much lags and hadn't long queues. It had nice problems, all seem original, having wide diversity. B wasn't about implementation, but about logic and patterns, solving of which reduces implementation difficulty.

Thanks for organizers team.

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

I published my code on ideone.com with default settings as public. It was a coincidence. Please restore my ratings. I'm just a newbie so I didn't know much about this. I'll take care about this in future, I'm so sorry.