Codeforces Round #733 (Div. 1 + Div. 2)
By tourist, 3 years 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 (346)
| Write comment?
»
3 years ago, # |
← Rev. 4   Vote: I like it +307 Vote: I do not like it
Oh No
→ Reply
»
3 years ago, # |
  Vote: I like it +267 Vote: I do not like it

Oh Yes

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

Wow! A tourist contest.

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

What is (Engine)?

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

2000+ upvotes easily

→ Reply
»
3 years 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
»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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

→ Reply
»
3 years 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
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +307 Vote: I do not like it

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

    tourist is always first, dates come second

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

    Why not both?

    → Reply
  • »
    »
    3 years 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
    • »
      »
      »
      3 years 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
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +102 Vote: I do not like it

    wait a minute you guys having a girlfriend

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

    Dude, thats hilarious !! Best of luck !!

    → Reply
  • »
    »
    3 years 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
    • »
      »
      »
      3 years 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
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Yes, I feel very bad now.

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

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

          → Reply
    • »
      »
      »
      3 years 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
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yeah one actually.

        → Reply
      • »
        »
        »
        »
        3 years 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
»
3 years 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
»
3 years ago, # |
← Rev. 2   Vote: I like it +132 Vote: I do not like it

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

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

    Let's hope same for problem statement.

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

    Me? I've never written an announcement.

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

tourist orz!!

→ Reply
»
3 years 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
»
3 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Experting in a tourist contest would be so honorable ;)

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

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

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

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

→ Reply
»
3 years 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
  • »
    »
    3 years 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
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

OTZ

→ Reply
»
3 years 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
  • »
    »
    3 years 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
»
3 years 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
  • »
    »
    3 years 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
»
3 years ago, # |
  Vote: I like it -6 Vote: I do not like it

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

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

    Yes you can make him by getting Rank = 3748 .

    → Reply
    • »
      »
      »
      3 years 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
»
3 years 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
»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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

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

Should I be excited or worried about tourist round?

→ Reply
»
3 years 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
  • »
    »
    3 years 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
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years 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
  • »
    »
    3 years 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
    • »
      »
      »
      3 years 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
»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

problem a will probably be a 3000

→ Reply
»
3 years 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
»
3 years ago, # |
  Vote: I like it +55 Vote: I do not like it

Time to upsolve global round 5.

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

    (which is also prepared by tourist)

    → Reply
    • »
      »
      »
      3 years 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
  • »
    »
    3 years 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
  • »
    »
    3 years 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
    • »
      »
      »
      3 years 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
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        ehhh, you dint get the jokeT-T

        Spoiler
        → Reply
        • »
          »
          »
          »
          »
          3 years 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
    • »
      »
      »
      3 years 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
»
3 years ago, # |
  Vote: I like it -30 Vote: I do not like it

tourist what do you eat? orz

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

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

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

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

→ Reply
»
3 years 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
»
3 years 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
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Are the scores of the problems published?

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

https://codeforces.net/contest/1315

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

→ Reply
»
3 years 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
»
3 years 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
»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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

→ Reply
»
3 years 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
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

More than 1441 upvotes wow !

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

tourist round, amazing!

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Specialist i'm coming!!!

→ Reply
»
3 years 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
»
3 years 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
»
3 years 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
»
3 years ago, # |
← Rev. 2   Vote: I like it -12 Vote: I do not like it

My bad! I M SORRY

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

    Do you find it a tedtalk stage?

    → Reply
    • »
      »
      »
      3 years 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
      • »
        »
        »
        »
        3 years 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
        • »
          »
          »
          »
          »
          3 years 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
»
3 years 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
»
3 years 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
»
3 years 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
  • »
    »
    3 years 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
»
3 years 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
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope this round is going to be amazing.

→ Reply
»
3 years 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
»
3 years ago, # |
← Rev. 5   Vote: I like it +7 Vote: I do not like it

After seeing no. of registration
IMG-20210717-191502

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

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

→ Reply
»
3 years 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
  • »
    »
    3 years 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
»
3 years 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
»
3 years 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
  • »
    »
    3 years 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
    • »
      »
      »
      3 years 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
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Mission accomplished! tourist on the contribution board!

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

Best round I have ever seen for adhoc.

→ Reply
»
3 years 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
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +27 Vote: I do not like it

    how was your sandwich?

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

      Falafel so delicious XD

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

        The taste of the sandwich is your wasted score :D

        → Reply
»
3 years 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
  • »
    »
    3 years 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
  • »
    »
    3 years 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
    • »
      »
      »
      3 years 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
      • »
        »
        »
        »
        3 years 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
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I got the exact same cases.

    → Reply
  • »
    »
    3 years 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
  • »
    »
    3 years 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
  • »
    »
    3 years 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
  • »
    »
    3 years 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
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +32 Vote: I do not like it

    → Reply
