Codeforces Round #733 (Div. 1 + Div. 2)
By tourist, 22 months 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. 244mhq

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

Comments Comments (345)
| Write comment?
»
22 months ago, # |
← Rev. 4   Vote: I like it +307 Vote: I do not like it
Oh No
→ Reply
»
22 months ago, # |
  Vote: I like it +267 Vote: I do not like it

Oh Yes

→ Reply
»
22 months ago, # |
← Rev. 2   Vote: I like it +53 Vote: I do not like it

Wow! A tourist contest.

→ Reply
»
22 months ago, # |
  Vote: I like it +172 Vote: I do not like it

What is (Engine)?

→ Reply
»
22 months ago, # |
  Vote: I like it +124 Vote: I do not like it

2000+ upvotes easily

→ Reply
»
22 months 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.

→ Reply
»
22 months ago, # |
  Vote: I like it +10 Vote: I do not like it

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

→ Reply
»
22 months 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.

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +307 Vote: I do not like it

    → Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +126 Vote: I do not like it

    tourist is always first, dates come second

    → Reply
    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it +184 Vote: I do not like it

      Nah, second is Benq, check the top

      → Reply
      • »
        »
        »
        »
        22 months ago, # ^ |
          Vote: I like it +377 Vote: I do not like it

        That's not a contradiction.

        → Reply
        • »
          »
          »
          »
          »
          22 months ago, # ^ |
            Vote: I like it -102 Vote: I do not like it

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

          → Reply
          • »
            »
            »
            »
            »
            »
            22 months ago, # ^ |
              Vote: I like it +45 Vote: I do not like it

            Lmao, others fans got serious.

            → Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    Why not both?

    → Reply
  • »
    »
    22 months 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!

    → Reply
    • »
      »
      »
      22 months 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 :)

      → Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +102 Vote: I do not like it

    wait a minute you guys having a girlfriend

    → Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Dude, thats hilarious !! Best of luck !!

    → Reply
  • »
    »
    22 months 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.

    → Reply
    • »
      »
      »
      22 months 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 :(

      → Reply
      • »
        »
        »
        »
        22 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Yes, I feel very bad now.

        → Reply
        • »
          »
          »
          »
          »
          22 months ago, # ^ |
            Vote: I like it +10 Vote: I do not like it

          Lets look at bright side. You got contribution points. :)

          → Reply
          • »
            »
            »
            »
            »
            »
            22 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Can contribution nullify the point that Girl is mad?

            → Reply
    • »
      »
      »
      22 months 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 :(

      → Reply
      • »
        »
        »
        »
        22 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yeah one actually.

        → Reply
      • »
        »
        »
        »
        22 months 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.

        → Reply
»
22 months 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.

→ Reply
»
22 months ago, # |
← Rev. 2   Vote: I like it +132 Vote: I do not like it

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

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Let's hope same for problem statement.

    → Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Me? I've never written an announcement.

    → Reply
»
22 months ago, # |
  Vote: I like it +43 Vote: I do not like it

tourist orz!!

→ Reply
»
22 months 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!

→ Reply
»
22 months ago, # |
  Vote: I like it +18 Vote: I do not like it

Experting in a tourist contest would be so honorable ;)

→ Reply
»
22 months ago, # |
  Vote: I like it +20 Vote: I do not like it

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

→ Reply
»
22 months ago, # |
  Vote: I like it +527 Vote: I do not like it

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

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +75 Vote: I do not like it

    OH NOO! is this a sign again?

    → Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

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

    → Reply
  • »
    »
    22 months 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

    → Reply
»
22 months 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) ?

→ Reply
  • »
    »
    22 months 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

    → Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

OTZ

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    22 months 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.

    → Reply
»
22 months 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.

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    one is the actual contest, and the other is the mirror of it i think

    → Reply
»
22 months ago, # |
  Vote: I like it -6 Vote: I do not like it

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

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    Yes you can make him by getting Rank = 3748 .

    → Reply
    • »
      »
      »
      22 months 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. (. ❛ ᴗ ❛.)

      → Reply
»
22 months 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. :)

→ Reply
»
22 months ago, # |
  Vote: I like it +11 Vote: I do not like it

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

→ Reply
»
22 months ago, # |
← Rev. 2   Vote: I like it -58 Vote: I do not like it

Should I be excited or worried about tourist round?

→ Reply
»
22 months 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

→ Reply
  • »
    »
    22 months 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

    → Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
22 months 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!

→ Reply
  • »
    »
    22 months 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.

    → Reply
    • »
      »
      »
      22 months 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.

      → Reply
»
22 months ago, # |
  Vote: I like it +6 Vote: I do not like it

problem a will probably be a 3000

→ Reply
»
22 months 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

→ Reply
»
22 months ago, # |
  Vote: I like it +55 Vote: I do not like it

Time to upsolve global round 5.

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    (which is also prepared by tourist)

    → Reply
    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

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

      → Reply
  • »
    »
    22 months 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.

    → Reply
  • »
    »
    22 months 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...

    → Reply
    • »
      »
      »
      22 months 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...

      → Reply
      • »
        »
        »
        »
        22 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        ehhh, you dint get the jokeT-T

        Spoiler
        → Reply
        • »
          »
          »
          »
          »
          22 months 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.

          → Reply
    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it +50 Vote: I do not like it

      you will never get the same problem in the future contests

      false

      → Reply
