Блог пользователя Aris

Автор Aris, 2 года назад, перевод, По-русски

Привет! В 10.01.2022 17:35 (Московское время) начнётся Codeforces Round 764 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 7-8 задач, которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.

Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Мы постарались сделать приличные тесты — так же как и вы, мы будем расстроены, если у многих будут падать решения после окончания контеста.

Вам будет предложено 7-8 задач и 2 часа 15 минут на их решение. Одна из задач интерактивная. Не забудьте прочитать инструкцию по интерактивным задачам.

Штраф за неверную попытку в этом раунде будет равняться 10 минутам.

Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:

  • принять участие не менее чем в пяти рейтинговых раундах (и решить в каждом из них хотя бы одну задачу)
  • не иметь в рейтинге точку 1900 или выше.

Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.

Спасибо MikeMirzayanov за платформы, помощь с идеями для задач и координацией нашей работы. Задачи были придуманы и написаны командой Университета ИТМО: MikeMirzayanov, MisterGu, myav, Gol_D, Aris, senjougaharin и Vladosiya.

Также большое спасибо: itohdak, Yogi79, smtcoder, Ra16bit, Tlatoani, nigus, MrDindows, leaf1415, Kniaz, Alireza, mini4141, Jostic11, BitHashTech, An_yujin, oversolver и sodafago за тестирование раунда и весьма полезные замечания. Список тестеров будет пополняться.

Всем удачи!

UPD: Вот фото нашего коллектива во время ответа на ваши вопросы во время раунда:

UPD 2: Разбор

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

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

I wish every gray, become green! Good luck!

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

Excited to participate in the first Div. 3 round of $$$2022$$$ and my first unrated round, yay!

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

Interactive problems in div.3 round are epic.

Look forward to this contest!

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

Could we please have div3 rounds on the weekends? Most people in div3 probably have school Thanks

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

I hate Div 3 so boring

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

I wish my cyan color become blue!

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

Another permutation or binary search on problem C

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

Will there be div 4 contests in the near future

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

I tried solving a few interactive problems but got the idle limit exceeded! how to solve them?

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

    I don't think there is any interactive problem that doesn't warn about flushing the output. Read the problem statement carefully from now on.

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

    There is a link in the announcement of the round about interactive problems

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

Oh,no. I am very unhappy, because I will go to school on Tuesday. I want to have more rated, but I really won't have time. ):

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

The status of the problem I submitted 40 mins ago is still in queue. Is the same happening with all of you?

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

So excited to see blogs on Codeforces( this the second one). I haven't seen them for a year. (just a joke)

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

I wish my cyan color become blue!

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

I hope you done the best! Good luck for everyone!

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

Here we go again...............

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

First Div. 3 round in 2022!

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

All the best :) everyone, stay hydrated.

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

I hope I do good ;)

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

wow you guys are having fun (photo)

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

Thank you for this amazing round!

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

G has more submissions let's solve it.

can't solve G -> move to F

can't solve F -> move to E

can't solve E -> back to G ;_;

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

In the photo are all of these guys also the setters of this round or just for answering the question asked by everyone?

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

How to solve problem D,

I just thought of putting all the occurances of each letter into a set , & do the process optimally for k times , can someone help me, I know my solution will fail at cases like aaaaaaa, k = 2.. :

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

    Hint — Binary search for the answer

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

    Can be also solved greedily.

    Count occurences of letters in original string and count number of singles and doubles.

    (doubles — how many pairs of letters there are, singles — number of letters minus doubles * 2).

    Knowing singles and doubles values you can calculate solution.

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

    There's no need for maintaining sets, you only need the counts of the possible number of pairs you can form for all the letters.
    This divided and then multiplied by k (integer division) will give the number of pairs that will be assigned to each color.
    If there are still other letters which have not been selected in any of the selected pairs yet, you can add 1 such char to the string of each color (eg: cac).
    My Submission.

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

DAAAMN, I had so much fun solving E (although I didn't quite finish it).

I thought that out of all solutions we were supposed to pick one that has least segments — which imo is even better problem (not sure if harder then original though).

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

I somehow frequently mess up the easier problems smh. Got 3 WAs on B when it was just basic implementation, and wasted a lot of time on D, when my first instinct was greedy with priority queue, but ended up trying to solve it with Binary Search unsuccessfully and finally solved it with my first instinct smh.

Great problems though.

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

It’s so great to solve all problems without a WA for the first time!

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

Solved C using Kuhn's algorithm... LMAO :D

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

    Same. The first thing that came to my mind after reading the problem is bipartite matching.

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

    I solved it using priority queue :)

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

    Could you explain your approach, please? I just don't see how's this problem about bipartite matching...

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

      For each number a_i in the array, consider the set of numbers from 1 to n that appear when you keep doing floor(a_i/2).

      For example, a_i=25 and n=5, then the set is {1,3}.

      Then we have a bipartite graph of positions and the numbers that could go there. As we can only have one number in each position, this implies a bipartite matching in the graph.

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

