By tourist, 2 weeks ago, translation, In English

Hello, Codeforces!

Welcome to the Codeforces Round #733 (Div. 1 + Div. 2, based on VK Cup 2021 - Elimination (Engine)) that will start on Jul/17/2021 17:35 (Moscow time). It will be a combined rated round for both divisions.

This round is a mirror of VK Cup 2021 Elimination. VK Cup is an annual championship for Russian-speaking competitors organized by VK — a social networking service based in Saint Petersburg and the most popular website in Russia. VK Cup started in 2012 and has grown to be a four-track competition in competitive programming, ML, design, and mobile development.

All the problems were authored and prepared by me. Big thanks to everyone without whom this round would not be possible: PavelKunyavskiy, KAN, lperovskaya, ksun48, Sert, Aleks5d, MikeMirzayanov.

You will be given 8 problems and 3 hours to solve them. It is recommended to read all the problems. Good luck!

UPD: Scoring distribution: 500 — 750 — 1000 — 1500 — 2000 — 2750 — 3750 — 4750

UPD2: Congratulations to the winners!

VK Cup 2021 — Elimination (Engine):

  1. Um_nik
  2. Petr
  3. Endagorion
  4. Golovanov399
  5. kefaa2

Codeforces Round #733:

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

Editorial of problems A-E is out, problems F-H will appear later.

UPD3: Editorial now contains problems F-H as well.

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

»
2 weeks ago, # |
Rev. 4   Vote: I like it +307 Vote: I do not like it
Oh No
»
2 weeks ago, # |
  Vote: I like it +267 Vote: I do not like it

Oh Yes

»
2 weeks ago, # |
Rev. 2   Vote: I like it +53 Vote: I do not like it

Wow! A tourist contest.

»
2 weeks ago, # |
  Vote: I like it +172 Vote: I do not like it

What is (Engine)?

»
2 weeks ago, # |
  Vote: I like it +124 Vote: I do not like it

2000+ upvotes easily

»
2 weeks ago, # |
  Vote: I like it +35 Vote: I do not like it

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

Really excited.

»
2 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

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

»
2 weeks ago, # |
Rev. 2   Vote: I like it +563 Vote: I do not like it

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.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +307 Vote: I do not like it

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +126 Vote: I do not like it

    tourist is always first, dates come second

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +184 Vote: I do not like it

      Nah, second is Benq, check the top

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it +377 Vote: I do not like it

        That's not a contradiction.

        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it -102 Vote: I do not like it

          Hii, Errichto what's up! I am your huge fan.

          • »
            »
            »
            »
            »
            »
            2 weeks ago, # ^ |
              Vote: I like it +45 Vote: I do not like it

            Lmao, others fans got serious.

            • »
              »
              »
              »
              »
              »
              »
              2 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Yup, It is seeming like that.

        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it -17 Vote: I do not like it

          Tourist is first and second are we all. Let's have a better ratings this time to all.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it -22 Vote: I do not like it

      nah second is secondthread,after that 1-gon and then may be some more, after which comes date.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    Why not both?

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Me too, I would have a sweet date with my girlfriend tonight. But when I saw it is tourist round after, I give up the date have no hesitation!

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

      I would have a sweet date with my girlfriend tonight. I asked her to participate in this contest with me :)

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +102 Vote: I do not like it

    wait a minute you guys having a girlfriend

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Dude, thats hilarious !! Best of luck !!

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    Unfortunately, I will have a negative delta. I stuck too much time on problem D, although it passed in the end. I solve problem E 10 minutes after the contest, but it's too late.
    This contest is good, but not good as I expected, the real problem D and E are just implementation and corner cases analysis, the solution is not beautiful.I don't like that.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

      Imagine now your girl is mad at you cuz you cancelled your date and on the other hand you get negative delta. Life suck sometimes :(

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      D really has any corner case? I don't see any corner case in my solution :(

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yeah one actually.

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I didn't consider any corner cases either and got AC, probably some logics don't encounter the corner case.

»
2 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

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

»
2 weeks ago, # |
Rev. 2   Vote: I like it +132 Vote: I do not like it

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

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Let's hope same for problem statement.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Me? I've never written an announcement.

»
2 weeks ago, # |
  Vote: I like it +43 Vote: I do not like it

tourist orz!!

»
2 weeks ago, # |
  Vote: I like it -36 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it +18 Vote: I do not like it

Experting in a tourist contest would be so honorable ;)