»
22 months ago, # |
  Vote: I like it -30 Vote: I do not like it

tourist what do you eat? orz

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

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

    → Reply
»
22 months ago, # |
  Vote: I like it -11 Vote: I do not like it

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

→ Reply
»
22 months 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.

→ Reply
»
22 months 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.

→ Reply
»
22 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Are the scores of the problems published?

→ Reply
»
22 months ago, # |
  Vote: I like it +3 Vote: I do not like it

https://codeforces.com/contest/1315

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

→ Reply
»
22 months ago, # |
  Vote: I like it +6 Vote: I do not like it

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

→ Reply
»
22 months 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.

→ Reply
»
22 months ago, # |
  Vote: I like it +9 Vote: I do not like it

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

→ Reply
»
22 months 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 :(

→ Reply
»
22 months ago, # |
  Vote: I like it +1 Vote: I do not like it

More than 1441 upvotes wow !

→ Reply
»
22 months ago, # |
  Vote: I like it +5 Vote: I do not like it

tourist round, amazing!

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Specialist i'm coming!!!

→ Reply
»
22 months 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

→ Reply
»
22 months 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 :<

→ Reply
»
22 months 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 :)

→ Reply
»
22 months ago, # |
← Rev. 2   Vote: I like it -12 Vote: I do not like it

My bad! I M SORRY

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Do you find it a tedtalk stage?

    → Reply
    • »
      »
      »
      22 months 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!

      → Reply
      • »
        »
        »
        »
        22 months 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

        → Reply
        • »
          »
          »
          »
          »
          22 months 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

          → Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

May this Tourist round have mercy on my rating

→ Reply
»
22 months 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

→ Reply
»
22 months 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.（（（

→ Reply
»
22 months 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!!!

→ Reply
  • »
    »
    22 months 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.

    → Reply
»
22 months 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 Monogon

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope this round is going to be amazing.

→ Reply
»
22 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
22 months ago, # |
← Rev. 5   Vote: I like it +7 Vote: I do not like it

After seeing no. of registration
IMG-20210717-191502

→ Reply
»
22 months ago, # |
  Vote: I like it -6 Vote: I do not like it

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

→ Reply
»
22 months 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

→ Reply
  • »
    »
    22 months 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?

    → Reply
»
22 months 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.

→ Reply
»
22 months 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

→ Reply
  • »
    »
    22 months 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

    → Reply
    • »
      »
      »
      22 months 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

      → Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Mission accomplished! tourist on the contribution board!

→ Reply
»
22 months ago, # |
← Rev. 2   Vote: I like it -30 Vote: I do not like it

Best round I have ever seen for adhoc.

→ Reply
»
22 months 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

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +27 Vote: I do not like it

    how was your sandwich?

    → Reply
    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it +42 Vote: I do not like it

      Falafel so delicious XD

      → Reply
      • »
        »
        »
        »
        22 months ago, # ^ |
          Vote: I like it +9 Vote: I do not like it

        The taste of the sandwich is your wasted score :D

        → Reply
»
22 months 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.
→ Reply
  • »
    »
    22 months 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?

    → Reply
  • »
    »
    22 months 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. :(

    → Reply
    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it +19 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        22 months 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

        → Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I got the exact same cases.

    → Reply
  • »
    »
    22 months 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.

    → Reply
  • »
    »
    22 months 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.

    → Reply
  • »
    »
    22 months 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.

    → Reply
  • »
    »
    22 months 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).

    → Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +32 Vote: I do not like it

    → Reply
»
22 months 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 :(

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Don't feel sad. It happens.

    → Reply
  • »
    »
    22 months 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.

    → Reply
  • »
    »
    22 months 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

    → Reply
    • »
      »
      »
      22 months 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.

      → Reply
      • »
        »
        »
        »
        22 months 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

        → Reply
      • »
        »
        »
        »
        22 months 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

        → Reply
  • »
    »
    22 months 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.

    → Reply
  • »
    »
    22 months 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

    → Reply
»
22 months ago, # |
  Vote: I like it +39 Vote: I do not like it

How to solve F?

→ Reply
»
22 months 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 :'(

→ Reply
»
22 months 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.

→ Reply
»
22 months 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~

→ Reply
  • »
    »
    22 months 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.

    → Reply
    • »
      »
      »
      22 months 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.

      → Reply
    • »
      »
      »
      22 months 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 >:(

      → Reply
    • »
      »
      »
      22 months 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".

      → Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I passed it in 3.5s :) 122866086

    → Reply
»
22 months 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)?

→ Reply
»
22 months 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

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No. You can look at my comment above.

    → Reply
    • »
      »
      »
      22 months 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. :)

      → Reply
  • »
    »
    22 months 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

    → Reply
  • »
    »
    22 months 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

    → Reply
