By awoo, history, 2 years ago, translation, In English

Hello Codeforces!

On Sep/08/2022 17:35 (Moscow time) Educational Codeforces Round 135 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 6 or 7 problems and 2 hours to solve them.

The problems were invented and prepared by Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

UPD: Editorial is out

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

| Write comment?
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

plz be good round plz be good round plz be good round

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

    You can be sure that the problems will atleast be original.

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

    awoo is one of the great authors , problems will be original and creative surely(in my experience).

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

      Of course, I find educational round problems very good, however I feel like the round is a bit unbalanced

»
2 years ago, # |
  Vote: I like it -15 Vote: I do not like it

Hoping for Creative round

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

Educational Rounds always have original problems.

I Love Educational Rounds

Update: Although EDUs have repeated problems, still I Love Educational Rounds

»
2 years ago, # |
  Vote: I like it -20 Vote: I do not like it

Finally a Rated,Original round. Hoping for a fair and creative round.

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

+1

»
2 years ago, # |
  Vote: I like it -47 Vote: I do not like it

Are they all original? I don't want to waste two hours and then unrated:(

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

    The most important thing isn't rating. It's the experience and the algorithms or approaches that matter. Only cheaters cheat themselves by their ratings, and I'm sure that you aren't that people:)
    And I believe theft will disappear in Codeforces, at least in a period of time.

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

      The least important thing is rating.

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

      The CodeForces match basically started at 22:35 in my country and I had to stay up late for the match, so I was looking forward to the rating:(.

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

        Then what about me?
        And I believe that one who sits into midnight is more likely to pay attention to their ability, not rating:)

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

          I totally agree with you, but I think I can go to bed early and write the next day without rating, instead of staying up late and hurting myself

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

Great way to start long weekend. Happy moon festival to all!

»
2 years ago, # |
  Vote: I like it -25 Vote: I do not like it

I hope this won't be a waste of time.

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

    Bro no contest is a waste of time lol

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

      right bro,we should pay more attention to which we learn from the round but not the rating.

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

⣿⣿⣿⣿⣿⣿⣿⢿⠟⠛⠿⠻⠿⠿⠟⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿ ⣿⣿⣿⡿⠛⢙⣨⣥⣶⣶⣿⢿⣿⣿⣷⣦⣅⠛⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿ ⣿⣿⠟⢀⡴⠟⠋⢉⣀⣠⣤⣤⣤⣀⠉⠻⣿⣧⡈⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿ ⣿⣿⠀⠁⣠⣴⣾⣿⣿⣿⣿⣿⣿⣿⣷⠀⢻⣿⣇⠝⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿ ⣿⣿⠀⣼⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⡀⣼⡿⠟⠀⠙⣛⣬⠱⣿⣿⣿⣿⣿⣿ ⣿⣿⠀⠹⣿⣿⣿⣿⣿⣿⣿⣿⠿⠋⢀⠄⠁⣠⣶⣾⣿⣿⣿⡆⣼⣿⣿⣿⣿⣿ ⣿⣿⠀⣀⠙⣛⣛⣻⠛⠋⣉⣢⣤⣾⠃⣰⡄⠸⣿⣿⣿⣿⣿⣷⠘⣿⣿⣿⣿⣿ ⣿⣿⣤⢹⣷⣶⣶⣶⣾⣿⣿⣿⣿⣿⡄⠸⣷⠀⢻⣿⣿⡿⠟⠛⠡⣿⣿⣿⣿⣿ ⣿⣿⣿⠄⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⠄⠻⠇⢈⠁⠀⠀⠲⠠⠞⠿⣿⣿⣿⣿ ⣿⣿⣿⣷⠈⢿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣶⣶⢤⠀⠀⢲⣿⣿⣿⣷⣤⡉⣻⣿⣿ ⣿⣿⣿⣿⣧⠈⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣳⡀⢻⣿⣿⣿⣿⣷⠐⣿⣿ ⣿⣿⣿⣿⣿⣯⡈⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣾⡇⡆⣿⣿⣿⣿⡟⣀⣿⣿ ⣿⣿⣿⣿⣿⣿⣷⡀⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠃⢃⡿⠿⠛⡋⣀⣾⣿⣿ ⣿⣿⣿⣿⣿⣿⣿⣷⣀⠹⣿⣿⣿⣿⣿⣿⣿⠿⠋⢁⣠⣿⡦⠐⠀⢈⡙⢿⣿⣿ ⣿⣿⣿⣿⣿⣿⣿⣿⠋⢀⣿⣿⣿⣿⠟⢃⣤⣤⡀⠻⣿⣇⣠⣴⡿⠄⠹⣧⡸⣿ ⣿⣿⣿⣿⣿⣿⡿⠃⢠⣾⣿⣿⡿⢋⣤⣿⣿⣿⣿⣄⠈⢿⡿⠋⣠⣤⣀⠈⣡⣿ ⣿⣿⣿⠅⣀⣈⠁⣰⣿⣿⡿⠋⣤⣾⣿⣿⣿⣿⣿⣿⣷⣵⣂⣽⣿⣿⣿⣿⣿⣿ ⣿⣿⣿⣄⠘⢿⣿⣿⠟⠋⣠⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿ ⣿⣿⣿⣿⣷⣤⣬⣅⣶⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿

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

Comments in codeforces..

2020
2022
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

gl everyone. I'm sure it's original unlike the previous one ;D

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

Codeforces Language Picker -- chrome extension to fix codeforces language picker.

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

Good Luck to all Coders ! Never give up the CodeForces ! ! !

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

Hope to perform best in this contest

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

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

    meh not so many upvotes i guess i lost my touch

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

Very good round ❤❤
Thanks for all the authors and testers!(✿◠‿◠).

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

