Автор tourist, 3 года назад, По-русски

Привет, Codeforces!

VK Cup 2021 - Отборочный раунд (Engine) уже совсем скоро, не пропустите начало: 17.07.2021 17:35 (Московское время). Это соревнование предназначено для тех, кто решил хотя бы 7 задач из 8 в квалификационном раунде VK Cup 2021. Раунд будет рейтинговым для всех.

Но даже если вы не регистрировались на VK Cup 2021, добро пожаловать на объединенный Div. 1 + Div. 2 раунд Codeforces Round 733 (Div. 1 + Div. 2, основан на VK Cup 2021 - Отбор (Engine)), который начнётся в то же время. Он также будет рейтинговым и открытым для обоих дивизионов.

Все задачи были придуманы и подготовлены мной. Большое спасибо всем, без кого этот раунд не смог бы состояться: PavelKunyavskiy, KAN, lperovskaya, ksun48, Sert, Aleks5d, MikeMirzayanov.

Участникам будет предложено 8 задач и 3 часа на их решение. Рекомендуем прочитать условия всех задач. Удачи!

Среди участников закрытого отборочного раунда, 64 лучших участника получат фирменные футболки VK Cup, а топ 32 пройдут в финал и будут бороться за солидные призы:

  • 1-е место — 300 000 рублей;
  • 2-е — 200 000;
  • 3-е — 100 000;
  • 4-е — 50 000;
  • и 5-е — 30 000.

UPD: Распределение баллов: 500 — 750 — 1000 — 1500 — 2000 — 2750 — 3750 — 4750

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

VK Cup 2021 — Отборочный раунд (Engine):

  1. Um_nik
  2. Petr
  3. Endagorion
  4. Golovanov399
  5. 244mhq

Codeforces Round #733:

  1. jiangly
  2. ecnerwala
  3. Radewoosh
  4. maroonrk
  5. Benq

Выложен разбор задач A-E на английском языке.

UPD3: В разборе появились решения задач F-H на английском языке. Русскоязычная версия разбора появится позднее.

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

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

Oh Yes

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

Wow! A tourist contest.

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

What is (Engine)?

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

2000+ upvotes easily

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

For the first time i will be participating in tourist's round.

Really excited.

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

Looking forward to participating! Good luck to everyone who is participating.

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

Originally I am not planned to participate this contest because I have a date then. But when I see the author, I just postponed the date and register for this contest. Wish I can turn purple.

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

Just wonderful to see the author's name. Really excited to participate in tourist contest.

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

And the award for the shortest announcement goes to...

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

tourist orz!!

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

After a long time!
A contest written by tourist!
I'm enjoying the contest already!

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

Experting in a tourist contest would be so honorable ;)

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

Take my upvote

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

tourist recommended to read all the problems. We should ....

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

As a tester, I won't be participating in the round.

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

This would be my first contest whose problems are completely authored by tourist. Hope to perform great this time :). Just a little question, why the name is Elimination(Engine) ?

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

OTZ

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

is this going to be much harder than normal div 2 contest ?

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

Why is there a second contest (VK Cup 2021 — Elimination (Engine) ) at the same time ?

EDIT : My bad, overlooked the mirror part.

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

My first tourist contest, I hope to make him proud.

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

The quality of problems would most probably be exceptional to say the least. Hope to have a great round. :)

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

Nothing! Just coming every hour to see the upvote count. (◔‿◔)

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

Should I be excited or worried about tourist round?

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

Extremely glad to participate in this round, my first ever contest by tourist

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

How you guys manage contest and dinner in 3 hrs p?

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

Hello , the round will be rated right? plus the problems will be sorted from easiest to the hardest right? Thanks in advance!

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

    First of all answer my this question, Who was using your account for past 8 months? Judging from your questions, the person could not be you. But if it's the case then, The cute answer to your questions is YES.

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

      nah bro , i asked coz he suggested reading every problem , i thought that he might not havebsorted the problems fmas we are used to. about raiting changing i don't usually take part in contests except from div2 , educational ones and div3.

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

