By awoo, history, 3 weeks 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

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

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

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

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

  • »
    »
    3 weeks 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).

    • »
      »
      »
      3 weeks 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

»
3 weeks ago, # |
  Vote: I like it -15 Vote: I do not like it

Hoping for Creative round

»
3 weeks 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

»
3 weeks ago, # |
  Vote: I like it -20 Vote: I do not like it

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

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

+1

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

Hope that that incident will be the last, forever.

»
3 weeks 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:(

  • »
    »
    3 weeks 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.

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

      The least important thing is rating.

    • »
      »
      »
      3 weeks 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:(.

      • »
        »
        »
        »
        3 weeks 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:)

        • »
          »
          »
          »
          »
          3 weeks 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

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

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

»
3 weeks ago, # |
  Vote: I like it -25 Vote: I do not like it

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

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

    Bro no contest is a waste of time lol

    • »
      »
      »
      3 weeks 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.

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

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

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

Comments in codeforces..

2020
2022
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Good round or Bad Round? It's a problem.

»
3 weeks 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

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

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

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

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

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

Hope to perform best in this contest

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

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

    meh not so many upvotes i guess i lost my touch

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

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

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

How to solve D?

  • »
    »
    3 weeks 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 ;~;)

    • »
      »
      »
      3 weeks 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?

      • »
        »
        »
        »
        3 weeks 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).

        • »
          »
          »
          »
          »
          3 weeks 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

          • »
            »
            »
            »
            »
            »
            3 weeks 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.

            • »
              »
              »
              »
              »
              »
              »
              3 weeks 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.

              • »
                »
                »
                »
                »
                »
                »
                »
                3 weeks 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 LightBrand99'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.

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

      What is the time complexity for this solution ?

      • »
        »
        »
        »
        3 weeks 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).

        • »
          »
          »
          »
          »
          9 days 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?

          • »
            »
            »
            »
            »
            »
            8 days 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 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        marajuana

»
3 weeks 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.

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

how to solve C?

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

    Hint: use a heap.

  • »
    »
    3 weeks 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.

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

    Use a map and compare the frequency

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

How did you solve C?

  • »
    »
    3 weeks 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.

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

      Very simple approach, a multiset didnt come to my mind in the moment, I did weird stuff with a map, thanks a lot, ill give it a try

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

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

»
3 weeks 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).

  • »
    »
    3 weeks 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

»
3 weeks 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.

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

    sorry, seems like I misread the question.

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

    bacd

    • »
      »
      »
      3 weeks 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

      • »
        »
        »
        »
        3 weeks 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.

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

      Gives me Alice on running my code

    • »
      »
      »
      3 weeks 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?

      • »
        »
        »
        »
        3 weeks 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

  • »
    »
    3 weeks 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?

  • »
    »
    3 weeks 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.

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

      Why?

    • »
      »
      »
      3 weeks 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?

  • »
    »
    3 weeks 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

    • »
      »
      »
      3 weeks 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 ?

      • »
        »
        »
        »
        3 weeks 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.

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

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

  • »
    »
    3 weeks 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).

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

      Thanks; I still keep making silly mistakes, gotta be more careful.

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

The hardest Div.2 round I've seen.

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

    believe me it's not

  • »
    »
    3 weeks 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.

»
3 weeks 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

  • »
    »
    3 weeks 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.

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

    Int ma=v[0] called before input

  • »
    »
    3 weeks 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.

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

    ma = v[0] after cin >> v[i] loop;

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

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

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

    Hhhhhhh so stupid. Anyway thank you.

»
3 weeks 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

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

How to solve D ?

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

      What if the importance of DP here?

      • »
        »
        »
        »
        3 weeks 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

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

    My Submission

    • »
      »
      »
      3 weeks 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
  • »
    »
    3 weeks 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 ;~;)

»
3 weeks 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 ?

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

Any hints on E?

  • »
    »
    3 weeks 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!

    • »
      »
      »
      3 weeks 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.

      • »
        »
        »
        »
        3 weeks 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!

        • »
          »
          »
          »
          »
          3 weeks 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.

        • »
          »
          »
          »
          »
          3 weeks 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.

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

»
3 weeks 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?

  • »
    »
    3 weeks 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.

  • »
    »
    3 weeks 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

    • »
      »
      »
      3 weeks 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.

»
3 weeks 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

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

How to solve B?

  • »
    »
    3 weeks 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

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

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

      • »
        »
        »
        »
        3 weeks 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.

      • »
        »
        »
        »
        3 weeks 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.

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

      Hey thanks I got it now feelin stupid :(

»
3 weeks 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.

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

so many constructive >:(

»
3 weeks 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]$$$.

  • »
    »
    3 weeks 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.

»
3 weeks 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?

  • »
    »
    3 weeks 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

»
3 weeks 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?

»
3 weeks 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?

»
3 weeks 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.

  • »
    »
    3 weeks 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.

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

      Well i didn't use it because i am aware of it. I agree this is an important topic and everyone should be aware of this

»
3 weeks 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.cc/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

  • »
    »
    3 weeks 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

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

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

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

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

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

I could not solve Problem B in the contest But I like it because it teases my Brain to think over it ?

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

Very nice problems A B C!

  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks 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

      • »
        »
        »
        »
        3 weeks 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)

        • »
          »
          »
          »
          »
          3 weeks 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

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

            maybe tomorrow you will become specialist

            • »
              »
              »
              »
              »
              »
              »
              3 weeks 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

              • »
                »
                »
                »
                »
                »
                »
                »
                3 weeks 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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 weeks 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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 weeks 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.

        • »
          »
          »
          »
          »
          3 weeks 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.

    • »
      »
      »
      3 weeks 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.

      • »
        »
        »
        »
        3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it -24 Vote: I do not like it