How to solve D?

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

    My approach was just recursive DP + memoization. Make a function for Alice's turn with arguments for left index and right index of the remaining string. Make a function for Bob's turn with arguments for left index and right index of the remaining string AND the latest character that Alice picked (important for tie-breaks). Check base cases (length 2 for Alice, length 1 for Bob), check if this case was encountered before (use two maps to store results, one for Alice, one for Bob), and if neither of those hold, then recursively check the two choices (pick first or pick last character). Obviously pick the winning choice if you can, but otherwise try to force a draw.

    My submission: 171425586 (sadly, it was uploading right when the timer hit 0, so it didn't count ;~;)

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

      Why did you use map? Are you trying to save memory?

      Is it better to use maps instead of arrays in these type of problems?

      • »
        »
        »
        »
        2 years ago, # ^ |
        Rev. 3   Vote: I like it -14 Vote: I do not like it

        The map is for memoization. If any recursive call revisits the same case, the map indicates what the answer is and it is immediately returned.

        Without this, each step would always invoke two recursive calls until it reaches the base case, which leads to a time complexity of $$$O(2^n)$$$ (you can imagine the recursive calls forming a binary tree, with base cases as leaves, and each level removing only one character from its parent). This would get time limit exceeded. However, there are only $$$O(n^2)$$$ substrings, so those $$$(2^n)$$$ nodes involve a crapton of repeated calls to the same substrings, which can be avoided by saving the answer in a map after you compute it the first time (instead of rebuilding the same subtree every single freaking time).

        This technique of "check if you solved the case before and only recurse if you didn't" is called memoization. There are other ways to achieve this, but I'm just personally comfortable with using a map for it, since it can adapt to whatever your case is described by (e.g., since Bob's case involves both Alice's character and the substring endpoints, the corresponding map also has these three parameters for the key).

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

          Bro i know that much.

          I think code looks pretty with arrays anyways your choice

          • »
            »
            »
            »
            »
            »
            2 years ago, # ^ |
            Rev. 3   Vote: I like it -44 Vote: I do not like it

            (please don't assume genders)

            To each their own, but I prefer maps for various reasons:

            1. Arrays require the scenario to be described by an index (possibly multi-dimensional), but maps can adapt to any type of scenario.
            2. The size of the map is equal to the number of cases encountered, whereas the size of the array would be based on how large the value gets. This is notable for problems where the scenarios may involve very large values but you don't actually encounter too many different scenarios within a single test case.
            3. For a scenario that was not encountered, the default for a map is that the scenario simply doesn't exist in the map, and you can check this with the count function. But for an array, every scenario begins with a default value (0, false, "", etc), which might, in some cases, actually be legitimate possible answers, so you're forced to come up with some impossible value to fill up your array before each test case, or make a second boolean array to distinguish between encountered and non-encountered.

            The only real downside to maps imo is that checking and retrieving values takes $$$O(\log (\text{map size}))$$$ time (as opposed to $$$O(1)$$$ time with an array), but this is generally fast enough for the vast majority of problems, especially since the map size only scales with the number of reachable scenarios.

            EDIT: As later replies demonstrated, the time constraints and input sizes would not actually have accommodated the additional logarithmic factor. The acceptance of my submission was due to how successive map lookups involved keys in close proximity, so there were fewer cache misses and the worst-case runtime was not invoked as often. I would not recommend relying on this kind of approach to achieve the runtime. I do still stand by my general opinions on the advantages of maps, but I agree that its use in this particular problem is not justified due to the time complexity disadvantage.

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

              Your condescending tone is so cute, although it is nice that you actually explained your approach.

              this is generally fast enough for the vast majority of problems

              Is it though? I'm actually very surprised that your solution did not get TLE. It sounds like almost $$$10^7$$$ operations with maps, which I wouldn't expect to fit in 5 seconds, not to say 2.

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

                Don't be very surprised, it is actually quite easy to explain!

                Maps are slow, and can't do $$$10^7$$$ random access operations in 5 seconds, because of one reason — cache misses. When you search for an element in a map, you need to look at $$$O(\log n)$$$ random memory locations, which is slow, if you haven't accessed it recently.

                But if you search for an element, which is located near the element you already searched, it should work pretty fast as most memory locations of the tree path to that node should be in cache.

                In the case of the Andalus's code, to calculate dp for $$$(l, r)$$$, first $$$(l+1, r)$$$ is calculated recursively, and then $$$(l, r - 1)$$$.

                If you write down the actual order in which dp states are calculated, in most situations we don't go to the $$$(l+1, r)$$$ child, because it is already calculated, and just go to the $$$(l, r-1)$$$, then to $$$(l, r - 2)$$$, then to $$$(l, r - 3)$$$, and so on.

                And such elements are located close to each other in the map, so access is fast.

                For example, if instead of storing pair $$$(l, r)$$$ in the map, we use $$$(r, l)$$$, it gets TL: 171450551.

                Or if we first calculate $$$(l, r - 1)$$$ instead of $$$(l+1, r)$$$, it also gets TL: 171451903.

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

      What is the time complexity for this solution ?

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

        It takes $$$O(n^2 \log n)$$$ time because there are $$$O(n^2)$$$ substrings, and we'd look for them in the map at most twice. The memoization ensures that revisiting the same case will take $$$O(\log n)$$$ time to return the past answer (saved in a map). For $$$n = 2000$$$, this is actually really risky and I would not recommend this (see other related comments for why my submission was fortunately accepted despite appearing to be too slow).

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

          Is it not $$$\Theta\left(n^2\log n\right)$$$ due to the use of maps?

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

            Yes, you're right, sorry about that. I'll edit it, but idk if anybody would see it. My approach was already demonstrated as being unsuitable for the time constraints, with the AC verdict being a fortunate outcome of how the specific sequence of map lookups resulted in fewer cache misses than a worst-case estimation (due to the close proximity of successive key lookups), and it is not recommended to attempt this kind of risk in general.

            I agree with the assessment and would not advise anyone to follow my approach (I guess I sorta assumed that the downvotes would take care of the visibility, but that might not be the case).

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

I couldn't solve C, and felt its implementation would be pretty tough. This is a me issue though, great contest anyways.

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

how to solve C?

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

    Hint: use a heap.

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

    I did the following Greedy:

    Pick the biggest element in each array. If they are equal, they are a match, ignore them. If they are different, apply f to the biggest one.

    Keep doing until every element has a match.

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

      This kind of simulation with a priority queue might be called a trial tree?

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

    Use a map and compare the frequency

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

How did you solve C?

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

    I maintained 2 multisets corresponding to each array, and in each iteration I compared their largest elements. If equal remove them. Otherwise replace the larger one with its reduced version, as it cannot be obtained by any other reduction.

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

    Video Solution for Problem C. Will upload D in the morning.

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

Great contest. Solved till D after a long time. 499 Rank. Got stuck at E. Learnt diophantine equations mid-contest, but did not get how to answer queries in O(1).

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

    queries in O(1) seems a little crazy, think on ternary search, to the n+1 possible ways of buying pepper

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

Is it ever possible for Bob to win in D? I have the conditional in my code, but I don't think it is ever actually hit.

  • »
    »
    2 years ago, # ^ |
    Rev. 3   Vote: I like it -13 Vote: I do not like it

    sorry, seems like I misread the question.

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

    bacd

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

      my logic was: they're all different. It doesn't matter what the first two moves are in this example cuz at the end they're gonna be two different characters and A just has to pick the smaller of the two, leaving B to pick the biggest and thus the first string is smaller

      After that I sketched a proof using induction that the string HAS to be a palindrome for B to have a draw, apparently it's wrong tho LOL

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

        aabb isn't a palindrome but is a draw. Alice and Bob both end up with ab if they play optimally.

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

      Gives me Alice on running my code

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

      Alice takes 'd'. Doesn't matter whether Bob takes 'b' or 'c': Alice will take 'a' and win, right?

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

        bruh wtf, I didn't noticed it was they were prepending the char, I thought they were appending instead

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

    Seems like no? I mean if Alice can just be greedy and pick something at least as good as Bob every step, so Bob can't win?

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

    If the first letter and last letter are the same, Alice must take one of them while the optimal move for Bob is to take the other. If they are different, draw comes if and only if all continuous segments have a length of even, like "aabbbbaaaa". Otherwise Alice wins. Poor Bob.

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

      Why?

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

      I don't think that draw is iff all continues segments have even lengths. Take abccba for example, it's clear that Bob can just "mirror" the Alice's turn and therefore they end up with the same string. Did I misunderstand your condition?

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

    Nope. If my solution is correct then he can never win since this observation is the sole basis for my solution lol

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

      but for s="baab". bob will win. beacuse no matter which 'b' alice picks, bob will get an 'a'. right ?

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

        The character being picked is prepended to the string, not appended. If Alice picks b and Bob picks a, then Alice picks a to get a final string of ab, leaving Bob to pick b to get a final string of ba. In this case, Alice wins.

        It would actually be optimal for Bob if, after Alice picks b for the first move, Bob also picks b, so they both end up with ab, which is a draw.

        In any case, it's always impossible for Bob to win if Alice plays optimally.

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

My answer for B, I think, is correct, but I got WA.

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

    ...that means it wasn't correct

    Try $$$n = 5$$$. Your sequence generates [3, 2, 1, 4, 5]. The 3 raises $$$x$$$ to 3. The 2 resets $$$x$$$ to 0. The 1 raises $$$x$$$ to 1. The 4 raises $$$x$$$ to 5. The 5 resets $$$x$$$ to 0.

    Your idea of ending with $$$(n - 1)$$$ and $$$n$$$ was correct, but what's critical is that the element before $$$(n - 1)$$$ must cause $$$x$$$ to reset to 0. If $$$x$$$ ends up increasing instead, then it's impossible for $$$x$$$ to accept both the $$$(n - 1)$$$ and $$$n$$$. Constructing the first $$$n - 2$$$ elements is the second challenge here (which is still easy, but it's not as trivial as you thought).

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

The hardest Div.2 round I've seen.

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

    believe me it's not

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

    Don't think so, at least E is easier than normal, it's pretty trivial if you know exgcd.

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

Probelm A.

can you please point out why this submission in wrong. 171352491

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

    you reset the initial maximum value before the input. you'll get AC after you fix this.

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

    Dear rezidentura, you should put ma = v[0] after the line of cin.

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

    try reading the input before the line you give value to ma

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

multiplying my memory just by 2 killed me on D &_& got AC just by deleting that extra parameter

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

How to solve D ?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it -13 Vote: I do not like it
    My solution
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What if the importance of DP here?

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

        dp[i][j] gives answer only for i to j part of string. 1 if Alice 2 if Bob 3 if Draw

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it
    Hint 1
    Hint 2

    My Submission

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

      Always try to add explanation otherwise your comment is pointless.

      You added hints but its also important to add explanation.

      Can you add it in a spoiler?

      Like this

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

    My approach was just recursive DP + memoization. Make a function for Alice's turn with arguments for left index and right index of the remaining string. Make a function for Bob's turn with arguments for left index and right index of the remaining string AND the latest character that Alice picked (important for tie-breaks). Check base cases (length 2 for Alice, length 1 for Bob), check if this case was encountered before (use two maps to store results, one for Alice, one for Bob), and if neither of those hold, then recursively check the two choices (pick first or pick last character). Obviously pick the winning choice if you can, but otherwise try to force a draw.

    My submission: 171425586 (sadly, it was uploading right when the timer hit 0, so it didn't count ;~;)

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

Why I always solved out the last problem I've tried just a minute after the ending ?

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

Any hints on E?

  • »
    »
    2 years ago, # ^ |
    Rev. 3   Vote: I like it +8 Vote: I do not like it

    I think you may precalculate $$$dp[i] (0 \leq i \leq n)$$$, where $$$dp[i]$$$ represents the max taste you can get using $$$i$$$ red peppers and $$$n-i$$$ black peppers. The key observation is $$$dp$$$ could be decomposed into two parts, the ascending part $$$A$$$ and the descending part $$$B$$$ such that $$$A \cap B = \emptyset,\,A \cup B = \{0, 1, 2, ..., n\}, 0 \leq |A| \leq n+1, 0 \leq |B| \leq n+1$$$. For example, $$$dp$$$ could not increase, decrease, then increase. So you only have to search around the peak point.

    Here is my submission: 171418858. Welcome to hack me!

    Update: Hacked!

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

      I did the same. Just use exgcd to find a particular solution so you don't get TLE, and then get it close to the peak point. My submission: 171477615.

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

        The 171418858 is written in a hurry. After being hacked, I review my code and find it is potentially flawed. The problem lies in the following two lines:

        for(; lp >= 0; lp -= xj) -- line1

        for(; rp <= n; rp += xj) -- line2

        If yj > xj, These two steps may execute up to $$$O(n)$$$ steps. So we need to swap xi and yj if yj > xj. If xj >= yj, then:

        (1) line1 executes at most O(peak/xj) <= O(n/xj) steps.

        (2) line1 executes at most yj <= xj steps to find a lp such that (n $$$-$$$ lp)%yj == 0.

        So the complexity is min(O(n/xj), O(xj)) <= O($$$\sqrt n$$$). This is sufficient. Similar idea works for line2.

        Devil is in the details. In Chinese words, 细节决定成败. I write this code really in a hurry. Reading the problem takes me too much time. Anyway, thanks hacker @robostac!

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

          That's cool, I got it. And I think you wanted to write min(O(n/xj), O(xj)) instead of max.

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

          O(Nsqrt(N)) is not enough unless you add a lot of cutoffs, at which point it is easier to write the O(log A) per query solution and not try to fit in anything else. If anybody has a good O(sqrt(N)) solution which fits in TL, please show. I could not fit it in during the contest.

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

              That's a cool solution! I was too lazy to precalc all factors, but that seems to be the missing part in my solution. Thank you for sharing.

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

I can't find a case where Bob wins. Alice always wins right?

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

    I modified my submission to call Bob a loser if he somehow wins and it still got accepted: 171428919

    So the only question is whether Alice wins or Bob forces a draw. Kinda like tic-tac-toe.

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

    baccab

    sorry ,misread the question , i thought that character should append at last

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

      Alice picks a b. WLOG, let's assume it's the first b.

      If Bob picks a b, we're at acca, which is a forced draw (identical to second test case).

      If Bob picks the a instead, we're at ccab. Here, Alice can pick c. Then no matter what Bob picks next, Alice can claim the a and get a string starting with a, which will beat whatever Bob picks.

      So Bob can only force a draw at best.

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

How many got a +1 in D because of appending and not prepending?

PS: Me even after reading that

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

How to solve B?

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

    you need to output the biggest two number last so you make it reset every two number For example : n=15 7 8 6 9 5 10 4 11 3 12 2 13 1 14 15

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

      can you tell me whats wrong in my solution? https://codeforces.net/contest/1728/submission/171372656

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

        $$$1$$$ does not forcefully reset the value, it can in fact change the value to $$$1$$$ if it is currently $$$0$$$. you need a different way.

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

        It doesn't guarantee that the (n — 2)-th element will reset $$$x$$$ to 0. For example, consider $$$n = 6$$$, where your code generates [2, 3, 4, 1, 5, 6].

        2 increases $$$x$$$ to 2.

        3 increases $$$x$$$ to 5.

        4 resets $$$x$$$ to 0.

        1 increases $$$x$$$ to 1 (!!!)

        5 increases $$$x$$$ to 6.

        6 resets $$$x$$$ to 0.

        You need to generate the first $$$(n - 2)$$$ elements in a more intelligent manner that guarantees that the $$$(n - 2)$$$-th element triggers a reset. Hint: handle even and odd cases separately.

»
2 years ago, # |
  Vote: I like it -22 Vote: I do not like it

Congratulations awoo with my last educational round in which I participated from any account.

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

so many constructive >:(

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

Is there something wrong with G?

I tried to hack with a testcase with $$$m=18$$$, but I received Invalid Input because it said $$$m$$$ should be in the range $$$[1,16]$$$.

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

    Yes, there is. About 40 minutes before the contest, I've noticed that one specific version of model solution runs too close to TL, so I decided to drop the constraints to $$$16$$$, but totally forgot to update the statement. I am sorry for this issue.

    Since I don't want to affect the people who got AC during the contest, I will change the problem statement, so it coincides with the validator.

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

In problem C In one operation,

1.pick some integer i from 1 to n;
2.assign either f(ai) to ai or f(bi) to bi.

What should I select,
only one index?
or some indices?

if it is only one index.

Then, what does it mean by some?

or Am I thinking in a wrong way?

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

    The problem means you can do the operation as much as you want and in each time you should select only one index

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

if I hacked a solution and my hack was unsuccessful will my standing be down?

  • »
    »
    2 years ago, # ^ |
    Rev. 3   Vote: I like it +14 Vote: I do not like it

    No, educational rounds and div3/4/5/6/7/8/9/10 rounds don't have any scoring hacking phase!

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

What is the test case hackers are using to break a lot of solutions on Problem C?

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

So is the C question today again facing the dictionary hack in python that happened a few contests ago? Makes me wonder about the extent of this disadvantage for python users. BTW I guess this can be fixed by taking random XORs to reduce collisions while hashing.

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

    How to hack hash tables and how to prevent hacks on hash tables is a very important discussion topic on Codeforces. Now that you learnt this time, you can either salt the hash or otherwise not use the hash table at all from now on.

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

Code is giving correct output for "ba" on local but wrong on CF. Please someone help.

https://codeforces.net/contest/1728/submission/171407603

last tells Alice made previous move on l-1(last = 0) or r+1(last = 1) or nowhere and win tells in the suffix where both alice and bob has put characters who was dominating recently

stores 0 -> loosing, 1-> winning 2 -> draw state

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

    you should access dp after checking if l > r because r might be -1

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

      Thanks a lot. Why the verdict wasn't Runtime error.

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

        Out of bound is not a runtime error but undefined behavior.

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

Very nice problems A B C!

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

    After looking at the solution of C, it looked pretty standard and reminded me of some greedy problems I solved some time ago. I am actually curious about the proof though.

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

      dk if this might help but look at it this way First remove anything in a that’s in b and remove anything in b that’s in a , then turn apply operations on all number that’s greater than 9 in both a and b, let the number of operations be ans , now do the same as step one where you remove elements, now the remaining ones HAVE to be converted to 1 so just count the number of remaining number of numbers greater than 1 and add it to ans , this is your answer

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

        yeah, I noticed this, but I am looking for a formal proof (why applying from biggest is optimal)

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

          Hmm I’m bad at formal proofs , so , sorry , can’t help you there , maybe that’s why I’m still a pupil haha

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

            maybe tomorrow you will become specialist

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

              Cf predictor is saying only +30 so I doubt it , I took wayyy too long to solve A , idk I was being dumb

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

                oh, let's look forward to the Div.3 contest coming soon then

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

                  8 months back cf-predictor always underestimated my delta but now it always overestimates it

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

                  Yea, i also feel cf predictor is giving more than actual delta nowadays. It says 15 for me i just hope its not negative at this point lol.

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

          It doesn't have to be the biggest, but you do need to deal with multi-digit numbers before the single-digit numbers.

          My approach was to first remove elements that appear in both arrays, so now the two arrays have no overlaps.

          Now that there are no overlaps, we now apply the operation on every number that's $$$\geq 10$$$ (contains 2 digits or more). As proof of why this is always required, note that the values are only as high as $$$10^9$$$, so there is no number with 10 or more digits. Therefore, the operation can only produce numbers from 1 to 9. So if you have a multi-digit number $$$x$$$ in the first array while the second array has no $$$x$$$, then it's impossible to produce $$$x$$$ in the second array through operations, and it is therefore necessary to apply the operation to $$$x$$$ on the first array.

          After these operations, the arrays have only one-digit numbers. We can remove overlaps once more (no operations performed) until there is no element appearing in both arrays.

          At this point, we have to transform everything into 1, so we count the number of non-1s, applying that many operations to turn them all into 1, after which we are done.

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

      Note that the operation is individual for each number and the operation will make a number smaller. So let's just consider the biggest number and assume it is in A. If there's a number in B that equals to A then alright remove them all. If not, it's clear that we should apply operations on it or we won't find a number to match it.

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

        As for the time complexity, considering we can make all the numbers to 1, and the numbers of operations is not more than 2, so the total number is mot more than 4n.

»
2 years ago, # |
  Vote: I like it -24 Vote: I do not like it

Did you know that adding more samples is totally free?

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

Any hint for E? I know how to precompute the best answer for $$$i$$$ red peppers for all $$$i$$$, but I don't really know how to deal with the queries fast enough. I guess I'm missing some observation.

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

    Probably the diophantine equations and the extended euclidean algorithm are what you are missing.

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

      I actually knew about that but I was just thinking how should I iterate all possible solutions to find the maximum. I just noticed I only needed to check the 3 closest solutions to the global maximum since after sorting the peppers by difference, the tastiness function is a parabola.

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

    exgcd

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

Is there anyone can hack my C problem?

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

    Can you briefly describe your approach? I'm having a hard time understanding what you're doing...

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

      Frstly,if there are some pairs of numbers which are same to each other,we could ignore them.Secondly,all the numbers'lengths are under 9,so if some numbers'lengths are beyond 9,we can only converts them into numbers beneath 9 so that they have chance to be the same to another number.

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

For C, what is the proof that if you have a match, you always want to pair them immediately?

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

    Suppose you have $$$x > 1$$$ an even number of times (and you already dealt with bigger numbers). Suppose you change one of them to $$$f(x)$$$. Now the amount of $$$x$$$ would be odd, which means one $$$x$$$ would have no pair, so you must actually change both of them to $$$f(x)$$$. But both $$$f(x)$$$ are equal, so you just did two unnecessary operations, because you could just match them when they were $$$x$$$.

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

Can anyone please help me where I am wrong? Talking about problem C.

My submission : https://codeforces.net/contest/1728/submission/171436863

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

    Can you please briefly describe your approach? It's hard for me to figure out exactly what you're doing.

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

      Yeah sure

      I made 2 vectors a and b initially. Then I made a vector a1 and map m1.

      a1 contains elements of a that are not matching with elements of vector b. similarly m1 contains element of b that are not matching with elements of vector a.

      then I iterated over a1:

      let e be element of a1

      if(e>1&&e<=9)
      e>9

      now we iterate over remaining element in m1 (lets name this element as p)
      if(p==1)continue;
      if(p<=9)ans++;
      else ans+=2

      Code link : https://codeforces.net/contest/1728/submission/171436863 Giving WA on TC2

      Revision 1 : AC now!

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

I think I have an $$$O(n)$$$ solution for Problem D. 171446061

If the string has following structure:

$$$ABC$$$

Where $$$AC$$$ is a palindrome and $$$B$$$ is made out of pairs of equal letters (e.g. aahheeiiwwmmyy), then it is a draw. Else Alice wins.

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

    Nice structure! I think I have some argument. Suppose we have a string of minimum length that Bob can win, denoted by a1 a2 X a3 a4. Bob must pick smaller letter than Alice at the first turn, since the best outcome afterwards is a draw. Hence, we have three posibilities:

    (1) a1 > a2 and a4 > a3

    i) a1 = a4

    X a3 a4 must be a draw, and a1 a2 X must be a draw, so X = a4 a3 Y a2 a1. We now have that Y a2 a1 and a4 a3 Y must be draws. This repeated chain can't end, contradiction.

    ii) wlog a1 > a4

    a1 a2 X must be a draw, so X = Y a2 a1, where Y is a draw. Hence, when Alice pick a1 in a1 a2 Y a2 a1 a3 a4, neither a2 Y a2 a1 a3 nor Y a2 a1 a3 a4 can't be a draw, contracdiction.

    (2) a1 > a4 and a4 > a3 (and thus a1 <= a2 by excluding (1)), i.e., a2 >= a1 > a4 > a3.

    If Alice pick a1, Bob should choose a4. a2 X a3 must be a draw. Since a2 != a3, X = a2 Y a3 where Y is a sequence of pairs of identical letters. Now, Alice pick a4, Bob should choose a3, and a1 a2 a2 Y a3 can't be a draw, since a1 != a3.

    (3) a4 > a1 so a1 > a2, which is symmetric to (2)

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

    Great solution! Could you share your logic on deducing ABC template for draw scenarios? It took me significant amount of time to do it, perhaps your way is faster?

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

      Bob wants to force a draw by always picking the same letter as Alice. There are only two possible answers to Alices moves. Either pick on the same side as Alice or on the other side.

      In the palindrome situation Bob needs to pick always the other side as Alice did pick. In the $$$B$$$ situation Bob always needs to pick on the same side as Alice picked.

      Transition from palindrome to $$$B$$$-situation works out for Bob. Transition from $$$B$$$ to palindrome does not work out. Alice can start picking on the palindrome before the $$$B$$$ part is finished, so one side of the palindrome won't be reachable. So the structure needs to be $$$ABC$$$.

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

I messed up this round and got a rank in the 8000s. I hope to perform well in the upcoming contests <3

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

    In my experience, messing up in a manner that is not reflective of your skill level is usually not a problem (unless it happens a lot). Even if your rating decreases by a lot, it would quickly climb back up when you do later contests at your consistent skill level. The initial drop means you'll generally gain more rating in the next contest, so you should quickly catch up.

    More importantly, I hope you actually learned more from doing the contest and improved, even if only slightly. Improving your personal skill level would eventually lead to consistently maintaining a higher rating, despite the occasional drops from randomly choking.

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

      Nice thought! One of my problems is that I get stuck in a problem, and then struggle with it for 45 mins or even an hour. Then during upsolving I realise that the problem was not that difficult and could have solved it within 15 mins. In short, I think I can solve problems, but I take so much time that my rating doesn't increase as much as it should, or even decrease. Can you advice me on this?

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

        Each person is different, so my advice may not necessarily be the best for you. However, my suggestion is that, when you find yourself struggling with a problem that you are able to easily upsolve later, try to think carefully about what was the crucial observation you missed that prevented you from solving it faster. I then recommend writing this down physically on paper. In my experience, this helps to avoid missing similar observations in the future.

        If you find that a particular issue arises frequently for you, then make a special note of this and try to make arrangements to remind you of this for future problems, e.g., adding it to your code template as a comment, placing a sticky note on the corner of your screen, etc. Eventually, you should get the hang of dealing with these issues quickly on your own.

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

in problem D. if the string is baab the answer will be Bob right?? or is it a draw??

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

    In each turn, the player add a character to the beginning of their string, not to the end. You probably miss this

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

      Ohh shit I just wasted 5hours reading the question wrong. I was adding at the end of the string. Thanks man.

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

        Happened to me during the contest.
        Luckily, not much modification was required.

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

    It's a draw, like following: 1. Alice chooses 'b' 2. Bob either chooses 'a' or 'b' 3. Alice choose 'a' 4. Bob choose the last one. So Alice has "ab" and Bob has "ab" or "ba", it's a draw.

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

It seems that Bob can't win in problem D. I got the AC during the contest but still can't come up with an elegant proof to back it up. Any suggestions?

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

    in the test case "baab" Bob will win right??

    Update : sorry i read the question wrong. Please ignore.

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

      Nope he doesn't in this case

      I had an inductive proof for that but it is too long still anyway:

      Base case: we will have a string of length 2. if the characters are different Alice wins, if the characters are same we'd have a draw.

      Recursive case: Suppose we have a string of length l where Bob wins. Since Alice can always pick the lesser of the first and last characters we'd skip the case where Alice and Bob pick characters from the opposite side. Consider the case where Bob and Alice pick the characters from the same side. For the recursive case we have made the assumption that Bob can't win for any string with length < l. Let the string be c1.c2.s(some string).cn-1.cn. If Bob wins then cn > cn-1 and c1.c2.s will result in a draw and c1 > c2 and s.cn-1.cn will result in a draw. Since the frequency of each character in a string which is a draw, is even, we get c1 = cn, c2 = cn-1.

      Now, we have c1.c2.s.c2.c1. Since, c1.c2.s is a draw string, if Alice decides to pick c1 then, s has to end with c1. In a similar way, s also has to start with c1. We keep on repeating this process, build s and we arrive at a contradiction at a position in s.

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

        Proof: As the length of the string is even.

        The deciding factor will be the last 2 remaining characters. Now the 2characters can be same or different if different then as alice gets the first pick she wins.

        If the characters are same then both of them have the same first letter in their own string. So the deciding factor will be the 2 characters picked before the last ones.

        Same logic here those 2 character can be same or different if different alice wins as she gets the first pick. If same then deciding factor will be the 2characters picked just before. And this will continue. So you can see that Bob can never win.

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

          This line of thinking is not correct. In your own testcase baab. Either way, for the first pick Alice gets to pick b and Bob gets a, though Alice wins in the end.

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

        I just got the problem accepted. I read the question wrong and spent 5hours on the wrong question.

        I was adding the characters to the end of Alice and Bobs string.

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

          I understand the pain.

          In many AC solutions I saw that people had recursions for the case where Bob wins and had print statements for Alice, Bob and Draw. But Bob doesn't win any game. So basically the cases where Bob wins are a contradiction among themselves and the code execution doesn't reach those lines.

          Yours too had provisions in case Bob wins. https://codeforces.net/contest/1728/submission/171455329

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

            Even i did the same as it is a dp solution i dont need to waste time thinking if bob can ever win. Just check all possible ways and print who ever wins. If bob can never win "Bob" will never be printed anyways.

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

              Yepp true, I mistakenly believed that Bob can't win and ended up handling only Draws and Alice wins. It worked magically. Then I first realized I had the wrong idea which was actually correct but yeah I still don't have a more elegant proof for why.

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

    I think you can look at a problem backwards. At last 2 letters Alice goes first and can choose lesser letter and win. So Bob can only hope for draw so last 2 letters should be the same.
    It means optimal strategy for Alice is choose at any step lesser letter, strategy for Bob is to choose the same letter as Alice for getting draw.
    I feel like problem can be solved in O(n) though I didn't solve it

    UPD. https://codeforces.net/blog/entry/106726?#comment-951491 found comment with O(n) solution. Looks like I missed a piece of observation with combining palindromes and pairs of same letters :(

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

      Alice is not gauranteed to have the lesser letter at each move. Consider caac

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

        I did not say about guaranteeing. Only strategy

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

In problem F, how to prove that the number of useful values is $$$O(n)$$$? I've added lots of trivial optimizations but still got TLE. Or is it maybe I need a faster max flow template?

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

Would appreciate if Educational rounds could release the editoral soon after the contests :) Most other contests have been doing so, and I think it would help for learning about unsolved problems while it is still fresh in our minds.

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

Codeforces becomes Mathforces in these days

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

    Always has been

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

      but when i solve c2j problems i see old contest qusestion that questions are some algo orieneted but now in live contest i see questions are mainly from numbertheory

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

        Well, math and algorithms are strongly interconnected, so there is nothing special about that. Some problems are from numbertheory, but in this round C and D were not

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

          actually i am beginner so i am never get a opportunity to meet c and d question can u tell what topic is neccesary to become speclist ?

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

            As I remember you can get to specialist just by solving a and b very quickly. For that just solve 800-1100 problems, they usually don't require anything hard. Might be an easy dp, but that is learnable. If you find a problem with a dp tag, just look through the code of the solution, maybe do some research on CF/Google. As for C they usually require great understanding of STL data structures and/or constructives. C is most of the time around 1500, sometimes can get up to 2000, but that's a rare thing, and usually has such high rating because of a cringy solution. That's mostly it for the specialist

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

I'm a newcomer in Codeforces.That's my 5th contest... But i have noticed it takes really long to update ratings on codeforces.. Why is it so?

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

    Because of the open-hack phase, it is for Edu and Div 3 (maybe also 4) rounds, lasts 12 or 24 hours. That's the main reason why it took so long

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

      Hey, Can you give me some guidance on how you reached expert so quickly..?

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

        I'm an 8 grader who learns AnDS in different school clubs + actively solving CF problems on different topics, also try CF EDU

        https://www.youtube.com/c/pavelmavrin this channel is cool.

        And finally I think there should be a website where there are most of the topics for CP

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

Is my Solution to A good? I feel like I wasted time to write such a solution, and could have written a much simpler solution in less time.

https://codeforces.net/contest/1728/submission/171356537

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

why are ratings still not published, is this round rated or unrated?

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

    Edu round take time to update rating

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

      How long usually ? And why? Why different times to update ratings for different types of rounds ?

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

        There is no fix timing but it take long to update rating, the reason is after hacking phase they add hack test cases to thier test case file and then multiple times system testing

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

        Because there is the 12 hour hacking phase and after that all the solutions need to be re-judged on the successful hack testcases. Oh and also Mike needs some rest too :)

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

Via debugging E, I'm surprised to find out that -54/15=-3 (in c++) and -54//15=-4 (in py)

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

When will the rating update?I cant wait to get a positive result.

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

If I solve any question even though I am div 4, will my rating go up??

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

    I think you will gain rating.It is easy to gain rating in your first six contest.

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

I completed 2 problems in yesterday's contest still i am unrated. When does it gets updated?

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

When will the ratings get updated and tutorial get released for this round?

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

Why rating hadn’t changed yet isn’t it supposed to be after 2 or 3 hours just after open hacking phase?

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

I have read the problem B. It's clean but i can't solve. Help me! p/s: i just have solve as brute force thank you

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

    ok here is the idea u will notice that you can at most get the sum of the two largest numbers in the sequence that because each two consecutive positive integers must be greater than to the following number to them this is the case for n > 3 so if i give you n = 5 then max you can get is 4 + 5 which equals nine and if n = 8 then the result will be 7 + 8 and so on the problem comes is that how i make sure that when i start to count the two largest numbers the current res is 0 so if it is even n like this case n = 6 then the sequence will be like 4 3 2 1 5 6 which if you trace will get 0 4 0 2 0 5 11 so if it is even print from n-2 to 1 then print n-1 and n if n is odd like n = 7 then just replace n-2 with n-3 so it will be like that 4 5 3 2 1 6 7 which by tracing gives 0 4 9 0 2 0 6 13 and you can generalize this on any n.

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

when will be the rating changes?

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

uhh... when will the rating update?

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

why haven't the rating changes appeared yet?

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

I guess the rating will be updated after the #820 starts to register to prevent some bugs of rating calculation.

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

Why is my code giving tle on problem C(digital algorithm) using unordered_map but getting ac using map?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Why?
»
2 years ago, # |
Rev. 3   Vote: I like it +5 Vote: I do not like it

My intuitive reasoning to D :

First, because Alice play first and the length of the string is even, Alice can force Bob to take any particular character in the string by simply never take it. After Bob take this character either the string become empty and the game end, or it become a shorter string with even length, then we use this strategy again for the shorter string. By take advantage of this, when play optimally Alice will never lose.

The only way for Bob to draw is to always take the same character as Alice. Now we reverse the game from the end to begin to see what the original string would look like :

For each double turn of Alice + Bob, we add 2 identical character to the same side or different side of our string (for example : $$$aa \rightarrow aabb, bbaa$$$ or $$$baab$$$)

The critical point is that if we add to the different side, we can't add to same side anymore. Take the example $$$baab \rightarrow baabcc$$$, here Alice can take $$$b$$$ and Bob can't take any $$$b$$$ so he will lose

So the form of our string is : half palindrome + some pairs + other half palindrome, the 1st and 3rd part form a palindrome

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

In problem D why using global recursive function link gives AC whereas converting it into a recursive lambda link is giving MLE ?

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

Hey everyone... is this round rated? I don't see my rating changes for 1 day (mostly, it takes under 1 day) so I just ask in curious.

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

    Yep, the round is rated, system testing has been done few minutes ago we may expect rating change soon!

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

Can anyone explain me non-dp (greedy) solution for D? i.e. $$$O(n)$$$ solution?

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

    You can get an inductive/recursive proof for the type of string, once you get that code is fairly simple.

    Sketch/Approach
    Answer

    Link to the code: https://codeforces.net/contest/1728/submission/171419727.

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

    What exactly is the meaningful change? It's hard to tell with how you also adjusted indentation and brackets and such

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

      Oh it's because I used .count() which can be O(n) worst case.

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

        Uhh, I think .count() on a map would have runtime logarithmic to the size of the map, in the worst-case. If that's the only change, I'd be surprised if that led to the time limit exceeding. Then again, I suppose the check happens quite a lot in here...

»
2 years ago, # |
  Vote: I like it -28 Vote: I do not like it

Why did you skip my d? Do we have to ask everyone to use different ideas to solve the same problem? I don't understand

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

https://codeforces.net/contest/1728/submission/171413965 https://codeforces.net/contest/1728/submission/171404066 can you tell me why my code skipped look at my code it OBVIOUSLY not the same plz look at the two codes MikeMirzayanov

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

    Absolutely same. Just stop cheating.

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

      True. Trickster_001 you just changed the variable names and thought that you are clever enough, but the Codeforces cheater-catching machine outsmarted you.

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

      can you tell me when will the rating be updated, please.

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

      Hello mike, sorry to bother you here, can you please take a look at this aswell link

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

Why the rating hasn't been updated yet!?(┬┬﹏┬┬) MikeMirzayanov
and where is the editorial? ◑﹏◐

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

Hey, yesterday I had 3 accepted solutions and today I have only two. I've got TLE on this submission: 171386970

Is it an error or is my solution bad?

Can I download a test to check on my own?

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

    TLE because you used unordered_map, which can be hacked using anti-hashing. Just use map instead and try again.

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

    I think you can see the test cases for every submit now. Just look for "link" in bottom left corner of you submission link

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

      I can see a "Click to see test details" but there are only like 70 of 200000 numbers followed by ellipsis in the test input. Am I missing anything?

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

        Oh no, my bad. You can't download the tests it seems. But even if you download I don't know how would you evaluate TLEs. Do you know some hacks for it?

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

          What do you mean by "evaluate TLE"? I would have executed my program and typed in the test. 2 seconds is a lot for a program that was supposed to be O(n) time complexity. Earlier, I thought I got TLE due to, for example, a lag of the CodeForces server.

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

            I mean the server running the tests might be having different configurations than your personal computer. So I was curious to know how would you identify TLEs because of this configuration changes.

            But surely O(n) solution should take less time than 2 seconds unless the built-in libraries used take O(n)

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

              As far as I know, the configuration of compiler is available here. I'm not sure if there is no newer one.

»
2 years ago, # |
  Vote: I like it -35 Vote: I do not like it

Hi, MikeMirzayanov.

The submission 171396201 and 171412747 of 1728D - Letter Picking are just coincidences

I am sure I didn't copy the code or send it to others.

Obviously, we have the same idea of this problem, and coincidentally, our code styles are similar.

My submission is at 23:33(UTC+8) and the other one's submission is at 00:09(UTC+8). And this problem is simple for me. This ruled out the possibility that I copied his code.

By the time he submitted his code, I had already came up with the solution to 1728E, so I am sure I can become yellow after this contest. I have no reason to send my code to others and cause me to be skipped.

Moreover, solutions to 1728D are all very similar, except dfs and the O(n) solution. If necessary, I can find more submissions similar to mine.

So I just have the same idea and similar code style with a stranger coincidentally.

Thanks!

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

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).

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

How to become pupil as soon as what topic really need to solve 1000 1100 and 1200 1300 rated problem ?

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

I am finally an expert. Thanks to this contest :)

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

Can someone explain digital logarithm to me? I just don't understand what "f(x) for a positive integer x as the length of the base-10 representation of x without leading zeros" means. In example 2 why does f(2) = 1? and f(100) = 3?

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

It's a great competition.I like it very much.

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

trash