how to solve F? Tried something close to a binary search but got WA.

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

I felt crippled at binary search in F :))

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

    F made me realise that if my usual binary search implementation isn't suitable for the problem, then I am screwed :)

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

This round is amazing! I really enjoy the problems. Thank you very much :)

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

NOice:))

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

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

Why is G so simple, although I won't

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

Interactive problems and BinarySearchForces.

Name a more iconic duo. I'll wait.

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

Why? Just why??

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

Got the binary search idea for D but did not know how to handle the odd case

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

Don't know why but That photo looks like a team of hackers from some Hollywood movie lol :/

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

What I learned from this contest . Take all inputs before even thinking of outputting an edge case

How foolish can I be at times

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

Great round!

»
2 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится
Then you can swap any two symbols painted in the same color as many times as you want.

Imagine not noticing this line in problem D.

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

Are exceeded queries in interactive problems always tagged WA. I kept on thinking about issues with the logic when my solution was actually asking for an extra query than needed.

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

    You can have something like this in your code. Now you get MLE if you ask more than 10 queries.

    if(asked>10){
         vector<ll> check(MAX*MAX);  
     }
    
»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hi

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

Great round. I really enjoyed solving the problems, especially problem G.

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

In F the condition that x < n was written on top, and I skip it so in 1h30m I can't reduce 11 queries to 10 queries lol :L rip everyone liked me :(

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

    In the exact same boat as you lol. Hurts a lot since it's a rated contest for me.

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

    yea but howcome the answer for the first testcase is 3, it should be less than n right Aris?

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

      How about you read the goddamned statement before trying to point fingers nowhere?

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

        well the statement wasn't clear for me, it hurts to be polite !?

        • »
          »
          »
          »
          »
          2 года назад, # ^ |
            Проголосовать: нравится -9 Проголосовать: не нравится
          Spoiler because i won't flood the page with useless writing
          • »
            »
            »
            »
            »
            »
            2 года назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            lool, did you even read whatever you pasted? I didn't offend anyone, I was asking a question, I didn't complain about the problem during/after the contest, I also didn't blame the problem writer, nothing happened like that.

            what I really see is you trying to mimic um_nik's attitude, and it just doesn't look good.

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

                Congratulations you're not illiterate, because you were able to read the problem statement.

                Try to have peace in your life, good luck ;)

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

Was problem G taken from somehwere? It has way too many submissions.

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

Nice Div.3 contest. Thank you!

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

Does "wrong answer Jury has answer, but participant doesn't (test case 3648)" means my answer is -1 but Jury is not or my answer is empty? Moreover, I just touch the length of segment must be 2 or 3 in problem E, but I implement it so complex, and finally get a wa2 without anymore clue... https://codeforces.com/contest/1624/submission/142294335

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

    Yes, it means that the jury was able to find an answer, but you could not. For example, consider this testcase.

    1
    
    2 3
    000
    000
    000
    

    The required phone number is just a duplicate of the existing numbers. Hence, an answer definitely exists. However, your code produces $$$-1$$$.

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

Video Solutions for anyone looking

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

This round was very special for me because for the first time I have solved a problem in live contest. I loved it. I am happy and only I know how happy I am. We need more division 3 contest.

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

Got a binary search solution for F, but it gets W/A on 6th test. Can anyone explain mistate or send a test that fails https://codeforces.com/contest/1624/submission/142288442 Thanks!

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

Amazing contest!

The problems were very interesting, especially problem G!

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

oops, I tried to do something more clever with F and figure out the bits one by one. was wondering why I was retarded for the past hour lol

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

I'am gray. But it is showing under 'only unrated' in my profile's contest page.

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

Upsolved E by matching a string using extended patterns (with code) within regexes (DFS simulation). Perl: 142302044.

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

Solution to Problem C using "Max Flow" :)142222070
Resource For Dinic's algorithm

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

nice contest

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

Please help, For which TC I am getting WA (Problem C) Your text to link here... thanks in advance

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Input
    Expected Output
    Your Output
    Comments
»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

O(32(n+m)) was not acceptable in problem G?

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

for E consider the following test case

2 4