»
2 weeks ago, # |
  Vote: I like it +20 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it +527 Vote: I do not like it

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

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +75 Vote: I do not like it

    OH NOO! is this a sign again?

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    In other words, "As a tester, I want contribution points".

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it -32 Vote: I do not like it

    I signed up for this contest seconds before seeing this. SECONDS FROM DISASTER

»
2 weeks ago, # |
Rev. 2   Vote: I like it -25 Vote: I do not like it

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

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Engine is the name of the competitive programming track for the VK Cup

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

And the fun has already started.

P.S.: Unfortunately, i missed the registration deadline for VK Cup 2021 — Elimination (Engine) and i've registered for Codeforces Round #733 (Div. 1 + Div. 2, based on VK Cup 2021 — Elimination (Engine)). Idk what will happen. ;(

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

OTZ

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Aye, this is a Div.1 + Div.2, so it obviously will be harder.

»
2 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

EDIT : My bad, overlooked the mirror part.

»
2 weeks ago, # |
  Vote: I like it -6 Vote: I do not like it

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

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    Yes you can make him by getting Rank = 3748 .

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      If this is the condition. Then I want to make 1-gon proud. (. ❛ ᴗ ❛.)

»
2 weeks ago, # |
  Vote: I like it -13 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
Tourist orz
»
2 weeks ago, # |
  Vote: I like it -66 Vote: I do not like it

Excited for the tourist round!

»
2 weeks ago, # |
Rev. 2   Vote: I like it -58 Vote: I do not like it

Should I be excited or worried about tourist round?

»
2 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

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

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Why are you guys tagging him again and again.That would be disturbing for him for sure

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
2 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

problem a will probably be a 3000

»
2 weeks ago, # |
  Vote: I like it +47 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it +55 Vote: I do not like it

Time to upsolve global round 5.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    (which is also prepared by tourist)

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      I always thought I was the only one who did that trick >.<

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +75 Vote: I do not like it

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

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +34 Vote: I do not like it

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

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it -6 Vote: I do not like it

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

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        ehhh, you dint get the jokeT-T

        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +50 Vote: I do not like it

      you will never get the same problem in the future contests

      false

»
2 weeks ago, # |
  Vote: I like it -30 Vote: I do not like it

tourist what do you eat? orz

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    He always eats the 1* first position in Div. 1

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Ohh tourist <3

»
2 weeks ago, # |
  Vote: I like it -11 Vote: I do not like it

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

»
2 weeks ago, # |
Rev. 2   Vote: I like it +40 Vote: I do not like it

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

G Korotkevich

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

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

It's pleasure to me that I'm going participate tourist's round for the first time. Hope everybody will enjoy this round. :)

»
2 weeks ago, # |
  Vote: I like it -12 Vote: I do not like it

Giving first contest hosted by the God of cp tourist. Feeling excited.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
2 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Are the scores of the problems published?

»
2 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

https://codeforces.cc/contest/1315

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

»
2 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

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

Let's nail it guys.

»
2 weeks ago, # |
  Vote: I like it -34 Vote: I do not like it

SWAG just like Thomas Shelby ..

»
2 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

More than 1441 upvotes wow !

»
2 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Tourist + contest = Amazing contest

»
2 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

tourist round, amazing!

»
2 weeks ago, # |
Rev. 2   Vote: I like it -21 Vote: I do not like it

kids write 10-15 blogs and 25-30 comments a month for contribution,all it takes to make it to contrbution board for our legend is 1 single blog.antontrygubO_o ,u agree?

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Specialist i'm coming!!!

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Noice

»
2 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it
     "It is recommended to read all the problems. "

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

»
2 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

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

Very Excited for this Round :)

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

too much hope . please don't disappoint.

»
2 weeks ago, # |
Rev. 2   Vote: I like it -12 Vote: I do not like it

My bad! I M SORRY

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Do you find it a tedtalk stage?

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      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!

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it +10 Vote: I do not like it

          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

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

May this Tourist round have mercy on my rating

»
2 weeks ago, # |
  Vote: I like it +29 Vote: I do not like it

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

»
2 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