problem a will probably be a 3000

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

I was expecting tourist to win this round and surpass 3800 for the first time in CF history.

Now, seeing the King himself hosting the round. Can't wait. <3

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

Time to upsolve global round 5.

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

    (which is also prepared by tourist)

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

    jiangly literally solved every contests ever hosted by tourist within last week. I can already see him in top 10.

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

    As tourist said upsolving anything is meaningless, because you will never get the same problem in the future contests...

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

      There are many various blog posts, explaining that humans are bad at coming up with random number sequences. One website even implements a demonstration in the form of a game. All of this has some practical implications on passwords strength, etc.

      It's possible that tourist believes that his new problems are really unpredictable, so upsolving the older problems is meaningless. But he is a human too, and humans are bad at randomness...

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

        ehhh, you dint get the jokeT-T

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

          More like, being a new guy around here, I haven't seen this joke before. And TheDramaQueen's comment didn't look like a joke to me in the context of this discussion. Thanks for the link!

          So jokes aside, is it generally useful to check the older problems authored by the same problem setter before the contest? I guess, in the worst case this at least doesn't do any harm.

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

      you will never get the same problem in the future contests

      false

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

tourist what do you eat? orz

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

tourist round! Can't wait for the great problems :)

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

The round will be perfectly balanced. As all things should be.

G Korotkevich

If you are a true tourist fan you would remember this.

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

is it going to be a tough round for div 2 participants since it is a combined div 1+2 round? But since there are 8 problems this means first 5 problems would be like normal div 2 rounds.

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

Are the scores of the problems published?

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

https://codeforces.me/contest/1315

if anyone wants to take reference this is last vk cup.

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

And this is the shortest announcement I have ever seen #tourist swag

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

Who all are fired up just after seeing the author of the contest?

Let's nail it guys.

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

Imagine Benq winning and gaining the first position in this round.:-)

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

There goes another opportunity of getting a chance of defeating tourist in a round :(

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

More than 1441 upvotes wow !

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

tourist round, really excited!!!

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

tourist round, amazing!!!

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

tourist round, amazing!

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

Specialist i'm coming!!!

»
3 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
     "It is recommended to read all the problems. "

says tourist ! Super excited to see what new is coming :D

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

Looking forward to participating! Good luck to everyone who is participating. I hope I can be pupil after this round :<

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

Whats-App-Image-2021-07-17-at-3-51-29-PM

Very Excited for this Round :)

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

My bad! I M SORRY

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

    Do you find it a tedtalk stage?

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

      Tbh... It's better to share something you have on your mind with the CF community, cause they are always understanding and help you out. So thought of sharing it so that it might help those having the same mindset as I did. If not TEDTalk, it definitely is CFTalk stage!

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

        It's better to share your thoughts when a topic arises related to that in some comment.Otherwise if people keep posting their thoughts not related to contest announcement, then it doesn't look good

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

          Maybe, But instead of just sharing memes and funny posts on the round... I thought this might be a bit of change in the flow. Just CF things

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

tourist : Finally prepares a contest.
Everyone : tagging tourist
tourist : That's why i don't do it

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

A tourist contest! I think the contest will be difficult. /kk/kk/kk