»
3 years 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
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Don't feel sad. It happens.

    → Reply
  • »
    »
    3 years 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
  • »
    »
    3 years 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
    • »
      »
      »
      3 years 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
      • »
        »
        »
        »
        3 years 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
      • »
        »
        »
        »
        3 years 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
  • »
    »
    3 years 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
  • »
    »
    3 years 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
»
3 years ago, # |
  Vote: I like it +39 Vote: I do not like it

How to solve F?

→ Reply
»
3 years 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
»
3 years 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
»
3 years 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
  • »
    »
    3 years 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
    • »
      »
      »
      3 years 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
    • »
      »
      »
      3 years 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
    • »
      »
      »
      3 years 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
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I passed it in 3.5s :) 122866086

    → Reply
»
3 years 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
»
3 years 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
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No. You can look at my comment above.

    → Reply
    • »
      »
      »
      3 years 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
  • »
    »
    3 years 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
  • »
    »
    3 years 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
»
3 years 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
»
3 years 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
  • »
    »
    3 years 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
  • »
    »
    3 years 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
»
3 years 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
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

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

    You can do it without using Graph Theory.

    → Reply
  • »
    »
    3 years 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
    • »
      »
      »
      3 years 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
      • »
        »
        »
        »
        3 years 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
  • »
    »
    3 years 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
  • »
    »
    3 years 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
»
3 years ago, # |
  Vote: I like it +26 Vote: I do not like it

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

→ Reply
»
3 years 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
»
3 years ago, # |
  Vote: I like it +33 Vote: I do not like it

Zero hacks?

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

    Well, were you expecting weak pretests from tourist?

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

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

      → Reply
      • »
        »
        »
        »
        3 years 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
        • »
          »
          »
          »
          »
          3 years 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
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What was the pretest 2 for problem E?

→ Reply
»
3 years 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
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You missed f(s) = n-1.

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

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

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

    Yes these are the only cases

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

    Did you miss inputs like aabababa?

    → Reply
  • »
    »
    3 years 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
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      3 years 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
  • »
    »
    3 years 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
»
3 years 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
  • »
    »
    3 years 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
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      [Deleted]

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

      You guys have random string generators?

      → Reply
      • »
        »
        »
        »
        3 years 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
  • »
    »
    3 years 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
  • »
    »
    3 years 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
  • »
    »
    3 years 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
»
3 years 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
  • »
    »
    3 years 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
»
3 years ago, # |
← Rev. 2   Vote: I like it +136 Vote: I do not like it

Me when in the contest :>

→ Reply
»
3 years 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
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    wait for some time.

    get over your contest depression first :)

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

why cant we submit now(without marks ofcourse)

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

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

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

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

→ Reply
  • »
    »
    3 years 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
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You haven't even written this contest

      → Reply
      • »
        »
        »
        »
        3 years 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
        • »
          »
          »
          »
          »
          3 years 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
»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

When can we see other people's submissions

→ Reply
»
3 years 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
»
3 years 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
»
3 years 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
»
3 years 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
»
3 years 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
»
3 years 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
  • »
    »
    3 years 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
    • »
      »
      »
      3 years 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
      • »
        »
        »
        »
        3 years 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
»
3 years 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
  • »
    »
    3 years 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
    • »
      »
      »
      3 years 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
      • »
        »
        »
        »
        3 years 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
    • »
      »
      »
      3 years 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
      • »
        »
        »
        »
        3 years 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
  • »
    »
    3 years 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
  • »
    »
    3 years 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
»
3 years 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
»
3 years 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
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    What's the formula to calculate it?

    → Reply
  • »
    »
    3 years 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
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        3 years 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
»
3 years 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
»
3 years 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
  • »
    »
    3 years 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
  • »
    »
    3 years 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
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why solution not open yet??

→ Reply
»
3 years 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
  • »
    »
    3 years 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
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

https://codeforces.net/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
»
3 years ago, # |
  Vote: I like it +471 Vote: I do not like it

My first time winning div.1, cool!

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

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

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

Anyone please tell how to solve D ?

→ Reply
  • »
    »
    3 years 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
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone help me with my problem C

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

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

    → Reply
»
3 years ago, # |
  Vote: I like it -10 Vote: I do not like it

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

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

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

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

    Your soln has "tu" twice which makes max value 2 for some prefix.

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

      GOT it ThankYou. I was reading suffix of string from right to left (in reverse) MY BAD.

      → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

Failing on second test case(273rd TC).

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

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

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

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

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

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

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
        ← Rev. 11   Vote: I like it 0 Vote: I do not like it

        1

        7

        8 8 32 42 51 56 67

        25 31 38 51 53 75 92

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

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

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

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

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

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

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

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

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

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

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

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

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

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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

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

F-H editorial when?

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

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

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

HAIL tourist

→ Reply