I will have no rating.(((

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The time was 3hrs because the number of problems ; if it was 5 problems as it usually be it would be about 2hrs ; anyway it was amazing

»
2 weeks ago, # |
  Vote: I like it -23 Vote: I do not like it

Congrats tourist on making it to top ten contibutors Your competitor is here 1-gon

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope this round is going to be amazing.

»
2 weeks ago, # |
  Vote: I like it -6 Vote: I do not like it

I am lazy to take part in 3 hour contest but after knowing the fact tourist prepared this i just couldnt stop myself to register. Best of Luck to all!!

  • »
    »
    2 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I think if your average solve count in div-2 contests is near 2.75 I don't think length of the contest being 2 hours or 3 hours matters

»
2 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
2 weeks ago, # |
Rev. 5   Vote: I like it +7 Vote: I do not like it

After seeing no. of registration
IMG-20210717-191502

»
2 weeks ago, # |
  Vote: I like it -7 Vote: I do not like it

As i'm a participant, I'm a participant.XD

»
2 weeks ago, # |
  Vote: I like it -13 Vote: I do not like it

Why scoring distribution is always delayed?

»
2 weeks ago, # |
  Vote: I like it -9 Vote: I do not like it

As the problems are authored and prepared by tourist, hoping to see a great contest ahead. All the best, everyone.

»
2 weeks ago, # |
  Vote: I like it -6 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it +57 Vote: I do not like it

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

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    You liar! Seem that solving problems consistently keeps you in a good shape, right?

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    me too the rating is not every thing but always I be happy and fine when I solve problems and in make my rating good;

»
2 weeks ago, # |
  Vote: I like it +65 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Scoring Update Please

»
2 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

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

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Little sign of nervousness will always be there no matter how much experienced you are

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      it's been a while since i felt that nervous probably tourist effect

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

GG applying round(c/4) just saw the changes now .

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Mission accomplished! tourist on the contribution board!

»
2 weeks ago, # |
Rev. 2   Vote: I like it -30 Vote: I do not like it

Best round I have ever seen for adhoc.

»
2 weeks ago, # |
  Vote: I like it +17 Vote: I do not like it

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

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +27 Vote: I do not like it

    how was your sandwich?

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same happened with me in the previous contest after solving C I went on to take a nap otherwise I would have been expert by now

»
2 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Nice contest but stuck at problem C.

Gonna wait for the editorial now, :( After seeing C I thought finally 3 problems ez pz but guess what — tourist doesn't set such ez problems

»
2 weeks ago, # |
Rev. 2   Vote: I like it +83 Vote: I do not like it

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.
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

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

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

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

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +19 Vote: I do not like it

      After this E I feel like I should practice constructive problems more...

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it -11 Vote: I do not like it

        This isn't even constructive. I got 2 of those cases by just running a brute against my soln

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I got the exact same cases.

  • »
    »
    2 weeks ago, # ^ |
    Rev. 2   Vote: I like it +13 Vote: I do not like it

    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.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

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

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +32 Vote: I do not like it

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I see this too but I get WR in test 2 ; so sad &_&

»
2 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

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 :(

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Don't feel sad. It happens.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          The first test case of the provided test cases is this situation only, I think.

      • »
        »
        »
        »
        2 weeks ago, # ^ |
        Rev. 2   Vote: I like it +11 Vote: I do not like it

        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

  • »
    »
    2 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
2 weeks ago, # |
  Vote: I like it +39 Vote: I do not like it

How to solve F?

»
2 weeks ago, # |
  Vote: I like it +90 Vote: I do not like it

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

I want t-shirt too :'(

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +62 Vote: I do not like it

    lol imagine being 64th

    • »
      »
      »
      2 weeks ago, # ^ |
      Rev. 2   Vote: I like it +24 Vote: I do not like it

      However congrats, you won me :D

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it -44 Vote: I do not like it

        You just want contribution.
        Try practicing, it's better than writing useless comments.

»
2 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

»
2 weeks ago, # |
Rev. 3   Vote: I like it +11 Vote: I do not like it

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~

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +37 Vote: I do not like it

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

    • »
      »
      »
      2 weeks ago, # ^ |
      Rev. 2   Vote: I like it +18 Vote: I do not like it

      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 >:(

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I passed it in 3.5s :) 122866086

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No. You can look at my comment above.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
2 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve problem d?

»
2 weeks ago, # |
Rev. 2   Vote: I like it +62 Vote: I do not like it

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.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    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.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
2 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    You can do it without using Graph Theory.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

  • »
    »
    2 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

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

  • »
    »
    2 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    I used only a greedy strategy. Try to satisfy all the possible wishes and then for each who don't have a matching half, select 1 of the not used. Be careful that nobody can give themselves a present, so you should check it. Not really sure if you will understand my comment, so try checking my solution or texting me :)122840888

»
2 weeks ago, # |
  Vote: I like it +26 Vote: I do not like it

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

»
2 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

CShould we check for k+k/4 for the additional steps?

»
2 weeks ago, # |
  Vote: I like it +28 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it +33 Vote: I do not like it

Zero hacks?

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    Well, were you expecting weak pretests from tourist?

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +25 Vote: I do not like it

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

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it +11 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What was the pretest 2 for problem E?

»
2 weeks ago, # |
Rev. 6   Vote: I like it +11 Vote: I do not like it

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 :(

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You missed f(s) = n-1.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      sorry, yes, edited. But it should be something else

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    Yes these are the only cases

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      so, what's wrong with pretest 2?)

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Did you miss inputs like aabababa?

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    what? i do exactly what you've explained and get AC. did you implement your idea wrong?

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think substring abbbba of abbbbaaa..... makes wrong answer

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      no, my solutions returns aabbbb. By 2.i I meant everything which could starts from aa

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +30 Vote: I do not like it

    Stupidest mistake award goes to me, got all the cases correct except the first one :(

»
2 weeks ago, # |
  Vote: I like it +119 Vote: I do not like it

image

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

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    • »
      »
      »
      2 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      [Deleted]

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      You guys have random string generators?

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

        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.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

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

  • »
    »
    2 weeks ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

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

    Edit: missed abbbaaaaaaaaaaa ;(

  • »
    »
    2 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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$$$

»
2 weeks ago, # |
  Vote: I like it +25 Vote: I do not like it

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

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Hey, at least it's not your 3rd negative rating change in a row :///

»
2 weeks ago, # |
Rev. 2   Vote: I like it +136 Vote: I do not like it

Me when in the contest :>

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If editorial comes out, you will get to see in the blog

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    wait for some time.

    get over your contest depression first :)

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

why cant we submit now(without marks ofcourse)

»
2 weeks ago, # |
  Vote: I like it +50 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it +212 Vote: I do not like it

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

  • »
    »
    2 weeks ago, # ^ |
    Rev. 2   Vote: I like it -28 Vote: I do not like it

    I think even for a div-2 contestant there should have been harder C and Ds

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You haven't even written this contest

      • »
        »
        »
        »
        2 weeks ago, # ^ |
        Rev. 2   Vote: I like it -18 Vote: I do not like it

        Does it say I can't have opinions on problems?Will you disagree on the part D could have been harder at least?

        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          no, I don't think so, because an amount of tasks is bigger, than in usual dif2 contest

»
2 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

When can we see other people's submissions

»
2 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

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.

»
2 weeks ago, # |
  Vote: I like it +66 Vote: I do not like it

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

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    I don't think that is an unpopular opinion.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +78 Vote: I do not like it

    I would rather say just implementation problems with zero ideas.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +122 Vote: I do not like it

    I wouldn't call CDE adhoc at all, they seem implementation+some casework to me

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it -34 Vote: I do not like it

    From where people like you came , who blame problems that it was maths based or pure ad-hoc etc. It takes a lot of effort to design a single problem, so respect every problem and author's efforts.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    It's pretty funny that people just put "ad-hoc" on wherever they want these days and then upvote each others lol.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I tried doing C using Priority Queue, but messed up big time :(

»
2 weeks ago, # |
  Vote: I like it +122 Vote: I do not like it

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.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 weeks ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

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.

»
2 weeks ago, # |
  Vote: I like it +165 Vote: I do not like it

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.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    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?

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +22 Vote: I do not like it

      I think he(she) means A-F problems not just F. and I'm totally agree with him(her).

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it +14 Vote: I do not like it

        They mean. Agree with them. I think it's easier to write

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      2 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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 so