I will have no rating.(((

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

oh guys I solved some problem in the last round which write by tourist and it was easy do not be nervous!!!

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

    Just because his previous round/s was/were easy, how does that make this round easy? 3hrs contest are usually hard than standard 2hrs contests.

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

Congrats tourist on making it to top ten contibutors Your competitor is here Monogon

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

I hope this round is going to be amazing.

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

Hoping to become specialist in this round. (edit: did it!)

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

After seeing no. of registration
IMG-20210717-191502

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

Thankyou tourist for this round. Hope I take most from it.

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

Coming out of rated contests retirement for this round, I'm going down but I don't care

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

Scoring? I know that you're not a huge fan of dynamic scoring, so don't keep us waiting.

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

why am i feeling nervous even though I participated in 247 rounds and my rating is at it's worst

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

is this round rated?

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

He is demanding 2500 upvotes for score distribution

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

Mission accomplished! tourist on the contribution board!

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

Best round I have ever seen for adhoc.

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

I'm so stupid when I solved C I thought this is it and I probably won't solve D so I made a sandwich and ate it and wasted 15 minutes that would be 50 points difference

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

How to solve E without lots of casework? I've got 5 cases (each case immediately exits):

  1. all char are the same
  2. one char appears only once
  3. the min char appears <= (N / 2) + 1 times.
  4. there are only two distinct characters.
  5. three or more distinct characters.
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    I think f(t) can be only 0 and 1. This simplifies the problem. What was pretest 2 of E. Anybody has some idea?

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

    I got exactly the same cases. Thank god I'm not the only one, felt wrong implementing that many cases. :(

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

    I got the exact same cases.

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

    This is my pseudocode

    • If all the same, there is nothing to do
    • If there is a unique character, start with the smallest unique character and sort the rest for score 0
      • Otherwise you will need to have score at least 1, but you should be able to force a score of 1.
    • Try to force aab(minimise sequence while avoiding an aa)
      • does not work if there is too many a
    • If there is no c, return a(all the b)(all the remaining a) to avoid having ab elsewhere
    • Otherwise, return ab(all the remaining a)(smallest c)(all the remaining b)(remaining alphabets in order) to avoid having ab elsewhere

    a refers to the smallest alphabet, b refers to the second smallest alphabet, c refers to all other alphabets.

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

    Didn't finish but I think 3-5 are the same after you figure out the first couple characters (aab vs ab), then you can just brute force for the next character that fits and isn't a prefix.

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

    I only thought of first 3 cases but tell but little differently. I combined your case 3,4 and 5. Since except the first case, in all other cases f(t) will never exceed 1. Then I found the 1st char whose freq is less than cel(n,2) ans started the string with that char and tried to filled other positions in optimal way.

    This was my idea but couldn't pass pretest, tell me if I made some logical error.

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

    Yep, same. I'd be surprised if you can do it with less cases, as these all require different solutions (except maybe "all char are same", as then literally anything works).

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

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

D felt too hard for me, I have no idea how to even start. I feel like practicing has been a huge waste of time considering my last couple of performances :(

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

    Don't feel sad. It happens.

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

    I just did some dfs with vertices with zero in-degrees for D.

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

    I felt it's easy the number of wishes is how many distinct numbers used so just keep those and distribute unused numbers without someone gifting himself

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

      What if $$$n-1$$$ people gift presents to each other in a circular fashion, and one last guy remains all alone (can't gift to himself)? The solution needs to ensure that this doesn't happen. I spent a lot of time to implement something monstrous, but now I'm worried about system tests.

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

        I handled this case but i don't think it will happen we'll see

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

        This can never happen actually because in the array we are given values such that arr[i]!=i. So if the first n-1 people give gifts to each other in a cyclic manner and we are left with "n" for the nth guy, knowing arr[n]!=n, we can just swap any other person giving gift to arr[n] with the nth person.

        My submission : 122808827

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

    Looks like lots of heuristics. For example, if all of a[i] are different, there is no need to change anything. If there several a[i] == a[j] == a[k] then we have to choose two of i, j, k and reroute them to someone who has noone wanting to give them presents. If there are several people pointing to the same guy, then there is certainly someone who has noone that points to them. If there are several people pointing at a[i] and one of them is j and if k points to j and if k has noone pointing at him then we most certainly must reroute j to point to k =)

    So we need to decouple cases when we have lots of people pointing at the same person by rerouting them to the ones who has noone that points at them.

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

    I solved it using Dinic's algorithm for maximum bipartite matching. Then if some vertices got matched with themselves, I corrected them manually in linear time. It was almost a straightforward implementation, so here is my code 122817211

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

How to solve F?

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

Screenshot-from-2021-07-17-21-33-58

I want t-shirt too :'(

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

Can you do F using broken profile DP? I tried doing that and I think it works but the implementation seemed bad so it might not be intended.

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

Can $$$O(n^22^n)$$$ pass problem F?I get TLE on test 10 :(

My feeling(maybe negative)

Update:It seems that if I optimize the initialization part(before FWT)from $$$O(n^22^n)$$$ to $$$O(n2^n)$$$ it could pass in 6.5s,thanks~

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

    My solution is $$$O(n2^{n})$$$. I don't think $$$O(n^{2}2^{n})$$$ can pass.

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

      I passed pretests with $$$O(n^{2} \cdot 2^{n})$$$ (after lots of constant optimization, and took 6.5s). :| Guess that is not intended.

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

      I passed pretests in 6.9s with $$$O(n^2 2^n)$$$ ( 122855739). The main optimisation is to skip 2/3 of the or-convolutions, as you don't need to transform the same array back and forth between handling every column.

      Locally my code takes 3s in the worst case ($$$n = 21$$$, time used doesn't depend on input), but somehow it is over 2x slower on codeforces. I'm very afraid that random changes in the timing over many tests will TLE my code >:(

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

      I have $$$O(n^2 2^n)$$$, the only limiting operation is "multiply+mod vector * vector".

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

    I passed it in 3.5s :) 122866086

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

Is F solution DP in complexity n^2 * 2^n * 8 (8 bcs of mask of diagonals and current column)?

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

Is knowledge of prefix function required in E ? Also what is the solution for E

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

    No. You can look at my comment above.

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

      I found one guy in my room skip these cases discussion, maybe it has anothor solution which is more beautiful. :)

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

    There was one observation that the value of function can be at most 1 if all are not same. No knowledge of prefix functions was required

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

    No You just need to know what is the definition of prefix function(that is given already in statement) Atleast for the solution which solve all cases separately

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

lol E got 500 more submissions in the last 30 mins, I left the contest thinking it was too hard for me, stupid me :(

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

I know my implementation skills are bad, but this felt more implementation forces than normal. Maybe there are good solutions for D and E and I'm just missing them.

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

    My E was pretty nasty too. For D I used Hopcroft Karp maximum matching, which might have been overkill, but the advantage for me was that I could rely on templated code and had to add minimal lines myself, decreasing the probability of a mistake.

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

    D was not too implementation-heavy for me, Here is my solution. I hope it passes system tests too.

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

I think F was broken profile bitmasking dp on row or columns. We could set diagonal mask initially and build the answer for rows or columns.

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

How to solve D? Is it somehow related to graph theory?

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

    You can do it without using Graph Theory.

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

    I used Dinic's (max flow) to find the max number of possible assignments. Then did some post processing to fill in the unassigned people. There's probably a better way though.

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

      Could you please explain this a little more? How did you model this as max-flow problem? (I did it without using graphs)

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

        The flow network is an edge with capacity 1 from the source (node 0) to n nodes numbered from 1 to n. Then we create another n nodes numbered n+1 to 2n and for each i in 1 to n we add an edge with capacity 1 from node i to node a[i]+n. Then for each node numbered n+1 to 2n we an edge with capacity 1 to the sink (node 2n+1). The max flow on this network gives max number of ways you can assign people to their secret Santa and their assignments. Then you are left with some people who are unmatched and you have to do some post process to assigned.

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

    I considered the functional graph created by edges of the form $$$i \rightarrow a[i]$$$. The maximum number of fulfilled wishes is the number of nodes with positive indegree.

    This graph has a bunch of cycles with trees hanging off them, and I flattened each tree into the cycle in DFS exit order, to get the functional graph for $$$b$$$.

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

    I passed it by random_shuffle the positions i that a[i] isn't appears for the first time until the answer is valid.

    It can be proved that the expected complexity is O(n).

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

Problem statements were short and clear. Enjoyed the contest:)

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

I think there are a hell lot of corner cases for E, :(

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

Zero hacks?

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

    Well, were you expecting weak pretests from tourist?

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

      I was expecting a non-zero number of hacks...

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

        The chances of that happening is same as the chances that he actually missed some corner case :)

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

          But it only has to be a corner case for one solution. There are many creative ways to make a weird, tiny mistake.

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

What was the pretest 2 for problem E?

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

for E it should be only 5 types of answer:

1) f(s) = 0 (there is a unique symbol) daaaabbbbccccxyz

2) f(s) = 1:

i) aababacacadadafffgggg.

ii) abbbbaaaaaaaaaaaaaaaa...

iii) abaaaaaaaaaaaaaaacbbbbbccccdddd...