Did you know that adding more samples is totally free?

»
3 weeks 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.

  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks 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.

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

    exgcd

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

Is there anyone can hack my C problem?

  • »
    »
    3 weeks 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...

    • »
      »
      »
      3 weeks 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.

»
3 weeks 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?

  • »
    »
    3 weeks 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$$$.

»
3 weeks 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.cc/contest/1728/submission/171436863

  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks 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.cc/contest/1728/submission/171436863 Giving WA on TC2

      Revision 1 : AC now!

»
3 weeks 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
  • »
    »
    3 weeks 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)

  • »
    »
    3 weeks 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?

    • »
      »
      »
      3 weeks 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$$$.

»
3 weeks 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

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

    Same, will lose green after the ranks are updated. I don't think I've gotten a positive delta in an Edu round, but generally I always learn something so it's worth the drop in points.

  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks 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?

      • »
        »
        »
        »
        3 weeks 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.

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

B is a good question

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

    yes it is. First I tried to solve it using backtracking, but that approach didnt give answers fast wnough for n more than 10.

»
3 weeks 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??

  • »
    »
    3 weeks 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

    • »
      »
      »
      3 weeks 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.

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

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

  • »
    »
    3 weeks 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.

»
3 weeks 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?

  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks 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.

      • »
        »
        »
        »
        3 weeks 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.

        • »
          »
          »
          »
          »
          3 weeks 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.

      • »
        »
        »
        »
        3 weeks 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.

        • »
          »
          »
          »
          »
          3 weeks 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.cc/contest/1728/submission/171455329

          • »
            »
            »
            »
            »
            »
            3 weeks 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.

            • »
              »
              »
              »
              »
              »
              »
              3 weeks 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.

  • »
    »
    3 weeks 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.cc/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 :(

    • »
      »
      »
      3 weeks 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

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

        I did not say about guaranteeing. Only strategy

»
3 weeks 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?

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

awoo is one of the great authors. Problems will be original and creative undoubtedly (in my experience). Already happened this!

»
3 weeks 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.

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

Codeforces becomes Mathforces in these days

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

    Always has been

    • »
      »
      »
      3 weeks 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

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

              currently i am doing 1000 rated problem from c2j but see my profile i am consistant but my growth is nothing

»
3 weeks 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 weeks 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

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

When will the editorial be done, any idea anyone? Looking forward to it

»
3 weeks 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.cc/contest/1728/submission/171356537

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

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

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

    Edu round take time to update rating

    • »
      »
      »
      3 weeks 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 ?

      • »
        »
        »
        »
        3 weeks 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

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

          That's the kind answer that one expects from a competitive programmer

      • »
        »
        »
        »
        3 weeks 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 :)

»
3 weeks 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)

»
3 weeks 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.

»
3 weeks 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??

  • »
    »
    3 weeks 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.

»
3 weeks 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?

»
3 weeks 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?

»
3 weeks 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?

»
3 weeks 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

  • »
    »
    3 weeks 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.

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

    Well,the basic idea is that the max ans in every case will be n-1 + n therefore the last two numbers will be n-1 and n, so we just have to arrange the rest numbers i.e from 1 to n-2 in an order such that it'll give zero after applying the given operation for those n-2 numbers. So there will be 2 trends one when n is even and other when n is odd.Just observe carefully you'll figure it out on how to arrange in both cases.

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

when will be the rating changes?

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

uhh... when will the rating update?

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

I started giving contest from the previous round. Its ratings were removed :( And now this round is not publishing ratings What's the problem with me universe???

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

why haven't the rating changes appeared yet?

»
3 weeks 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.

»
3 weeks 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?

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

    In worst case, unordered_map can be O(n), but ordered map remains O(logn). Also memory usage is more as compared to ordered map.

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

sorry if this sounds non-sense question but i am really suck at solving div2c problems in generl can someone share his thinking process during this contest in order to get c? i knew the answer from the comments but i really can't imagine how could i get it in the contest

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

Why does the rating appear so late in Educational Rounds?

»
3 weeks 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

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

guys , When will each competitor points be determined?

»
3 weeks 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 ?

»
3 weeks 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.

  • »
    »
    3 weeks 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!

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

Problem C was like a brainstorm for me but, I find it iconic OwO.

Cant anyone provide me with problems with nearly same idea?

»
3 weeks 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?

  • »
    »
    3 weeks 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.cc/contest/1728/submission/171419727.

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

    • »
      »
      »
      3 weeks 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.

      • »
        »
        »
        »
        3 weeks 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...

»
3 weeks 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

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

https://codeforces.cc/contest/1728/submission/171413965 https://codeforces.cc/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

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

    Absolutely same. Just stop cheating.

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

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

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

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

    • »
      »
      »
      3 weeks 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

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

      it's natural there's a lot of people solve it with the same idea but the two codes are obviously different but if you open the two codes and still see it cheating Nevermind:)

»
3 weeks 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? ◑﹏◐

»
3 weeks 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?

  • »
    »
    3 weeks 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.

  • »
    »
    3 weeks 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

    • »
      »
      »
      3 weeks 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?

      • »
        »
        »
        »
        3 weeks 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?

        • »
          »
          »
          »
          »
          3 weeks 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.

          • »
            »
            »
            »
            »
            »
            3 weeks 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 weeks 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.

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

Problems were amazing. hatsoff

»
3 weeks 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!

»
3 weeks 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).

»
3 weeks 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 ?

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

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

»