1278

6935

7878

output->

2

3 4 1

3 4 1

I wanted to ask whether the output is correct? that is can we repeat a particular segment?

UPD-> Got it, read the announcement now:)

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

Editorial?

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

Can somebody please explain me why I didn't get any rating for participation in this contest?

I don't want to create a new post, so desperately hoping my comment here will get some attention.

I'm a newbie in competitive programming and just recently joined Codeforces. I hoped to start acquiring rating and earning experience by participating in Div.3 contests. Even if this contest (#764) is the second contest I'm participating (the first one was Hello 2022 where I solved just one problem), I assumed I'm qualified to be rated in Div.3 contests. However, this one didn't affect my rating at all.

Please, help me understand the rules of the system!

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

    Ratings haven't been updated yet. Normally in div3 rounds, there is a 12-hour hacking phase. When the hacking phase is done, ratings will be updated in a couple of hours.

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

    you can always wait until the record of this contest appears in your contest history.

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

I got wrong answer "wrong answer Jury has answer, but participant doesn't" in Problem E. I use greedy and kmp algorithm. I match target number as much as possible. Once match is one, i will backtrace one and rematch again. If it can't match target number or one of the segments is one, it will break and output "-1". My algorithm complexity would timed out. But is this algorithm is wrong? I try many tests and verify my answer is correct.

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

    No, this is correct, you must have made a mistake somwhere.

    I've done something very similar and it fails only on big tests (tle).

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

      Okay, I overestimated your solution. To make up for my mistake here is a test where your solution is failing :).

      1 1 10 abcxcdxdcx abcdcdcdcd

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

Still rating is not updated

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

Again! I turned into a zombie after solving 2 problems

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

Are there any problems with the players ranked 212?Can anybody check it?

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

I saw someone was gonna stream the solution of these but I could not find it now, do you have that link?

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

Why this contest is unrated for me? Wasn't it rated for all participant under rating 1600?

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

    Instead of killing your nerve cells in waiting you can always use CF predictor (it is quite accurate)

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

rating changes when??

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

I know this isn't the intended solution of C, but can someone explain why this wouldn't work?
My Submission (WA on 5).

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

Time limit of Problem G is not java friendly ;(

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

This was my submission — 142369596 for 1624E - Masha-forgetful.

The checker log gives me the following message:
wrong answer Integer parameter [name=r] equals to 4, violates the range [1, 2] (test case 249)

Does this mean that my code prints r = 4 for some line while the length of the number is 2? (correct me if I'm wrong)

I can't seem to find my mistake. Any help would be appreciated!

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

    No, it doesn't.

    You forgot to print the number of segments used if $$$m$$$ is 2 or 3.

    For example, one failing test case can be.

    1
    
    1 2
    00
    00
    

    A possible answer is

    1
    1 2 1
    

    but your code would produce

    1 2 1
    

    So, in the original testcase, the jury thinks that you're going to print $$$L$$$ segments, while you actually intended to print just one. Hence the WA.

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

Просьба тем, кто решал на python

Если вам удалось решить G без TL, подскажите, пожалуйста или поделитесь решением

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

    Вы можете посмотреть на все сданные решения на питоне с помощью фильтра. Попробуйте использовать алгоритм Крускала(как я понял, вы его не используете), он должен быть побыстрее других.

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

      Вот код, сразу извините, если у вас вытекут глаза от кода, я на питоне почти не пишу :)

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

        Большое спасибо.Думаю надо прочитать Крускала и станет яснее :)

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

        Забавно, вроде сделал все тоже самое, но мое решение работает почти 2 секунды, а написанное Вами — 1600 мс. Дьявол в деталях :)

        Еще раз спасибо, в итоге и разобрался, и реализовал

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

This is my submission for problem E 142402622. The checker log gives the message wrong answer Answer phone is not "s" (test case 532). I am not able to understand the meaning of this message and also not able to find the bug in my code. Could somebody please help?

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Input
    A Valid Output
    Your Output
    Comments
»
2 года назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

MikeMirzayanov my submission 142240970 coincides with 142233988 from bernardo_amorim, after looking at his code I think it was triggered because of the main, he have a similar style to mine and this problem is a classical 15 lines problem, I do not know this guy and I did not cheat in any way!!. Please remove the cheating accusation. I saw that he complained too here https://codeforces.com/blog/entry/8790?#comment-876676.

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

The hardest problem of this round: Figuring out what the pun in problem F's name is.

I was like: "Interac-dive? But the problem has got nothing to do with diving"

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

The girl on the bottom-left looks cute!