EDT: f(s) = n — 1: zzzzzzzzzzzzz

What else???

UPD: nothing else, just forgot to add '\n' after one of the options :(

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

image

my random string generator can't reach it smh my head

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

    I too had to struggle, but my random generator actually caught strings like these, when I restricted the character set to 2 and 3

    Anyone struggling on E should try the following test 8 abbbaaa abbbaaaa abbbaaaaa abbbaaaaaa abbbaaaaacc abbbaaaaaacc abbbaaaaaaacc abbbaaaaaaaacc

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

      [Deleted]

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

      You guys have random string generators?

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

        Random string of length N is just generating random integer from 1 to A N times where A is the alphabet size.

        I wrote one during the contest (hardly 4 lines) to generate random strings.

        In case you need, there's this test generator which might help.

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

    I got 5 WAs to figure out all 5 cases. add 1 case for each WA.

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

    I did code for "abaaaaaacbc", "baaaaaaa", "baaaaaaaaaaabb" but sadly, still don't know where the corner case is.

    Edit: missed abbbaaaaaaaaaaa ;(

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

    Yeah, I was also really confused passing several thousand rounds against a brute with $$$n \leq 10$$$ and getting WA2, so I tried reducing the number of distinct characters to reduce the number of distinct strings and get next permutation to run faster. Thankfully found this pretty quickly with $$$n \leq 15$$$ and $$$\text{distinct chars} \leq 3$$$

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

DELETED

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

If only I could solve D earlier... I really want to cry.

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

Me when in the contest :>

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

when will be editorial posted . if it is already posted than i dont know where to check .ps i am a newbie. its my first time doing cp.

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

why cant we submit now(without marks ofcourse)

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

But why E? (when you can simply don't

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

I hope the finals will not be as boring as this.

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

When can we see other people's submissions

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

Great contest, as a Div 2 participant the difficulty curve felt really nice.

I'll probably get negative delta because I spent too long on D and as a result ran out of time to solve E, but I had a fun time.

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

Unpopular Opinion: it wasn't a good contest , as B,C,D,E were pure ad-hoc s.

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

It seems that G and H are the only problems in this round. D, E are just boring case analysis problems and F are also too messy to code, so I skipped F and used my remaining time to solve G but nothing good ideas came out with me QQ.

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

Honestly, we all knew that tourist wouldn't win this contest :d

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

So happy, I finally solved 2 problems in the contest.

Feel like mike should give me bonus points :) for such an awesome achievement.

This might not mean a lot to you guys but I really put in a lot of effort in the prev 20-25 days and now I feel more motivated than ever to prepare for the next contest. Thanks CF for such a wonderful feeling.

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

I think this contest is terrible to mediocre participants like me.

Every problem before F is too obvious and implementation oriented (perhaps F is harder because $$$n^22^n$$$ should not pass). I spent at least two hours and thirty minutes on coding, and could not even finish F due to my poor implementation skill.

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

    Just curious, how could you spend 2.5 hours on F when you finished E at 1 hour and 45 min mark? Did you multitask?

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

I got stuck on problem C (Pursuit). I tried to simulate the process and find sum using prefix sum for every different stages and compare that sum to opponent until it becomes equal or greater. Could someone find the error in my code ?

My code link

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

    Try this input:

    1
    4
    100 100 100 0
    100 100 100 100
    

    Your code outputs 1 instead of 0. You should remember that Ilya's overall result is also computed from the highest $$$k - \lfloor k/4 \rfloor$$$ scores.

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

      Can you please tell me where am i getting wrong in problem C? 122851201

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

        Try this:

        1
        3
        50 50 50
        100 100 1
        

        The correct output is 2. With only one extra stage, your score can only be at most $$$100+50+50=200$$$ but Ilya's score is at least $$$100+100+1=201$$$.

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

      Thank you, now I am using prefix sum for both players. For Illaya I have to push front in the prefix array of Illaya score which is giving me TLE error. Could this problem solve using Prefix sum ?Thank you My code link VTifand Carti_Tester alwerty

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

        The line b.insert(b.begin(),0) is probably too slow in vectors. Have you tried using a deque?

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

    Changing the total number of cases can also change B score. For example:

    b = 50, 100, 100, 100 -> score = 300

    b = 50, 100, 100, 100, 0 -> score = 350

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

    You forgot to increase Ilya's score with the increase in number of rounds.

    For example, if n=12, you only check for the top 9 scores for both but for n=13, you have to check for top 10 scores.

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

Why is not my solution for B in queue? It is still showing 'pretest passed'.

Edit : fixed

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

D can be solved by randomly shuffle leftover people to people with replicated wishes, because the probability of getting a valid solution is greater than $$$\frac{1}{e}$$$.

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

    What's the formula to calculate it?

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

    Could you describe your algorithm and proof strictly? For example, do you take any leftover people and fix them before shuffling? If so, if you have one leftover, with probability 1/2 you will choose wrong guy who can be matched with himself only.

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

then:

Codeforces Global Round 15 Jul/25/2021 22:35UTC+8 02:30 Before start 8 days Before registration 5 days

dangerous

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

I don't like this round.

A, B is simple math, and C is just implementation.

D, E requires observation but not knowledge about algorithms. Especially, E has a lot of annoying corner cases.

This round is neither educational nor enjoyable, at least for those who can't solve F, G, H. I could learn almost nothing from A~E.

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

    I don't how problem D is supposed to be solved but it was my first time implementing something with the "linked list logic", if there is such a thing. So for a beginner that problem was cool. Didn't solve E but I also didn't like ABC that much.

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

    Problems A and B are Div 2 problems A and B, thus they have to be simple) IMHO, observation-based problems are much better than algorithm-based ones. Additionally, such problems as E are created to test your technical skills, so you just have to learn how to solve them. I've seen a couple of problems, which required hardcoding about 50 cases (coding and decoding a labyrinth or interactive chess for example) and that was an overkill, but this problem definitely isn't. At least, you can stress your solution and find all the corner cases really fast.

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

Why solution not open yet??

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

For D, my O(nlogn) solution gave TLE on test_case36. But isn't it good enough to pass in general?

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

    Your code's complexity is not $$$O(n \log n)$$$ because you are copying vectors that might have length up to $$$n$$$, $$$n$$$ times:

    pair<pair<int,int>,vector<int>> f=*it2,l=*it;
    
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

98% tested but solution not even in queue, any idea?

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

https://codeforces.me/contest/1530/submission/122840063 Can someone explain what exactly happened here? The solution had passed on pretests but the system tests seemed to not even run it?

Edit : It's fixed now.

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

My first time winning div.1, cool!

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

The contest is finished, yet my solution of problem B is not judged. It is still showing 'pretest passed'.

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

Acc to CF predictor, I am finally becoming specialist.

It feels extra special coz this upgrade came on a tourist contest :)

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