»
22 months 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 :(

→ Reply
»
22 months 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.

→ Reply
  • »
    »
    22 months 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.

    → Reply
  • »
    »
    22 months 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.

    → Reply
»
22 months 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.

→ Reply
»
22 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    You can do it without using Graph Theory.

    → Reply
  • »
    »
    22 months 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.

    → Reply
    • »
      »
      »
      22 months 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)

      → Reply
      • »
        »
        »
        »
        22 months 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.

        → Reply
  • »
    »
    22 months 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$$$.

    → Reply
  • »
    »
    22 months 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).

    → Reply
»
22 months ago, # |
  Vote: I like it +26 Vote: I do not like it

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

→ Reply
»
22 months ago, # |
  Vote: I like it +28 Vote: I do not like it

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

→ Reply
»
22 months ago, # |
  Vote: I like it +33 Vote: I do not like it

Zero hacks?

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    Well, were you expecting weak pretests from tourist?

    → Reply
    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it +25 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        22 months 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 :)

        → Reply
        • »
          »
          »
          »
          »
          22 months 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.

          → Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What was the pretest 2 for problem E?

→ Reply
»
22 months 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 :(

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You missed f(s) = n-1.

    → Reply
    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    Yes these are the only cases

    → Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Did you miss inputs like aabababa?

    → Reply
  • »
    »
    22 months 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?

    → Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      22 months 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

      → Reply
  • »
    »
    22 months 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 :(

    → Reply
»
22 months ago, # |
  Vote: I like it +119 Vote: I do not like it

image

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

→ Reply
  • »
    »
    22 months 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

    → Reply
    • »
      »
      »
      22 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      [Deleted]

      → Reply
    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      You guys have random string generators?

      → Reply
      • »
        »
        »
        »
        22 months 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.

        → Reply
  • »
    »
    22 months 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.

    → Reply
  • »
    »
    22 months 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 ;(

    → Reply
  • »
    »
    22 months 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$$$

    → Reply
»
22 months ago, # |
  Vote: I like it +25 Vote: I do not like it

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

→ Reply
  • »
    »
    22 months 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 :///

    → Reply
»
22 months ago, # |
← Rev. 2   Vote: I like it +136 Vote: I do not like it

Me when in the contest :>

→ Reply
»
22 months 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.

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    wait for some time.

    get over your contest depression first :)

    → Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

why cant we submit now(without marks ofcourse)

→ Reply
»
22 months ago, # |
  Vote: I like it +50 Vote: I do not like it

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

→ Reply
»
22 months ago, # |
  Vote: I like it +212 Vote: I do not like it

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

→ Reply
  • »
    »
    22 months 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

    → Reply
    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You haven't even written this contest

      → Reply
      • »
        »
        »
        »
        22 months 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?

        → Reply
        • »
          »
          »
          »
          »
          22 months 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

          → Reply
»
22 months ago, # |
  Vote: I like it +8 Vote: I do not like it

When can we see other people's submissions

→ Reply
»
22 months 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.

→ Reply
»
22 months 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.

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    I don't think that is an unpopular opinion.

    → Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +78 Vote: I do not like it

    I would rather say just implementation problems with zero ideas.

    → Reply
  • »
    »
    22 months 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

    → Reply
  • »
    »
    22 months 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.

    → Reply
»
22 months 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.

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
22 months 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.

→ Reply
»
22 months 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.

→ Reply
  • »
    »
    22 months 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?

    → Reply
    • »
      »
      »
      22 months 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).

      → Reply
      • »
        »
        »
        »
        22 months ago, # ^ |
          Vote: I like it +14 Vote: I do not like it

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

        → Reply
»
22 months 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

→ Reply
  • »
    »
    22 months 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.

    → Reply
    • »
      »
      »
      22 months 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

      → Reply
      • »
        »
        »
        »
        22 months 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$$$.

        → Reply
    • »
      »
      »
      22 months 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 solve using Prefix sum ?Thank you My code link VTifand Carti_Tester alwerty

      → Reply
      • »
        »
        »
        »
        22 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
  • »
    »
    22 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

    → Reply
  • »
    »
    22 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
22 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

Edit : fixed

→ Reply
»
22 months ago, # |
  Vote: I like it +65 Vote: I do not like it

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

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    What's the formula to calculate it?

    → Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I handle the case when there is only one leftover separately.

      → Reply
      • »
        »
        »
        »
        22 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Hmm. I guess this is because the number of derangements is zero. Then its clear.

        → Reply
»
22 months ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

then:

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

dangerous

→ Reply
»
22 months ago, # |
← Rev. 2   Vote: I like it +37 Vote: I do not like it

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.

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

    → Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    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.

    → Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why solution not open yet??

→ Reply
»
22 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

    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;
    → Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
22 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

https://codeforces.com/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.

→ Reply
»
22 months ago, # |
  Vote: I like it +471 Vote: I do not like it

My first time winning div.1, cool!

→ Reply
»
22 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
22 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Acc to CF predictor, I am finally becoming specialist.

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

→ Reply
»
22 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
22 months ago, # |
  Vote: I like it -11 Vote: I do not like it

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!

→ Reply
»
22 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
22 months ago, # |
  Vote: I like it +12 Vote: I do not like it

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?

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone please tell how to solve D ?

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»