Even after 100% system testing is done, my submission still showing Pretest Passed. But it should show either an accepted or the wrong answer. Why is it happening?

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

Why we can't see other people's solutions? UPD : now it's fixed.

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

Is there a chance that actual VK cup results will be merged with the rated round?

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

I wasn't able to solve A and B in any of other contests but in this one I solved them and I am Happy thanks tourist for amazing problem set!

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

Why I am unable to see the code of other people given that testing is done?

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

The system testing is finished, but I'm still not able to submit solutions to these problems for practice. When will I be able to?

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

Anyone please tell how to solve D ?

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

    Place all the unique elements on their place and all remaining elements such that if there exist a number such that if b[i]!=i then use that element otherwise place i there. Then check if there exist any index i such tha b[i] == i then swap it with another j such that a[i] == a[j]. It is easy to see that there will be at most 1 such index after applying above algorithm.

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

My Randomised greedy solution got accepted and I'm not sure if it should. I got an intuition that if I shuffle the array after some tries (very less), I will be able to find solution with straight-forward greedy. Can anyone proof this (or atleast tell me why my solution works) ?

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

Are there any kind of plagiarism checks done because almost half of submissions of all the questions including E are same.

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

I looked into the standings and did not find tourist. Now suddenly noticed in the sidebar that this post was from tourist.

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

can someone help me with my problem C

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

    if number of stages can be divided by 4 you should add 100 to s1 and subtract it by the lowest stage he had let's say you have 3 numbers 20 30 40 then sum is 90 if you add 100 then you have 20 30 40 100 but you take n-n/4 so you have now 30 40 100 sum is now 170 not 190

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

In problem E we have to minimize the longest prefix suffix and find the lexicographically smallest one among possible configurations.

But in TEST case 2 it's giving wrong Ans, and the expected output is NOT the lexicographically smallest

TEST CASE 2 wrong answer 64th words differ - expected: 'tutttttttttttttttttvuuuuuuuuvvvv', found: 'tutttttttttttttttttuuuuuuuuvvvvv' Can anyone explain what's wrong? Am I missing something? 122865709

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

Problem C
Can anyone help to tell the error in my code

Failing on second test case(273rd TC).

https://codeforces.me/contest/1530/submission/122867622

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

    int k = mid — mid / 4; bsum = b[min(n — 1, k)];

    It doesn't work for every circumstance. Since we assume that we add only 0 to b, therefore we eliminate 0 first rather than element of b. For example, let n = 7, mid = 8. Then bsum must be the b[5], but it is b[6] maybe?

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

      Could you give an input that shows this issue? I think I don't understand your explanation.

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

        1

        7

        8 8 32 42 51 56 67

        25 31 38 51 53 75 92

        Can be a possible example that a given code doesn't work.

        Edit. I found my explanation is a little bit wrong. But this counterexample still works I guess and bsum is still miscalculated.

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

Ratings updated preliminarily. We will remove cheaters and update the ratings again soon!

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

Thank you for this round and particularly for strong examples: I got bunch of WA1, and thus no extra penalty! First time I became master! (after color revolution in 2015). (My screencast, 53th place official contest. Nothing interesting after E)

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

Really interesting contest but I still can't be pupil :< Hope next contest I could be...

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

And this is what happens when tourist is the author of the contest: 0 Successful Hacks!!!

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

I get wrong answer on testcase 2 for problem C ? can you help me ? my code : https://codeforces.me/contest/1530/submission/122892715

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

For problem B. Putting Plates Why this one is incorrect for 4 4? Please someone explain it. ~~~~~ 1010 0000 1001 0000 ~~~~~

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

    in your submissions it's 1010 0000 1001 1000 the one you wrote is correct as HP21 said

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

F-H editorial when?

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

3 days have passed, could you please where can i found the editorials for the problems f to h, or rather, they have not been made public.? thank you.

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

HAIL tourist

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

когда следующий?